On the structure of solution sets to regular word equations
conference contributionposted on 16.10.2020 by Joel Day, Florin Manea
Any type of content contributed to an academic conference, such as papers, presentations, lectures or proceedings.
© Joel D. Day and Florin Manea; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). For quadratic word equations, there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation. For regular word equations - those for which each variable occurs at most once on each side of the equation - we investigate the properties of this graph, such as bounds on its diameter, size, and DAG-width, as well as providing some insights into symmetries in its structure. As a consequence, we obtain a combinatorial proof that the problem of deciding whether a regular word equation has a solution is in NP.
DFG grant MA 5725/2-1
- Mathematical Sciences