Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case

• Autorzy: Masopust T.
• Języki publikacji: EN

Abstrakty

EN

We continue the investigation of pushdown automata which are allowed to make a nondeterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata.

Słowa kluczowe

EN

pushdown automata; computational power

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 111--124
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Masopust T.

• Mathematical Institute, Czech Academy of Sciences, Żiżkova 22, 616 62 Brno, Czech Republic,

Bibliografia

• [1] Alur, R., Madhusudan, P.: Visibly pushdown languages, Proceedings of the 36th Annual ACM Symposium on Theory of Computing (L. Babai, Ed.), ACM, 2004.
• [2] Bollig, B.: On the expressive power of 2-stack visibly pushdown automata, Logical Methods in Computer Science, 4(4), 2008, 1-35.
• [3] Dassow, J., Pǎun, G.: Regulated Rewriting in Formal Language Theory, Springer, Berlin, 1989.
• [4] Dassow, J., Pǎun, G., Salomaa, A.: Grammars with controlled derivations, Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), 2, Springer, Berlin, 1997.
• [5] Geffert, V.: Normal Forms for Phrase-Structure Grammars, RAIRO - Theoretical Informatics and Applications, 25(5), 1991, 473-496.
• [6] Hopcroft, J. E., Ullman, J. D.: Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Massachusetts, 1969.
• [7] Kolář, D., Meduna, A.: Regulated Pushdown Automata, Acta Cybernetica, 4, 2000, 653-664.
• [8] Křivka, Z.: Rewriting Systems with Restricted Configurations, Ph.D. Thesis, Faculty of Information Technology, Brno University of Technology, Brno, 2008.
• [9] Kutrib, M., Malcher, A., Werlein, L.: Regulated Nondeterminism in Pushdown Automata, Theoretical Computer Science, 410(37), 2009, 3447-3460.
• [10] Meduna, A., Kolář, D.: One-Turn Regulated Pushdown Automata and Their Reduction, Fundamenta Informaticae, 51(4), 2002, 399-405.
• [11] Okawa, S., Hirose, S.: Homomorphic characterizations of recursively enumerable languages with very small language classes, Theoretical Computer Science, 250(1-2), 2001, 55-69.
• [12] Salomaa, A.: Formal Languages, Academic Press, New York, 1973.
• [13] Salomaa, A.: Computation and Automata, Cambridge University Press, Cambridge, 1985.