The completely distributive lattice of machine invariant sets of infinite words

• Autorzy: Aleksandrs Belovs , Jānis Buls
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

mealy machine   machine invariant class   completely distributive lattice   length   width  

Kategorie tematyczne

• 68Q45: Formal languages and automata
• 68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
• 68R15: Combinatorics on words
• 06D10: Complete distributivity
• 68Q70: Algebraic theory of languages and automata

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae - General Algebra and Applications
• Rocznik: 2007
• Tom: 27
• Numer: 1
• Strony: 109-121

Daty

wydano

2007

otrzymano

2006-04-25

poprawiono

2006-07-06

Twórcy

autor

Aleksandrs Belovs

• Department of Mathematics, University of Latvia, Raiņa bulvāris 19, Rīga, LV-1586 Latvia

autor

Jānis Buls

• Department of Mathematics, University of Latvia, Raiņa bulvāris 19, Rīga, LV-1586 Latvia

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgaa.1122