Klarlund, Nils ; Mukund, Madhavan ; Sohoni, Milind (2005) Determinizing Büchi asynchronous automata In: 15th International Conference on Foundations of Software Technology and Theoretical Computer Science, 18-20 Dec 2005, Bangalore, India.
Full text not available from this repository.
Official URL: https://link.springer.com/chapter/10.1007%2F3-540-...
Related URL: http://dx.doi.org/10.1007/3-540-60692-0_67
Abstract
Büchi asynchronous automata are a natural distributed machine model for recognizing ω-regular trace languages. Like their sequential counterparts, these automata need to be non-deterministic in order to capture all ω-regular languages. Thus complementation of these automata is non-trivial. Complementation is an important operation because it is fundamental for treating the logical connective “not” in decision procedures for monadic second-order logics. In this paper, we present a direct determinization procedure for Büchi asynchronous automata, which generalizes Safra's construction for sequential Büchi automata. As in the sequential case, the blow-up in the state space is essentially that of the underlying subset construction.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag |
| Keywords: | Secondary Information; Linear Time; Temporal Logic; Determinized Automaton; Infinite Word; Asynchronous Automaton |
| ID Code: | 114225 |
| Deposited On: | 25 May 2018 04:54 |
| Last Modified: | 25 May 2018 04:54 |
Repository Staff Only: item control page
