On Goedel speed-up and succinctness of language representations

DOI10.1016/0304-3975(83)90016-6zbMath0526.68034OpenAlexW2008388355MaRDI QIDQ594584

Juris Hartmanis

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90016-6

zbMATH Keywords

non-recursive shortening of proofsrelative succinctness between different representations of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Proof theory and constructive mathematics (03F99)

Related Items (18)

The chop of languages ⋮ On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ Document spanners: from expressive power to decision problems ⋮ Two recursion theoretic characterizations of proof speed-ups ⋮ Extended regular expressions: succinctness and decidability ⋮ Expressiveness and static analysis of extended conjunctive regular path queries ⋮ Unnamed Item ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA ⋮ Self-Verifying Pushdown and Queue Automata ⋮ One-Time Nondeterministic Computations ⋮ New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems ⋮ On reducing the number of stack symbols in a PDA ⋮ Concise representations of regular languages by degree and probabilistic finite automata

Cites Work

• On the Succinctness of Different Representations of Languages
• Program size in restricted programming languages
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• On the size of machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On Goedel speed-up and succinctness of language representations