A guided tour across the boundaries of learning recursive languages
Lecture notes in computer sciencePublished 1 January 1995
Thomas Zeugmann, Steffen Lange
Citations115
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The influence of various monotonicity constraints to the learning process is considered, and a thorough study concerning the influence of several parameters is provided, which provides a unifying framework for learning.
Abstract
The present paper deals with the learnability of indexed families of uniformly recursive languages from positive data as well as from both, positive and negative data. We consider the influence of various monotonicity constraints to the learning process, and provide a thorough study concerning the influence of several parameters. In particular, we present examples pointing to typical problems and solutions in the field. Then we provide a unifying framework for learning. Furthermore, we survey results concerning learnability in dependence on the hypothesis space, and concerning order independence. Moreover, new results dealing with the efficiency of learning are provided. First, we investigate the power of iterative learning algorithms. The second measure of efficiency studied is the number of mind changes a learning algorithm is allowed to perform. In this setting we consider the problem whether or not the monotonicity constraints introduced do influence the efficiency of learning algorithms. The paper mainly emphasis to provide a comprehensive summary of results recently obtained, and of proof techniques developed. Finally, throughout our guided tour we discuss the question of what a natural language learning algorithm might look like.
Keywords
Computer Science
Information and ControlLanguage identification in the limit
3,569 Citations1967Eric Gold
It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.
Information and ControlA formal theory of inductive inference. Part II
1,786 Citations1964Ray J. Solomonoff
Four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction.
Language<b>Formal principles of language acquisition</b> . By Kenneth Wexler and Peter W. Culicover. Cambridge, MA: MIT Press, 1980. Pp. xvii, 647. $35.00.
1,525 Citations1982C. L. Baker
The authors of this book have developed a rigorous and unified theory that opens the study of language learnability to discoveries about the mechanisms of language acquisition in human beings and has important implications for linguistic theory, child language research, and the philosophy of language.
IGI Global eBooksEncyclopedia of Artificial Intelligence
1,400 Citations2009Rabuñal Dopico, Juan Ramón 1973-
Formal Languages and Their Relation to Automata
1,341 Citations1969John E. Hopcroft, Jeffrey D. Ullman
The theory of formal languages as a coherent theory is presented and its relationship to automata theory is made explicit, including the Turing machine and certain advanced topics in language theory.
Information and ControlA formal theory of inductive inference. Part I
1,149 Citations1964Ray J. Solomonoff
Nuclear Science and EngineeringFormal Languages and their Relation to Automata
1,004 Citations1970James B. Morris
ACM Computing SurveysInductive Inference: Theory and Methods
899 Citations1983Dana Angluin, Carl H. Smith
This survey highlights and explains the main ideas that have been developed in the study of inductive inference, with special emphasis on the relations between the general theory and the specific algorithms and implementations.
Information and ControlInductive inference of formal languages from positive data
750 Citations1980Dana Angluin
A theorem characterizing when an indexed family of nonempty recursive formal languages is inferrable from positive data is proved, and other useful conditions for inference frompositive data are obtained.
Journal of Computer and System SciencesFinding patterns common to a set of strings
607 Citations1980Dana Angluin
The main result is a polynomial-time algorithm for the special case of patterns containing only one variable symbol (possibly occurring several times in the pattern).
Journal of the ACMComputational limitations on learning from examples
532 Citations1988Leonard Pitt, Leslie G. Valiant
It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP, and relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.
The MIT Press eBooksThe Acquisition of Syntactic Knowledge
512 Citations1985Robert C. Berwick
An explicit computational model of language acquisition is presented which can actually learn rules of English syntax given a sequence of grammatical, but otherwise unprepared, sentences and demonstrates how constraints that may be reasonably assumed to aid sentence processing also aid language acquisition.
Systems That Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists
487 Citations1986Daniel N. Osherson, Michael Stob +1 more
Systems That Learn presents a mathematical framework for the study of learning in a variety of domains that provides the basic concepts and techniques of learning theory as well as a comprehensive account of what is currently known about a range of learning paradigms.
Encyclopedia of Artificial Intelligence
425 Citations2021
Theoretical Computer ScienceComparison of identification criteria for machine inductive inference
415 Citations1983John Case, Carl H. Smith
A natural ωpLω+1 hierarchy of successively more general criteria of success for inductive inference machines is described based on the size of sets of anomalies in programs synthesized by such machines.
Computational learning theory
322 Citations1992Dana Angluin
The general AI meetings, AAAI and IJCAI, currently have a large number of papers devoted to learning, as do the neural net meetings, and the European meetings on Analogical and Inductive Inference and the AI machine learning communit y’s annual International Conference on Machine Learning.
Nonmonotonic Reasoning: Logical Foundations of Commonsense
270 Citations1991Gerhard Brewka
CERN Document Server (European Organization for Nuclear Research)Machine Learning: A Theoretical Approach
253 Citations1992BALAS K. NATARAJAN
This paper presents a meta-modelling framework that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive process of learning about discrete-time learning.
Lecture notes in computer scienceMachine inductive inference and language identification
181 Citations1982John Case, Christopher Lynes
It is shown that for some classes of recursive languages, from the characteristic function of any L in ℒ an approximate decision procedure for L with no more than n+1 mistakes can be (uniformly effectively) inferred in the limit; whereas, in general, a grammar with no less than n mistakes cannot be inferred.
Information and ComputationPrudence and other conditions on formal language learning
130 Citations1990Mark A. Fulk
It is shown that set-driven IIMs are limited in power, whereas order- independent, rearrangement-independent, and prudent IIM are not, and the motivation of formal language learning theory from human language learning is questioned.
New Generation ComputingPolynomial-time inference of arbitrary pattern languages
128 Citations1991Steffen Lange, Rolf Wiehagen
An inconsistent polynomial-time algorithm is presented which identifies every pattern language in the limit and investigates inference of arbitrary pattern languages within the framework of learning from good examples.
ACM Transactions on Programming Languages and SystemsEditing by example
101 Citations1985Robert Nix
By developing an editing by example system that solves a useful class of text processing problems, this paper demonstrates that program synthesis is feasible in the domain of text editing.
New Generation ComputingMonotonic and non-monotonic inductive inference
84 Citations1991Klaus P. Jantke
The main goal is to exhibit the relationship between research work on non-monotonic reasoning and recursion-theoretically based approaches to inductive learning.
Types of monotonic language learning and their characterization
81 Citations1992Steffen Lange, Thomas Zeugmann
It is proved that strong-monotonic inference can be performed with iteratively learning devices without limiting the inference capabilities, while monotonic and weak-monotsonic inference cannot.
Lecture notes in computer scienceA thesis in inductive inference
79 Citations2005Rolf Wiehagen
The following thesis was stated: Any class of recursive functions which is identifiable at all can always be identified by an enumeratively working strategy and the identification canAlways be realized with respect to a suitable nonstandard (i.e. non-Godel) numbering.
Journal of Symbolic LogicInductive inference and unsolvability
72 Citations1991Leonard M. Adleman, Manuel Blum
It is shown that many different problems have the same degree of unsolvability, and these unsolvable problems are strictly easier than the halting problem.
Lecture notes in computer scienceMonotonic versus non-monotonic language learning
64 Citations2006Steffen Lange, Thomas Zeugmann
Strong- monotonic, monotonie and weak-monotonic reasoning is studied in the context of algorithmic language learning theory from positive as well as from positive and negative data.
Conference on Learning TheoryA polynomial-time algorithm for learning k-variable pattern languages from examples
64 Citations1989Michael Kearns, Leonard Pitt
Theoretical Computer ScienceOn the power of probabilistic strategies in inductive inference
52 Citations1983Rolf Wiehagen, Rūsiņš Freivalds +1 more
Advantages of probabilistic strategies over deterministic ones are shown concerning their power in principle and their computational complexity (linear speed-up of the number of changes of hypotheses necessary for inference by deterministic strategies).
Information and ComputationCharacterizations of Monotonic and Dual Monotonic Language Learning
50 Citations1995Thomas Zeugmann, Steffen Lange +1 more
These characterizations provide a unifying framework for learning from positive data under the various monotonicity constraints and yield additional insight into the problem of what a natural learning algorithm should look like.
Lecture notes in computer scienceLearning and consistency
46 Citations1995Rolf Wiehagen, Thomas Zeugmann
In designing learning algorithms it seems quite reasonable to construct them in such a way that all data the algorithm already has obtained are correctly and completely reflected in the hypothesis the algorithm outputs on these data, but this approach may totally fail.
Elsevier eBooksA Polynomial-time Algorithm for Learning k-variable Pattern Languages from Examples
42 Citations1989Michael Kearns, Leonard Pitt
This chapter focuses on a polynomial-time algorithm for learning k -variable pattern languages in the learning model introduced by Valiant, where k is a string of constant and variable symbols and p is a target pattern.
International Journal of Foundations of Computer ScienceLEARNING RECURSIVE LANGUAGES WITH BOUNDED MIND CHANGES
33 Citations1993Steffen Lange, Thomas Zeugmann
The learnability of enumerable families ℒ of uniformly recursive languages in dependence on the number of allowed mind changes is studied, i.e. with respect to a well-studied measure of efficiency.
Theory of Computing SystemsSet-driven and rearrangement-independent learning of recursive languages
32 Citations1996Steffen Lange, Thomas Zeugmann
The impact of order independence to the learnability of indexed families of uniformly recursive languages from positive data is studied and it is proved that for all but two of the learning models considered set-drivenness is a severe restriction, however, class-comprising set- drivenconservative learning is exactly as powerful as unrestricted class- comprisingconservative learning.
Lecture notes in computer scienceMonotonic and non-monotonic inductive inference of functions and patterns
31 Citations2005Klaus P. Jantke
It turned out that in the area of inductive inference of total recursive functions monotonicity can rarely be guaranteed and these results are compared to the problem of inductively inferring text patterns from finite samples.
Lecture notes in computer scienceMonotonic language learning
23 Citations1993Shyam Kapur
The ideas from inductive reasoning are instantiated in alternative ways, and links are established between the various new constraints both among themselves as well as with other well-known constraints, such as conservativeness.
Lecture notes in computer scienceLanguage learning without overgeneralization
20 Citations1992Shyam Kapur, Gianfranco Bilardi
Kyoto University Research Information Repository (Kyoto University)Polynomial Time Inference of Extended Regular Pattern Languages.
19 Citations1982Takeshi Shinohara
The Subset Principle is an Intensional Principle
19 Citations1993Kenneth Wexler
Lecture notes in computer scienceInductive inference with bounded mind changes
17 Citations1993Yasuhito Mukouchi
An n-bounded finite tell-tale and a pair of n- bounded finiteTell-tales of a language are introduced and it is shown that the inferability of a class from positive data strictly increases, when the allowed number of mind changes increases.
Elsevier eBooksLEARNING SIMPLE DETERMINISTIC LANGUAGES
14 Citations1989Hiroki Ishizaka
The algorithm described in this paper is essentially based on the theory of model inference given by Shapiro, however, nonterminal membership queries, for nonterminals except the start symbol, are not used and extended equivalence queries are used.
New Generation ComputingA machine discovery from amino acid sequences by decision trees over regular patterns
11 Citations1993Setsuo Arikawa, Satoru Miyano +4 more
It is shown that the class of languages defined by decesion trees of depth at mostd overk-variable regular patterns is polynomial-time learnable in the sense of probably approximately correct (PAC) learning for any fixedd, k≥0.
Journal of Experimental & Theoretical Artificial IntelligenceCharacterization of language learning front informant under various monotonicity constraints
11 Citations1994Steffen Lange, Thomas Zeugmann
A unifying approach to monotonic language learning is elaborate by showing that there is exactly one learning algorithm which can perform any monotonics inference task.
Lecture notes in computer scienceAsking questions versus verifiability
9 Citations1992William Gasarch, Mahendran Velauthapillai
The representation of recursive languages and its impact on the efficiency of learning
7 Citations1994Steffen Lange
The measure of efficiency is applied to prove the superiority of class comprising learning algorithms over class preserving learning which itself turns out to be superior to exact learning algorithms.