# The completely distributive lattice of machine invariant sets of infinite words

Discussiones Mathematicae - General Algebra and Applications (2007)

- Volume: 27, Issue: 1, page 109-121
- ISSN: 1509-9415

## Access Full Article

top## Abstract

top## How to cite

topAleksandrs Belovs, and Jānis Buls. "The completely distributive lattice of machine invariant sets of infinite words." Discussiones Mathematicae - General Algebra and Applications 27.1 (2007): 109-121. <http://eudml.org/doc/276885>.

@article{AleksandrsBelovs2007,

abstract = {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.},

author = {Aleksandrs Belovs, Jānis Buls},

journal = {Discussiones Mathematicae - General Algebra and Applications},

keywords = {mealy machine; machine invariant class; completely distributive lattice; length; width; Mealy machine; lattice of machine-invariant classes; subword complexity; growth function},

language = {eng},

number = {1},

pages = {109-121},

title = {The completely distributive lattice of machine invariant sets of infinite words},

url = {http://eudml.org/doc/276885},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Aleksandrs Belovs

AU - Jānis Buls

TI - The completely distributive lattice of machine invariant sets of infinite words

JO - Discussiones Mathematicae - General Algebra and Applications

PY - 2007

VL - 27

IS - 1

SP - 109

EP - 121

AB - 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.

LA - eng

KW - mealy machine; machine invariant class; completely distributive lattice; length; width; Mealy machine; lattice of machine-invariant classes; subword complexity; growth function

UR - http://eudml.org/doc/276885

ER -

## References

top- [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. Zbl1169.68560
- [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. Zbl0481.68052
- [4] B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002. Zbl1002.06001
- [5] J.A. Goguen, L-fuzzy sets, J. Math. Anal. Appl. 8 (1967), 145-174. Zbl0145.24404
- [6] J. Hartmanis and R.E. Stearns, Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1966. Zbl0154.41701
- [7] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer-Verlag, Berlin, Heidelberg 1999. Zbl0935.68056
- [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. Zbl0875.68657
- [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. Zbl0604.68058
- [11] A.A. Kurmit, Posledovatel'naya dekompoziciya konechnyh avtomatov, Sequential Decomposition of Finite Automata, Riga, Zinatne (Russian) 1982. Zbl0558.68049
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.