2023/09/01 by Laura Ciobanu, Ciobanu, Laura, Alex Evetts +3
Computer Science · #03D05 #20F10 #20F65 #68Q45 #Advanced Algebra and Logic #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR) #Logic, programming, and type systems #semigroups and automata theory
paper · doi:10.48550/arxiv.2309.00475
openalex publication_date 2023/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study the satisfiability and solutions of group equations when combinatorial, algebraic and language-theoretic constraints are imposed on the solutions. We show that the solutions to equations with length, lexicographic order, abelianisation or context-free constraints added, can be effectively produced in finitely generated virtually abelian groups. Crucially, we translate each of the constraints above into a rational set in an effective way, and so reduce each problem to solving equations with rational constraints, which is decidable and well understood in virtually abelian groups. A byproduct of our results is that the growth series of a virtually abelian group, with respect to any generating set and any weight, is effectively computable. This series is known to be rational by a result of Benson, but his proof is non-constructive.