Geodesic
Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
Kybernetika, Tome 43 (2007) no. 3, pp. 265-278 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {2007},
     volume = {43},
     number = {3},
     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
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
%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/

[1] Jacobson N.: Basic Algebra. Second edition. W. H. Freeman, New York 1989 | MR | Zbl

[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars. Acta Informatica 20 (1983), 391–411 | MR | Zbl

[3] Aho A. V., Ullman J. D.: The Theory of Parsing, Translation and Compiling. Volume I: Parsing. Prentice Hall, Englewood Cliffs, NJ 1972 | MR

[4] Autebert J., Berstel, J., Boasson L.: Context-Free Languages and Pushdown Automata. In: Handbook of Formal Languages (G. Rozenberg, and A. Salomaa, eds.), Springer, Berlin 1997 | MR

[5] Courcelle B.: On jump deterministic pushdown automata. Math. Systems Theory 11 (1977), 87–109 | MR | Zbl

[6] Greibach S. A.: Checking automata and one-way stack languages. J. Comput. Systems Sci. 3 (1969), 196–217 | MR | Zbl

[7] Ginsburg S., Greibach S. A., Harrison M. A.: One-way stack automata. J. Assoc. Comput. Mach. 14 (1967), 389–418 | MR | Zbl

[8] Ginsburg S., Spanier E.: Finite-turn pushdown automata. SIAM J. Control 4 (1968), 429–453 | MR

[10] Holzer M., Kutrib M.: Flip-pushdown automata: $k+1$ pushdown reversals are better than $k$. In: Languages and Programming – ICALP 2003 (Lecture Notes in Computer Science 2719), Springer, Berlin 2003, pp. 490–501 | MR | Zbl

[11] Lewis H. R., Papadimitriou C. H.: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, NJ 1981 | Zbl

[12] Martin J. C.: Introduction to Languages and the Theory of Computation. McGraw-Hill, New York 1991 | Zbl

[13] Meduna A.: Automata and Languages: Theory and Applications. Springer, London 2000 | MR | Zbl

[14] Meduna A.: Simultaneously one-turn two-pushdown automata. Internat. Computer Math. 82 (2003), 679–687 | MR | Zbl

[15] Meduna A., Kolář D.: Regulated pushdown automata. Acta Cybernet. 14 (2000), 653–664 | MR | Zbl

[16] Sakarovitch J.: Pushdown automata with terminating languages. In: Languages and Automata Symposium, RIMS 421 (1981), 15–29

[17] Sarkar P.: Pushdown automaton with the ability to flip its stack. TR01-081, Electronic Colloquium on Computational Complexity (ECCC), November 2001

[18] Sudkamp T. A.: Languages and Machines. Addison Wesley, Reading, Mass. 1988

[19] Valiant L.: The equivalence problem for ceterministic finite turn pushdown automata. Inform. and Control 81 (1989), 265–279