Program Size Complexity of Correction Grammars in the Ershov Hierarchy

DOI10.1007/978-3-319-40189-8_25zbMath1466.03009OpenAlexW2467208211MaRDI QIDQ3188262

James S. Royer, John Case

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

Mathematics Subject Classification ID

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

Difficulties in Forcing Fairness of Polynomial Time Inductive Inference

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