Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Petr Blatný; Radek Bidlo; Alexander Meduna

Kybernetika (2007)

  • Volume: 43, Issue: 3, page 265-278
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Blatný, Petr, Bidlo, Radek, and Meduna, Alexander. "Automata with two-sided pushdowns defined over free groups generated by reduced alphabets." Kybernetika 43.3 (2007): 265-278. <http://eudml.org/doc/33857>.

@article{Blatný2007,
abstract = {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.},
author = {Blatný, Petr, Bidlo, Radek, Meduna, Alexander},
journal = {Kybernetika},
keywords = {pushdown automata; modifications; recursively enumerable languages; recursively enumerable languages},
language = {eng},
number = {3},
pages = {265-278},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Automata with two-sided pushdowns defined over free groups generated by reduced alphabets},
url = {http://eudml.org/doc/33857},
volume = {43},
year = {2007},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 43
IS - 3
SP - 265
EP - 278
AB - 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.
LA - eng
KW - pushdown automata; modifications; recursively enumerable languages; recursively enumerable languages
UR - http://eudml.org/doc/33857
ER -

References

top
  1. Jacobson N., Basic Algebra, Second edition. W. H. Freeman, New York 1989 Zbl0694.16001MR1009787
  2. Kleijn H. C. M., Rozenberg G., On the generative power of regular pattern grammars, Acta Informatica 20 (1983), 391–411 (1983) Zbl0541.68048MR0732313
  3. Aho A. V., Ullman J. D., The Theory of Parsing, Translation and Compiling, Volume I: Parsing. Prentice Hall, Englewood Cliffs, NJ 1972 MR0408321
  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 MR1469995
  5. Courcelle B., On jump deterministic pushdown automata, Math. Systems Theory 11 (1977), 87–109 (1977) Zbl0365.02021MR0464717
  6. Greibach S. A., Checking automata and one-way stack languages, J. Comput. Systems Sci. 3 (1969), 196–217 (1969) Zbl0174.02702MR0243953
  7. Ginsburg S., Greibach S. A., Harrison M. A., One-way stack automata, J. Assoc. Comput. Mach. 14 (1967), 389–418 (1967) Zbl0171.14803MR0243944
  8. Ginsburg S., Spanier E., Finite-turn pushdown automata, SIAM J. Control 4 (1968), 429–453 (1968) MR0204294
  9. 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 Zbl1039.68066MR2080723
  10. Lewis H. R., Papadimitriou C. H., Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, NJ 1981 Zbl0464.68001
  11. Martin J. C., Introduction to Languages and the Theory of Computation, McGraw-Hill, New York 1991 Zbl0905.68085
  12. Meduna A., Automata and Languages: Theory and Applications, Springer, London 2000 Zbl0951.68056MR1778364
  13. Meduna A., Simultaneously one-turn two-pushdown automata, Internat. Computer Math. 82 (2003), 679–687 Zbl1103.68587MR1984796
  14. Meduna A., Kolář D., Regulated pushdown automata, Acta Cybernet. 14 (2000), 653–664 Zbl1011.68049MR1790232
  15. Sakarovitch J., Pushdown automata with terminating languages, In: Languages and Automata Symposium, RIMS 421 (1981), 15–29 (1981) 
  16. Sarkar P., Pushdown automaton with the ability to flip its stack, TR01-081, Electronic Colloquium on Computational Complexity (ECCC), November 2001 
  17. Sudkamp T. A., Languages and Machines, Addison Wesley, Reading, Mass. 1988 
  18. Valiant L., The equivalence problem for ceterministic finite turn pushdown automata, Inform. and Control 81 (1989), 265–279 (1989) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.