Lower bounds on words separation: are there short identities in transformation semigroups?
From MaRDI portal
Publication:2401420
zbMath1372.68156arXiv1609.03199MaRDI QIDQ2401420
Olga Karpova, Andrei A. Bulatov, Konstantin Startsev, Arseny M. Shur
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
Combinatorics on words (68R15) Formal languages and automata (68Q45) Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic theory of languages and automata (68Q70) Symmetric groups (20B30)
Related Items
A survey on varieties generated by small semigroups and a companion website ⋮ Separating words problem over groups ⋮ Identities in twisted Brauer monoids ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- On a generalization of abelian equivalence and complexity of infinite words
- Identity checking problem for transformation monoids
- Complexity of the identity checking problem for finite semigroups.
- Separating strings with small automata
- Identities in full transformation semigroups
- On the diameter of permutation groups.
- Divisibility and laws in finite simple groups.
- Asymptotic growth and least common multiples in groups
- Separating words with machines and groups
- Remarks on Separating Words