1 Search Results for "Wong, Karianto"


Document
On Nondeterministic Unranked Tree Automata with Sibling Constraints

Authors: Christof Löding and Karianto Wong

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


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.

Cite as

Christof Löding and Karianto Wong. On Nondeterministic Unranked Tree Automata with Sibling Constraints. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 311-322, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{loding_et_al:LIPIcs.FSTTCS.2009.2328,
  author =	{L\"{o}ding, Christof and Wong, Karianto},
  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 =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.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}
}
  • Refine by Author
  • 1 Löding, Christof
  • 1 Wong, Karianto

  • Refine by Classification

  • Refine by Keyword
  • 1 Unranked tree automata
  • 1 equality and disequality constraints
  • 1 monadic second-order logic

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

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