Detail publikace

Mediating for reduction (on minimizing alternating Buchi automata)

Originální název

Mediating for reduction (on minimizing alternating Buchi automata)

Anglický název

Mediating for reduction (on minimizing alternating Buchi automata)

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

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)",
  annote="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.",
  address="NEUVEDEN",
  chapter="111664",
  doi="10.1016/j.tcs.2014.08.003",
  edition="NEUVEDEN",
  howpublished="online",
  institution="NEUVEDEN",
  number="552",
  volume="2014",
  year="2014",
  month="october",
  pages="26--43",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}