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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.3233/FI-2011-584 | Fundam. Inform. |
Keywords | Field | DocType |
language family,blackhole pushdown automaton,pushdown automaton,distinguished states check,present characterization,regulated pushdown automaton,control language,pushdown content,blackhole pushdown automata,blackhole variant,regulation | Deterministic context-free grammar,Embedded pushdown automaton,Discrete mathematics,Two-way deterministic finite automaton,Context-free language,Nested word,Deterministic pushdown automaton,Deterministic context-free language,Theoretical computer science,Pushdown automaton,Mathematics | Journal |
Volume | Issue | ISSN |
112 | 2-3 | 0169-2968 |
Citations | PageRank | References |
2 | 0.43 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Erzsébet Csuhaj-Varjú | 1 | 593 | 87.27 |
Tomáš Masopust | 2 | 81 | 9.64 |
György Vaszil | 3 | 277 | 40.65 |