Detail výsledku

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

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y. Mediating for Reduction (On Minimizing Alternating Büchi Automata). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). LIPIcs, sv. 4. Wadern: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2009. s. 1-12. ISBN: 978-3-939897-13-2.
Typ
článek ve sborníku konference
Jazyk
česky
Autoři
Holík Lukáš, doc. Mgr., Ph.D., FIT (FIT), UITS (FIT)
Vojnar Tomáš, prof. Ing., Ph.D., UITS (FIT)
Abdulla Parosh
Chen Yu-Fang
Abstrakt

Navrhli jsme novou metodu redukce alternujících Büchi automatůslučováním stavů ekvivalentních podle podle nové relace, takzvanezprostředkované (mediated) ekvivalenece. Zprostředkovaná ekvivalece jekombinací dopředné a zpětné simulace. Efektivitu metody jsme otestovalina experiementech s alternujícími automaty vznikajícími v rámcikomplementace Büchi automatů.

Klíčová slova anglicky

alternating automata, Büchi automata, reduction, simulation

URL
Anotace

Navrhli jsme novou metodu redukce alternujících Büchi automatů slučováním stavů ekvivalentních podle podle nové relace, takzvane zprostředkované (mediated) ekvivalenece. Zprostředkovaná ekvivalece je kombinací dopředné a zpětné simulace. Efektivitu metody jsme otestovali na experiementech s alternujícími automaty vznikajícími v rámci komplementace Büchi automatů.

Rok
2009
Strany
1–12
Sborník
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Řada
LIPIcs, sv. 4
Konference
Annual Conference on Foundations of Software Technology and Theoretical Computer Science
ISBN
978-3-939897-13-2
Vydavatel
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Místo
Wadern
BibTeX 
@inproceedings{BUT30903,
  author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Yu-Fang {Chen}",
  title="Mediating for Reduction (On Minimizing Alternating Büchi Automata)",
  booktitle="IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)",
  year="2009",
  series="LIPIcs, sv. 4",
  pages="1--12",
  publisher="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  address="Wadern",
  isbn="978-3-939897-13-2",
  url="http://www.fit.vutbr.cz/~holik/pub/FSTTCS09.pdf"
}
Projekty
Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů, GAČR, Doktorské granty, GD102/09/H042, zahájení: 2009-01-30, ukončení: 2012-12-31, ukončen
Pokročilé formální přístupy v návrhu a automatické verifikaci počítačových systémů, GAČR, Standardní projekty, GA102/07/0322, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina automatizované analýzy a verifikace - VeriFIT (VZ VERIFIT)
Pracoviště
Ústav inteligentních systémů (UITS)
Nahoru