1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 University of Gdánsk3 LaBRI. Université Bordeaux I
Weak acceptance conditions for automata on infinite words or trees are defined in terms of the set of states that appear in the run. This is in contrast with, more usual, strong conditions that are defined in terms of states appearing infinitely often on the run. Weak conditions appear in the context of model-checking and translations of logical formalisms to automata. We study the complexity of the emptiness problem for tree automata with weak conditions. We also study the translations between automata with weak and strong conditions.
Information Processing Letters, 2002, Vol 84, Issue 4/3, p. 181-187