Geodesic
Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
Kybernetika, Tome 43 (2007) no. 3, pp. 265-278

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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 no more than four symbols.
Classification : 68Q05, 68Q45
Keywords: pushdown automata; modifications; recursively enumerable languages 
@article{KYB_2007__43_3_a0,
     author = {Blatn\'y, Petr and Bidlo, Radek and Meduna, Alexander},
     title = {Automata with two-sided pushdowns defined over free groups generated by reduced alphabets},
     journal = {Kybernetika},
     pages = {265--278},
     publisher = {mathdoc},
     volume = {43},
     number = {3},
     year = {2007},
     mrnumber = {2362718},
     zbl = {1135.68027},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2007__43_3_a0/}
}
TY  - JOUR
AU  - Blatný, Petr
AU  - Bidlo, Radek
AU  - Meduna, Alexander
TI  - Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
JO  - Kybernetika
PY  - 2007
SP  - 265
EP  - 278
VL  - 43
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2007__43_3_a0/
LA  - en
ID  - KYB_2007__43_3_a0
ER  - 
%0 Journal Article
%A Blatný, Petr
%A Bidlo, Radek
%A Meduna, Alexander
%T Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
%J Kybernetika
%D 2007
%P 265-278
%V 43
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2007__43_3_a0/
%G en
%F KYB_2007__43_3_a0
Blatný, Petr; Bidlo, Radek; Meduna, Alexander. Automata with two-sided pushdowns defined over free groups generated by reduced alphabets. Kybernetika, Tome 43 (2007) no. 3, pp. 265-278. http://geodesic.mathdoc.fr/item/KYB_2007__43_3_a0/