Program size complexity of correction grammars in the Ershov hierarchy

DOI10.1007/978-3-319-40189-8_25zbMATH Open1466.03009OpenAlexW2467208211MaRDI QIDQ3188262FDOQ3188262

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

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

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)

Cites Work

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

Cited In (5)

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

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)