scientific article

zbMath0445.68033MaRDI QIDQ3890112

Kurt Mehlhorn

Publication date: 1980

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Turing machinesrecognition algorithmsrandom access machinesoptimal time space productpebbling mountain rangesrecognition of deterministic context-free languages

Mathematics Subject Classification ID

Related Items (55)

Ramsey-Based Inclusion Checking for Visibly Pushdown Automata ⋮ Model-checking structured context-free languages ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ On Distinguishing NC $$^1$$ and NL ⋮ Input-driven languages are linear conjunctive ⋮ Synchronization of Regular Automata ⋮ Unnamed Item ⋮ On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? ⋮ State complexity of operations on input-driven pushdown automata ⋮ On the power of pushing or stationary moves for input-driven pushdown automata ⋮ Tinput-Driven Pushdown Automata ⋮ Locally Chain-Parsable Languages ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$ ⋮ Conjunctive Visibly-Pushdown Path Queries ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Beyond operator-precedence grammars and languages ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ Input-Driven Double-Head Pushdown Automata ⋮ Sofic-Dyck shifts ⋮ Extending Wagner's hierarchy to deterministic visibly pushdown automata ⋮ Queue Automata: Foundations and Developments ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ P-hardness of the emptiness problem for visibly pushdown languages ⋮ Sweeping input-driven pushdown automata ⋮ Edit-Distance Between Visibly Pushdown Languages ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Additive number theory via automata theory ⋮ Operator precedence and the visibly pushdown property ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ Further closure properties of input-driven pushdown automata ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ On the power of pushing or stationary moves for input-driven pushdown automata ⋮ Unnamed Item ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Toward a theory of input-driven locally parsable languages ⋮ Unnamed Item ⋮ State Complexity of the Quotient Operation on Input-Driven Pushdown Automata ⋮ Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata ⋮ Input-driven multi-counter automata ⋮ Consensus string problem for multiple regular languages ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ On the overlap assembly of strings and languages ⋮ Weighted operator precedence languages ⋮ Weighted Operator Precedence Languages ⋮ On the determinization of event-clock input-driven pushdown automata ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Digging input-driven pushdown automata ⋮ Input-driven pushdown automata on well-nested infinite strings

This page was built for publication: