A note on the succinctness of descriptions of deterministic languages

DOI10.1016/S0019-9958(76)90173-XzbMath0338.68059MaRDI QIDQ4105806

Leslie G. Valiant

Publication date: 1976

Published in: Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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