An Improved Construction of Deterministic Omega-automaton Using Derivatives

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Redziejowski, Roman R.

Affiliations: Giraf's Research, [email protected]

Note: [] Address for correspondence: Ceremonimästarvägen 10, SE-181 40 Lidingö, Sweden

Abstract: In an earlier paper, the author used derivatives to construct a deterministic automaton recognizing the language defined by an ω-regular expression. The construction was related to a determinization method invented by Safra. This paper describes a new construction, inspired by Piterman's improvement to Safra's method. It produces an automaton with fewer states. In addition, the presentation and proofs are simplified by going via a nondeterministic automaton having derivatives as states.

DOI: 10.3233/FI-2012-744

Journal: Fundamenta Informaticae, vol. 119, no. 3-4, pp. 393-406, 2012