Program Size Complexity of Correction Grammars in the Ershov Hierarchy
From MaRDI portal
Publication:3188262
DOI10.1007/978-3-319-40189-8_25zbMath1466.03009OpenAlexW2467208211MaRDI QIDQ3188262
Publication date: 17 August 2016
Published in: Pursuit of the Universal (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-40189-8_25
Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On Goedel speed-up and succinctness of language representations
- Turing oracle machines, online computing, and three displacements in computability theory
- Proof theory. 2nd ed
- Relative complexity of checking and evaluating
- On the role of procrastination in machine learning
- Proof-theoretic analysis of termination proofs
- Subrecursive programming languages. II. On program size
- On a hierarchy of sets. III
- Rice and Rice-Shapiro Theorems for transfinite correction grammars
- Theory of Formal Systems. (AM-47)
- Learning correction grammars
- On the Succinctness of Different Representations of Languages
- Program size in restricted programming languages
- Rice Theorems For D.R.E. Sets
- Succinctness of Descriptions of Unambiguous Context-Free Languages
- On the recursion-theoretic complexity of relative succinctness of representations of languages
- Degrees of Unsolvability. (AM-55)
- On the size of machines
- Recursive Structures and Ershov's Hierarchy
- On notation for ordinal numbers
- On axiomatizability within a system
- An introduction to Kolmogorov complexity and its applications
