A note on the succinctness of descriptions of deterministic languages
From MaRDI portal
Publication:4105806
DOI10.1016/S0019-9958(76)90173-XzbMath0338.68059MaRDI QIDQ4105806
Publication date: 1976
Published in: Information and Control (Search for Journal in Brave)
Related Items (19)
On the sizes of DPDAs, PDAs, LBAs ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Why it might pay to assume that languages are infinite ⋮ Syntax checking either way ⋮ On Goedel speed-up and succinctness of language representations ⋮ Pushdown automata with bounded nondeterminism and bounded ambiguity ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Concise description of finite languages ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ A pushdown automaton or a context-free grammar - which is more economical? ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Syntax checking either way ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ Pushdown automata with bounded nondeterminism and bounded ambiguity ⋮ Lower bounds on the size of deterministic parsers ⋮ On reducing the number of stack symbols in a PDA
This page was built for publication: A note on the succinctness of descriptions of deterministic languages
