On learning systolic languages

Takashi Yokomori

doi:10.1007/3-540-57369-0_26

On learning systolic languages

Takashi Yokomori^*

^*Corresponding author for this work

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

3 Citations (Scopus)

Abstract

We study the learning problem of systolic languages from queries and counterexamples. A systolic language is specified by a systolic automaton which is a kind of network consisting of uniformly connected processors(finite automata). In this article, we show that the class of binary systolic tree languages is learnable in polynomial time from the learning protocol what is called minimally adequate teacher. Since the class of binary systolic tree languages properly contains the class of regular languages, the main result in this paper gives a generalization of the corresponding Angluin’s result for regular languages.

Original language	English
Title of host publication	Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings
Editors	Shuji Doshita, Koichi Furukawa, Klaus P. Jantke, Toyaki Nishida
Publisher	Springer Verlag
Pages	41-52
Number of pages	12
ISBN (Print)	9783540573692
DOIs	https://doi.org/10.1007/3-540-57369-0_26
Publication status	Published - 1993
Externally published	Yes
Event	3rd Workshop on Algorithmic Learning Theory, ALT 1992 - Tokyo, Japan Duration: 1992 Oct 20 → 1992 Oct 22

Publication series

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

Other

Other	3rd Workshop on Algorithmic Learning Theory, ALT 1992
Country/Territory	Japan
City	Tokyo
Period	92/10/20 → 92/10/22

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-57369-0_26

Cite this

Yokomori, T. (1993). On learning systolic languages. In S. Doshita, K. Furukawa, K. P. Jantke, & T. Nishida (Eds.), Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings (pp. 41-52). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 743 LNAI). Springer Verlag. https://doi.org/10.1007/3-540-57369-0_26

On learning systolic languages. / Yokomori, Takashi.
Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. ed. / Shuji Doshita; Koichi Furukawa; Klaus P. Jantke; Toyaki Nishida. Springer Verlag, 1993. p. 41-52 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 743 LNAI).

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

Yokomori, T 1993, On learning systolic languages. in S Doshita, K Furukawa, KP Jantke & T Nishida (eds), Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 743 LNAI, Springer Verlag, pp. 41-52, 3rd Workshop on Algorithmic Learning Theory, ALT 1992, Tokyo, Japan, 92/10/20. https://doi.org/10.1007/3-540-57369-0_26

@inproceedings{bc00c5852b3946b18a775f21dfae8b60,

title = "On learning systolic languages",

abstract = "We study the learning problem of systolic languages from queries and counterexamples. A systolic language is specified by a systolic automaton which is a kind of network consisting of uniformly connected processors(finite automata). In this article, we show that the class of binary systolic tree languages is learnable in polynomial time from the learning protocol what is called minimally adequate teacher. Since the class of binary systolic tree languages properly contains the class of regular languages, the main result in this paper gives a generalization of the corresponding Angluin{\textquoteright}s result for regular languages.",

author = "Takashi Yokomori",

year = "1993",

doi = "10.1007/3-540-57369-0_26",

language = "English",

isbn = "9783540573692",

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

publisher = "Springer Verlag",

pages = "41--52",

editor = "Shuji Doshita and Koichi Furukawa and Jantke, {Klaus P.} and Toyaki Nishida",

booktitle = "Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings",

note = "3rd Workshop on Algorithmic Learning Theory, ALT 1992 ; Conference date: 20-10-1992 Through 22-10-1992",

}

TY - GEN

T1 - On learning systolic languages

AU - Yokomori, Takashi

PY - 1993

Y1 - 1993

N2 - We study the learning problem of systolic languages from queries and counterexamples. A systolic language is specified by a systolic automaton which is a kind of network consisting of uniformly connected processors(finite automata). In this article, we show that the class of binary systolic tree languages is learnable in polynomial time from the learning protocol what is called minimally adequate teacher. Since the class of binary systolic tree languages properly contains the class of regular languages, the main result in this paper gives a generalization of the corresponding Angluin’s result for regular languages.

AB - We study the learning problem of systolic languages from queries and counterexamples. A systolic language is specified by a systolic automaton which is a kind of network consisting of uniformly connected processors(finite automata). In this article, we show that the class of binary systolic tree languages is learnable in polynomial time from the learning protocol what is called minimally adequate teacher. Since the class of binary systolic tree languages properly contains the class of regular languages, the main result in this paper gives a generalization of the corresponding Angluin’s result for regular languages.

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

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

U2 - 10.1007/3-540-57369-0_26

DO - 10.1007/3-540-57369-0_26

M3 - Conference contribution

AN - SCOPUS:0010598230

SN - 9783540573692

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

SP - 41

EP - 52

BT - Algorithmic Learning Theory - 3rd Workshop, ALT 1992, Proceedings

A2 - Doshita, Shuji

A2 - Furukawa, Koichi

A2 - Jantke, Klaus P.

A2 - Nishida, Toyaki

PB - Springer Verlag

T2 - 3rd Workshop on Algorithmic Learning Theory, ALT 1992

Y2 - 20 October 1992 through 22 October 1992

ER -

On learning systolic languages

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this