Lattice structures of automata

Abstract

This paper is motivated by the results in [M. Ito, Algebraic structures of automata, Theoretical Computer Science 428 (2012) 164-168.]. Structures and the number of subautomata of a finite automaton are investigated. It is shown that the set of all subautomata of a finite automaton A is upper semilattice. We give conditions which allow us to determine whether for a finite upper semilattice (L;≤) there exists an automaton A such that the set of all subautomata of A under set inclusion is isomorphic to (L;≤). Examples illustrating the results are presented.

Keywords

• Automaton
• Subautomaton
• upper semilattice
• decomposition of an automaton
• crisp deterministic fuzzy automaton

References

1. Birkhoff, G., Lattice theory, Amer. Math. Soc., 1973.
2. Calugareanu, G., Lattice Concepts of Module Theory, Springer Science+Business Media Dordrecht, 2000.
3. Ćirić, M., Bogdanović, S., The Lattice of Subautomata of an Automaton - A Survey, Publications de l'Institut Mathématique, 64 (78) (1998), 165-182 .
4. Atani, S. E., Bazari, M. Sedghi Shanbeh, Decomposable Fillters of Lattces, Kragujevac Journal of Mathematics, 43(1) (2019), 59-73.
5. Halaš , R., Relative polars in ordered sets, Carleton University, Czechoslovak Math. J., 50 (125) (2) 2000, 415-429.
6. Halaš, R., Jukl, M., On Beck;s coloring of posets, Discrete Math., 309 (13) (2009), 4584-4589.
7. Ito, M., Algebraic structures of automata, Theoretical Computer Science, 428 (2012), 164-168.
8. Ito, M., Algebraic structures of automata and Languages, World Scientific, Singapore, 2004.

9. Muir, A., Warner, M. W., Lattice valued relations and automata, Discrete App. Math., 7 (1984), 65-78.
10. Saliĭ, V. N., Universal Algebra and Automata, Saratov Univ., Saratov, 1988. (in Russian).
11. Smid, A. Maheshwari Michiel, Introduction to Theory of Computation, Ottawa, 2016.
12. Verma, R., Tiwri, S. P., Distinguishability and Completeness of Crispdeterministic Fuzzy Automata, Iranian Journal of Fuzzy Systems, 5 (2017), 19-30.