Jump to content

Alternating tree automata

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by A3nm (talk | contribs) at 16:10, 2 April 2018 (add computational complexity section following TATA). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. ^ a b 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)


P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Alternating_tree_automata&oldid=833824021"