Search Results

Documents authored by Maletti, Andreas

Document
DOI: 10.4230/LIPIcs.STACS.2024.51
Weighted HOM-Problem for Nonnegative Integers

Authors: Andreas Maletti, Andreea-Teodora Nász, and Erik Paul

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The HOM-problem asks whether the image of a regular tree language under a given tree homomorphism is again regular. It was recently shown to be decidable by Godoy, Giménez, Ramos, and Àlvarez. In this paper, the ℕ-weighted version of this problem is considered and its decidability is proved. More precisely, it is decidable in polynomial time whether the image of a regular ℕ-weighted tree language under a nondeleting, nonerasing tree homomorphism is regular.
Cite as

Andreas Maletti, Andreea-Teodora Nász, and Erik Paul. Weighted HOM-Problem for Nonnegative Integers. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{maletti_et_al:LIPIcs.STACS.2024.51,
  author =	{Maletti, Andreas and N\'{a}sz, Andreea-Teodora and Paul, Erik},
  title =	{{Weighted HOM-Problem for Nonnegative Integers}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.51},
  URN =		{urn:nbn:de:0030-drops-197614},
  doi =		{10.4230/LIPIcs.STACS.2024.51},
  annote =	{Keywords: Weighted Tree Automaton, Decision Problem, Subtree Equality Constraint, Tree Homomorphism, HOM-Problem, Weighted Tree Grammar, Weighted HOM-Problem}
}
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}
}
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