Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Complete Lattice
Finite Automata
Polynomial Time
Simulation Game
Left Right
Subscribe
Academic
Publications
Multipebble Simulations for Alternating Automata  (Extended Abstract)
Multipebble Simulations for Alternating Automata  (Extended Abstract),10.1007/9783642153754_21,Lorenzo Clemente,Richard Mayr
Edit
Multipebble Simulations for Alternating Automata  (Extended Abstract)
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Lorenzo Clemente
,
Richard Mayr
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 MiyanoHayashi construction [10] on ABA. A technical report with full proofs is available [2].
Conference:
International Conference on Concurrency Theory  CONCUR
, pp. 297312, 2010
DOI:
10.1007/9783642153754_21
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(12)
Mediating for Reduction (on Minimizing Alternating Büchi Automata)
(
Citations: 2
)
Parosh Aziz Abdulla
,
Yufang Chen
,
Lukás Holík
,
Tomás Vojnar
Conference:
Foundations of Software Technology and Theoretical Computer Science  FSTTCS
, pp. 112, 2009
A Hierarchy of PolynomialTime Computable Simulations for Automata
(
Citations: 12
)
Kousha Etessami
Conference:
International Conference on Concurrency Theory  CONCUR
, pp. 131144, 2002
Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
(
Citations: 57
)
Kousha Etessami
,
Thomas Wilke
,
Rebecca A. Schuller
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 694707, 2001
Simulation relations for alternating Büchi automata
(
Citations: 14
)
Carsten Fritz
,
Thomas Wilke
Journal:
Theoretical Computer Science  TCS
, vol. 338, no. 13, pp. 275314, 2005
Trees, automata, and games
(
Citations: 142
)
Yuri Gurevich
,
Leo Harrington
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 6065, 1982
Sort by:
Citations
(2)
Büchi Automata can have Smaller Quotients
Lorenzo Clemente
Journal:
Computing Research Repository  CORR
, vol. abs/1102.3, 2011
Experimental Aspects of Synthesis
Rüdiger Ehlers
Journal:
Electronic Proceedings in Theoretical Computer Science
, pp. 116, 2011