Geodesic
Lower bounds on words separation: are there short identities in transformation semigroups?
Andrei A. Bulatov1 ; Olga Karpova2 ; Arseny M. Shur2 ; Konstantin Startsev2
1Simon Fraser University
2Ural Federal University
The electronic journal of combinatorics, Tome 24 (2017) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The words separation problem, originally formulated by Goralcik and Koubek (1986), is stated as follows. Let $Sep(n)$ be the minimum number such that for any two words of length $\le n$ there is a deterministic finite automaton with $Sep(n)$ states, accepting exactly one of them. The problem is to find the asymptotics of the function $Sep$. This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups $T_k$. The known lower bound on $Sep$ stems from the unary identity in $T_k$. We find the first series of identities in $T_k$ which are shorter than the corresponding unary identity for infinitely many values of $k$, and thus slightly improve the lower bound on $Sep(n)$. Then we present some short positive identities in symmetric groups, improving the lower bound on separating words by permutational automata by a multiplicative constant. Finally, we present the results of computer search for short identities for small $k$.
DOI : 10.37236/6450
Classification : 68Q45, 20B30, 20M20, 68Q70, 68R15
Mots-clés : words separation, finite automaton, transformation semigroup, symmetric group, identity

Andrei A. Bulatov  1   ; Olga Karpova  2   ; Arseny M. Shur  2   ; Konstantin Startsev  2

1 Simon Fraser University
2 Ural Federal University 
@article{10_37236_6450,
     author = {Andrei A. Bulatov and Olga Karpova and Arseny M. Shur and Konstantin Startsev},
     title = {Lower bounds on words separation: are there short identities in transformation semigroups?},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {3},
     doi = {10.37236/6450},
     zbl = {1372.68156},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6450/}
}
TY  - JOUR
AU  - Andrei A. Bulatov
AU  - Olga Karpova
AU  - Arseny M. Shur
AU  - Konstantin Startsev
TI  - Lower bounds on words separation: are there short identities in transformation semigroups?
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6450/
DO  - 10.37236/6450
ID  - 10_37236_6450
ER  - 
%0 Journal Article
%A Andrei A. Bulatov
%A Olga Karpova
%A Arseny M. Shur
%A Konstantin Startsev
%T Lower bounds on words separation: are there short identities in transformation semigroups?
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6450/
%R 10.37236/6450
%F 10_37236_6450
Andrei A. Bulatov; Olga Karpova; Arseny M. Shur; Konstantin Startsev. Lower bounds on words separation: are there short identities in transformation semigroups?. The electronic journal of combinatorics, Tome 24 (2017) no. 3. doi: 10.37236/6450

Cité par Sources :