The strong, weak, and very weak finite context and kernel properties

Makoto Kanazawa; Ryo Yoshinaka

doi:10.1007/978-3-319-53733-7_5

The strong, weak, and very weak finite context and kernel properties

Makoto Kanazawa, Ryo Yoshinaka

INF - System Information Sciences

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

1 Citation (Scopus)

Abstract

We identify the properties of context-free grammars that exactly correspond to the behavior of the dual and primal versions of Clark and Yoshinaka’s distributional learning algorithm and call them the very weak finite context/kernel property. We show that the very weak finite context property does not imply Yoshinaka’s weak finite context property, which has been assumed to hold of the target language for the dual algorithm to succeed. We also show that the weak finite context property is genuinely weaker than Clark’s strong finite context property, settling a question raised by Yoshinaka.

Original language	English
Title of host publication	Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
Editors	Frank Drewes, Carlos Martín-Vide, Bianca Truthe
Publisher	Springer Verlag
Pages	77-88
Number of pages	12
ISBN (Print)	9783319537320
DOIs	https://doi.org/10.1007/978-3-319-53733-7_5
Publication status	Published - 2017
Event	11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden Duration: 2017 Mar 6 → 2017 Mar 9

Publication series

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

Other

Other	11th International Conference on Language and Automata Theory and Applications, LATA 2017
Country/Territory	Sweden
City	Umea
Period	17/3/6 → 17/3/9

Keywords

Context-free languages
Distributional learning
Finite context property
Finite kernel property
Grammatical inference and algorithmic learning

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-53733-7_5

Cite this

Kanazawa, M., & Yoshinaka, R. (2017). The strong, weak, and very weak finite context and kernel properties. In F. Drewes, C. Martín-Vide, & B. Truthe (Eds.), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings (pp. 77-88). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-53733-7_5

The strong, weak, and very weak finite context and kernel properties. / Kanazawa, Makoto; Yoshinaka, Ryo.

Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. ed. / Frank Drewes; Carlos Martín-Vide; Bianca Truthe. Springer Verlag, 2017. p. 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS).

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

Kanazawa, M & Yoshinaka, R 2017, The strong, weak, and very weak finite context and kernel properties. in F Drewes, C Martín-Vide & B Truthe (eds), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10168 LNCS, Springer Verlag, pp. 77-88, 11th International Conference on Language and Automata Theory and Applications, LATA 2017, Umea, Sweden, 17/3/6. https://doi.org/10.1007/978-3-319-53733-7_5

Kanazawa M, Yoshinaka R. The strong, weak, and very weak finite context and kernel properties. In Drewes F, Martín-Vide C, Truthe B, editors, Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Springer Verlag. 2017. p. 77-88. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-53733-7_5

Kanazawa, Makoto ; Yoshinaka, Ryo. / The strong, weak, and very weak finite context and kernel properties. Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. editor / Frank Drewes ; Carlos Martín-Vide ; Bianca Truthe. Springer Verlag, 2017. pp. 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f9cf81fee79d4bdfb0e3a60e8a4ed0f5,

title = "The strong, weak, and very weak finite context and kernel properties",

abstract = "We identify the properties of context-free grammars that exactly correspond to the behavior of the dual and primal versions of Clark and Yoshinaka{\textquoteright}s distributional learning algorithm and call them the very weak finite context/kernel property. We show that the very weak finite context property does not imply Yoshinaka{\textquoteright}s weak finite context property, which has been assumed to hold of the target language for the dual algorithm to succeed. We also show that the weak finite context property is genuinely weaker than Clark{\textquoteright}s strong finite context property, settling a question raised by Yoshinaka.",

keywords = "Context-free languages, Distributional learning, Finite context property, Finite kernel property, Grammatical inference and algorithmic learning",

author = "Makoto Kanazawa and Ryo Yoshinaka",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 11th International Conference on Language and Automata Theory and Applications, LATA 2017 ; Conference date: 06-03-2017 Through 09-03-2017",

year = "2017",

doi = "10.1007/978-3-319-53733-7_5",

language = "English",

isbn = "9783319537320",

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

publisher = "Springer Verlag",

pages = "77--88",

editor = "Frank Drewes and Carlos Mart{\'i}n-Vide and Bianca Truthe",

booktitle = "Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings",

}

TY - GEN

T1 - The strong, weak, and very weak finite context and kernel properties

AU - Kanazawa, Makoto

AU - Yoshinaka, Ryo

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We identify the properties of context-free grammars that exactly correspond to the behavior of the dual and primal versions of Clark and Yoshinaka’s distributional learning algorithm and call them the very weak finite context/kernel property. We show that the very weak finite context property does not imply Yoshinaka’s weak finite context property, which has been assumed to hold of the target language for the dual algorithm to succeed. We also show that the weak finite context property is genuinely weaker than Clark’s strong finite context property, settling a question raised by Yoshinaka.

AB - We identify the properties of context-free grammars that exactly correspond to the behavior of the dual and primal versions of Clark and Yoshinaka’s distributional learning algorithm and call them the very weak finite context/kernel property. We show that the very weak finite context property does not imply Yoshinaka’s weak finite context property, which has been assumed to hold of the target language for the dual algorithm to succeed. We also show that the weak finite context property is genuinely weaker than Clark’s strong finite context property, settling a question raised by Yoshinaka.

KW - Context-free languages

KW - Distributional learning

KW - Finite context property

KW - Finite kernel property

KW - Grammatical inference and algorithmic learning

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

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

U2 - 10.1007/978-3-319-53733-7_5

DO - 10.1007/978-3-319-53733-7_5

M3 - Conference contribution

AN - SCOPUS:85013388996

SN - 9783319537320

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

SP - 77

EP - 88

BT - Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings

A2 - Drewes, Frank

A2 - Martín-Vide, Carlos

A2 - Truthe, Bianca

PB - Springer Verlag

T2 - 11th International Conference on Language and Automata Theory and Applications, LATA 2017

Y2 - 6 March 2017 through 9 March 2017

ER -

The strong, weak, and very weak finite context and kernel properties

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this