Přístupnostní navigace
E-application
Search Search Close
Publication detail
HOLÍK, L. VOJNAR, T. ABDULLA, P. CHEN, Y.
Original Title
Mediating for reduction (on minimizing alternating Buchi automata)
Type
journal article in Web of Science
Language
English
Original Abstract
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.
Keywords
alternating Buchi automata space reduction simulation quotinet mediation
Authors
HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.
RIV year
2014
Released
20. 10. 2014
ISBN
0304-3975
Periodical
Theoretical Computer Science
Year of study
Number
552
State
Kingdom of the Netherlands
Pages from
26
Pages to
43
Pages count
18
URL
http://dx.doi.org/10.1016/j.tcs.2014.08.003
BibTex
@article{BUT111664, author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Yu-Fang {Chen}", title="Mediating for reduction (on minimizing alternating Buchi automata)", journal="Theoretical Computer Science", year="2014", volume="2014", number="552", pages="26--43", doi="10.1016/j.tcs.2014.08.003", issn="0304-3975", url="http://dx.doi.org/10.1016/j.tcs.2014.08.003" }