Language identification in the limit

DOI10.1016/S0019-9958(67)91165-5zbMath0259.68032WikidataQ29013514 ScholiaQ29013514MaRDI QIDQ5674988

Publication date: 1967

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

68Q45: Formal languages and automata

Related Items

On the inference of optimal descriptions, On the inference of strategies, Learning approximately regular languages with reversible languages, Investigations on measure-one identification of classes of languages, A note on batch and incremental learnability, Learning with refutation, Stream surface construction using mass conservative interpolation, On the inductive inference of recursive real-valued functions, Approximation methods in inductive inference, Learning via queries and oracles, The logic of reliable and efficient inquiry, Maximal machine learnable classes, Inductive inference in the limit for first-order sentences, A model for science kinematics, Extremes in the degrees of inferability, Structured connectionist models and language learning, Logic program synthesis from incomplete specifications, Synthesis of real time acceptors, Complex systems, complexity measures, grammars and model-inferring, Characterizing language identification by standardizing operations, The query complexity of learning DFA, Program size restrictions in computational learning, The learnability of description logics with equality constraints, Learning in the presence of inaccurate information, On aggregating teams of learning machines, Learning-theoretic perspectives of acceptable numberings, Generating grammars for SGML tagged texts lacking DTD, An interactive learning algorithm for acquisition of concepts represented as CFL, Kolmogorov numberings and minimal identification, Recent advances of grammatical inference, Learning deterministic even linear languages from positive examples, Probabilistic language learning under monotonicity constraints, Noisy inference and oracles, On the intrinsic complexity of learning recursive functions, Identification of function distinguishable languages., Learning how to separate., Separation of uniform learning classes., Inference of \(\omega\)-languages from prefixes., Learning by switching type of information., Algorithmic complexity of recursive and inductive algorithms, Experience, generations, and limits in machine learning, An average-case optimal one-variable pattern language learner, Learning languages and functions by erasing, Some classes of Prolog programs inferable from positive data, Structural measures for games and process control in the branch learning model, Ordinal mind change complexity of language identification, Mind change complexity of learning logic programs, Language learning from texts: Degrees of intrinsic complexity and their characterizations, On learning formulas in the limit and with assurance., Inductive inference with additional information., Generalized logical consequence: Making room for induction in the logic of science, Learning local transductions is hard, Semantic bootstrapping of type-logical grammar, Increasing the power of uniform inductive learners, Trade-off among parameters affecting inductive inference, On the power of incremental learning., Learning classes of approximations to non-recursive functions., Even linear simple matrix languages: formal language properties and grammatical inference., The synthesis of language learners., Incremental concept learning for bounded data mining., Robust behaviorally correct learning., The complexity of universal text-learners., Induction by enumeration, Learning by the process of elimination, Variants of iterative learning, Advanced elementary formal systems., Decision lists over regular patterns., Refutable language learning with a neighbor system., On learning of functions refutably., Refuting learning revisited., Polynomial-time identification of very simple grammars from positive data., Learning power and language expressiveness., PAC learning of probability distributions over a discrete domain., Intrinsic complexity of learning geometrical concepts from positive data, Trees and learning, Robust learning -- rich and poor, Generalized notions of mind change complexity, Counting extensional differences in BC-learning, Testing nonlinear operators, Autonomous theory building systems, The appropriateness of predicate invention as bias shift operation in ILP, Inductive inference in the limit of empirically adequate theories, Recursion theoretic models of learning: Some results and intuitions, A comparative analysis of recent identification approaches for discrete-event systems, Grammar induction by unification of type-logical lexicons, Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data, Generality's price: Inescapable deficiencies in machine-learned programs, \(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures, On the data consumption benefits of accepting increased uncertainty, Learning tree languages from positive examples and membership queries, Invertible classes, `Ideal learning' of natural language: positive results about learning from positive evidence, Ockham's razor, empirical complexity, and truth-finding efficiency, Results on memory-limited U-shaped learning, Formal language identification: query learning vs. gold-style learning, E-generalization using grammars, Language structure: psychological and social constraints, Some natural conditions on incremental learning, Iterative learning from positive data and negative counterexamples, A general comparison of language learning from examples and from queries, Probabilistic inductive inference: A survey, Synthesizing learners tolerating computable noisy data, Robust learning is rich, Control structures in hypothesis spaces: The influence on learning, Learning algebraic structures from text, Aspects of complexity of probabilistic learning under monotonicity constraints, A comparison of identification criteria for inductive inference of recursive real-valued functions, Closedness properties in ex-identification, Comparison of identification criteria for machine inductive inference, Learning all subfunctions of a function, Classes with easily learnable subclasses, On the classification of recursive languages, Anomalous learning helps succinctness, Monotonic and dual monotonic language learning, A learning-theoretic characterization of classes of recursive functions, Language learning without overgeneralization, Training digraphs, On a question about learning nearly minimal programs, Case-based representation and learning of pattern languages, Towards a mathematical theory of machine discovery from facts, Characterizing language identification in terms of computable numberings, Solving divergence in Knuth--Bendix completion by enriching signatures, On the non-existence of maximal inference degrees for language identification, Resource restricted computability theoretic learning: Illustrative topics and problems, Input-dependence in function-learning, Inductive inference of monotonic formal systems from positive data, Polynomial-time inference of arbitrary pattern languages, Inference of deterministic one-counter languages, Note on a central lemma for learning theory, On the inference of approximate programs, Training sequences, Learning via finitely many queries, ``Linear chaos via paradoxical set decompositions., A non-learnable class of E-pattern languages, Unifying logic, topology and learning in parametric logic, The complexity of finding SUBSEQ\((A)\), Learning languages in a union, On the learnability of vector spaces, An approach to intrinsic complexity of uniform learning, On ordinal VC-dimension and some notions of complexity, From learning in the limit to stochastic finite learning, Learning of erasing primitive formal systems from positive examples, Learning a subclass of regular patterns in polynomial time, Prudence and other conditions on formal language learning, Learning recursive functions: A survey, Reflective inductive inference of recursive functions, Quantum inductive inference by finite automata, Measuring teachability using variants of the teaching dimension, Some classes of term rewriting systems inferable from positive data, Developments from enquiries into the learnability of the pattern languages from positive data, Discontinuities in pattern inference, Learning indexed families of recursive languages from positive data: A survey, Learning and extending sublanguages, When unlearning helps, Non-U-shaped vacillatory and team learning, Learning languages from positive data and negative counterexamples, Probabilistic and team PFIN-type learning: General properties, Inferring answers to queries, Taming teams with mind changes, Learning with belief levels, Learning in Friedberg numberings, Kernel methods for learning languages, Universal automata and NFA learning, Consistent and coherent learning with \(\delta \)-delay, Topological properties of concept spaces (full version), Models of active learning in group-structured state spaces, Numberings optimal for learning, On some open problems in reflective inductive inference, Iterative learning of simple external contextual languages, Incremental learning with temporary memory, On some open problems in monotonic and conservative learning, Toward the interpretation of non-constructive reasoning as non-monotonic learning, Learning \((k,l)\)-contextual tree languages for information extraction from web pages, U-shaped, iterative, and iterative-with-counter learning, Algorithms for learning regular expressions from positive data, Prescribed learning of r.e. classes, Parallelism increases iterative learning power, Incremental learning of approximations from positive data, One-shot learners using negative counterexamples and nearest positive examples, Necessary and sufficient conditions for learning with correction queries, Bridging learning theory and dynamic epistemic logic, Mind change optimal learning of Bayes net structure from dependency and independency data, Identification of pattern languages from examples and queries, Probability and plurality for aggregations of learning machines, Index sets in the arithmetical hierarchy, Synthesizing inductive expertise, Inference of even linear grammars and its application to picture description languages, On the power of recursive optimizers, Saving the phenomena: Requirements that inductive inference machines not contradict known data, Paradigms of truth detection, Schema induction for logic program synthesis, On the relative sizes of learnable sets, Research in the theory of inductive inference by GDR mathematicians - A survey, Inductive inference from all positive and some negative data, Learning in the presence of partial explanations, Learning elementary formal systems, Efficient learning of context-free grammars from positive structural examples, Aggregating inductive expertise on partial recursive functions, Memory systems, computation, and the second law of thermodynamics, Inductive reasoning and Kolmogorov complexity, On uniform learnability of language families, Learning semilinear sets from examples and via queries, IIPS: A framework for specifying inductive-inference problems, On the power of inductive inference from good examples, A mathematical theory of learning transformational grammar, On the stability of some biological schemes with cellular interactions, Finite automata and S-R models, Inference for regular bilanguages, Learning deterministic regular grammars from stochastic samples in polynomial time, Infinitary self-reference in learning theory, The power of probabilism in Popperian FINite learning, Characterization of language learning front informant under various monotonicity constraints, Ignoring data may be the only way to learn efficiently, A framework for polynomial-time query learnability, Machine learning of higher-order programs, The structure of intrinsic complexity of learning, The functions of finite support: a canonical learning problem, Set-driven and rearrangement-independent learning of recursive languages, Applying formal concepts to learning systems validation, On an open problem in classification of languages, Unnamed Item, Generalization versus classification, Prudence in vacillatory language identification, A grammatical inference for harmonic linear languages, Fuzzy Technique Based Recognition of Handwritten Characters, Parsimony hierarchies for inductive inference, UNAMBIGUOUS MORPHIC IMAGES OF STRINGS, The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx, Inductive logic programming, Explanatory and creative alternatives to the MDL principle, Robust learning with infinite additional information, Costs of general purpose learning, On the learnability of recursively enumerable languages from good examples, Synthesizing noise-tolerant language learners, Hierarchies of probabilistic and team FIN-learning, Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries, Vacillatory and BC learning on noisy data, Inductive inference of unbounded unions of pattern languages from positive data, Learning multiple languages in groups, Learning languages from positive data and a limited number of short counterexamples, Learnability of pregroup grammars, Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms, Evolutionary induction of stochastic context free grammars, Natural language grammar induction with a generative constituent-context model, Smoothing and compression with stochastic \(k\)-testable tree languages, Learning languages from positive data and a finite number of queries, Identification of birfsa languages., Mind change efficient learning, Variations on U-shaped learning, Learning in varieties of the form \(\mathbf {V^{*}LI}\) from positive data, System identification via state characterization, On the inference of Turing machines from sample computations, On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms, Inductive inference of approximations for recursive concepts, Learning erasing pattern languages with queries, Relations between Gold-style learning and query learning, On learnability of restricted classes of categorial grammars, A family of languages which is polynomial-time learnable from positive data in pitt's sense, Introducing new predicates to model scientific revolution, Infinite Arrays and Domino Systems, PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part I: Dynamic Complexity, PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part II: Static Complexity, On a Question of Frank Stephan, Learning tree languages from text, Learning discrete categorial grammars from structures, Parallelism Increases Iterative Learning Power, Prescribed Learning of R.E. Classes, Learning in Friedberg Numberings, One-Shot Learners Using Negative Counterexamples and Nearest Positive Examples, Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries, Learning Meets Verification, Learning Left-to-Right and Right-to-Left Iterative Languages, On Learning Regular Expressions and Patterns Via Membership and Correction Queries, A Note on the Relationship between Different Types of Correction Queries, Evaluation and Comparison of Inferred Regular Grammars, Identification in the Limit of k,l-Substitutable Context-Free Languages, Learning Node Label Controlled Graph Grammars (Extended Abstract), Active Learning of Group-Structured Environments, Iterative Learning of Simple External Contextual Languages, Topological Properties of Concept Spaces, Dynamic Modeling in Inductive Inference, Numberings Optimal for Learning, Learning Meaning Before Syntax, Unnamed Item, Prediction of Recursive Real-Valued Functions from Finite Examples, Analytical Inductive Functional Programming, Hypothesis Spaces for Learning, Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory, Learning by Erasing in Dynamic Epistemic Logic, One-Clock Deterministic Timed Automata Are Efficiently Identifiable in the Limit, Identification through Inductive Verification, Learning correction grammars, Difficulties in Forcing Fairness of Polynomial Time Inductive Inference, Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data, Uncountable Automatic Classes and Learning, Iterative Learning from Texts and Counterexamples Using Additional Information, Incremental Learning with Ordinal Bounded Example Memory, Learning from Streams, Regular prefix relations, Inductive inference of context-free languages based on context-free expressions, Unnamed Item, Learning via queries in [+, <], The gap between abstract and concrete results in machine learning, SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY, Total complexity and the inference of best programs, Continuous operations on languages, Unnamed Item, Inferring regular languages by merging nonterminals