Informatics Report Series
Report
 EDI-INF-RR-1376
 Related Pages Report (by Number) Index Report (by Date) Index Author Index Institute Index Home
Title:Multipebble Simulations for Alternating Automata
Authors: Richard Mayr ; Lorenzo Clemente
Date:Aug 2010
Publication Title:Proceedings of CONCUR 2010.
Publisher:Springer Verlag
Publication Type:Conference Paper Publication Status:Pre-print
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 [Etessami:05] and ABA in [Wilke and Fritz:05], and (1,k)-simulation for NBA in [Etessami:02]. 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, 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. multipebble delayed simulation preserves its language. Finally, multipebble simulations yield new insights into the Miyano-Hayashi construction on ABA.