Learning efficiency of very simple grammars from positive data

Ryo Yoshinaka

doi:10.1007/978-3-540-75225-7_20

Learning efficiency of very simple grammars from positive data

Ryo Yoshinaka

INF - System Information Sciences

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

5 Citations (Scopus)

Abstract

The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.

Original language	English
Title of host publication	Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings
Publisher	Springer Verlag
Pages	227-241
Number of pages	15
ISBN (Print)	9783540752240
DOIs	https://doi.org/10.1007/978-3-540-75225-7_20
Publication status	Published - 2007
Event	18th International Conference on Algorithmic Learning Theory, ALT 2007 - Sendai, Japan Duration: 2007 Oct 1 → 2007 Oct 4

Publication series

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

Conference

Conference	18th International Conference on Algorithmic Learning Theory, ALT 2007
Country/Territory	Japan
City	Sendai
Period	07/10/1 → 07/10/4

Access to Document

10.1007/978-3-540-75225-7_20

Cite this

Yoshinaka, R. (2007). Learning efficiency of very simple grammars from positive data. In Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings (pp. 227-241). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4754 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-540-75225-7_20

@inproceedings{9fce0e4757104ab4b02441e3505d218b,

title = "Learning efficiency of very simple grammars from positive data",

abstract = "The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.",

author = "Ryo Yoshinaka",

note = "Funding Information: This work was supported by Grant-in-Aid for Young Scientists (B-20700124) and a grant from the Global COE Program, {\textquoteleft}{\textquoteleft}Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation{\textquoteright}{\textquoteright}, from the Ministry of Education, Culture, Sports, Science and Technology of Japan.; 18th International Conference on Algorithmic Learning Theory, ALT 2007 ; Conference date: 01-10-2007 Through 04-10-2007",

year = "2007",

doi = "10.1007/978-3-540-75225-7_20",

language = "English",

isbn = "9783540752240",

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

publisher = "Springer Verlag",

pages = "227--241",

booktitle = "Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings",

address = "Germany",

}

Yoshinaka, R 2007, Learning efficiency of very simple grammars from positive data. in Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4754 LNAI, Springer Verlag, pp. 227-241, 18th International Conference on Algorithmic Learning Theory, ALT 2007, Sendai, Japan, 07/10/1. https://doi.org/10.1007/978-3-540-75225-7_20

Learning efficiency of very simple grammars from positive data. / Yoshinaka, Ryo.
Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings. Springer Verlag, 2007. p. 227-241 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4754 LNAI).

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

TY - GEN

T1 - Learning efficiency of very simple grammars from positive data

AU - Yoshinaka, Ryo

N1 - Funding Information: This work was supported by Grant-in-Aid for Young Scientists (B-20700124) and a grant from the Global COE Program, ‘‘Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation’’, from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

PY - 2007

Y1 - 2007

N2 - The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.

AB - The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.

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

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

U2 - 10.1007/978-3-540-75225-7_20

DO - 10.1007/978-3-540-75225-7_20

M3 - Conference contribution

AN - SCOPUS:38149007133

SN - 9783540752240

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

SP - 227

EP - 241

BT - Algorithmic Learning Theory - 18th International Conference, ALT 2007, Proceedings

PB - Springer Verlag

T2 - 18th International Conference on Algorithmic Learning Theory, ALT 2007

Y2 - 1 October 2007 through 4 October 2007

ER -

Learning efficiency of very simple grammars from positive data

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this