A power-set construction for reducing Büchi automata to non-determinism degree two |
| |
Authors: | Ulrich Ultes-Nitsche |
| |
Affiliation: | Department of Computer Science, University of Fribourg, Boulevard de Pérolles 90, CH-1700 Fribourg, Switzerland |
| |
Abstract: | Büchi automata are finite automata that accept languages of infinitely long strings, so-called ω-languages. It is well known that, unlike in the finite-string case, deterministic and non-deterministic Büchi automata accept different ω-language classes, i.e., that determination of a non-deterministic Büchi automaton using the classical power-set construction will yield in general a deterministic Büchi automaton which accepts a superset of the ω-language accepted by the given non-deterministic automaton.In this paper, a power-set construction to a given Büchi automaton is presented, which reduces the degree of non-determinism of the automaton to at most two, meaning that to each state and input symbol, there exist at most two distinct successor states. The constructed Büchi automaton of non-determinism degree two and the given Büchi automaton of arbitrary non-determinism degree will accept the same ω-language. |
| |
Keywords: | Formal languages Bü chi automata Non-determinism Regular ω-languages |
本文献已被 ScienceDirect 等数据库收录! |
|