Fuzzy alternating automata over distributive lattices

Nondeterminism gives computation models the power of existential choice. As a generalization of nondeterminism, “alternation” gives computation models the power of existential choice and universal choice simultaneously. In this paper, we extend fuzzy nondeterministic automata to a model called fuzzy alternating automata over distributive lattices. Compared with the previous work, a weight labels a leaf node of the run tree rather than be involved in the edge between states when executing a transition. One advantage of our setting is that it is easy to complement a given fuzzy alternating automaton. It suffices to take the dual operation on the transition function and negate final costs on states. Moreover, we show that fuzzy alternating automata have the same expressive power as fuzzy nondeterministic automata, and the former ones are exponentially more succinct than the latter ones. In addition, we illustrate that such exponential blow-up is unavoidable.