Back to Search
Start Over
Simulation relations for alternating Büchi automata.
- Source :
-
Theoretical Computer Science . Jun2005, Vol. 338 Issue 1-3, p275-314. 40p. - Publication Year :
- 2005
-
Abstract
- Abstract: Quotienting by simulation equivalences is a well-established technique for reducing the size of nondeterministic Büchi automata. We adapt this technique to alternating Büchi automata. To this end we suggest two new quotients, namely minimax and semi-elective quotients, prove that they preserve the recognized languages, and show that computing them is not more difficult than computing quotients for nondeterministic Büchi automata. Our approach is game-theoretic; the proofs rely on a specifically tailored join operation for strategies in simulation games which is interesting in its own right. We explain the merits of our quotienting procedures with respect to converting alternating Büchi automata into nondeterministic ones. [Copyright &y& Elsevier]
- Subjects :
- *MACHINE theory
*ALGORITHMS
*MATHEMATICAL logic
*MATHEMATICAL models
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 338
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 17064393
- Full Text :
- https://doi.org/10.1016/j.tcs.2005.01.016