Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

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
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
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 = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh