Solution sets for equations over free groups are EDT0L languages

DOI10.1142/S0218196716500363zbMath1401.68156OpenAlexW2494564294MaRDI QIDQ2821818

Laura Ciobanu, Volker Diekert, Murray J. Elder

Publication date: 23 September 2016

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196716500363

zbMATH Keywords

compressionindexed languageEDT0L languageequation in a free groupfree monoid with involution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Related Items (14)

The Diophantine problem in the classical matrix groups ⋮ The complexity of solution sets to equations in hyperbolic groups ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Equations in virtually abelian groups: Languages and growth ⋮ Word equations in the context of string solving ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ EDT0L solutions to equations in group extensions ⋮ Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Applications of L systems to group theory ⋮ Unnamed Item ⋮ Equations in groups that are virtually direct products ⋮ On equations and first-order theory of one-relator monoids ⋮ Diophantine problems in solvable groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• An efficient algorithm for solving word equations
• Recompression
• Solution Sets for Equations over Free Groups are EDT0L Languages
• Finding All Solutions of Equations in Free Groups and Monoids with Involution

This page was built for publication: Solution sets for equations over free groups are EDT0L languages