Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
pushdown automata; modifications; recursively enumerable languages
pushdown automata; modifications; recursively enumerable languages
Summary:
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.
References:
[1] Jacobson N.: Basic Algebra. Second edition. W. H. Freeman, New York 1989 MR 1009787 | Zbl 0694.16001
[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars. Acta Informatica 20 (1983), 391–411 MR 0732313 | Zbl 0541.68048
[3] Aho A. V., Ullman J. D.: The Theory of Parsing, Translation and Compiling. Volume I: Parsing. Prentice Hall, Englewood Cliffs, NJ 1972 MR 0408321
[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 1469995
[5] Courcelle B.: On jump deterministic pushdown automata. Math. Systems Theory 11 (1977), 87–109 MR 0464717 | Zbl 0365.02021
[6] Greibach S. A.: Checking automata and one-way stack languages. J. Comput. Systems Sci. 3 (1969), 196–217 MR 0243953 | Zbl 0174.02702
[7] Ginsburg S., Greibach S. A., Harrison M. A.: One-way stack automata. J. Assoc. Comput. Mach. 14 (1967), 389–418 MR 0243944 | Zbl 0171.14803
[8] Ginsburg S., Spanier E.: Finite-turn pushdown automata. SIAM J. Control 4 (1968), 429–453 MR 0204294
[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 2080723 | Zbl 1039.68066
[11] Lewis H. R., Papadimitriou C. H.: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, NJ 1981 Zbl 0464.68001
[12] Martin J. C.: Introduction to Languages and the Theory of Computation. McGraw-Hill, New York 1991 Zbl 0905.68085
[13] Meduna A.: Automata and Languages: Theory and Applications. Springer, London 2000 MR 1778364 | Zbl 0951.68056
[14] Meduna A.: Simultaneously one-turn two-pushdown automata. Internat. Computer Math. 82 (2003), 679–687 MR 1984796 | Zbl 1103.68587
[15] Meduna A., Kolář D.: Regulated pushdown automata. Acta Cybernet. 14 (2000), 653–664 MR 1790232 | Zbl 1011.68049
[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
Search
Partner of
