@inproceedings{44d8647ec27c4d4ab20ce7987b49ec7d,
title = "Bottom-up tree automata with term constraints",
abstract = "We introduce bottom-up tree automata with equality and disequality term constraints. These constraints are more expressive than the equality and disequality constraints between brothers introduced by Bogaert and Tison in 1992. Our new class of automata is still closed under Boolean operations. Moreover, we show that for tree automata with term constraints not only membership but also emptiness is decidable. This contrasts with the undecidability of emptiness for automata with arbitrary equality constraints between subterms identified by paths as shown in 1981 by Mongy.",
author = "Andreas Reu{\ss} and Helmut Seidl",
year = "2010",
doi = "10.1007/978-3-642-16242-8_41",
language = "English",
isbn = "364216241X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "581--593",
booktitle = "Logic for Programming, Artificial Intelligence, and Reasoning - 17th International Conference, LPAR-17, Proceedings",
}