• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries

Cristina Tirnauca, Timo Knuutila, Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries. In: R.A. Servedio E. Takimoto M. Hutter (Ed.), Proceedings of the 18th International Conference on Algorithmic Learning Theory (ALT 07), Lecture Notes in Artificial Intelligence, Springer-Verlag, 2007.

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.

BibTeX entry:

@INPROCEEDINGS{inpTiKn07a,
  title = {Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries},
  booktitle = {Proceedings of the 18th International Conference on Algorithmic Learning Theory (ALT 07)},
  author = {Tirnauca, Cristina and Knuutila, Timo},
  number = {4754},
  series = {Lecture Notes in Artificial Intelligence},
  editor = {M. Hutter, R.A. Servedio E. Takimoto},
  publisher = {Springer-Verlag},
  year = {2007},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI)

Edit publication