@inproceedings{10.1007/978-3-319-98654-8_41,
    Abstract = {Unambiguous B{\"u}chi automata, i.e. B{\"u}chi automata allowing only one accepting run per word, are a useful restriction of B{\"u}chi automata that is well-suited for probabilistic model-checking. In this paper we propose a more permissive variant, namely finitely ambiguous B{\"u}chi automata, a generalisation where each word has at most k accepting runs, for some fixed k. We adapt existing notions and results concerning finite and bounded ambiguity of finite automata to the setting of {\$}{\$}{\backslash}omega {\$}{\$}-languages and present a translation from arbitrary nondeterministic B{\"u}chi automata with n states to finitely ambiguous automata with at most {\$}{\$}3^n{\$}{\$}states and at most n accepting runs per word.},
    Address = {Cham},
    Author = {L{\"o}ding, Christof and Pirogov, Anton},
    BookTitle = {Developments in Language Theory},
    Editor = {Hoshi, Mizuho and Seki, Shinnosuke},
    File = {On Finitely Ambiguous B¨uchi Automata - Löding-Pirogov2018\_Chapter\_OnFinitelyAmbiguousBüchiAutoma - a - g.pdf},
    ISBN = {978-3-319-98654-8},
    Pages = {503--515},
    Publisher = {Springer International Publishing},
    Title = {On Finitely Ambiguous B{\"u}chi Automata},
    Year = {2018},
    date-added = {2020-07-25 10:55:41 +0200},
    date-modified = {2020-07-25 10:55:41 +0200},
    doi = {10.1007/978-3-319-98654-8_41}
}

@inproceedings{10.1007/978-3-319-98654-8_41, Abstract = {Unambiguous B{\"u}chi automata, i.e. B{\"u}chi automata allowing only one accepting run per word, are a useful restriction of B{\"u}chi automata that is well-suited for probabilistic model-checking. In this paper we propose a more permissive variant, namely finitely ambiguous B{\"u}chi automata, a generalisation where each word has at most k accepting runs, for some fixed k. We adapt existing notions and results concerning finite and bounded ambiguity of finite automata to the setting of {\$}{\$}{\backslash}omega {\$}{\$}-languages and present a translation from arbitrary nondeterministic B{\"u}chi automata with n states to finitely ambiguous automata with at most {\$}{\$}3^n{\$}{\$}states and at most n accepting runs per word.}, Address = {Cham}, Author = {L{\"o}ding, Christof and Pirogov, Anton}, BookTitle = {Developments in Language Theory}, Editor = {Hoshi, Mizuho and Seki, Shinnosuke}, File = {On Finitely Ambiguous B¨uchi Automata - Löding-Pirogov2018_Chapter_OnFinitelyAmbiguousBüchiAutoma - a - g.pdf}, ISBN = {978-3-319-98654-8}, Pages = {503--515}, Publisher = {Springer International Publishing}, Title = {On Finitely Ambiguous B{\"u}chi Automata}, Year = {2018}, date-added = {2020-07-25 10:55:41 +0200}, date-modified = {2020-07-25 10:55:41 +0200}, doi = {10.1007/978-3-319-98654-8_41} }