Succinctness of Descriptions of Unambiguous Context-Free Languages
From MaRDI portal
Publication:4133160
DOI10.1137/0206039zbMath0357.68088OpenAlexW2094856502MaRDI QIDQ4133160
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
Related Items
IN MEMORIAM CHANDRA KINTALA ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ 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 ⋮ Concise description of finite languages ⋮ A pushdown automaton or a context-free grammar - which is more economical? ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Pushdown automata with bounded nondeterminism and bounded ambiguity ⋮ On reducing the number of stack symbols in a PDA