Faculty of Information Technology, BUT

Publication Details

Some Power-Decreasing Derivation Restrictions in Grammar Systems

MEDUNA Alexander, ČERMÁK Martin and MASOPUST Tomáš. Some Power-Decreasing Derivation Restrictions in Grammar Systems. Schedae Informaticae, vol. 2010, no. 19, pp. 23-34. ISSN 0860-0295.
Czech title
Oslabující omezení na derivacích v gramatických systémech
Type
journal article
Language
english
Authors
Keywords
Grammar systems, derivation restriction, generative power.
Abstract
The paper, places some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by regular languages.
The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for
some k=1,...,n. The second restriction says how many blocks of non-terminals can be in every sentential form.
The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in every sentential form.
We demonstrate that under these restrictions, the grammar systems generate different families of languages.
Published
2011
Pages
23-34
Journal
Schedae Informaticae, vol. 2010, no. 19, ISSN 0860-0295
Book
Schedae Informaticae
BibTeX
@ARTICLE{FITPUB9509,
   author = "Alexander Meduna and Martin \v{C}erm\'{a}k and Tom\'{a}\v{s} Masopust",
   title = "Some Power-Decreasing Derivation Restrictions in Grammar Systems",
   pages = "23--34",
   booktitle = "Schedae Informaticae",
   journal = "Schedae Informaticae",
   volume = 2010,
   number = 19,
   year = 2011,
   ISSN = "0860-0295",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9509"
}
Back to top