|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2010, Number 1, Pages 69–73
(Mi ivm6553)
|
|
|
|
The mirror image of the language of 2-synchronizing words
I. V. Petrov Chair of Algebra and Discrete Mathematics, Ural State University, Ekaterinburg, Russia
Abstract:
A word $w$ over a finite alphabet $\Sigma$ is called $n$-synchronizing if for each deterministic finite automaton $\mathscr A=\langle Q,\Sigma,\delta\rangle$ such that $|Q|=n+1$ the equality $|\delta(Q,w)|=1$ holds provided that $|\delta(Q,u)|=1$ for some word $u\in\Sigma^*$ (depending on $\mathscr A$). In this paper we prove that the language of all 2-synchronizing words is closed under the mapping that associates each word $w=a_1a_2\cdots a_t\in\Sigma^*$ with its mirror image $\overleftarrow w=a_t\cdots a_2a_1$.
Keywords:
synchronizing word, universal synchronizing word, synchronizable automaton, mirror image, formal language.
Received: 03.02.2007
Citation:
I. V. Petrov, “The mirror image of the language of 2-synchronizing words”, Izv. Vyssh. Uchebn. Zaved. Mat., 2010, no. 1, 69–73; Russian Math. (Iz. VUZ), 54:1 (2010), 55–58
Linking options:
https://www.mathnet.ru/eng/ivm6553 https://www.mathnet.ru/eng/ivm/y2010/i1/p69
|
Statistics & downloads: |
Abstract page: | 416 | Full-text PDF : | 50 | References: | 38 | First page: | 3 |
|