Detail publikace

Forbidding ET0L Systems

MEDUNA Alexander a ŠVEC Martin. Forbidding ET0L Systems. Theoretical Computer Science, roč. 2003, č. 306, s. 449-469. ISSN 0304-3975.
Název česky
Zakazující EOL systémy
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Švec Martin, Ing. (UIFS FIT VUT)
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, FR
BibTeX 
@ARTICLE{FITPUB7141,
   author = "Alexander Meduna and Martin \v{S}vec",
   title = "Forbidding ET0L Systems",
   pages = "449--469",
   booktitle = "Theoretical Computer Science",
   journal = "Theoretical Computer Science",
   volume = 2003,
   number = 306,
   year = 2003,
   location = "Paris, FR",
   publisher = "Elsevier Science",
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7141"
}
Nahoru