How to embed noncrossing trees in Universal Dependencies treebanks in a low-complexity regular language

• Autorzy: Yli-Jyrä Anssi Mikael

Identyfikatory

DOI

10.15398/jlm.v7i2.213

• Języki publikacji: EN

Abstrakty

EN

A recently proposed balanced-bracket encoding (Yli-Jyrä and Gómez-Rodríguez 2017) has given us a way to embed all noncrossing dependency graphs into the string space and to formulate their exact arcfactored inference problem (Kuhlmann and Johnsson 2015) as the best string problem in a dynamically constructed and weighted unambiguous context-free grammar. The current work improves the encoding and makes it shallower by omitting redundant brackets from it. The streamlined encoding gives rise to a bounded-depth subset approximation that is represented by a small finite-state automaton. When bounded to 7 levels of balanced brackets, the automaton has 762 states and represents a strict superset of more than 99.9999% of the noncrossing trees available in Universal Dependencies 2.4 (Nivre et al. 2019). In addition, it strictly contains all 15-vertex noncrossing digraphs. When bounded to 4 levels and 90 states, the automaton still captures 99.2% of all noncrossing trees in the reference dataset. The approach is flexible and extensible towards unrestricted graphs, and it suggests tight finite-state bounds for dependency parsing, and for the main existing parsing methods.

Słowa kluczowe

EN

bounded stack; coding morphisms; context-free grammars; dependencies; finite-state; parsing; state complexity; treebanks

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2019
• Tom: Vol. 7, No. 2
• Strony: 177--232
• Opis fizyczny: Bibliogr. 55 poz., rys., tab., wykr.

Twórcy

autor

Yli-Jyrä Anssi Mikael

• University of Helsinki, Finland

Bibliografia

• [1] Bernd Bohnet, Ryan McDonald, Emily Pitler, and Ji Ma (2016), Generalized transition-based dependency parsing via control parameters, in Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL 2016), pp. 150-160, Association for Computational Linguistics, http://dx.doi.org/10.18653/v1/P16-1015.
• [2] Mikołaj Bojańczyk and Michał Pilipczuk (2016), Definability equals recognizability for graphs of bounded treewidth, in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’16, pp. 407-416, ACM, New York, NY, USA, ISBN 978-1-4503-4391-6, http://dx.doi.org/10.1145/2933575.2934508.
• [3] Noam Chomsky (1963), Formal properties of grammars, in R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of mathematical psychology, volume 2, pp. 323-418, John Wiley and Sons, New York.
• [4] Bruno Courcelle (1990), The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, 85 (1): 12-75, ISSN 0890-5401, doi: https://doi.org/10.1016/0890-5401(90)90043-H, http://www.sciencedirect.com/science/article/pii/089054019090043H.
• [5] Michael A. Covington (2001), A fundamental algorithm for dependency parsing, in John A. Miller and Jeffrey W. Smith, editors, Proceedings of the 39th Annual ACM Southeast Conference, pp. 95-102, Association for Computing Machinery, http://www.covingtoninnovations.com/mc/dgpacm.pdf.
• [6] Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith (2015), Transition-based dependency parsing with Stack Long Short-Term Memory, in Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 334-343, Association for Computational Linguistics, Beijing, China, http://dx.doi.org/10.3115/v1/P15-1033.
• [7] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith (2016), Recurrent neural network grammars, in Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 199-209, Association for Computational Linguistics, http://www.aclweb.org/anthology/N16-1024.
• [8] Jason Eisner and Giorgio Satta (1999), Efficient parsing for bilexical context-free grammars and Head Automaton Grammars, in Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL 1999), pp. 457-464, Association for Computational Linguistics, https://doi.org/10.3115/1034678.1034748.
• [9] Edward Gibson (1998), Linguistic complexity: locality of syntactic dependencies, Cognition, 68 (1): 1-76, http://doi.org/10.1016/S0010-0277(98)00034-1.
• [10] Filip Ginter, Sampo Pyysalo, Jorma Boberg, and Tapio Salakoski (2006), Regular approximation of Link grammar, in Proceedings of the 5th International Conference on Advances in Natural Language Processing, FinTAL’06, pp. 564-575, Springer-Verlag, Berlin, Heidelberg, ISBN 3-540-37334-9, 978-3-540-37334-6, http://dx.doi.org/10.1007/11816508_56.
• [11] Charles F. Goldfarb (1999), Future directions in SGML/XML, in Wiebke Möhr and Ingrid Schmidt, editors, SGML und XML: Anwendungen und Perspektiven, pp. 3-25, Springer, Berlin, Germany, https://doi.org/10.1007/978-3-642-46881-0_1.
• [12] Carlos Gómez-Rodríguez and Joakim Nivre (2010), A transition-based parser for 2-planar dependency structures, in Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL 2010), pp. 1492-1501, Association for Computational Linguistics, http://dl.acm.org/citation.cfm?id=1858681.1858832.
• [13] Sheila Greibach (1973), The hardest context-free language, SIAM Journal on Computing, 2 (4): 304-310, http://dx.doi.org/10.1137/0202025.
• [14] Jiří Havelka (2007), Beyond projectivity: multilingual evaluation of constraints and measures on non-projective structures, in Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (ACL 2007), pp. 608-615, Association for Computational Linguistics, http://www.aclweb.org/anthology/P07-1077.
• [15] Jeffrey Heinz and James Rogers (2013), Learning subregular classes of languages with factored deterministic automata, in Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), pp. 64-71, Association for Computational Linguistics, Sofia, Bulgaria, https://www.aclweb.org/anthology/W13-3007.
• [16] Mans Hulden and Miikka Silfverberg (2014), Finite-state subset approximation of phrase structure, in Proceedings of the International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, USA, https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_NLP_Hulden_Silfverberg.pdf.
• [17] Eliyahu Kiperwasser and Yoav Goldberg (2016), Simple and accurate dependency parsing using bidirectional LSTM feature representations, Transactions of the Association for Computational Linguistics, 4: 313-327, http://dx.doi.org/10.1162/tacl_a_00101.
• [18] András Kornai and Zsolt Tuza (1992), Narrowness, path-width, and their application in natural language processing, Discrete Applied Mathematics, 36 (1): 87-92, https://doi.org/10.1016/0166-218X(92)90208-R.
• [19] Kimmo Koskenniemi (1990), Finite-state parsing and disambiguation, in Hans Karlgren, editor, 13th International Conference on Computational Linguistics, (COLING 1990), pp. 229-232, http://aclweb.org/anthology/C90-2040.
• [20] Steven Krauwer and Louis des Tombe (1981), Transducers and grammars as theories of language, Theoretical Linguistics, 8 (1-3): 173-202, https://doi.org/10.1515/thli.1981.8.1-3.173.
• [21] Marco Kuhlmann (2015), Tabulation of noncrossing acyclic digraphs, arXiv:1504.04993, https://arxiv.org/abs/1504.04993.
• [22] Marco Kuhlmann and Peter Johnsson (2015), Parsing to noncrossing dependency graphs, Transactions of the Association for Computational Linguistics, 3: 559-570, http://aclweb.org/anthology/Q/Q15/Q15-1040.pdf.
• [23] Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, Graham Neubig, and Noah A. Smith (2017), What do recurrent neural network grammars learn about syntax?, in Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL 2017), pp. 1249-1258, Association for Computational Linguistics, http://aclweb.org/anthology/E17-1117.
• [24] D. Terence Langendoen (1975), Finite-state parsing of phrase-structure languages and the status of readjustment rules in grammar, Linguistic Inquiry, 6 (4): 533-554, http://www.jstor.org/stable/4177899.
• [25] D. Terence Langendoen and Yedidyah Langsam (1984), The representation Of constituent structures for finite-state parsing, in Yorick Wilks, editor, 10th International Conference on Computational Linguistics and 22nd Annual Meeting of the Association for Computational Linguistics, Proceedings of COLING’84, July 2-6, 1984, Stanford University, California, USA., pp. 24-27, ACL, http://aclweb.org/anthology/P84-1007.
• [26] Jindřich Libovický (2016), Neural scoring function for MST parser, in Nicoletta Calzolari, Khalid Choukri, Thierry Declerck, Sara Goggi, Marko Grobelnik, Bente Maegaard, Joseph Mariani, Helene Mazo, Asuncion Moreno, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), European Language Resources Association (ELRA), http://www.lrec-conf.org/proceedings/lrec2016/summaries/649.html.
• [27] Xuezhe Ma and Eduard H. Hovy (2017), Neural probabilistic model for non-projective MST parsing, in Proceedings of the The 8th International Joint Conference on Natural Language Processing (IJCNLP), pp. 59-69, Asian Federation of Natural Language Processing, http://www.aclweb.org/anthology/I17-1007.
• [28] Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič (2005), Non-projective dependency parsing using spanning tree algorithms, in Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pp. 523-530, Association for Computational Linguistics, http://www.aclweb.org/anthology/H/H05/H05-1066.pdf.
• [29] George A. Miller (1956), The magical number seven, plus or minus two: some limits on our capacity for processing information, Psychological Review, 63 (2): 81-97, http://dx.doi.org/10.1037/h0043158.
• [30] Mehryar Mohri (1997), Finite-state transducers in language and speech processing, Computational Linguistics, 23 (2): 1-42, http://www.aclweb.org/anthology/J97-2003.
• [31] Mark-Jan Nederhof (2000), Practical experiments with regular approximation of context-free languages, Computational Linguistics, 26 (1): 17-44, http://dx.doi.org/10.1162/089120100561610.
• [32] Joakim Nivre (2008), Algorithms for deterministic incremental dependency parsing, Computational Linguistics, 34 (4): 513-553, https://doi.org/10.1162/coli.07-056-R1-07-027.
• [33] Joakim Nivre (2009), Non-projective dependency parsing in expected linear time, in Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, pp. 351-359, Association for Computational Linguistics, http://dl.acm.org/citation.cfm?id=1687878.1687929.
• [34] Joakim Nivre, Mitchell Abrams, Željko Agić, Lars Ahrenberg, Gabrielė Aleksandravičiūtė, Lene Antonsen, Katya Aplonova, Maria Jesus Aranzabe, Gashaw Arutie, Masayuki Asahara, Luma Ateyah, Mohammed Attia, Aitziber Atutxa, Liesbeth Augustinus, Elena Badmaeva, Miguel Ballesteros, Esha Banerjee, Sebastian Bank, Verginica Barbu Mititelu, Victoria Basmov, John Bauer, Sandra Bellato, Kepa Bengoetxea, Yevgeni Berzak, Irshad Ahmad Bhat, Riyaz Ahmad Bhat, Erica Biagetti, Eckhard Bick, Agnė Bielinskienė, Rogier Blokland, Victoria Bobicev, Loïc Boizou, Emanuel Borges Völker, Carl Börstell, Cristina Bosco, Gosse Bouma, Sam Bowman, Adriane Boyd, Kristina Brokaitė, Aljoscha Burchardt, Marie Candito, Bernard Caron, Gauthier Caron, Gülşen Cebiroğlu Eryiğit, Flavio Massimiliano Cecchini, Giuseppe G. A. Celano, Slavomír Čéplö, Savas Cetin, Fabricio Chalub, Jinho Choi, Yongseok Cho, Jayeol Chun, Silvie Cinková, Aurélie Collomb, Çağrı Çöltekin, Miriam Connor, Marine Courtin, Elizabeth Davidson, Marie-Catherine de Marneffe, Valeria de Paiva, Arantza Diaz de Ilarraza, Carly Dickerson, Bamba Dione, Peter Dirix, Kaja Dobrovoljc, Timothy Dozat, Kira Droganova, Puneet Dwivedi, Hanne Eckhoff, Marhaba Eli, Ali Elkahky, Binyam Ephrem, Tomaž Erjavec, Aline Etienne, Richárd Farkas, Hector Fernandez Alcalde, Jennifer Foster, Cláudia Freitas, Kazunori Fujita, Katarína Gajdošová, Daniel Galbraith, Marcos Garcia, Moa Gärdenfors, Sebastian Garza, Kim Gerdes, Filip Ginter, Iakes Goenaga, Koldo Gojenola, Memduh Gökırmak, Yoav Goldberg, Xavier Gómez Guinovart, Berta González Saavedra, Matias Grioni, Normunds Grūzītis, Bruno Guillaume, Céline Guillot-Barbance, Nizar Habash, Jan Hajič, Jan Hajič jr., Linh Hà Mỹ, Na-Rae Han, Kim Harris, Dag Haug, Johannes Heinecke, Felix Hennig, Barbora Hladká, Jaroslava Hlaváčová, Florinel Hociung, Petter Hohle, Jena Hwang, Takumi Ikeda, Radu Ion, Elena Irimia, Ọlájídé Ishola, Tomáš Jelínek, Anders Johannsen, Fredrik Jørgensen, Hüner Kaşıkara, Andre Kaasen, Sylvain Kahane, Hiroshi Kanayama, Jenna Kanerva, Boris Katz, Tolga Kayadelen, Jessica Kenney, Václava Kettnerová, Jesse Kirchner, Arne Köhn, Kamil Kopacewicz, Natalia Kotsyba, Jolanta Kovalevskaitė, Simon Krek, Sookyoung Kwak, Veronika Laippala, Lorenzo Lambertino, Lucia Lam, Tatiana Lando, Septina Dian Larasati, Alexei Lavrentiev, John Lee, Phương Lê Hồng, Alessandro Lenci, Saran Lertpradit, Herman Leung, Cheuk Ying Li, Josie Li, Keying Li, KyungTae Lim, Yuan Li, Nikola Ljubešić, Olga Loginova, Olga Lyashevskaya, Teresa Lynn, Vivien Macketanz, Aibek Makazhanov, Michael Mandl, Christopher Manning, Ruli Manurung, Cătălina Mărănduc, David Mareček, Katrin Marheinecke, Héctor Martínez Alonso, André Martins, Jan Mašek, Yuji Matsumoto, Ryan McDonald, Sarah McGuinness, Gustavo Mendonça, Niko Miekka, Margarita Misirpashayeva, Anna Missilä, Cătălin Mititelu, Yusuke Miyao, Simonetta Montemagni, Amir More, Laura Moreno Romero, Keiko Sophie Mori, Tomohiko Morioka, Shinsuke Mori, Shigeki Moro, Bjartur Mortensen, Bohdan Moskalevskyi, Kadri Muischnek, Yugo Murawaki, Kaili Müürisep, Pinkey Nainwani, Juan Ignacio Navarro Horñiacek, Anna Nedoluzhko, Gunta Nešpore-Bērzkalne, Lương Nguyễn Thị, Huyền Nguyễn Thị Minh, Yoshihiro Nikaido, Vitaly Nikolaev, Rattima Nitisaroj, Hanna Nurmi, Stina Ojala, Adédayọ̀ Olúòkun, Mai Omura, Petya Osenova, Robert Östling, Lilja Øvrelid, Niko Partanen, Elena Pascual, Marco Passarotti, Agnieszka Patejuk, Guilherme Paulino-Passos, Angelika Peljak-Łapińska, Siyao Peng, Cenel-Augusto Perez, Guy Perrier, Daria Petrova, Slav Petrov, Jussi Piitulainen, Tommi A Pirinen, Emily Pitler, Barbara Plank, Thierry Poibeau, Martin Popel, Lauma Pretkalniņa, Sophie Prévost, Prokopis Prokopidis, Adam Przepiórkowski, Tiina Puolakainen, Sampo Pyysalo, Andriela Rääbis, Alexandre Rademaker, Loganathan Ramasamy, Taraka Rama, Carlos Ramisch, Vinit Ravishankar, Livy Real, Siva Reddy, Georg Rehm, Michael Rießler, Erika Rimkutė, Larissa Rinaldi, Laura Rituma, Luisa Rocha, Mykhailo Romanenko, Rudolf Rosa, Davide Rovati, Valentin Roșca, Olga Rudina, Jack Rueter, Shoval Sadde, Benoît Sagot, Shadi Saleh, Alessio Salomoni, Tanja Samardžić, Stephanie Samson, Manuela Sanguinetti, Dage Särg, Baiba Saulīte, Yanin Sawanakunanon, Nathan Schneider, Sebastian Schuster, Djamé Seddah, Wolfgang Seeker, Mojgan Seraji, Mo Shen, Atsuko Shimada, Hiroyuki Shirasu, Muh Shohibussirri, Dmitry Sichinava, Natalia Silveira, Maria Simi, Radu Simionescu, Katalin Simkó, Mária Šimková, Kiril Simov, Aaron Smith, Isabela Soares-Bastos, Carolyn Spadine, Antonio Stella, Milan Straka, Jana Strnadová, Alane Suhr, Umut Sulubacak, Shingo Suzuki, Zsolt Szántó, Dima Taji, Yuta Takahashi, Fabio Tamburini, Takaaki Tanaka, Isabelle Tellier, Guillaume Thomas, Liisi Torga, Trond Trosterud, Anna Trukhina, Reut Tsarfaty, Francis Tyers, Sumire Uematsu, Zdeňka Urešová, Larraitz Uria, Hans Uszkoreit, Sowmya Vajjala, Daniel van Niekerk, Gertjan van Noord, Viktor Varga, Eric Villemonte de la Clergerie, Veronika Vincze, Lars Wallin, Abigail Walsh, Jing Xian Wang, Jonathan North Washington, Maximilan Wendt, Seyi Williams, Mats Wirén, Christian Wittern, Tsegay Woldemariam, Tak-sum Wong, Alina Wróblewska, Mary Yako, Naoki Yamazaki, Chunxiao Yan, Koichi Yasuoka, Marat M. Yavrumyan, Zhuoran Yu, Zdeněk Žabokrtský, Amir Zeldes, Daniel Zeman, Manying Zhang, and Hanzhi Zhu (2019), Universal Dependencies 2.4, http://hdl.handle.net/11234/1-2988, LINDAT/CLARIN digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University.
• [35] Kemal Oflazer (2003), Dependency parsing with an extended finite-state approach, Computational Linguistics, 29 (4): 515-544, http://dx.doi.org/10.1162/089120103322753338.
• [36] Pushpendre Rastogi, Ryan Cotterell, and Jason Eisner (2016), Weighting finite-state transductions with neural context, in Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 623-633, Association for Computational Linguistics, http://dx.doi.org/10.18653/v1/N16-1076.
• [37] Brian Roark and Kristy Hollingshead (2008), Classifying chart cells for quadratic complexity context-free inference, in Proceedings of the 22nd International Conference on Computational Linguistics (COLING 2008), volume 1, pp. 745-752, Association for Computational Linguistics, http://dl.acm.org/citation.cfm?id=1599081.1599175.
• [38] Arto Salomaa (1973), Formal languages, Academic Press, New York, NY.
• [39] Michalina Strzyz, David Vilares, and Carlos Gómez-Rodríguez (2019), Viable dependency parsing as sequence labeling, in Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pp. 717-723, Association for Computational Linguistics, ISBN 978-1-950737-13-0, https://aclweb.org/anthology/papers/N/N19/N19-1077/.
• [40] Warren Teitelman (1978), INTERLISP reference manual, Xerox Palo Alto Research Center (PARC), Palo Alto, CA.
• [41] Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey E. Hinton (2015), Grammar as a foreign language, in Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2773-2781, http://papers.nips.cc/paper/5635-grammar-as-a-foreign-language.
• [42] Anssi Yli-Jyrä (2003a), Describing syntax with star-free regular expressions, in 10th Conference of the European Chapter of the Association for Computational Linguistics, Association for Computational Linguistics, Budapest, Hungary, https://www.aclweb.org/anthology/E03-1031.
• [43] Anssi Yli-Jyrä (2003b), Multiplanarity – a model for dependency structures in treebanks, in Joakim Nivre and Erhard Hinrichs, editors, TLT 2003. Proceedings of the Second Workshop on Treebanks and Linguistic Theories, volume 9 of Mathematical Modelling in Physics, Engineering and Cognitive Sciences, pp. 189-200, Växjö University Press, Växjö, Sweden, http://hdl.handle.net/10138/33872.
• [44] Anssi Yli-Jyrä (2003c), Regular approximations through labeled bracketing, in Gerald Penn, editor, Proceedings of FGVienna: the 8th Conference on Formal Grammar, pp. 153-166, CSLI Publications, Stanford, CA, http://cslipublications.stanford.edu/FG/2003/ylijyra.pdf.
• [45] Anssi Yli-Jyrä (2004), Axiomatization of restricted non-projective dependency trees through finite-state constraints that analyse crossing bracketings, in Geert-Jan M. Kruijff and Denys Duchier, editors, Recent Advances in Dependency Grammar (COLING 2004 workshop), pp. 25-32, Association for Computational Linguistics, Geneva, Switzerland, https://www.aclweb.org/anthology/W/W04/W04-1504.pdf.
• [46] Anssi Yli-Jyrä (2005a), Approximating dependency grammars through intersection of star-free regular languages, International Journal of Foundations of Computer Science, 16 (3): 565-579, http://dx.doi.org/10.1142/S0129054105003169.
• [47] Anssi Yli-Jyrä (2005b), Contributions to the theory of finite-state based grammars, Ph.D. thesis, University of Helsinki, Faculty of Arts, Department of General Linguistics, http://urn.fi/URN:ISBN:952-10-2510-7.
• [48] Anssi Yli-Jyrä (2005c), Linguistic grammars with very low complexity, in Antti Arppe et al., editor, Inquiries into Words, Constraints and Contexts: Festschrift in the Honour of Kimmo Koskenniemi on his 60th Birthday, CSLI Studies in Computational Linguistics ONLINE, pp. 172-183, CSLI Publications, Stanford, CA, https://web.stanford.edu/group/cslipublications/cslipublications/koskenniemi-festschrift/17-yli-jyra.pdf.
• [49] Anssi Yli-Jyrä (2008), Applications of diamonded double negation, in T. Hanneforth and K-M. Würzner, editors, Finite-State Methods and Natural Language Processing, 6th International Workshop, FSMNL-2007, Potsdam, Germany, September 14-16, Revised Papers, pp. 6-30, Potsdam University Press, Potsdam, https://publishup.uni-potsdam.de/opus4-ubp/frontdoor/index/index/year/2008/docId/2519.
• [50] Anssi Yli-Jyrä (2012), On dependency analysis via contractions and weighted FSTs, in Diana Santos, Krister Lindén, and Wanjiku Ng’ang’a, editors, Shall we play the Festschrift game? Essays on the occasion of Lauri Carlson’s 60th birthday, pp. 133-158, Springer, Berlin, Germany, http://dx.doi.org/10.1007/978-3-642-30773-7_10.
• [51] Anssi Yli-Jyrä (2019), Transition-based coding and formal language theory for ordered digraphs, Paper accepted to FSMNLP 2019, The 14th International Conference on Finite-State Methods and Natural Language Processing, September 23-25, Dresden, Germany.
• [52] Anssi Yli-Jyrä and Carlos Gómez-Rodríguez (2017), Generic axiomatization of families of noncrossing graphs in dependency parsing, in Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL 2017), pp. 1745-1755, Association for Computational Linguistics, http://aclweb.org/anthology/P17-1160.
• [53] Anssi Yli-Jyrä and Matti Nykänen (2014), A hierarchy of mildly context-sensitive dependency grammars, in Paola Monachesi, editor, Proceedings of the Nancy Conference, Formal Grammar 2004, pp. 155-170, CSLI Publications, Stanford, CA, http://cslipublications.stanford.edu/FG/2004/fg-2004-paper11.pdf.
• [54] Hao Zhang and Ryan T. McDonald (2014), Enforcing structural diversity in cube-pruned dependency parsing, in Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (ACL 2014), pp. 656-661, Association for Computational Linguistics, http://aclweb.org/anthology/P/P14/P14-2107.pdf.
• [55] Xiaoqing Zheng (2017), Incremental graph-based neural dependency parsing, in Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1655-1665, Association for Computational Linguistics, http://dx.doi.org/10.18653/v1/D17-1173.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).