Program size complexity of correction grammars in the Ershov hierarchy

DOI10.1007/978-3-319-40189-8_25MaRDI QIDQ3188262zbMATH OpenOpenAlexFDO

Authors 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

Grammars and rewriting systems (68Q42) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Learning correction grammars
• Learning Correction Grammars
• Rice and Rice-Shapiro theorems for transfinite correction grammars
• Infinite Computations and a Hierarchy in  3 Reconsidered
• scientific article; zbMATH DE number 4028931

Cites work

• scientific article; zbMATH DE number 5838313 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 408817 (Why is no real title available?)
• scientific article; zbMATH DE number 1390277 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• An introduction to Kolmogorov complexity and its applications
• Degrees of Unsolvability. (AM-55)
• Introduction to mathematical logic
• Learning correction grammars
• On Goedel speed-up and succinctness of language representations
• On a hierarchy of sets. III
• On axiomatizability within a system
• On notation for ordinal numbers
• On the Succinctness of Different Representations of Languages
• On the recursion-theoretic complexity of relative succinctness of representations of languages
• On the role of procrastination in machine learning
• On the size of machines
• Program size in restricted programming languages
• Proof theory. 2nd ed
• Proof-theoretic analysis of termination proofs
• Recursive Structures and Ershov's Hierarchy
• Relative complexity of checking and evaluating
• Rice Theorems For D.R.E. Sets
• Rice and Rice-Shapiro theorems for transfinite correction grammars
• Subrecursive programming languages. II. On program size
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• Theory of Formal Systems. (AM-47)
• Turing oracle machines, online computing, and three displacements in computability theory

Cited in

(5)

• Infinite Computations and a Hierarchy in  3 Reconsidered
• Learning correction grammars
• Learning Correction Grammars
• Difficulties in Forcing Fairness of Polynomial Time Inductive Inference
• Rice and Rice-Shapiro theorems for transfinite correction grammars

This page was built for publication: Program size complexity of correction grammars in the Ershov hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188262)