Alternating tree automata

On this page

In automata theory, an alternating tree automaton (ATA) is an extension of nondeterministic tree automaton as same as alternating finite automaton extends nondeterministic finite automaton (NFA).

We don't have any images related to Alternating tree automata yet.

You can add one yourself here.

We don't have any YouTube videos related to Alternating tree automata yet.

You can add one yourself here.

We don't have any PDF documents related to Alternating tree automata yet.

You can add one yourself here.

We don't have any Books related to Alternating tree automata yet.

You can add one yourself here.

We don't have any archived web articles related to Alternating tree automata yet.

You can submit a link to a page to archive here.

Computational complexity

The emptiness problem (deciding whether the language of an input ATA is empty) and the universality problem for ATAs are EXPTIME-complete.¹ The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME².

References

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications [1] (Theorem 7.5.1 and subsequent remark) http://tata.gforge.inria.fr/ ↩
H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications [1] (Theorem 7.5.1 and subsequent remark) http://tata.gforge.inria.fr/ ↩