Result Details

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.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Čermák Martin, Ing., Ph.D., DIFS (FIT)
Masopust Tomáš, doc. RNDr., Ph.D.
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.
Keywords

Grammar systems, derivation restriction, generative power.

Published
2011
Pages
23–34
Journal
Schedae Informaticae, vol. 2010, no. 19, ISSN 0860-0295
Book
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"
}
Projects
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top