Paper Info
Title
Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries
Abstract
We investigate two of the language classes intensively studied by the algorithmic learning theory community in the context of learning with correction queries. More precisely, we show that any pattern language can be inferred in polynomial time in length of the pattern by asking just a linear number of correction queries, and that k-reversible languages are efficiently learnable within this setting. Note that although the class of all pattern languages is learnable with membership queries, this cannot be done in polynomial time. Moreover, the class of k-reversible languages is not learnable at all using membership queries only.
Year
DOI
Venue
2007
10.1007/978-3-540-75225-7_23
ALT
Keywords
Field
DocType
learning k-reversible languages,k-reversible language,correction query,pattern language,pattern languages,polynomial time algorithms,correction queries,theory community,polynomial time,language class,membership query,linear number,learning theory
Algorithmic learning theory,Computer science,Square-free polynomial,Algorithm,Theoretical computer science,Pattern language,Artificial intelligence,Polynomial algorithm,Time complexity,Machine learning
Conference
Volume
ISSN
Citations 
4754
0302-9743
8
PageRank 
References 
Authors
0.50
17
2
Name
Order
Citations
PageRank
Cristina Tîrnăucă1384.10
Timo Knuutila212514.06