License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.44
URN: urn:nbn:de:0030-drops-116063
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11606/
Go to the corresponding LIPIcs Volume Portal

Kuhlmann, Marco ; Maletti, Andreas ; Schiffer, Lena Katharina

The Tree-Generative Capacity of Combinatory Categorial Grammars

pdf-format:
LIPIcs-FSTTCS-2019-44.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{kuhlmann_et_al:LIPIcs:2019:11606,
  author =	{Marco Kuhlmann and Andreas Maletti and Lena Katharina Schiffer},
  title =	{{The Tree-Generative Capacity of Combinatory Categorial Grammars}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11606},
  URN =		{urn:nbn:de:0030-drops-116063},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.44},
  annote =	{Keywords: Combinatory Categorial Grammar, Regular Tree Language, Linear Context-free Tree Language}
}

Keywords: Combinatory Categorial Grammar, Regular Tree Language, Linear Context-free Tree Language
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI