Document Open Access Logo

The Tree-Generative Capacity of Combinatory Categorial Grammars

Authors Marco Kuhlmann , Andreas Maletti , Lena Katharina Schiffer

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.44.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Marco Kuhlmann
  • Dept. of Computer and Information Science, Linköping University, SE-581 83 Linköping, Sweden
Andreas Maletti
  • Institute for Computer Science, Universität Leipzig, P.O. box 100 920, D-04009 Leipzig, Germany
Lena Katharina Schiffer
  • Institute for Computer Science, Universität Leipzig, P.O. box 100 920, D-04009 Leipzig, Germany

Funding

  • Kuhlmann, Marco: Supported by the Centre for Industrial IT (CENIIT), grant 15.02.
  • Schiffer, Lena Katharina: Supported by the German Research Foundation (DFG) Research Training Group GRK 1763 "Quantitative Logics and Automata".

Cite As Get BibTex

Marco Kuhlmann, Andreas Maletti, and Lena Katharina Schiffer. The Tree-Generative Capacity of Combinatory Categorial Grammars. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.44

Abstract

The generative capacity of combinatory categorial grammars as acceptors of tree languages is investigated. It is demonstrated that the such obtained tree languages can also be generated by simple monadic context-free tree grammars. However, the subclass of pure combinatory categorial grammars cannot even accept all regular tree languages. Additionally, the tree languages accepted by combinatory categorial grammars with limited rule degrees are characterized: If only application rules are allowed, then they can accept only a proper subset of the regular tree languages, whereas they can accept exactly the regular tree languages once first degree composition rules are permitted.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Tree languages
  • Theory of computation → Grammars and context-free languages
  • Computing methodologies
  • Computing methodologies → Artificial intelligence
  • Computing methodologies → Natural language processing
Keywords
  • Combinatory Categorial Grammar
  • Regular Tree Language
  • Linear Context-free Tree Language

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Kazimierz Ajdukiewicz. Die syntaktische Konnexität. Studia Philosophica, 1:1-27, 1935. Google Scholar
  2. Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1998. Google Scholar
  3. Yehoshua Bar-Hillel. A quasi-arithmetical notation for syntactic description. Language, 29(1):47-58, 1953. Google Scholar
  4. Yehoshua Bar-Hillel, Haim Gaifman, and Eli Shamir. On Categorial and Phrase Structure Grammars. In Yehoshua Bar-Hillel, editor, Language and Information: Selected Essays on Their Theory and Application, pages 99-115. Addison Wesley, 1964. Google Scholar
  5. Yehoshua Bar-Hillel, Micha Perles, and Eli Shamir. On formal properties of simple phrase structure grammars. In Yehoshua Bar-Hillel, editor, Language and Information: Selected Essays on their Theory and Application, chapter 9, pages 116-150. Addison Wesley, 1964. Google Scholar
  6. Noam Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113-124, 1956. Google Scholar
  7. Haskell B. Curry. Foundations of combinatorial logic. American Journal of Mathematics, 52(3):509-536, 1930. Google Scholar
  8. Haskell B. Curry, Robert Feys, and William Craig. Combinatory Logic. Number 1 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1958. Google Scholar
  9. Ferenc Gécseg and Magnus Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984. 2nd revision available at URL: https://arxiv.org/abs/1509.06233.
  10. Ferenc Gécseg and Magnus Steinby. Tree Languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1-68. Springer, 1997. Google Scholar
  11. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979. Google Scholar
  12. Aravind K. Joshi and Yves Schabes. Tree-Adjoining Grammars. In Grzegorz Rozenberg and Arto Salomaa, editors, Beyond Words, volume 3 of Handbook of Formal Languages, pages 69-123. Springer, 1997. Google Scholar
  13. Alexander Koller and Marco Kuhlmann. Dependency Trees and the Strong Generative Capacity of CCG. In Proc. 12th EACL, pages 460-468. ACL, 2009. Google Scholar
  14. Marco Kuhlmann, Alexander Koller, and Giorgio Satta. Lexicalization and Generative Power in CCG. Comput. Linguist., 41(2):187-219, 2015. Google Scholar
  15. Marco Kuhlmann, Giorgio Satta, and Peter Jonsson. On the Complexity of CCG Parsing. Comput. Linguist., 44(3):447-482, 2018. Google Scholar
  16. Joachim Lambek. The mathematics of sentence structure. Amer. Math. Monthly, 65(3):154-170, 1958. Google Scholar
  17. Kenton Lee, Mike Lewis, and Luke Zettlemoyer. Global neural CCG parsing with optimality guarantees. In Proc. 2016 EMNLP, pages 2366-2376. ACL, 2016. Google Scholar
  18. Mike Lewis and Mark Steedman. Unsupervised induction of cross-lingual semantic relations. In Proc. 2013 EMNLP, pages 681-692. ACL, 2013. Google Scholar
  19. William C. Rounds. Context-Free Grammars on Trees. In Proc. 1st STOC, pages 143-148. ACM, 1969. Google Scholar
  20. William C. Rounds. Tree-Oriented Proofs of Some Theorems on Context-Free and Indexed Languages. In Proc. 2nd STOC, pages 109-116. ACM, 1970. Google Scholar
  21. Yves Schabes, Anne Abeillé, and Aravind K. Joshi. Parsing Strategies with `Lexicalized' Grammars: Application to Tree Adjoining Grammars. In Proc. 12th CoLing, pages 578-583, 1988. Google Scholar
  22. Moses Schönfinkel. Über die Bausteine der mathematischen Logik. Mathematische Annalen, 92(3-4):305-316, 1924. Google Scholar
  23. Mark Steedman. The Syntactic Process. MIT Press, 2000. Google Scholar
  24. Mark Steedman and Jason Baldridge. Combinatory Categorial Grammar. In Robert D. Borsley and Kersti Börjars, editors, Non-Transformational Syntax: Formal and Explicit Models of Grammar, chapter 5, pages 181-224. Blackwell, 2011. Google Scholar
  25. Hans-Jörg Tiede. Deductive Systems and Grammars: Proofs as Grammatical Structures. PhD thesis, Indiana University, Bloomington, IN, USA, 1999. Google Scholar
  26. Krishnamurti Vijay-Shanker and David J. Weir. Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems. In Proc. 26th ACL, pages 278-285. ACL, 1988. Google Scholar
  27. Krishnamurti Vijay-Shanker and David J. Weir. Polynomial time parsing of combinatory categorial grammars. In Proc. 28th ACL, pages 1-8. ACL, 1990. Google Scholar
  28. Krishnamurti Vijay-Shanker and David J. Weir. The Equivalence of Four Extensions of Context-Free Grammars. Math. Systems Theory, 27(6):511-546, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact