Blackhole Pushdown Automata

• Autorzy: Csuhaj-Varjú, E. , Masopust, T. , Vaszil, G.
• Języki publikacji: EN

Abstrakty

EN

We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs.

Słowa kluczowe

EN

pushdown automaton; regulation; computational power

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 137-156
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Csuhaj-Varjú, E.

autor

Masopust, T.

autor

Vaszil, G.

• Computer and Automation Research Institute, Hungarian Academy of Sciences H-1111 Budapest, Kende u. 13-17, Hungary P.O. Box 63, 1518 Budapest, Hungary,

Bibliografia

• [1] Csuhaj-Varju, E., Masopust, T., Vaszil, G.: Blackhole state controlled regulated pushdown automata, Proceedings of the Second Workshop on Non-Classical Models of Automata and Applications (NCMA 2010) (H. Bordihn, R. Freund, T. Hinze,M. Holzer,M. Kutrib, F. Otto, Eds.), band 263 of [e-mail], Austrian Computer Society, 2010, 45-56.
• [2] Hopcroft, J., Ullman, J.: Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Massachusetts, 1969.
• [3] Křivka, Z.: Rewriting Systems with Restricted Configurations, Ph.D. Thesis, Faculty of Information Technology, Brno University of Technology, Brno, 2008.
• [4] Kutrib, M., Malcher, A., Werlein, L.: Regulated nondeterminism in pushdown automata, Theoretical Computer Science, 410(37), 2009, 3447-3460.
• [5] Masopust, T.: Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case, Fundamenta Informaticae, 104(1-2), 2010, 111-124.
• [6] Salomaa, A.: Formal Languages, Academic Press, New York, 1973.
• [7] Salomaa, A.: Computation and Automata, Cambridge University Press, Cambridge, 1985.
• [8] Szepietowski, A.: Turing Machines with Sublogarithmic Space, vol. 843 of Lecture Notes in Computer Science, Springer, Berlin, 1994.