An Improved Construction of Deterministic Omega-automaton Using Derivatives

• Autorzy: Redziejowski R.R.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

omega-regular languages; automata; derivative automaton; run tree

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 3/4
• Strony: 393--406
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Redziejowski R.R.

• Ceremonimästarvägen 10, SE-181 40 Lidingö, Sweden,

Bibliografia

• [1] Brzozowski, J. A.: Derivatives of Regular Expressions, Journal of the ACM, 11(4), October 1964, 481-494.
• [2] Owens, S., Reppy, J., Turon, A.: Regular-expression derivatives re-examined, Journal of Functional Programming, 19(2), 2009, 173-190.
• [3] Piterman, N.: From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata, Logical Methods in Computer Science, 3(3), 2007.
• [4] Redziejowski, R. R.: Construction of a deterministic ω-automaton using derivatives, Informatique Théorique et Applications, 33, 1999, 133-158.
• [5] Safra, S.: On The Complexity of ω-Automata, Proc. 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988.
• [6] Safra, S.: Complexity of Automata on Infinite Objects, Master Thesis, Weizmann Institute of Science, Rehovot, Israel, March 1989.