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.STACS.2019.47
URN: urn:nbn:de:0030-drops-102863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10286/
Go to the corresponding LIPIcs Volume Portal

Landwehr, Patrick ; Löding, Christof

Tree Automata with Global Constraints for Infinite Trees

pdf-format:
LIPIcs-STACS-2019-47.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{landwehr_et_al:LIPIcs:2019:10286,
  author =	{Patrick Landwehr and Christof L{\"o}ding},
  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 =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10286},
  doi =		{10.4230/LIPIcs.STACS.2019.47},
  annote =	{Keywords: Tree automata, infinite trees, global constraints}
}

Keywords: Tree automata, infinite trees, global constraints
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

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