On the classification of recursive languages

DOI10.1016/j.ic.2004.03.001zbMath1074.68030OpenAlexW2028185140MaRDI QIDQ598240

Frank Stephan, John Case, Arun Sharma, E. B. Kinber

Publication date: 6 August 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.03.001

zbMATH Keywords

inductive learningstructural complexityTuring degrees

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45) Other Turing degree structures (03D28)

Related Items (3)

Enlarging learnable classes ⋮ Learning and classifying ⋮ Inferring answers to queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of identification criteria for machine inductive inference
• Elementary formal systems, intrinsic complexity, and procrastination
• Monotonic and non-monotonic inductive inference
• Classical recursion theory. The theory of functions and sets of natural numbers
• Some natural properties of strong-identification in inductive inference
• Can finite samples detect singularities of real-valued functions?
• Classification using information
• On the role of procrastination in machine learning
• On one-sided versus two-sided classification
• Ordinal mind change complexity of language identification
• Generalized notions of mind change complexity
• Characterizations of monotonic and dual monotonic language learning
• Inductive inference of formal languages from positive data
• Inductive inference and unsolvability
• ON LEARNING LIMITING PROGRAMS
• Toward a mathematical theory of inductive inference
• Machine learning of higher-order programs
• Classifying Predicates and Languages
• Generalization versus classification
• On the classification of computable languages
• Decision problems forω-automata
• The degrees of bi‐immune sets
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton
• Language identification in the limit
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: On the classification of recursive languages