Detail publikace
Left-Forbidding Cooperating Distributed Grammar Systems
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Levě zakazující gramatika je bezkontextová gramatika, kde každé pravidlo má asociovánu množinu neterminálních symbolů (tzv. zakazující množinu). Takové pravidlo je pak aplikovatelné pokud se žádný symbol z jeho zakazující množiny nevyskytuje ve větné formě nalevo od symbolu, který má být přepsán. Článek diskutuje kooperující distribuované gramatické systémy s levě zakazujícími komponentami a prezentuje několik nových charakterizací jazyků Chomského hierarchie. Navíc ukazuje, že dvanáct neterminálů je postačujících k charakterizaci celé třídy rekurzívně spočetných jazyků.
Levě zakazující gramatika je bezkontextová gramatika, kde každé pravidlo má asociovánu množinu neterminálních symbolů (tzv. zakazující množinu). Takové pravidlo je pak aplikovatelné pokud se žádný symbol z jeho zakazující množiny nevyskytuje ve větné formě nalevo od symbolu, který má být přepsán. Článek diskutuje kooperující distribuované gramatické systémy s levě zakazujícími komponentami a prezentuje několik nových charakterizací jazyků Chomského hierarchie. Navíc ukazuje, že dvanáct neterminálů je postačujících k charakterizaci celé třídy rekurzívně spočetných jazyků.
@ARTICLE{FITPUB9215,
author = "Filip Goldefus and Tom\'{a}\v{s} Masopust and Alexander Meduna",
title = "Left-Forbidding Cooperating Distributed Grammar Systems",
pages = "3661--3667",
booktitle = "Theoretical Computer Science",
journal = "Theoretical Computer Science",
volume = 411,
number = 40,
year = 2010,
location = "Paris, FR",
publisher = "Elsevier Science",
ISSN = "0304-3975",
doi = "10.1016/j.tcs.2010.06.010",
language = "english",
url = "https://www.fit.vut.cz/research/publication/9215"
}