Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-16242-8_41 | LPAR (Yogyakarta) |
Keywords | Field | DocType |
bottom-up tree automaton,term constraint,new class,boolean operation,disequality constraint,arbitrary equality constraint,tree automaton,disequality term constraint,bottom up | Automata theory,Horn clause,Computer science,Automaton,Top-down and bottom-up design,Algorithm,Disjunctive normal form,Decidability,Emptiness,Tree automaton | Conference |
Volume | ISSN | ISBN |
6397 | 0302-9743 | 3-642-16241-X |
Citations | PageRank | References |
2 | 0.44 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Reuß | 1 | 2 | 1.46 |
| Helmut Seidl | 2 | 1468 | 103.61 |