Multipebble Simulations for Alternating Automata - (Extended Abstract)

Lorenzo Clemente, Richard Mayr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationCONCUR 2010 - CONCURRENCY THEORY
EditorsP Gastin, F Laroussinie
Place of PublicationBERLIN
PublisherSpringer-Verlag GmbH
Pages297-312
Number of pages16
ISBN (Print)978-3-642-1537407
Publication statusPublished - 2010
Event21st Conference on Concurrency Theory - Paris
Duration: 31 Aug 20103 Sep 2010

Conference

Conference21st Conference on Concurrency Theory
CityParis
Period31/08/103/09/10

Cite this