Detail publikace

Forbidding E0L Systems

MEDUNA, A.; ŠVEC, M. Forbidding E0L Systems. Theoretical Computer Science, 2003, vol. 2003, no. 306, p. 449-469. ISSN: 0304-3975.
Název česky
Zakazující EOL systémy
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Švec Martin, Ing., Ph.D.
Klíčová slova

Zakazující EOL systémy

Abstrakt

Zakazující EOL systémy jsou zkoumány.

Anotace

The present paper introduces and discusses forbidding ET0L grammars whose productions have some attached strings, called forbidding conditions. These grammars can make a derivation step only by using productions whose forbidding conditions do not appear in the rewritten sentential form. The paper demonstrates that some well-known relationships concerning the language families resulting from ordinary ET0L grammars do not hold in terms of the forbidding ET0L grammars. Most interestingly, while E0L grammars are less powerful than ET0L grammars, their forbidding versions with conditions of length one are equally powerful. On the other hand, while EP0L grammars are as powerful as E0L grammars, FEP0L grammars are less powerful than FE0L grammars.

Rok
2003
Strany
449–469
Časopis
Theoretical Computer Science, roč. 2003, č. 306, ISSN 0304-3975
Kniha
Theoretical Computer Science
Vydavatel
Elsevier Science
Místo
Paris
BibTeX 
@article{BUT41997,
  author="Alexandr {Meduna} and Martin {Švec}",
  title="Forbidding E0L Systems",
  journal="Theoretical Computer Science",
  year="2003",
  volume="2003",
  number="306",
  pages="449--469",
  issn="0304-3975"
}
Nahoru