Publication result detail

Mediating for reduction (on minimizing alternating Buchi automata)

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.

Original Title

Mediating for reduction (on minimizing alternating Buchi automata)

English Title

Mediating for reduction (on minimizing alternating Buchi automata)

Type

WoS Article

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.

English 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

Key words in English

alternating Buchi automata
space reduction
simulation
quotinet
mediation

Authors

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.

RIV year

2015

Released

20.10.2014

ISBN

0304-3975

Periodical

Theoretical Computer Science

Volume

2014

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"
}