Efficiency in the identification in the limit learning paradigm

Rémi Eyraud; Jeffrey Heinz; Ryo Yoshinaka

doi:10.1007/978-3-662-48395-4_2

Efficiency in the identification in the limit learning paradigm

Rémi Eyraud, Jeffrey Heinz, Ryo Yoshinaka

Research output: Chapter in Book/Report/Conference proceeding › Chapter

2 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Topics in Grammatical Inference
Publisher	Springer Berlin Heidelberg
Pages	25-46
Number of pages	22
ISBN (Electronic)	9783662483954
ISBN (Print)	9783662483930
DOIs	https://doi.org/10.1007/978-3-662-48395-4_2
Publication status	Published - 2016 Jan 1
Externally published	Yes

ASJC Scopus subject areas

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

Access to Document

10.1007/978-3-662-48395-4_2

Cite this

@inbook{7bd180b47cbb4de78c63d5edcc26e9f3,

title = "Efficiency in the identification in the limit learning paradigm",

abstract = "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.",

author = "R{\'e}mi Eyraud and Jeffrey Heinz and Ryo Yoshinaka",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-662-48395-4_2",

language = "English",

isbn = "9783662483930",

pages = "25--46",

booktitle = "Topics in Grammatical Inference",

publisher = "Springer Berlin Heidelberg",

}

TY - CHAP

T1 - Efficiency in the identification in the limit learning paradigm

AU - Eyraud, Rémi

AU - Heinz, Jeffrey

AU - Yoshinaka, Ryo

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84988642926&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988642926&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48395-4_2

DO - 10.1007/978-3-662-48395-4_2

M3 - Chapter

AN - SCOPUS:84988642926

SN - 9783662483930

SP - 25

EP - 46

BT - Topics in Grammatical Inference

PB - Springer Berlin Heidelberg

ER -

Efficiency in the identification in the limit learning paradigm

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this