## 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]

Original language | English |
---|---|

Title of host publication | CONCUR 2010 - CONCURRENCY THEORY |

Editors | P Gastin, F Laroussinie |

Place of Publication | BERLIN |

Publisher | Springer-Verlag GmbH |

Pages | 297-312 |

Number of pages | 16 |

ISBN (Print) | 978-3-642-1537407 |

Publication status | Published - 2010 |

Event | 21st Conference on Concurrency Theory - Paris Duration: 31 Aug 2010 → 3 Sep 2010 |

### Conference

Conference | 21st Conference on Concurrency Theory |
---|---|

City | Paris |

Period | 31/08/10 → 3/09/10 |