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