Learning concatenations of locally testable languages from positive data

Satoshi Kobayashi; Takashi Yokomori

doi:10.1007/3-540-58520-6_80

Learning concatenations of locally testable languages from positive data

Satoshi Kobayashi, Takashi Yokomori

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

5 Citations (Scopus)

Abstract

This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C. Then we show that, for each k, the class CLT^≤k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability, and define a class (k, l)-CLTS, which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.

Original language	English
Title of host publication	Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings
Editors	Setsuo Arikawa, Klaus P. Jantke
Publisher	Springer Verlag
Pages	407-422
Number of pages	16
ISBN (Print)	9783540585206
DOIs	https://doi.org/10.1007/3-540-58520-6_80
Publication status	Published - 1994
Externally published	Yes
Event	4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994 - Reinhardsbrunn Castle, Germany Duration: 1994 Oct 10 → 1994 Oct 15

Publication series

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

Other

Other	4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994
Country/Territory	Germany
City	Reinhardsbrunn Castle
Period	94/10/10 → 94/10/15

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-58520-6_80

Cite this

Kobayashi, S., & Yokomori, T. (1994). Learning concatenations of locally testable languages from positive data. In S. Arikawa, & K. P. Jantke (Eds.), Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings (pp. 407-422). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 872 LNAI). Springer Verlag. https://doi.org/10.1007/3-540-58520-6_80

Learning concatenations of locally testable languages from positive data. / Kobayashi, Satoshi; Yokomori, Takashi.
Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings. ed. / Setsuo Arikawa; Klaus P. Jantke. Springer Verlag, 1994. p. 407-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 872 LNAI).

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

Kobayashi, S & Yokomori, T 1994, Learning concatenations of locally testable languages from positive data. in S Arikawa & KP Jantke (eds), Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 872 LNAI, Springer Verlag, pp. 407-422, 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Reinhardsbrunn Castle, Germany, 94/10/10. https://doi.org/10.1007/3-540-58520-6_80

Kobayashi S, Yokomori T. Learning concatenations of locally testable languages from positive data. In Arikawa S, Jantke KP, editors, Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings. Springer Verlag. 1994. p. 407-422. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58520-6_80

Kobayashi, Satoshi ; Yokomori, Takashi. / Learning concatenations of locally testable languages from positive data. Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings. editor / Setsuo Arikawa ; Klaus P. Jantke. Springer Verlag, 1994. pp. 407-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{725ab877e28e40efa7e1bf24a5455a3b,

title = "Learning concatenations of locally testable languages from positive data",

abstract = "This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C. Then we show that, for each k, the class CLT≤k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability, and define a class (k, l)-CLTS, which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.",

author = "Satoshi Kobayashi and Takashi Yokomori",

year = "1994",

doi = "10.1007/3-540-58520-6_80",

language = "English",

isbn = "9783540585206",

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

publisher = "Springer Verlag",

pages = "407--422",

editor = "Setsuo Arikawa and Jantke, {Klaus P.}",

booktitle = "Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings",

note = "4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994 ; Conference date: 10-10-1994 Through 15-10-1994",

}

TY - GEN

T1 - Learning concatenations of locally testable languages from positive data

AU - Kobayashi, Satoshi

AU - Yokomori, Takashi

PY - 1994

Y1 - 1994

N2 - This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C. Then we show that, for each k, the class CLT≤k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability, and define a class (k, l)-CLTS, which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.

AB - This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C. Then we show that, for each k, the class CLT≤k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability, and define a class (k, l)-CLTS, which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.

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

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

U2 - 10.1007/3-540-58520-6_80

DO - 10.1007/3-540-58520-6_80

M3 - Conference contribution

AN - SCOPUS:49649102787

SN - 9783540585206

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

SP - 407

EP - 422

BT - Algorithmic Learning Theory - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994, Proceedings

A2 - Arikawa, Setsuo

A2 - Jantke, Klaus P.

PB - Springer Verlag

T2 - 4th International Workshop on Analogical and Inductive Inference, AII 1994 and 5th International Workshop on Algorithmic Learning Theory, ALT 1994

Y2 - 10 October 1994 through 15 October 1994

ER -

Learning concatenations of locally testable languages from positive data

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this