Paper Info
Title
A Negative Result on Inductive Inference of Extended Pattern Languages
Abstract
The question of learnability of the class of extended pattern languages is considered to be one of the eldest and outstanding open problems in inductive inference of formal languages. This paper provides an appropriate answer presenting a subclass - the terminal-free extended pattern languages - that is not learnable in the limit. In order to achieve this result we will have to limit the respective alphabet of terminal symbols to exactly two letters.In addition we will focus on the impact of ambiguity of pattern languages on inductive inference of terminal-free extended pattern languages. The conventional view on nondeterminism in patterns inspired by formal language theory is transformed into an approach that meets the requirements of inductive inference. These studies will lead to some useful learnability criteria for classes of terminal-free extended pattern languages.
Year
Venue
Keywords
2002
ALT
appropriate answer,pattern language,conventional view,extended pattern language,negative result,formal language theory,extended pattern languages,inductive inference,outstanding open problem,terminal-free extended pattern language,useful learnability criterion,formal language
Field
DocType
Volume
Computer science,Abstract family of languages,Theoretical computer science,Artificial intelligence,Natural language processing,Learnability,Ontology language,Second-generation programming language,Comparison of multi-paradigm programming languages,Formal language,Cone (formal languages),Machine learning,Language identification in the limit
Conference
2533
ISSN
ISBN
Citations 
0302-9743
3-540-00170-0
15
PageRank 
References 
Authors
0.77
16
1
Name
Order
Citations
PageRank
Daniel Reidenbach115418.06