Studying algorithmic problems for free semi-groups and groups

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05)

Review text

The author studies algorithmic solvability of equations of the form \(w(x_1,x_2,\dots,x_n)=g\) in free semigroups and groups and proves a number of interesting results. The author also studies Diophantine sets and solvability of equations under restrictions to subgroups. Let \(m\) be an integer and let \(m\geq 2\). Denote by \(\Pi_m\) and by \(F_m\) the free semigroup and group, respectively, generated by \(a_1,a_2,\dots,a_m\). We quote here only Theorem 1: The positive \(\forall\exists^3\)-theory of the free semigroup \(\Pi_m\) is algorithmically unsolvable. Theorem 2: The solvability problem for equations of the form \(w(x_1,x_2,\dots,x_n)=g\) in \(\Pi_2\) is NP-complete. Theorem 3: The solvability problem for equations with one coefficient in \(F_2\) is NP-difficult. For the entire collection see [Zbl 0865.00035].

Recommendations

Cited in

(14)

This page was built for publication: Studying algorithmic problems for free semi-groups and groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376048)