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

Abdulla, Parosh A.; Chen, Yu-Fang; Holik, Lukas; Vojnar, Tomas

doi:10.4230/LIPIcs.FSTTCS.2009.2302

Document

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

Authors Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik, Tomas Vojnar

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2009-12-07

PDF

File

PDF

LIPIcs.FSTTCS.2009.2302.pdf

Filesize: 0.7 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2009.2302
URN: urn:nbn:de:0030-drops-23027

Subject Classification

Keywords

Alternating Automata
Buchi Automata
Automata Minimization
Buchi Automata Complementation
Simulation Preorder
forward and backward simulation
mediated equivalence

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called \emph{mediated equivalence} on states of ABA, which is the maximal equivalence contained in the so called \emph{mediated preorder}. Two states $p$ and $q$ can be related by the mediated preorder if there is a~\emph{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.

Cite As Get BibTex

Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik, and Tomas Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2302

Author Details

Parosh A. Abdulla

Yu-Fang Chen

Lukas Holik

Tomas Vojnar

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail