Publication Details

Mediating for reduction (on minimizing alternating Buchi automata)

ABDULLA Parosh A., HOLÍK Lukáš, CHEN Yu-Fang and VOJNAR Tomáš. Mediating for reduction (on minimizing alternating Buchi automata). Theoretical Computer Science, vol. 2014, no. 552, pp. 26-43. ISSN 0304-3975. Available from: http://dx.doi.org/10.1016/j.tcs.2014.08.003
Czech title
Zprostředkování pro redukci (minimzlizace alternujících Buchi automatů)
Type
journal article
Language
english
Authors
Abdulla Parosh A. (Uppsala)
Holík Lukáš, Mgr., Ph.D. (DITS FIT BUT)
Chen Yu-Fang (ASIN)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Keywords

alternating Buchi automata
space reduction
simulation
quotinet
mediation

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.

Published
2014
Pages
26-43
Journal
Theoretical Computer Science, vol. 2014, no. 552, ISSN 0304-3975
Publisher
Elsevier Science
DOI
UT WoS
000342475400003
EID Scopus
BibTeX
@ARTICLE{FITPUB10741,
   author = "A. Parosh Abdulla and Luk\'{a}\v{s} Hol\'{i}k and Yu-Fang Chen and Tom\'{a}\v{s} Vojnar",
   title = "Mediating for reduction (on minimizing alternating Buchi automata)",
   pages = "26--43",
   journal = "Theoretical Computer Science",
   volume = 2014,
   number = 552,
   year = 2014,
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2014.08.003",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10741"
}
Back to top