License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2328/
Go to the corresponding LIPIcs Volume Portal

Löding, Christof ; Wong, Karianto

On Nondeterministic Unranked Tree Automata with Sibling Constraints

pdf-format:
09005.LoedingChristof.2328.pdf (0.2 MB)

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 =		{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
Collection: 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 | Privacy Published by LZI