Pumping lemma in automata theory based on complete residuated lattice-valued logic: A note

Automata theory based on complete residuated lattice-valued logic (called L-valued automata) was established in (Qiu, Automata theory based on completed residuated lattice-valued logic (1), Science in China (F) 44(6) (2001) 419-429; Qiu, Automata theory based on completed residuated lattice-valued logic (II), Science in China (F) 45(6) (2002) 442-452). In this note, we deal with the pumping lemma in L-valued automata theory. After recalling some preliminaries related to complete residuated lattices and L-valued automata, we define a number of L-valued accepting predicates. In particular, the pumping lemma for L-valued automata theory is set up. We show that if those related L-valued predicates are defined by using connective A instead of &, then the pumping lemma may not hold again. Furthermore, we investigate the L-valued automata with e-transitions, and present the equivalence between the L-valued automata without e-transitions and those with epsilon-transitions. Finally, a number of related questions is addressed. (c) 2006 Elsevier B.V. All rights reserved.