Lower bounds on words separation: are there short identities in transformation semigroups?

zbMath1372.68156arXiv1609.03199MaRDI QIDQ2401420

Andrei A. Bulatov, Arseny M. Shur, Olga Karpova, Konstantin Startsev

Publication date: 8 September 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.03199

zbMATH Keywords

symmetric group; finite automaton; transformation semigroup; identity; words separation

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

20M20: Semigroups of transformations, relations, partitions, etc.

68Q70: Algebraic theory of languages and automata

20B30: Symmetric groups