uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Mediating for reduction (on minimizing alternating Buchi automata)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2014 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 552, 26-43 p.Article in journal (Refereed) Published
Abstract [en]

We propose a new approach for minimizing alternating Buchi automata (ABA). The approach is based on the mediated equivalence on states of an ABA, which is the maximal equivalence contained in the mediated preorder. Two states p and q are related by the mediated preorder if there is a mediator (mediating state) which forward simulates p and backward simulates q. Under further conditions, letting a computation on some word jump from q to p preserves the language as the automaton can anyway already accept the word without jumps by runs through the mediator. We further show how the mediated equivalence can be computed efficiently. Finally, we show that, compared to the standard forward simulation equivalence, the mediated equivalence can yield much larger reductions when applied within the process of complementing Buchi automata where ABA are used as an intermediate model.

Place, publisher, year, edition, pages
2014. Vol. 552, 26-43 p.
Keyword [en]
Alternating Buchi automata, Simulation, Reduction, Quotient
National Category
Computer Science
URN: urn:nbn:se:uu:diva-235302DOI: 10.1016/j.tcs.2014.08.003ISI: 000342475400003OAI: oai:DiVA.org:uu-235302DiVA: diva2:761502
Available from: 2014-11-06 Created: 2014-10-30 Last updated: 2014-11-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Abdulla, Parosh Aziz
By organisation
Computer Systems
In the same journal
Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 229 hits
ReferencesLink to record
Permanent link

Direct link