Multipebble Simulations for Alternating Automata - (Extended Abstract)

We study generalized simulation relations for alternating Buchi automata (ABA), as well as alternating finite automata Having multiple pebbles allows the Duplicator to "hedge her bets' and delay decisions in the simulation game thus yielding a coarser simulation relation We define (k(1), k(2)) simulations with k(1)/k(2) pebbles on the left/right respectively This generalizes previous work on ordinary simulation (i e, (1, 1)-simulation) for nondeterministic Buchi automata (NBA) in [4] and ABA in [5] and (1, k)-simulation for NBA in [3]

We consider direct delayed and fair simulations In each case, the (k(1), k(2))-simulations induce a complete lattice of simulations where (1, 1)- and (n, n)-simulations are the bottom and top element (if the automaton has n states), respectively and the order is strict For any fixed k(1), k(2) the (k(1), k(2))-simulation implies (omega)language inclusion and can be computed in polynomial time Furthermore, quotienting an ABA w r t (1, n)-delayed simulation preserves its language Finally multipebble simulations yield new insights into the Miyano Hayashi construction [10] on ABA A technical report with full proofs is available [2]