License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2328
URN: urn:nbn:de:0030-drops-23281
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2328/
Löding, Christof ; Wong, Karianto

On Nondeterministic Unranked Tree Automata with Sibling Constraints

pdf-format:
Dokument 1.pdf (222 KB)

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 (FSTTCS 2009)},
  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: 14.12.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI