More Than 1700 Years of Word Equations

DOI10.1007/978-3-319-23021-4_2zbMath1402.68146arXiv1507.03215OpenAlexW2963899211MaRDI QIDQ2947143

Volker Diekert

Publication date: 22 September 2015

Published in: Algebraic Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Computer solution of Diophantine equations (11Y50)

Related Items (7)

String theories involving regular membership predicates: from practice to theory and back ⋮ Equations in virtually abelian groups: Languages and growth ⋮ Word equations in the context of string solving ⋮ EDT0L solutions to equations in group extensions ⋮ On equations and first-order theory of one-relator monoids ⋮ Deterministic regular expressions with back-references ⋮ A logic for document spanners

Cites Work

• Elementary theory of free non-abelian groups.
• Diophantine geometry over groups. VIII: Stability.
• Word-mappings of level 2
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of equations in free groups is in PSPACE
• Solution Sets for Equations over Free Groups are EDT0L Languages
• Satisfiability of word equations with constants is in PSPACE
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Efficient randomized pattern-matching algorithms
• Controlled iteration grammars and full hyper-AFL's
• Complexity of Makanin's algorithm
• Finding All Solutions of Equations in Free Groups and Monoids with Involution
• Diophantine equations, Presburger arithmetic and finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: More Than 1700 Years of Word Equations