License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-23281
URL:

;

On Nondeterministic Unranked Tree Automata with Sibling Constraints

pdf-format:


Abstract

We continue the study of bottom-up unranked tree automata with equality and disequality constraints between direct subtrees. In particular, we show that the emptiness problem for the nondeterministic automata is decidable. In addition, we show that the universality problem, in contrast, is undecidable.

BibTeX - Entry

@InProceedings{lding_et_al:LIPIcs:2009:2328,
  author =	{Christof L{\"o}ding and Karianto Wong},
  title =	{{On Nondeterministic Unranked Tree Automata with Sibling Constraints}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{311--322},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2328},
  URN =		{urn:nbn:de:0030-drops-23281},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2328},
  annote =	{Keywords: Unranked tree automata, equality and disequality constraints, monadic second-order logic}
}

Keywords: Unranked tree automata, equality and disequality constraints, monadic second-order logic
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue date: 2009
Date of publication: 2009


DROPS-Home | Fulltext Search | Imprint Published by LZI