nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

The Strong, Weak, and Very Weak Finite Context and Kernel Properties

verfasst von : Makoto Kanazawa, Ryo Yoshinaka

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Efficient Learning of Tier-Based Strictly k-Local Languages

Nächstes Kapitel -Memory Automata over the Alphabet

Clark and Yoshinaka have used the term “distributional learning” more loosely in connection with a number of different learning paradims (see [5] for a survey).

The present formulations follow [4].

It is clear from Ogden’s proof that the lemma is really about one particular derivation tree of a context-free grammar. If p is the constant of Ogden’s lemma for G, we obtain the required decomposition of the derivation tree by first marking the initial \(a^p\), then the \(b^p\) preceding \(\#\), and then the \(a^p\) immediately following \(\#\).

Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, vol. I. Prentice-Hall, Englewood Cliffs (1972)MATH

Clark, A.: Learning context free grammars with the syntactic concept lattice. In: Sempere, J.M., García, P. (eds.) ICGI 2010. LNCS (LNAI), vol. 6339, pp. 38–51. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15488-1_5 CrossRef

Clark, A.: The syntactic concept lattice: another algebraic theory of the context-free languages? J. Log. Comput. 25(5), 1203–1229 (2015). First published online: July 30, 2013MathSciNetCrossRefMATH

Clark, A., Kanazawa, M., Kobele, G.M., Yoshinaka, R.: Distributional learning of some nonlinear tree grammars. Fundamenta Informaticae 146(4), 339–377 (2016)MathSciNetCrossRef

Clark, A., Yoshinaka, R.: Distributional learning of context-free and multiple context-free grammars. In: Heinz, J., Sempere, J.M. (eds.) Topics in Grammatical Inference, pp. 143–172. Springer, Berlin (2016)CrossRef

Leiß, H.: Learning context free grammars with the finite context property: a correction of A. Clark’s algorithm. In: Morrill, G., Muskens, R., Osswald, R., Richter, F. (eds.) Formal Grammar 2014. LNCS, vol. 8612, pp. 121–137. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44121-3_8

Ogden, W.: A helpful result for proving inherent ambiguity. Math. Syst. Theory 2(3), 191–194 (1968)MathSciNetCrossRefMATH

Yoshinaka, R.: Towards dual approaches for learning context-free grammars based on syntactic concept lattices. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 429–440. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22321-1_37 CrossRef

Yoshinaka, R.: General perspectives on distributionally learnable classes. In: Kuhlmann, M., Kanazawa, M., Kobele, G.M. (eds.) Proceedings of the 14th Meeting on the Mathematics of Language, pp. 87–98. Association for Computational Linguistics, Stroudsburg (2015)

10.

Yoshinaka, R.: Learning conjunctive grammars and contextual binary feature grammars. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 623–635. Springer, Heidelberg (2015). doi:10.1007/978-3-319-15579-1_49

11.

Yoshinaka, R., Kanazawa, M.: Distributional learning of abstract categorial grammars. In: Pogodalla, S., Prost, J.-P. (eds.) LACL 2011. LNCS (LNAI), vol. 6736, pp. 251–266. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22221-4_17 CrossRef

Titel: The Strong, Weak, and Very Weak Finite Context and Kernel Properties
verfasst von: Makoto Kanazawa
Ryo Yoshinaka
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-319-53732-0

Electronic ISBN: 978-3-319-53733-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-53733-7_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"