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). In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). LIPIcs, sv. 4. Wadern: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2009, pp. 1-12. ISBN 978-3-939897-13-2.
English title
Mediating for Reduction (On Minimizing Alternating Büchi Automata)
Type
conference paper
Language
czech
Authors
Abdulla Parosh A. (Uppsala)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Chen Yu-Fang (Uppsala)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
URL
Keywords

alternating automata, Büchi automata, reduction, simulation

Abstract

We propose a new approach for minimizing alternating Büchi 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üchi automata where ABA are used
as an intermediate model.

Annotation

We propose a new approach for minimizing alternating Büchi 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üchi automata where ABA are used
as an intermediate model.

Published
2009
Pages
1-12
Proceedings
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Series
LIPIcs, sv. 4
Conference
Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Kanpur, IN
ISBN
978-3-939897-13-2
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place
Wadern, DE
BibTeX
@INPROCEEDINGS{FITPUB9140,
   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 = "1--12",
   booktitle = "IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)",
   series = "LIPIcs, sv. 4",
   year = 2009,
   location = "Wadern, DE",
   publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
   ISBN = "978-3-939897-13-2",
   language = "czech",
   url = "https://www.fit.vut.cz/research/publication/9140"
}
Back to top