Alternating Automata, the Weak Monadic Theory of Trees and its Complexity.

David E. Muller Ahmed Saoudi Paul E. Schupp

Published in: Theor. Comput. Sci. (1992)

Keyphrases

tree automata
decision trees
theoretical framework
datalog queries
theoretical basis
computational model
computational complexity
decision problems
general theory
markov chain
tree structure
expressive power
information theory
deductive databases
regular expressions
finite state
relational databases
data sets