On the Succinctness of Different Representations of Languages

DOI10.1137/0209010zbMath0453.68054OpenAlexW1999147218MaRDI QIDQ3901021

Juris Hartmanis

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1137/0209010

zbMATH Keywords

Turing machinescontext-free languagesvalid computationsdeterministic languagesunambiguous languagesverified representations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

The chop of languages ⋮ One-way reversible multi-head finite automata ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ On Goedel speed-up and succinctness of language representations ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Complexity of multi-head finite automata: origins and directions ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY ⋮ On the descriptional power of heads, counters, and pebbles ⋮ SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ Set Automata

This page was built for publication: On the Succinctness of Different Representations of Languages