Lattice structures of automata
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,
___
- Birkhoff, G., Lattice theory, Amer. Math. Soc., 1973.
- Calugareanu, G., Lattice Concepts of Module Theory, Springer Science+Business Media Dordrecht, 2000.
- Ćirić, M., Bogdanović, S., The Lattice of Subautomata of an Automaton - A Survey, Publications de l'Institut Mathématique, 64 (78) (1998), 165-182 .
- Atani, S. E., Bazari, M. Sedghi Shanbeh, Decomposable Fillters of Lattces, Kragujevac Journal of Mathematics, 43(1) (2019), 59-73.
- Halaš , R., Relative polars in ordered sets, Carleton University, Czechoslovak Math. J., 50 (125) (2) 2000, 415-429.
- Halaš, R., Jukl, M., On Beck;s coloring of posets, Discrete Math., 309 (13) (2009), 4584-4589.
- Ito, M., Algebraic structures of automata, Theoretical Computer Science, 428 (2012), 164-168.
- Ito, M., Algebraic structures of automata and Languages, World Scientific, Singapore, 2004.
- Muir, A., Warner, M. W., Lattice valued relations and automata, Discrete App. Math., 7 (1984), 65-78.
- Saliĭ, V. N., Universal Algebra and Automata, Saratov Univ., Saratov, 1988. (in Russian).
- Smid, A. Maheshwari Michiel, Introduction to Theory of Computation, Ottawa, 2016.
- Verma, R., Tiwri, S. P., Distinguishability and Completeness of Crispdeterministic Fuzzy Automata, Iranian Journal of Fuzzy Systems, 5 (2017), 19-30.
- ISSN: 1303-5991
- Yayın Aralığı: Yılda 4 Sayı
- Başlangıç: 1948
- Yayıncı: Ankara Üniversitesi