Geodesic
The completely distributive lattice of machine invariant sets of infinite words
Discussiones Mathematicae. General Algebra and Applications, Tome 27 (2007) no. 1, pp. 109-121.

Voir la notice de l'article provenant de la source Library of Science

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
Keywords: mealy machine, machine invariant class, completely distributive lattice, length, width 
@article{DMGAA_2007_27_1_a6,
     author = {Belovs, Aleksandrs and Buls, J\={a}nis},
     title = {The completely distributive lattice of machine invariant sets of infinite words},
     journal = {Discussiones Mathematicae. General Algebra and Applications},
     pages = {109--121},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGAA_2007_27_1_a6/}
}
TY  - JOUR
AU  - Belovs, Aleksandrs
AU  - Buls, Jānis
TI  - The completely distributive lattice of machine invariant sets of infinite words
JO  - Discussiones Mathematicae. General Algebra and Applications
PY  - 2007
SP  - 109
EP  - 121
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGAA_2007_27_1_a6/
LA  - en
ID  - DMGAA_2007_27_1_a6
ER  - 
%0 Journal Article
%A Belovs, Aleksandrs
%A Buls, Jānis
%T The completely distributive lattice of machine invariant sets of infinite words
%J Discussiones Mathematicae. General Algebra and Applications
%D 2007
%P 109-121
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGAA_2007_27_1_a6/
%G en
%F DMGAA_2007_27_1_a6
Belovs, Aleksandrs; Buls, Jānis. The completely distributive lattice of machine invariant sets of infinite words. Discussiones Mathematicae. General Algebra and Applications, Tome 27 (2007) no. 1, pp. 109-121. http://geodesic.mathdoc.fr/item/DMGAA_2007_27_1_a6/

[1] J. Berstel and J. Karhumäki, Combinatorics on Words - A Tutorial, Bulletin of the European Association for Theoretical Computer Science 79 (2003), 178-228.

[2] J. Buls, Machine Invariant Classes, p. 207-211 in: 'Proceedings of WORDS'03, 4th International Conference on Combinatorics on Words', September 10-13, 2003, Turku, Finland, Tero Harju and Juhani Karhumäki (Eds.), TUCS General Publication (No 27, August).

[3] J. Dassow, Completeness Problems in the Structural Theory of Automata, Mathematical Research (Band 7), Akademie-Verlag, Berlin 1981.

[4] B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.

[5] J.A. Goguen, L-fuzzy sets, J. Math. Anal. Appl. 8 (1967), 145-174.

[6] J. Hartmanis and R.E. Stearns, Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1966.

[7] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer-Verlag, Berlin, Heidelberg 1999.

[8] B.I. Plotkin, I.Ja. Greenglaz and A.A. Gvaramija, Algebraic Structures in Automata and Databases Theory, World Scientific, Singapore, New Jersey, London, Hong Kong 1992.

[9] D.R. Stinson, Cryptography, Theory and Practice, CRC Press 1995.

[10] V.B. Kudryavcev, S.V. Aleshin and A.S. Podkolzin, Vvedenie v teoriyu avtomatov, An Introduction to the Theory of Automata, Moskva, Nauka (Russian) 1985.

[11] A.A. Kurmit, Posledovatel'naya dekompoziciya konechnyh avtomatov, Sequential Decomposition of Finite Automata, Riga, Zinatne (Russian) 1982.

[12] B.A. Trahtenbrot and Ya.M. Barzdin, Konechnye avtomaty povedenie i sintez, Finite Automata (Behaviour and Synthesis) Moskva, Nauka (Russian) 1970.

[13] V.M. Fomichev, Diskretnaya matematika i kriptologiya, (Discrete Mathematics and Cryptology), Moskva, DIALOG-MIFI (Russian) 2003.