- 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.
- Links To Paper
- 1st Link
- Bibtex format
- @InProceedings{EDI-INF-RR-1376,
- author = {
Richard Mayr
and Lorenzo Clemente
},
- title = {Multipebble Simulations for Alternating Automata},
- book title = {Proceedings of CONCUR 2010.},
- publisher = {Springer Verlag},
- year = 2010,
- month = {Aug},
- url = {http://homepages.inf.ed.ac.uk/rmayr/multipebble.pdf},
- }
|
