All Questions
Tagged with combinatorics-on-words gr.group-theory
11 questions
17
votes
3
answers
736
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 20.2k
17
votes
0
answers
536
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
13
votes
1
answer
543
views
Number of trivializations of a trivial word in the free group
Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
- 18.4k
12
votes
1
answer
415
views
"Bisecting" a free subgroup with respect to word length
My broad question is regarding the lengths of (reduced) words in a subgroup of a free group.
As motivation, consider the free group $Gp(S)$ where $|S|=n$, that is, a free group of rank $n$. Let $S=\{...
- 949
11
votes
1
answer
328
views
Unique words in dihedral groups
Suppose $x$ is a word over the alphabet $\{0,1\}$.
Let $a$, $b$ be elements of the group Dih$_k$ for some $k$.
Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the ...
- 24.8k
6
votes
2
answers
319
views
Uniqueness of "Limit" of Cyclic Binary Strings
Set-up: By abuse, let $\sigma$ represent both the left shift operator on infinite bi-infinite strings and the cyclic left shift operator on finite strings. (Thus, for example, $\sigma(...01\bar{0}10......
- 115
5
votes
2
answers
387
views
Concatenation of strings [closed]
We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
- 59
5
votes
0
answers
113
views
Computability of the "free envelope rank" of an endomorphism of a free group
Let $F$ be a free group freely generated by the finite set $S$ and $\sigma\colon F\to F$ be a group morphism. We define the free envelope rank of $\sigma$, written $r(\sigma)$, as the smallest $k$ for ...
- 151
4
votes
1
answer
189
views
Equation in the conjugacy class of a free group
I will pose the question in the form in which it originally appeared to me:
Let $a,b,c,d$ be different letters in a finite alphabet $\mathcal{Z}$. Let $Q$ and $R$ be finite words with letters from $\...
- 111
3
votes
0
answers
285
views
Cayley Graphs and Cyclically reduced words [closed]
Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ...
- 949
2
votes
0
answers
189
views
$V$-like actions of $V$
This continues my question about prefix-continuous bijections (since the answer was "yes").
Notation and conventions: Let $A$ be a finite alphabet and $L \subset A^*$ a language. Let $G$ be a group. ...
- 6,652