On Nondeterministic Unranked Tree Automata with Sibling Constraints

Authors Christof Löding, Karianto Wong



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2009.2328.pdf
  • Filesize: 222 kB
  • 12 pages

Document Identifiers

Author Details

Christof Löding
Karianto Wong

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2328

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.
Keywords
  • Unranked tree automata
  • equality and disequality constraints
  • monadic second-order logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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