All Questions
Tagged with formal-languages gr.group-theory
9 questions
2
votes
0
answers
86
views
Rewriting systems for finite groups [closed]
This is a question about rewriting systems & languages for finite groups. I'm sure everything must be in the literature somewhere, but I find it hard to navigate the references I have (for example ...
- 2,287
4
votes
0
answers
179
views
A lemma from Jarden's and Lubotzky's paper 'Elementary equivalence of profinite groups'
I have a question about a reduction argument from
Jarden's and Lubotzky's paper 'Elementary equivalence of
profinite groups' in Lemma 1.1 on page 3:
Lemma 1.1: For each positive integer $n$ and each ...
- 5,998
1
vote
1
answer
260
views
The automorphism groups of smallest grammars of a language string are isomorphic
Let $s \in \Sigma^*$ be a formal language string. Consider the automorphism group of $s$, defined to be the set of all permutations of positions of $s$ that leave $s$ fixed. For instance $G(abab) = \...
- 260
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
4
votes
1
answer
191
views
Progress on group languages characterizations
Def. A group language is a recognizable language whose syntactic monoid is a group.
q1. Is it known a "nice" combinatorial characterization of group languages ?
q1.1. If no, is it well understood ...
- 424
6
votes
1
answer
774
views
word problem in free Burnside groups (and other torsion groups)
Question 1. Is it known that for some free Burnside groups the word problem is undecidable?
Provided that the answer is negative, what about the following easier question.
Question 2. Is there a ...
- 3,897
11
votes
5
answers
1k
views
Which Turing machines accept the language of trivial words in a finitely presented group?
Let $G$ be a finitely presented group with generators $g_1, g_1^{-1},\ldots, g_n, g_n^{-1}$. Let $L(G)$ be the language of all those words in $g_1, \ldots, g_n$ which represent the trivial element of $...
- 3,897
3
votes
2
answers
571
views
What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?
For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. :
$$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \...
- 786
27
votes
1
answer
1k
views
Automatic groups - recent progress
Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental ...
- 2,449