Publication:3890112
From MaRDI portal
zbMath0445.68033MaRDI QIDQ3890112
Publication date: 1980
Turing machines; recognition algorithms; random access machines; optimal time space product; pebbling mountain ranges; recognition of deterministic context-free languages
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Queue Automata: Foundations and Developments, State Complexity of the Quotient Operation on Input-Driven Pushdown Automata, Ramsey-Based Inclusion Checking for Visibly Pushdown Automata, Further closure properties of input-driven pushdown automata, Input-driven multi-counter automata, Edit distance neighbourhoods of input-driven pushdown automata, Edit distance neighbourhoods of input-driven pushdown automata, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Descriptional complexity of unambiguous input-driven pushdown automata, Toward a theory of input-driven locally parsable languages, Sofic-Dyck shifts, Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Generalizing input-driven languages: theoretical and practical benefits, Hardest languages for conjunctive and Boolean grammars, Operator precedence and the visibly pushdown property, Counting paths in VPA is complete for \(\#\mathrm{NC}^1\), Grammatical characterizations of NPDAs and VPDAs with counters, P-hardness of the emptiness problem for visibly pushdown languages, Additive number theory via automata theory, Consensus string problem for multiple regular languages, Beyond operator-precedence grammars and languages, On the overlap assembly of strings and languages, Deterministic input-driven queue automata: finite turns, decidability, and closure properties, State complexity of operations on input-driven pushdown automata, Input-driven languages are linear conjunctive, Tinput-Driven Pushdown Automata, Locally Chain-Parsable Languages, Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$, Conjunctive Visibly-Pushdown Path Queries, Edit-Distance Between Visibly Pushdown Languages, Descriptional Complexity of Input-Driven Pushdown Automata, Synchronization of Regular Automata, On Distinguishing NC $$^1$$ and NL, On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata, Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?
