Questions tagged [word-problem]
The word-problem tag has no usage guidance.
13 questions
4
votes
1
answer
141
views
Given a word $w$ in the braid group $B_n$, representing a pure braid, find the image of $w$ in the abelianization of $P_n$
Suppose I have a word $w$ in the standard generators $\sigma_1,\dots,\sigma_{n-1}$ of the braid group $B_n$ representing an element which we know belongs to the pure braid group $P_n$, is there an ...
- 765
28
votes
5
answers
4k
views
Are there any computational problems in groups that are harder than P?
There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).
Then there are several classes of groups like ...
- 391
2
votes
1
answer
232
views
Examples of group families with solvable uniform word problem
I would like to know of any examples of families of groups that are known (or conjectured) to have a solvable uniform word problem, i.e. an algorithm that given a presentation $P$ of a group in the ...
- 1,936
1
vote
1
answer
259
views
Which properties can be read off the balls of a Cayley graph?
For which properties (P) [of groups] does the following hold:
given a group $G$ which has a finite presentation with at most $n$ relations of length at most $\ell$, there is a $R(n,\ell)$ so that, if ...
- 4,432
2
votes
0
answers
219
views
Occurrence problem for commutator subgroup
The occurrence problem asks if, given a group $G$ and a subgroup $H$ of $G$, there exists an algorithm to decide whether $x\in G$ belongs to $H$.
Let $G$ be a group that has solvable word problem.
Is ...
- 115
5
votes
2
answers
489
views
The generalized word problem on groups
Given some group $G$ that is generated by $a$ and $b$, each of which has infinite order, and some free subgroup $N$ generated by $a^k$ and $b^k$, is there any algorithm that tells me if some $x \in G$ ...
- 469
3
votes
2
answers
423
views
Finite groups with small God's numbers
Let $G$ be a finite group and $S$ be generating set it. Now given all words with alphabet $S$, then there exists a minimum word length $N(S,G)$ such that all group elements are represented by a word ...
- 43
14
votes
1
answer
764
views
Finite-dimensional version of the word problem for groups
The (uniform) word problem for groups can be stated in several equivalent ways:
Word Problem for Groups (WP)
Instance: A finite presentation of a group G and an element w of G as a product of ...
- 1,959
14
votes
2
answers
1k
views
Economical hard word problem
Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am ...
- 29k
3
votes
0
answers
67
views
Word problem for finitely presented bounded lattices
There is a solution to the word problem for finitely presented (non-bounded) lattices, as well as a solution to the word problem for free bounded lattices. I am assuming that there is a solution to ...
- 203
4
votes
0
answers
140
views
Order problem in nilpotent groups
Let $G$ be a f.g. nilpotent group. I wanted to know if the order problem (given $g \in G$, deciding if there exists $n$ s.t. $g^n=e$) is decidable in $G$? In such a group, the word problem is ...
- 333
7
votes
1
answer
251
views
Asymptotics of the number of required Dehn relators in hyperbolic groups
If $G = \langle X | R \rangle$ is a $\delta$-hyperbolic group presentation, then Dehn's algorithm provides a linear time solution to the word problem, but the linear constant is horribly exponential ...
- 565
3
votes
0
answers
190
views
Universal polygraphic factorization of strict ω-categories relative to a cobase
Recall from 1 that a cofibration of strict ω-categories is a retract of relative $I$-cell complexes, where $I$ denotes the set of boundary inclusions $\partial D^n \hookrightarrow D^n$, where $D_n$ ...
- 19.6k