The completely distributive lattice of machine invariant sets of infinite words

Aleksandrs Belovs; Jānis Buls

Discussiones Mathematicae - General Algebra and Applications (2007)

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

Abstract

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

How to cite

top

Aleksandrs 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. [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. [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. [3] J. Dassow, Completeness Problems in the Structural Theory of Automata, Mathematical Research (Band 7), Akademie-Verlag, Berlin 1981. Zbl0481.68052
  4. [4] B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002. Zbl1002.06001
  5. [5] J.A. Goguen, L-fuzzy sets, J. Math. Anal. Appl. 8 (1967), 145-174. Zbl0145.24404
  6. [6] J. Hartmanis and R.E. Stearns, Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Inc., Englewood Cliffs, New Jersey 1966. Zbl0154.41701
  7. [7] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer-Verlag, Berlin, Heidelberg 1999. Zbl0935.68056
  8. [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. [9] D.R. Stinson, Cryptography, Theory and Practice, CRC Press 1995. 
  10. [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. [11] A.A. Kurmit, Posledovatel'naya dekompoziciya konechnyh avtomatov, Sequential Decomposition of Finite Automata, Riga, Zinatne (Russian) 1982. Zbl0558.68049
  12. [12] B.A. Trahtenbrot and Ya.M. Barzdin, Konechnye avtomaty povedenie i sintez, Finite Automata (Behaviour and Synthesis) Moskva, Nauka (Russian) 1970. 
  13. [13] V.M. Fomichev, Diskretnaya matematika i kriptologiya, (Discrete Mathematics and Cryptology), Moskva, DIALOG-MIFI (Russian) 2003. 

NotesEmbed ?

top

You must be logged in to post comments.