On_The_Structure_of_Solution_Sets_to_Regular_Word_Equations.pdf (582.79 kB)

On the structure of solution sets to regular word equations

Download (582.79 kB)
conference contribution
posted on 16.10.2020 by Joel Day, Florin Manea
© 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.

Funding

DFG grant MA 5725/2-1

History

School

  • Science

Department

  • Mathematical Sciences

Published in

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Pages

124:1--124:16

Publisher

Leibniz-Zentrum

Version

VoR (Version of Record)

Rights holder

© The authors

Publisher statement

This is an Open Access Article. It is published by Leibniz-Zentrum under the Creative Commons Attribution 3.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/3.0/

Publication date

2020-06-29

Copyright date

2020

ISBN

9783959771382

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics (LIPIcs); 168

Language

en

Editor(s)

Artur Czumaj and Anuj Dawar and Emanuela Merelli

Location

Saarbrücken, Germany

Event dates

July 8-11, 2020

Depositor

Dr Joel Day (email: J.Day@lboro.ac.uk | regno: 5019890). Deposit date: 14 October 2020

Licence

Exports

Logo branding

Categories

Licence

Exports