Back to Search Start Over

Simulation relations for alternating Büchi automata.

Authors :
Fritz, Carsten
Wilke, Thomas
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]

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