Mediating for reduction (on minimizing alternating Buchi automata)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU112069" target="_blank" >RIV/00216305:26230/14:PU112069 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2014.08.003" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2014.08.003</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2014.08.003" target="_blank" >10.1016/j.tcs.2014.08.003</a>
Alternative languages
Result language
angličtina
Original language name
Mediating for reduction (on minimizing alternating Buchi automata)
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Volume of the periodical
2014
Issue of the periodical within the volume
552
Country of publishing house
FR - FRANCE
Number of pages
18
Pages from-to
26-43
UT code for WoS article
000342475400003
EID of the result in the Scopus database
2-s2.0-84926326209