On Goedel speed-up and succinctness of language representations
From MaRDI portal
Publication:594584
DOI10.1016/0304-3975(83)90016-6zbMath0526.68034OpenAlexW2008388355MaRDI QIDQ594584
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
non-recursive shortening of proofsrelative succinctness between different representations of languages
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
