×

State space reductions for alternating Büchi automata. Quotienting by simulation equivalences. (English) Zbl 1027.68075

Agrawal, Manindra (ed.) et al., FST TCS 2002: Foundations of software technology and theoretical computer science. 22nd conference, Kanpur, India, December 12-14, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2556, 157-168 (2002).
Summary: 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. We explain the merits of of our quotienting procedures with respect to converting alternating Büchi automata into nondeterministic ones.
For the entire collection see [Zbl 1014.00021].

MSC:

68Q45 Formal languages and automata

Software:

Truth/SLC
PDFBibTeX XMLCite
Full Text: Link