Alternating_tree_automata

Alternating tree automata

Alternating tree automata

Add article description

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).

Computational complexity

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

References

  1. [1]
    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 expanding it.
Share this article:

This article uses material from the Wikipedia article Alternating_tree_automata, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.