Efficiency in the identification in the limit learning paradigm

Rémi Eyraud, Jeffrey Heinz, Ryo Yoshinaka

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Citations (Scopus)


The most widely used learning paradigm in Grammatical Inference was introduced in 1967 and is known as identification in the limit. An important issue that has been raised with respect to the original definition is the absence of efficiency bounds. Nearly fifty years after its introduction, it remains an open problem how to best incorporate a notion of efficiency and tractability into this framework. This chapter surveys the different refinements that have been developed and studied, and the challenges they face. Main results for each formalization, along with comparisons, are provided.

Original languageEnglish
Title of host publicationTopics in Grammatical Inference
PublisherSpringer Berlin Heidelberg
Number of pages22
ISBN (Electronic)9783662483954
ISBN (Print)9783662483930
Publication statusPublished - 2016 Jan 1
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)
  • Arts and Humanities(all)
  • Social Sciences(all)


Dive into the research topics of 'Efficiency in the identification in the limit learning paradigm'. Together they form a unique fingerprint.

Cite this