Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

DOI10.4230/LIPICS.ICALP.2019.110MaRDI QIDQ5091272zbMATH OpenFDO

Authors Laura Ciobanu, Murray Elder

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1902.07349

zbMATH Keywords

EDT0L languageexistential theoryhyperbolic groupPSPACE

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• The complexity of solution sets to equations in hyperbolic groups
• Solution sets for equations over free groups are EDT0L languages
• Solution sets for equations over free groups are EDT0L languages
• SLP compression for solutions of equations with constraints in free and hyperbolic groups.
• EDT0L solutions to equations in group extensions

Cites work

• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• Addendum to ``Random walk in random groups by M. Gromov.
• ALMOST EVERY GROUP IS HYPERBOLIC
• Applications of L systems to group theory
• Bounded automata groups are co-ET0L
• Canonical representatives and equations in hyperbolic groups
• Compressed Decision Problems in Hyperbolic Groups.
• Controlled iteration grammars and full hyper-AFL's
• Definable sets in a hyperbolic group.
• Finding all solutions of equations in free groups and monoids with involution
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups.
• scientific article; zbMATH DE number 1688361 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 65896 (Why is no real title available?)
• scientific article; zbMATH DE number 1789956 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3805807 (Why is no real title available?)
• scientific article; zbMATH DE number 849252 (Why is no real title available?)
• scientific article; zbMATH DE number 7204548 (Why is no real title available?)
• ON SOME ALGORITHMIC PROPERTIES OF HYPERBOLIC GROUPS
• On some families of languages related to developmental systems
• On the definition of word hyperbolic groups.
• Permutations of context-free, ET0L and indexed languages
• Random walk in random groups.
• Recompression: a simple and powerful technique for word equations
• REGULARITY OF QUASIGEODESICS IN A HYPERBOLIC GROUP
• Satisfiability of word equations with constants is in PSPACE
• Solution sets for equations over free groups are EDT0L languages
• Solutions of word equations over partially commutative structures
• The image of a group in a hyperbolic group
• The isomorphism problem for all hyperbolic groups.
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Word equations in nondeterministic linear space
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM

Cited in

(10)

• The complexity of solution sets to equations in hyperbolic groups
• Word equations in the context of string solving
• Solutions to twisted word equations and equations in virtually free groups
• scientific article; zbMATH DE number 7456062 (Why is no real title available?)
• Equations in virtually abelian groups: Languages and growth
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE
• Groups with context-free Diophantine problem
• Rational subsets of Baumslag-Solitar groups
• On the ET0L subgroup membership problem in bounded automata groups

This page was built for publication: Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

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