Publication Details

Mediating for Reduction (On Minimizing Alternating Büchi Automata)

ABDULLA Parosh A., HOLÍK Lukáš, CHEN Yu-Fang and VOJNAR Tomáš. Mediating for Reduction (On Minimizing Alternating Büchi Automata). Brno: Faculty of Information Technology BUT, 2009.
Type
technical report
Language
english
Authors
Abdulla Parosh A. (Uppsala)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Chen Yu-Fang (ASIN)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Abstract

We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called mediated equivalence on states of ABA, which is the maximal equivalence contained in the so called mediated preorder. Two states p and q can be related by the mediated preorder if there is a mediator (mediating state) which forward simulates p and backward simulates q. Under some further conditions, letting a computation on some word jump from q to p (due to they get collapsed) 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 more significant reductions when applied within the process of complementing B\"uchi automata where ABA are used as an intermediate model.

Published
2009
Pages
26
Publisher
Faculty of Information Technology BUT
Place
Brno, CZ
BibTeX 
@TECHREPORT{FITPUB9032,
   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 B{\"{u}}chi Automata)",
   pages = 26,
   year = 2009,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9032"
}
Back to top