An Automata-Theoretic Approach to L-valued Computation Tree Logic Model Checking

Translating computation tree logic formulas into Büchi tree automata has been proven to be an effective approach for implementing branching-time model checking. For a more generalized class of lattice-valued (L-valued, for short) computation tree logic formulas, the revelent study has not proceeded yet. We introduce the notion of L-valued alternating Büchi tree automata and achieve the goal of associating each L-valued computation tree logic formula with an L-valued Büchi tree automaton. We show that a satisfiability problem for an L-valued computation tree logic formula can be reduced to one for the language accepted by an L-valued Büchi tree automaton. L-valued alternating Büchi tree automata are the key to the automata-theoretic approach to L-valued computation tree logics, and we also study their expressive power and closure properties.