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

Linguistics

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

6 Scopus citations

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
State	Published - Jan 1 2016

Access to Document

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

Cite this

@inbook{7d64683b12a9428e9275f1699b36918d,

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 - https://www.scopus.com/pages/publications/84988642926

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

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

M3 - Chapter

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

Access to Document

Other files and links

Fingerprint

Cite this