Construction of a deterministic ω-automaton using derivatives
Redziejowski, Roman R.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 133-158 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_2_133_0,
     author = {Redziejowski, Roman R.},
     title = {Construction of a deterministic $\omega $-automaton using derivatives},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {133-158},
     mrnumber = {1707967},
     zbl = {0946.68078},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_2_133_0}
}

Redziejowski, Roman R. Construction of a deterministic $\omega $-automaton using derivatives. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 133-158. http://gdmltest.u-ga.fr/item/ITA_1999__33_2_133_0/

[1] V. Antimirov, Partial derivatives of regular expressions and finite automata constructions. In STACS 95, E.W. Mayr and C. Puech, Eds., Springer-Verlag (1995) 455-466. | MR 1379579

[2] J. A. Brzozowski, Derivatives of regular expressions. J. Assoc. Comput. Mach. 11 (1964) 481-494. | MR 174434 | Zbl 0225.94044

[3] J. A. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19-35. | MR 549752 | Zbl 0415.68023

[4] J. H. Conway, Regular Algebra and Finite Machines. Chapman and Hall (1971). | Zbl 0231.94041

[5] D. Park, Concurrency and automata on infinite sequences, in Proc. 5th GI Conference, Karlsruhe, Springer-Verlag, Lecture Notes in Computer Science 104 (1981) 167-183. | Zbl 0457.68049

[6] D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, J. van Leeuven, Ed., B, Elsevier Science Publishers (1990) 1-57. | MR 1127186 | Zbl 0900.68312

[7] D. Perrin and J.-E. Pin, Mots infinis. Internal report LITP 93.40, Laboratoire Informatique Théorique et Programmation, Institut Blaise Pascal, 4 Place Jussieu, F-75252 Paris Cedex 05 (1993).

[8] J.-E. Pin, Varieties of Formal Languages. North Oxford Academic (1986). | MR 912694 | Zbl 0655.68095

[9] R. R. Redziejowski, The theory of general events and its application to parallel programming. Technical paper TP 18.220, IBM Nordic Laboratory, Lidingö, Sweden (1972).

[10] S. Safra, On the complexity of ω-automata, in Proc. 29th Annual Symposium on Foundations of Computer Science IEEE (1988) 319-327.

[11] L. Staiger, Finite-state ω-languages. J. Comput. System Sci. 27 (1983) 434-448. | MR 727390 | Zbl 0541.68052

[12] L. Staiger, The entropy of finite-state ω-languages. Problems of Control and Information Theory 14 (1985) 383-392. | MR 820702 | Zbl 0582.94012

[13] L. Staiger, ω-languages. In Handbook of Formal Languages, G. Rozenberg and A. Salomaa, Eds., 3, Springer-Verlag (1997) 339-387. | MR 1470023

[14] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, J. van Leeuven, Ed., B, Elsevier Science Publishers (1990) 133-191. | MR 1127189 | Zbl 0900.68316