LIPIcs.FSTTCS.2009.2328.pdf
- Filesize: 222 kB
- 12 pages
Document
On Nondeterministic Unranked Tree Automata with Sibling Constraints
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-12-14
Cite As Get 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.
Subject Classification
Keywords
- Unranked tree automata
- equality and disequality constraints
- monadic second-order logic
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads