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: Yes, I'm sure it'll be very fun having to scavenge for food and water and such while competing with millions of other people.
gollark: Hmm. osmarks.net is functioning nominally since the incident.
gollark: The obvious solution is to airdrop nuclear power plants from orbit on top of all fossil fuel plants.
gollark: ALL OF THEM.
gollark: Indeed. This is why we should IMMEDIATELY switch fossil fuel plants for efficient nuclear reactors.

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


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.