Alternating tree automata

In automata theory, an alternating tree automaton (ATA) is a generalisation of a nondeterministic tree automaton in the same way that an alternating finite automaton is a generalisation of a nondeterministic finite automaton (NFA).

Computational complexity

The emptiness problem (deciding whether the language of an input ATA is empty) for ATAs, and therefore its complement, the universality problem, are EXPTIME-complete.^[1] The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME^[1].

References

1 2 H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications (Theorem 7.5.1 and subsequent remark)

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by adding missing information.

[comon2008tree-1] 1 2 H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications (Theorem 7.5.1 and subsequent remark)

[1]

A page that knows where it met you.

Computational complexity

References