Prof. RNDr. Alexander Meduna, CSc.

GOLDEFUS Filip, MASOPUST Tomáš a MEDUNA Alexander. Left-Forbidding Cooperating Distributed Grammar Systems. Theoretical Computer Science. Paris: Elsevier Science, 2010, roč. 40, č. 411, s. 3661-3667. ISSN 0304-3975.
Jazyk publikace:angličtina
Název publikace:Left-Forbidding Cooperating Distributed Grammar Systems
Název (cs):Levě zakazující kooperující distribuované gramatické systémy
Strany:3661-3667
Kniha:Theoretical Computer Science
Místo vydání:Paris, FR
Rok:2010
Časopis:Theoretical Computer Science, roč. 40, č. 411, Paris, FR
ISSN:0304-3975
Vydavatel:Elsevier Science
Klíčová slova
Cooperating distributed grammar system, cooperating derivation
mode, left-forbidding grammar, generative power, descriptional complexity.
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ů.
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ů.
BibTeX:
@ARTICLE{
   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 = 40,
 number = 411,
   year = 2010,
   location = {Paris, FR},
   publisher = {Elsevier Science},
   ISSN = {0304-3975},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9215}
}

Vaše IPv4 adresa: 18.232.53.231
Přepnout na https