Complementing Semi-deterministic Büchi Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00088081" target="_blank" >RIV/00216224:14330/16:00088081 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007/978-3-662-49674-9_49" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-662-49674-9_49</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-49674-9_49" target="_blank" >10.1007/978-3-662-49674-9_49</a>
Alternative languages
Result language
angličtina
Original language name
Complementing Semi-deterministic Büchi Automata
Original language description
We introduce an efficient complementation technique for semi-deterministic Büchi automata, which are Büchi automata that are deterministic in the limit: from every accepting state onward, their behaviour is deterministic. It is interesting to study semi-deterministic automata, because they play a role in practical applications of automata theory, such as the analysis of Markov decision processes. Our motivation to study their complementation comes from the termination analysis implemented in Ultimate Büchi Automizer, where these automata represent checked runs and have to be complemented to identify runs to be checked. We show that semi-determinism leads to a simpler complementation procedure: an extended breakpoint construction that allows for symbolic implementation. It also leads to significantly improved bounds as the complement of a semi-deterministic automaton with n states has less than 4^n states.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
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
Article name in the collection
Tools and Algorithms for the Construction and Analysis of Systems 22nd International Conference, TACAS 2016
ISBN
9783662496732
ISSN
0302-9743
e-ISSN
—
Number of pages
18
Pages from-to
770-787
Publisher name
Springer Berlin Heidelberg
Place of publication
Berlin
Event location
Eindhoven
Event date
Apr 2, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—