Redziejowski, Roman R.
Construction of a deterministic ω-automaton using derivatives
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2 , p. 133-158
Zbl 0946.68078 | MR 1707967
URL stable : http://www.numdam.org/item?id=ITA_1999__33_2_133_0

Bibliographie

[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