Learning mildly context-sensitive languages with multidimensional substitutability from positive data

Ryo Yoshinaka

doi:10.1007/978-3-642-04414-4_24

Learning mildly context-sensitive languages with multidimensional substitutability from positive data

Ryo Yoshinaka

INF - System Information Sciences

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

18 Citations (Scopus)

Abstract

Recently Clark and Eyraud (2007) have shown that substitutable context-free languages, which capture an aspect of natural language phenomena, are efficiently identifiable in the limit from positive data. Generalizing their work, this paper presents a polynomial-time learning algorithm for new subclasses of mildly context-sensitive languages with variants of substitutability.

Original language	English
Title of host publication	Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings
Pages	278-292
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-04414-4_24
Publication status	Published - 2009
Event	20th International Conference on Algorithmic Learning Theory, ALT 2009 - Porto, Portugal Duration: 2009 Oct 3 → 2009 Oct 5

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5809 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on Algorithmic Learning Theory, ALT 2009
Country/Territory	Portugal
City	Porto
Period	09/10/3 → 09/10/5

Access to Document

10.1007/978-3-642-04414-4_24

Cite this

Yoshinaka, R. (2009). Learning mildly context-sensitive languages with multidimensional substitutability from positive data. In Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings (pp. 278-292). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5809 LNAI). https://doi.org/10.1007/978-3-642-04414-4_24

@inproceedings{3bc212eac4be4d7ba8ec4f72eefad2f9,

title = "Learning mildly context-sensitive languages with multidimensional substitutability from positive data",

abstract = "Recently Clark and Eyraud (2007) have shown that substitutable context-free languages, which capture an aspect of natural language phenomena, are efficiently identifiable in the limit from positive data. Generalizing their work, this paper presents a polynomial-time learning algorithm for new subclasses of mildly context-sensitive languages with variants of substitutability.",

author = "Ryo Yoshinaka",

year = "2009",

doi = "10.1007/978-3-642-04414-4_24",

language = "English",

isbn = "3642044131",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "278--292",

booktitle = "Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings",

note = "20th International Conference on Algorithmic Learning Theory, ALT 2009 ; Conference date: 03-10-2009 Through 05-10-2009",

}

Yoshinaka, R 2009, Learning mildly context-sensitive languages with multidimensional substitutability from positive data. in Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5809 LNAI, pp. 278-292, 20th International Conference on Algorithmic Learning Theory, ALT 2009, Porto, Portugal, 09/10/3. https://doi.org/10.1007/978-3-642-04414-4_24

Learning mildly context-sensitive languages with multidimensional substitutability from positive data. / Yoshinaka, Ryo.
Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings. 2009. p. 278-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5809 LNAI).

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

TY - GEN

T1 - Learning mildly context-sensitive languages with multidimensional substitutability from positive data

AU - Yoshinaka, Ryo

PY - 2009

Y1 - 2009

N2 - Recently Clark and Eyraud (2007) have shown that substitutable context-free languages, which capture an aspect of natural language phenomena, are efficiently identifiable in the limit from positive data. Generalizing their work, this paper presents a polynomial-time learning algorithm for new subclasses of mildly context-sensitive languages with variants of substitutability.

AB - Recently Clark and Eyraud (2007) have shown that substitutable context-free languages, which capture an aspect of natural language phenomena, are efficiently identifiable in the limit from positive data. Generalizing their work, this paper presents a polynomial-time learning algorithm for new subclasses of mildly context-sensitive languages with variants of substitutability.

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

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

U2 - 10.1007/978-3-642-04414-4_24

DO - 10.1007/978-3-642-04414-4_24

M3 - Conference contribution

AN - SCOPUS:77952062180

SN - 3642044131

SN - 9783642044137

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 278

EP - 292

BT - Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings

T2 - 20th International Conference on Algorithmic Learning Theory, ALT 2009

Y2 - 3 October 2009 through 5 October 2009

ER -

Yoshinaka R. Learning mildly context-sensitive languages with multidimensional substitutability from positive data. In Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings. 2009. p. 278-292. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04414-4_24

Learning mildly context-sensitive languages with multidimensional substitutability from positive data

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this