Alternating tree automata
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].
gollark: It's very readable.
gollark: I would just dump the program's data structures directly into a framebuffer.
gollark: Yes, like the lack of pattern matching.
gollark: it could look like `bees::whatever()` or you could import it as `beeoid` if you wanted and get `beeoid::whatever()`.
gollark: That isn't required by an import system which works.
References
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.