| Title:
|
Automata with two-sided pushdowns defined over free groups generated by reduced alphabets (English) |
| Author:
|
Blatný, Petr |
| Author:
|
Bidlo, Radek |
| Author:
|
Meduna, Alexander |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
43 |
| Issue:
|
3 |
| Year:
|
2007 |
| Pages:
|
265-278 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
pushdown automata |
| Keyword:
|
modifications |
| Keyword:
|
recursively enumerable languages |
| MSC:
|
68Q05 |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 1135.68027 |
| idMR:
|
MR2362718 |
| . |
| Date available:
|
2009-09-24T20:23:41Z |
| Last updated:
|
2012-06-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135773 |
| . |
| Reference:
|
[1] Jacobson N.: Basic Algebra.Second edition. W. H. Freeman, New York 1989 Zbl 0694.16001, MR 1009787 |
| Reference:
|
[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars.Acta Informatica 20 (1983), 391–411 Zbl 0541.68048, MR 0732313 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[5] Courcelle B.: On jump deterministic pushdown automata.Math. Systems Theory 11 (1977), 87–109 Zbl 0365.02021, MR 0464717 |
| Reference:
|
[6] Greibach S. A.: Checking automata and one-way stack languages.J. Comput. Systems Sci. 3 (1969), 196–217 Zbl 0174.02702, MR 0243953 |
| Reference:
|
[7] Ginsburg S., Greibach S. A., Harrison M. A.: One-way stack automata.J. Assoc. Comput. Mach. 14 (1967), 389–418 Zbl 0171.14803, MR 0243944 |
| Reference:
|
[8] Ginsburg S., Spanier E.: Finite-turn pushdown automata.SIAM J. Control 4 (1968), 429–453 MR 0204294 |
| Reference:
|
[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 Zbl 1039.68066, MR 2080723 |
| Reference:
|
[11] Lewis H. R., Papadimitriou C. H.: Elements of the Theory of Computation.Prentice-Hall, Englewood Cliffs, NJ 1981 Zbl 0464.68001 |
| Reference:
|
[12] Martin J. C.: Introduction to Languages and the Theory of Computation.McGraw-Hill, New York 1991 Zbl 0905.68085 |
| Reference:
|
[13] Meduna A.: Automata and Languages: Theory and Applications.Springer, London 2000 Zbl 0951.68056, MR 1778364 |
| Reference:
|
[14] Meduna A.: Simultaneously one-turn two-pushdown automata.Internat. Computer Math. 82 (2003), 679–687 Zbl 1103.68587, MR 1984796 |
| Reference:
|
[15] Meduna A., Kolář D.: Regulated pushdown automata.Acta Cybernet. 14 (2000), 653–664 Zbl 1011.68049, MR 1790232 |
| Reference:
|
[16] Sakarovitch J.: Pushdown automata with terminating languages.In: Languages and Automata Symposium, RIMS 421 (1981), 15–29 |
| Reference:
|
[17] Sarkar P.: Pushdown automaton with the ability to flip its stack.TR01-081, Electronic Colloquium on Computational Complexity (ECCC), November 2001 |
| Reference:
|
[18] Sudkamp T. A.: Languages and Machines.Addison Wesley, Reading, Mass. 1988 |
| Reference:
|
[19] Valiant L.: The equivalence problem for ceterministic finite turn pushdown automata.Inform. and Control 81 (1989), 265–279 |
| . |
