Detail publikace

Left-Forbidding Cooperating Distributed Grammar Systems

GOLDEFUS Filip, MASOPUST Tomáš a MEDUNA Alexander. Left-Forbidding Cooperating Distributed Grammar Systems. Theoretical Computer Science, roč. 411, č. 40, 2010, s. 3661-3667. ISSN 0304-3975.
Název česky
Levě zakazující kooperující distribuované gramatické systémy
Typ
článek v časopise
Jazyk
angličtina
Autoři
Abstrakt

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ů.

Anotace

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ů.

Rok
2010
Strany
3661-3667
Časopis
Theoretical Computer Science, roč. 411, č. 40, ISSN 0304-3975
Kniha
Theoretical Computer Science
Vydavatel
Elsevier Science
Místo
Paris, FR
DOI
EID Scopus
BibTeX
@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"
}
Nahoru