Detail výsledku

Some Power-Decreasing Derivation Restrictions in Grammar Systems

MEDUNA, A.; ČERMÁK, M.; MASOPUST, T. Some Power-Decreasing Derivation Restrictions in Grammar Systems. Schedae Informaticae, 2011, vol. 2010, no. 19, p. 23-34. ISSN: 0860-0295.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Čermák Martin, Ing., Ph.D., UIFS (FIT)
Masopust Tomáš, doc. RNDr., Ph.D.
Abstrakt
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.
Klíčová slova

Grammar systems, derivation restriction, generative power.

Rok
2011
Strany
23–34
Časopis
Schedae Informaticae, roč. 2010, č. 19, ISSN 0860-0295
Kniha
Schedae Informaticae
BibTeX 
@article{BUT76285,
  author="Alexandr {Meduna} and Martin {Čermák} and Tomáš {Masopust}",
  title="Some Power-Decreasing Derivation Restrictions in Grammar Systems",
  journal="Schedae Informaticae",
  year="2011",
  volume="2010",
  number="19",
  pages="23--34",
  issn="0860-0295"
}
Projekty
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru