Succinctness of Descriptions of Unambiguous Context-Free Languages

DOI10.1137/0206039MaRDI QIDQ4133160zbMATH OpenOpenAlexFDO

Authors Thomas G. Szymanski, Erik Meineche Schmidt

Publication date 1977

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/7319

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited in

(12)

• Concise description of finite languages
• A pushdown automaton or a context-free grammar - which is more economical?
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• On the descriptional power of heads, counters, and pebbles
• In memoriam Chandra Kintala
• On reducing the number of stack symbols in a PDA
• Program size complexity of correction grammars in the Ershov hierarchy
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• On Goedel speed-up and succinctness of language representations
• Complexity of multi-head finite automata: origins and directions

This page was built for publication: Succinctness of Descriptions of Unambiguous Context-Free Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133160)