
We study short positive (\btie, containing no inverses) identities of finite symmetric groups. The interest in such identities is inspired by the problem of separating words with finite automata, in particular, with the automata in which each letter acts on the set of states as a permutation. We list all positive identities in symmetric groups $S_5$ and $S_6$ up to length 40 and prove that the shortest identity in the full transformation semigroup $T_5$ has length 48. Then we propose the classification of positive identities and describe the identities from some particular classes. We state a conjecture that the shortest positive identity in a sufficiently big symmetric group is ``numerical'', which implies an $O\big(\frac{\log^2 n}{\log\log n}\big)$ upper bound on the words separation function.
Journal of Automata, Languages and Combinatorics, Volume 26, Numbers 1-2, 2021, 67-89
symmetric group, Symmetric groups, words separation, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), Formal languages and automata, identity, finite automaton
symmetric group, Symmetric groups, words separation, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), Formal languages and automata, identity, finite automaton
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
