Search Results

Documents authored by Kuhlmann, Marco

Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.44
The Tree-Generative Capacity of Combinatory Categorial Grammars

Authors: Marco Kuhlmann, Andreas Maletti, and Lena Katharina Schiffer

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{kuhlmann_et_al:LIPIcs.FSTTCS.2019.44,
  author =	{Kuhlmann, Marco and Maletti, Andreas and Schiffer, Lena Katharina},
  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 =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.44},
  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}
}
Document
DOI: 10.4230/DagRep.5.3.143
Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)

Authors: Frank Drewes, Kevin Knight, and Marco Kuhlmann

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
In natural language processing (NLP) there is an increasing interest in formal models for processing graphs rather than more restricted structures such as strings or trees. Such models of graph transformation have previously been studied and applied in various other areas of computer science, including formal language theory, term rewriting, theory and implementation of programming languages, concurrent processes, and software engineering. However, few researchers from NLP are familiar with this work, and at the same time, few researchers from the theory of graph transformation are aware of the specific desiderata, possibilities and challenges that one faces when applying the theory of graph transformation to NLP problems. The Dagstuhl Seminar 15122 "Formal Models of Graph Transformation in Natural Language Processing" brought researchers from the two areas together. It initiated an interdisciplinary exchange about existing work, open problems, and interesting applications.
Cite as

Frank Drewes, Kevin Knight, and Marco Kuhlmann. Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122). In Dagstuhl Reports, Volume 5, Issue 3, pp. 143-161, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{drewes_et_al:DagRep.5.3.143,
  author =	{Drewes, Frank and Knight, Kevin and Kuhlmann, Marco},
  title =	{{Formal Models of Graph Transformation in Natural Language Processing (Dagstuhl Seminar 15122)}},
  pages =	{143--161},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Drewes, Frank and Knight, Kevin and Kuhlmann, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.143},
  URN =		{urn:nbn:de:0030-drops-53484},
  doi =		{10.4230/DagRep.5.3.143},
  annote =	{Keywords: Automata theory, Graph transformation, Natural language processing}
}
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 Imprint Privacy Contact