Multipebble Simulations for Alternating Automata - (Extended Abstract)

Multipebble Simulations for Alternating Automata - (Extended Abstract),10.1007/978-3-642-15375-4_21,Lorenzo Clemente,Richard Mayr

Multipebble Simulations for Alternating Automata - (Extended Abstract)   (Citations: 2)
BibTex | RIS | RefWorks Download
We study generalized simulation relations for alternating Büchi 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 Büchi automata (NBA)[4] in 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 (ω-)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].
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: