DLT 2003: Developments in Language Theory pp 254-265

On Enumeration of Müller Automata

• Michael Domaratzki
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)

Abstract

In this paper, we consider the problem of enumeration of Müller automata with a given number of states. Given a Müller automata, its acceptance table $$\mathcal{F}$$ is admissible if, for each element $$f \in \mathcal{F}$$, there exists an infinite word whose set of states visited infinitely often is exactly f.

We consider acceptance tables in Müller automata which are never admissible, regardless of the choice of transition function δ. We apply the results to enumeration of Müller automata by number of states.

References

1. 1.
Câmpeanu, C., Păun, A.: The number of similarity relations and the number of minimal deterministic finite cover automata. In Champarnaud, J.M., Maurel, D., eds.: Pre-Proceedings of the Seventh International Conference on Implementation and Application of Automata. (2002) 71–80Google Scholar
2. 2.
Domaratzki, M.: Improved bounds on the number of automata accepting finite languages. In Ito, M., Toyama, M., eds.: DLT 2002: Developments in Language Theory, Sixth International Conference. (2002) 159–181Google Scholar
3. 3.
Domaratzki, M., Kisman, D., Shallit, J.: On the number of distinct languages accepted by finite automata with n states. To appear, J. Automata, Languages and Combinatorics 7 (2002) 469–486Google Scholar
4. 4.
Liskovets, V.: Exact enumeration of acyclic automata. To appear, Formal Power Series and Algebraic Combinatorics 2003 (2003)Google Scholar
5. 5.
Perrin, D., Pin, J.E.: Infinite Words. Available electronically at http://www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html (2003)Google Scholar
6. 6.
Thomas, W.: Automata on infinite objects. In van Leeuwen, J., ed.: Handbook of Theoretical Computer Science. Elsevier (1990) 133–192Google Scholar
7. 7.
Staiger, L.: Finite-state ω-languages. J. Comp. Sys. Sci. 37 (1983) 434–448
8. 8.
Robinson, R.W.: Counting strongly connected finite automata. In Alavi, Y., Chartrand, G., Lesniak, L., Lick, D., Wall, C., eds.: Graph Theory with Applications to Algorithms and Computer Science. (1985) 671–685Google Scholar
9. 9.
Liskovets, V.: The number of connected initial automata. Cybernetics 5 (1969) 259–262
10. 10.
Korshunov, A.: Enumeration of finite automata (in Russian). Problemy Kibernetiki 34 (1978) 5–82