acl acl2012 acl2012-185 acl2012-185-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andreas Maletti ; Joost Engelfriet
Abstract: Recently, it was shown (KUHLMANN, SATTA: Tree-adjoining grammars are not closed under strong lexicalization. Comput. Linguist., 2012) that finitely ambiguous tree adjoining grammars cannot be transformed into a normal form (preserving the generated tree language), in which each production contains a lexical symbol. A more powerful model, the simple context-free tree grammar, admits such a normal form. It can be effectively constructed and the maximal rank of the nonterminals only increases by 1. Thus, simple context-free tree grammars strongly lexicalize tree adjoining grammars and themselves.
Franz Baader and Tobias Nipkow. 1998. Term Rewriting and All That. Cambridge University Press. Yehoshua Bar-Hillel, Haim Gaifman, and Eli Shamir. 1960. On categorial and phrase-structure grammars. Bulletin of the Research Council of Israel, 9F(1): 1–16. Norbert Blum and Robert Koch. 1999. Greibach normal form transformation revisited. Inform. and Comput., 150(1): 112–1 18. John Chen. 2001. Towards Efficient Statistical Parsing using Lexicalized Grammatical Information. Ph.D. thesis, University of Delaware, Newark, USA. Noam Chomsky. 1963. Formal properties of grammar. In R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of Mathematical Psychology, volume 2, pages 323–418. John Wiley and Sons, Inc. Joost Engelfriet, Grzegorz Rozenberg, and Giora Slutzki. 1980. Tree transducers, L systems, and two-way machines. J. Comput. System Sci., 20(2): 150–202. Michael J. Fischer. 1968. Grammars with macro-like productions. In Proc. 9th Ann. Symp. Switching and Automata Theory, pages 13 1–142. IEEE Computer Society. Akio Fujiyoshi. 2005. Epsilon-free grammars and lexicalized grammars that generate the class of the mildly context-sensitive languages. In Proc. 7th Int. Workshop Tree Adjoining Grammar and Related Formalisms, pages 16–23. Akio Fujiyoshi and Takumi Kasai. 2000. Spinal-formed context-free tree grammars. Theory Comput. Syst., 33(1):59–83. Ferenc G ´ecseg and Magnus Steinby. 1984. Tree Automata. Akad e´miai Kiad o´, Budapest. Ferenc G ´ecseg and Magnus Steinby. 1997. Tree languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer. Jonathan Goldstine, Hing Leung, and Detlef Wotschke. 1992. On the relation between ambiguity and nondeterminism in finite automata. Inform. and Comput., 100(2):261–270. Carlos G ´omez-Rodr ı´guez, Marco Kuhlmann, and Giorgio Satta. 2010. Efficient parsing of well-nested linear context-free rewriting systems. In Proc. Ann. Conf. North American Chapter of the ACL, pages 276–284. Association for Computational Linguistics. Hendrik Jan Hoogeboom and Paulien ten Pas. 1997. Monadic second-order definable text languages. Theory Comput. Syst., 30(4):335–354. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001 . Introduction to automata theory, languages, and computation. Addison-Wesley series in computer science. Addison Wesley, 2nd edition. 514 Aravind K. Joshi, S. Rao Kosaraju, and H. Yamada. 1969. String adjunct grammars. In Proc. 10th Ann. Symp. Switching and Automata Theory, pages 245– 262. IEEE Computer Society. Aravind K. Joshi, Leon S. Levy, and Masako Takahashi. 1975. Tree adjunct grammars. J. Comput. System Sci., 10(1): 136–163. Aravind K. Joshi and Yves Schabes. 1992. Treeadjoining grammars and lexicalized grammars. In Maurice Nivat and Andreas Podelski, editors, Tree Automata and Languages. North-Holland. Aravind K. Joshi and Yves Schabes. 1997. Treeadjoining grammars. In Grzegorz Rozenberg and Arto Salomaa, editors, Beyond Words, volume 3 of Handbook of Formal Languages, pages 69–123. Springer. Makoto Kanazawa. 2009. The convergence of wellnested mildly context-sensitive grammar formalisms. Invited talk at the 14th Int. Conf. Formal Grammar. slides available at: re search .nii ac . jp/ . ˜ k an a z awa . Makoto Kanazawa and Ryo Yoshinaka. 2005. Lexicalization of second-order ACGs. Technical Report NII2005-012E, National Institute of Informatics, Tokyo, Japan. Stephan Kepser and James Rogers. 2011. The equivalence of tree adjoining grammars and monadic linear context-free tree grammars. J. Log. Lang. Inf., 20(3):361–384. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. 2004. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoret. Comput. Sci., 327(3):349–373. Marco Kuhlmann. 2010. Dependency Structures and Lexicalized Grammars: An Algebraic Approach, volume 6270 of LNAI. Springer. Marco Kuhlmann and Mathias Mohl. 2006. Extended cross-serial dependencies in tree adjoining grammars. In Proc. 8th Int. Workshop Tree Adjoining Grammars and Related Formalisms, pages 121–126. ACL. Marco Kuhlmann and Giorgio Satta. 2012. Treeadjoining grammars are not closed under strong lexicalization. Comput. Linguist. available at: dx .doi . org/ 10 . 1 2 /COLI_a_0 0 0 9 0 . 16 Uwe M ¨onnich. 1997. Adjunction as substitution: An algebraic formulation of regular, context-free and tree adjoining languages. In Proc. 3rd Int. Conf. Formal Grammar, pages 169–178. Universit e´ de Provence, France. available at: arxiv .org/ abs / cmp-lg/ 970701 2v1. Uwe M ¨onnich. 2010. Well-nested tree languages and attributed tree transducers. In Proc. 10th Int. Conf. Tree Adjoining Grammars and Related Formalisms. Yale University. available at: www2 . re search . att . com/ ˜ s rini / TAG+ 10 /papers /uwe .pdf. Andreas Potthoff and Wolfgang Thomas. 1993. Regular tree languages without unary symbols are starfree. In Proc. 9th Int. Symp. Fundamentals of Computation Theory, volume 710 of LNCS, pages 396–405. Springer. William C. Rounds. 1969. Context-free grammars on trees. In Proc. 1st ACM Symp. Theory of Comput., pages 143–148. ACM. William C. Rounds. 1970. Tree-oriented proofs of some theorems on context-free and indexed languages. In Proc. 2nd ACM Symp. Theory of Comput., pages 109– 116. ACM. Yves Schabes. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA. Yves Schabes, Anne Abeill´ e, and Aravind K. Joshi. 1988. Parsing strategies with ‘lexicalized’ grammars: Application to tree adjoining grammars. In Proc. 12th Int. Conf. Computational Linguistics, pages 578–583. John von Neumann Society for Computing Sciences, Budapest. Yves Schabes and Richard C. Waters. 1995. Tree insertion grammar: A cubic-time parsable formalism that lexicalizes context-free grammars without changing the trees produced. Comput. Linguist. , 21(4):479– 513. Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. On multiple context-free grammars. Theoret. Comput. Sci., 88(2): 191–229. Heiko Stamer. 2009. Restarting Tree Automata: Formal Properties and Possible Variations. Ph.D. thesis, University of Kassel, Germany. Heiko Stamer and Friedrich Otto. 2007. Restarting tree automata and linear context-free tree languages. In Proc. 2nd Int. Conf. Algebraic Informatics, volume 4728 of LNCS, pages 275–289. Springer. K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proc. 25th Ann. Meeting of the Association for Computational Linguistics, pages 104–1 11. Association for Computational Linguistics. XTAG Research Group. 2001. A lexicalized tree adjoining grammar for English. Technical Report IRCS-0103, University of Pennsylvania, Philadelphia, USA. Ryo Yoshinaka. 2006. Extensions and Restrictions of Abstract Categorial Grammars. Ph.D. thesis, University of Tokyo. 515