Learning deterministic even linear languages from positive examples

Takeshi Koshiba*, Erkki Mäkinen, Yuji Takada

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


We consider the problem of learning deterministic even linear languages from positive examples. We show that, for any nonnegative integer k, the class of LR(k) even linear languages is not learnable from positive examples while there is a subclass called LRS(k), which is a natural subclass of LR(k) in the strong sense, learnable from positive examples. Our learning algorithm identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k-reversible languages that is more efficient than the one proposed by Angluin.

Original languageEnglish
Pages (from-to)63-79
Number of pages17
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 1997 Oct 10
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Learning deterministic even linear languages from positive examples'. Together they form a unique fingerprint.

Cite this