Affiliations: Computer and Automation Research Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary. csuhaj@sztaki.hu | Institute of Mathematics, Czech Academy of Sciences, Žižkova 22, 61662 Brno, Czech Republic. masopust@ipm.cz | Computer and Automation Research Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary. vaszil@sztaki.hu
Note: [] Address for correspondence: P.O. Box 63, 1518 Budapest, Hungary Also affiliated with the Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary
Note: [] Research supported by the GAČR grant no. P202/11/P028, and by the CAS, Inst. Research Plan no. AV0Z10190503.
Abstract: 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.
Keywords: Pushdown automaton, regulation, computational power
