1 Search Results for "Landwehr, Patrick"

Document
DOI: 10.4230/LIPIcs.STACS.2019.47
Tree Automata with Global Constraints for Infinite Trees

Authors: Patrick Landwehr and Christof Löding

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We study an extension of tree automata on infinite trees with global equality and disequality constraints. These constraints can enforce that all subtrees for which in the accepting run a state q is reached (at the root of that subtree) are identical, or that these trees differ from the subtrees at which a state q' is reached. We consider the closure properties of this model and its decision problems. While the emptiness problem for the general model remains open, we show the decidability of the emptiness problem for the case that the given automaton only uses equality constraints.
Cite as

Patrick Landwehr and Christof Löding. Tree Automata with Global Constraints for Infinite Trees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{landwehr_et_al:LIPIcs.STACS.2019.47,
  author =	{Landwehr, Patrick and L\"{o}ding, Christof},
  title =	{{Tree Automata with Global Constraints for Infinite Trees}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.47},
  URN =		{urn:nbn:de:0030-drops-102863},
  doi =		{10.4230/LIPIcs.STACS.2019.47},
  annote =	{Keywords: Tree automata, infinite trees, global constraints}
}
  • Refine by Author
  • 1 Landwehr, Patrick
  • 1 Löding, Christof

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects

  • Refine by Keyword
  • 1 Tree automata
  • 1 global constraints
  • 1 infinite trees

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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