Detail publikace

Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets

BIDLO Radek, BLATNÝ Petr a MEDUNA Alexander. Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets. Kybernetika, roč. 2007, č. 1, s. 21-35. ISSN 0023-5954.
Název česky
Automaty s oboustrannými zásobníky definovanými nad volnými grupami generovanými redukovanými abecedami
Typ
článek v časopise
Jazyk
angličtina
Autoři
Bidlo Radek, Ing. (UIFS FIT VUT)
Blatný Petr, Ing. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Klíčová slova

zásobníkové automaty, modifikace, rekurzívně vyčíslitelné jazyky

Abstrakt

Článek představuje a diskutuje modifikaci zásobníkových automatů. Tato modifikace je založena na oboustranných zásobnících, do kterých jsou symboly vkládány z obou stran. Tyto zásobníky nejsou definovány nad volnými monoidy, ale nad volnými grupami a mohou být zkráceny pouze standardní grupovou redukcí. Je demonstrováno, že tyto automaty charakterizují třídu rekurzívně vyčíslitelných jazyků i když jsou volné grupy generovány ne více než čtyřmi symboly.

Rok
2007
Strany
21-35
Časopis
Kybernetika, roč. 2007, č. 1, ISSN 0023-5954
Kniha
Kybernetika
Místo
Praha, CZ
BibTeX
@ARTICLE{FITPUB8289,
   author = "Radek Bidlo and Petr Blatn\'{y} and Alexander Meduna",
   title = "Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets",
   pages = "21--35",
   booktitle = "Kybernetika",
   journal = "Kybernetika",
   volume = 2007,
   number = 1,
   year = 2007,
   location = "Praha, CZ",
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8289"
}
Nahoru