Chomsky-Schützenberger parking for weighted multiple context-free languages

• Autorzy: Denkinger T.

Identyfikatory

DOI

10.15398/jlm.v5i1.159

• Języki publikacji: EN

Abstrakty

EN

We prove a Chomsky-Schützenberger representation theorem for multiple context-free languages weighted over complete commutative strong bimonoids. Using this representation we devise a parsing algorithm for a restricted form of those devices.

Słowa kluczowe

EN

Chomsky-Schützenberger; parsing; multiple context-free grammars; linear context-free rewriting systems

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2017
• Tom: Vol. 5, No. 1
• Strony: 3--55
• Opis fizyczny: Bibliogr. 41 poz., rys., tab.

Twórcy

autor

Denkinger T.

• Faculty of Computer Science, Technische Universität Dresden, Germany

Bibliografia

• [1] Alfred Vaino Aho and Jeffrey D. Ullman (1972), The Theory of Parsing, Translation, and Compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, ISBN 0-13-914556-7, http://dl.acm.org/citation.cfm?id=SERIES11430.578789.
• [2] Krasimir Angelov (2009), Incremental parsing with parallel multiple context-free grammars, in Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, pp. 69-76, Association for Computational Linguistics, http://dl.acm.org/citation.cfm?id=1609074.
• [3] François Barthélemy, Pierre Boullier, Philippe Deschamp, and Éric de la Clergerie (2001), Guided parsing of range concatenation languages, In Proceedings of the 39th Annual Meeting on Association for Computational Linguistics - ACL ’01, Association for Computational Linguistics (ACL), doi: 10.3115/1073012.1073019.
• [4] Pierre Boullier (1998), A generalization of mildly context-sensitive formalisms, in Proceedings of the Fourth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+ 4), pp. 17-20, Citeseer.
• [5] Sabine Brants, Stefanie Dipper, Peter Eisenberg, Silvia Hansen-Schirra, Esther König, Wolfgang Lezius, Christian Rohrer, George Smith, and Hans Uszkoreit (2004), TIGER: Linguistic Interpretation of a German Corpus, Research on Language and Computation, 2 (4): 597-620, doi: 10.1007/s11168-004-7431-3.
• [6] Håkan Burden and Peter Ljunglöf (2005), Parsing Linear Context-free Rewriting Systems, in Harry Bunt, Robert Malouf, and Alon Lavie, editors, Proceedings of the Ninth International Workshop on Parsing Technology, Parsing’05, pp. 11-17, Association for Computational Linguistics, Stroudsburg, PA, USA, http://dl.acm.org/citation.cfm?id=1654494.1654496.
• [7] Matthias Büchse, Daniel Geisler, Torsten Stüber, and Heiko Vogler (2010), n-Best Parsing Revisited, in Frank Drewes and Marco Kuhlmann, editors, Proceedings of the 2010 Workshop on Applications of Tree Automata In Natural Language Processing, pp. 46-54, Association for Computational Linguistics, http://www.aclweb.org/anthology/W10-2506.
• [8] Eugene Charniak, Michael Pozar, Theresa Vu, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, and Jeremy Moore (2006), Multilevel coarse-to-fine PCFG parsing, in Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics -, Association for Computational Linguistics (ACL), doi: 10.3115/1220835.1220857.
• [9] Noam Chomsky and Marcel Paul Schützenberger (1963), The algebraic theory of context-free languages, pp. 118-161, doi: 10.1016/S0049-237X(09)70104-1.
• [10] Tobias Denkinger (2015), A Chomsky-Schützenberger representation for weighted multiple context-free languages, in Proceedings of the 12th International Conference on Finite-State Methods and Natural Language Processing (FSMNLP 2015), http://aclweb.org/anthology/W15-4803.
• [11] Manfred Droste, Torsten Stüber, and Heiko Vogler (2010), Weighted finie automata over strong bimonoids, Information Sciences, 180 (1): 156-166, doi: 10.1016/j.ins.2009.09.003.
• [12] Manfred Droste and Heiko Vogler (2013), The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages, in Marie-Pierre Béal and Olivier Carton, editors, Developments in Language Theory, volume 7907 of Lecture Notes in Computer Science, pp. 203-214, Springer Berlin Heidelberg, ISBN 978-3-642-38770-8, doi: 10.1007/978-3-642-38771-5_19.
• [13] Jürgen Duske, Rainer Parchmann, and Johann Specht (1979), A Homomorphic Characterization of Indexed Languages, 15 (4): 187-195.
• [14] Séverine Fratani and El Makki Voundy (2015), Context-free characterization of Indexed Languages, abs/1409.6112, http://arxiv.org/abs/1409.6112.
• [15] Séverine Fratani and El Makki Voundy (2016), Homomorphic Characterizations of Indexed Languages, in Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, and Bianca Truthe, editors, Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2015), pp. 359-370, Springer Science + Business Media, doi: 10.1007/978-3-319-30000-9_28.
• [16] Luisa Herrmann and Heiko Vogler (2015), A Chomsky-Schützenberger Theorem for Weighted Automata with Storage, in Andreas Maletti, editor, Proceedings of the 6th International Conference on Algebraic Informatics (CAI 2015), volume 9270, pp. 90-102, Springer International Publishing, ISBN 978-3-319-23021-4, doi: 10.1007/978-3-319-23021-4_11.
• [17] Walter Hoffman and Richard Pavley (1959), A Method for the Solution of the Nth Best Path Problem, 6 (4): 506-514, doi: 10.1145/320998.321004.
• [18] John Edward Hopcroft and Jeffrey David Ullman (1969), Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc.
• [19] John Edward Hopcroft and Jeffrey David Ullman (1979), Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1st edition.
• [20] Liang Huang and David Chiang (2005), Better k-best Parsing, in Proceedings of the Ninth International Workshop on Parsing Technology, Parsing ’05, pp. 53-64, Association for Computational Linguistics, Stroudsburg, PA, USA, http://dl.acm.org/citation.cfm?id=1654494.1654500.
• [21] Mans Hulden (2011), Parsing CFGs and PCFGs with a Chomsky-Schützenberger Representation, in Zygmunt Vetulani, editor, Human Language Technology. Challenges for Computer Science and Linguistics, volume 6562 of Lecture Notes in Computer Science, pp. 151-160, Springer Berlin Heidelberg, ISBN 978-3-642-20094-6, doi: 10.1007/978-3-642-20095-3_14.
• [22] Laura Kallmeyer and Wolfgang Maier (2013), Data-driven parsing using probabilistic linear context-free rewriting systems, Computational Linguistics, 39 (1): 87-119, doi: 10.1162/COLI_a_00136.
• [23] Laura Kallmeyer and Wolfgang Maier (2015), LR Parsing for LCFRS, In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Association for Computational Linguistics (ACL), doi:10.3115/v1/n15-1134.
• [24] Makoto Kanazawa (2014), Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars, ISSN 1465-363X, doi: 10.1093/logcom/exu043.
• [25] Marco Kuhlmann and Giorgio Satta (2009), Treebank Grammar Techniques for Non-projective Dependency Parsing, in Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, EACL’09, pp. 478-486, Association for Computational Linguistics, Stroudsburg, PA, USA, http://dl.acm.org/citation.cfm?id=1609067.1609120.
• [26] Wolfgang Maier and Anders Søgaard (2008), Treebanks and mild context-sensitivity, in Proceedings of Formal Grammar, p. 61, http://web.stanford.edu/group/cslipublications/cslipublications/FG/2008/maier.pdf.
• [27] Jens Michaelis (2001a), Derivational Minimalism Is Mildly Context-Sensitive, in Michael Moortgat, editor, Logical Aspects of Computational Linguistics, volume 2014 of Lecture Notes in Computer Science, pp. 179-198, Springer Berlin Heidelberg, ISBN 978-3-540-42251-8, doi: 10.1007/3-540-45738-0_11.
• [28] Jens Michaelis (2001b), Transforming Linear Context-Free Rewriting Systems into Minimalist Grammars, in Philippe Groote, Glyn Morrill, and Christian Retoré, editors, Logical Aspects of Computational Linguistics, volume 2099 of Lecture Notes in Computer Science, pp. 228-244, Springer Berlin Heidelberg, ISBN 978-3-540-42273-0, doi: 10.1007/3-540-48199-0_14.
• [29] Mehryar Mohri (2000), Minimization algorithms for sequential transducers, 234 (1-2): 177-201, ISSN 0304-3975, doi: 10.1016/s0304-3975(98)00115-7.
• [30] Arto Salomaa (1973), Formal languages, Academic Press, ISBN 978-0126157505.
• [31] Arto Salomaa and Matti Soittola (1978), Automata-Theoretic Aspects of Formal Power Series, Springer New York, ISBN 978-1-4612-6266-4, doi: 10.1007/978-1-4612-6264-0.
• [32] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami (1991), On multiple context-free grammars, 88 (2): 191-229, ISSN 0304-3975, doi: 10.1016/0304-3975(91)90374-B.
• [33] Hiroyuki Seki, Ryuichi Nakanishi, Yuichi Kaji, Sachiko Ando, and Tadao Kasami (1993), Parallel Multiple Context-free Grammars, Finite-state Translation Systems, and Polynomial-time Recognizable Subclasses of Lexical-functional Grammars, in Proceedings of the 31st Annual Meeting on Association for Computational Linguistics, ACL ’93, pp. 130-139, Association for Computational Linguistics, Stroudsburg, PA, USA, doi: 10.3115/981574.981592.
• [34] Andreas van Cranenburgh (2012), Efficient Parsing with Linear Context-free Rewriting Systems, in Walter Daelemans, editor, Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, EACL’12, pp. 460-470, Association for Computational Linguistics, Stroudsburg, PA, USA, ISBN 978-1-937284-19-0, http://dl.acm.org/citation.cfm?id=2380816.2380873.
• [35] Krishnamurti Vijay-Shanker (1988), A study of tree adjoining grammars, Ph.D. thesis, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.401.1695&rep=rep1&type=pdf.
• [36] Krishnamurti Vijay-Shanker, David Jeremy Weir, and Aravind K. Joshi (1986), Tree adjoining and head wrapping, in Proceedings of the 11th Conference on Computational Linguistics, pp. 202-207, Association for Computational Linguistics, doi: 10.3115/991365.991425.
• [37] Krishnamurti Vijay-Shanker, David Jeremy Weir, and Aravind K. Joshi (1987), Characterizing Structural Descriptions Produced by Various Grammatical Formalisms, in Proceedings of the 25th Annual Meeting on Association for Computational Linguistics, ACL’87, pp. 104-111, Association for Computational Linguistics, Stroudsburg, PA, USA, doi: 10.3115/981175.981190.
• [38] Éric Villemonte de la Clergerie (2002), Parsing Mildly Context-Sensitive Languages with Thread Automata, in Proceedings of the 19th International Conference on Computational Linguistics (COLING’02), volume 1, pp. 1-7, Association for Computational Linguistics, Stroudsburg, PA, USA, doi: 10.3115/1072228.1072256.
• [39] David Jeremy Weir (1988), Characterizing mildly context-sensitive gram mar formalisms, Ph.D. thesis, http://repository.upenn.edu/dissertations/AAI8908403.
• [40] David Jeremy Weir and Aravind K. Joshi (1988), Combinatory categorial grammars: Generative power and relationship to linear context-free rewriting systems, in Proceedings of the 26th annual meeting on Association for Computational Linguistics, pp. 278-285, Association for Computational Linguistics, doi: 10.3115/982023.982057.
• [41] Ryo Yoshinaka, Yuichi Kaji, and Hiroyuki Seki (2010), Chomsky-Schützenberger-type characterization of multiple context-free languages, in Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, pp. 596-607, Springer, ISBN 978-3-642-13088-5, doi: 10.1007/978-3-642-13089-2_50.