The completely distributive lattice of machine invariant sets of infinite words
Aleksandrs Belovs ; Jānis Buls
Discussiones Mathematicae - General Algebra and Applications, Tome 27 (2007), p. 109-121 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:276885 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1122,
     author = {Aleksandrs Belovs and J\=anis Buls},
     title = {The completely distributive lattice of machine invariant sets of infinite words},
     journal = {Discussiones Mathematicae - General Algebra and Applications},
     volume = {27},
     year = {2007},
     pages = {109-121},
     zbl = {1132.06303},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1122}
}

Aleksandrs Belovs; Jānis Buls. The completely distributive lattice of machine invariant sets of infinite words. Discussiones Mathematicae - General Algebra and Applications, Tome 27 (2007) pp. 109-121. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1122/

[000] [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. | Zbl 1169.68560

[001] [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).

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

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

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

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

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

[007] [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. | Zbl 0875.68657

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

[009] [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. | Zbl 0604.68058

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

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

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