Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
BIDLO, R. BLATNÝ, P. MEDUNA, A.
Originální název
Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets
Typ
článek v časopise - ostatní, Jost
Jazyk
angličtina
Originální abstrakt
This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by nomore than four symbols.
Klíčová slova
pushdown automata, modifications, recursively enumerable languages
Autoři
BIDLO, R.; BLATNÝ, P.; MEDUNA, A.
Rok RIV
2007
Vydáno
21. 3. 2007
Místo
Praha
ISSN
0023-5954
Periodikum
Kybernetika
Ročník
Číslo
1
Stát
Česká republika
Strany od
21
Strany do
35
Strany počet
14
BibTex
@article{BUT45154, author="Radek {Bidlo} and Petr {Blatný} and Alexandr {Meduna}", title="Automata with Two-Sided Pushdowns Defined over Free Groups Generated by Reduced Alphabets", journal="Kybernetika", year="2007", volume="2007", number="1", pages="21--35", issn="0023-5954" }