On the classification of recursive languages

DOI10.1016/J.IC.2004.03.001MaRDI QIDQ598240zbMATH OpenOpenAlexFDO

Authors John Case, A. K. Sharma, Frank Stephan, Efim 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

structural complexityinductive learningTuring degrees

Mathematics Subject Classification ID

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

Recommendations

• On the classification of computable languages
• On one-sided versus two-sided classification
• Classifying Predicates and Languages
• LEARNING RECURSIVE LANGUAGES WITH BOUNDED MIND CHANGES
• Investigations on measure-one identification of classes of languages

Cites work

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

Cited in

(5)

• Learning and classifying
• On some properties of a linguistic classifier
• On the classification of computable languages
• Enlarging learnable classes
• Inferring answers to queries

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

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