equations_reg copy.pdf (672.71 kB)
0/0

The hardness of solving simple word equations

Download (672.71 kB)
conference contribution
posted on 24.04.2019 by Joel Day, Florin Manea, Dirk Nowotka
We investigate the class of regular-ordered word equations. In such equations, each variable occurs at most once in each side and the order of the variables occurring in both left and right hand sides is preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, we obtain that solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the minimal solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. The complexity of solving such word equations under regular constraints is also settled. Finally, we show that a related class of simple word equations, that generalises one-variable equations, is in P.

History

School

  • Science

Department

  • Computer Science

Published in

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Volume

83

Pages

18:1 - 18:14 (14)

Citation

DAY, J.D., MANEA, F. and NOWOTKA, D., 2017. The hardness of solving simple word equations. IN: Larsen, K.G., Bodlaender, H.L. and Raskin, J-F. (eds). 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Aalborg, Denmark, 21-25 August 2017, Article No. 18, pp.18:1-18:14.

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik © The Authors

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution 3.0 Unported (CC BY 3.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/by/3.0/

Publication date

2017

Notes

This is an Open Access article. It is published by Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik 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/

ISBN

9783959770460

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics (LIPIcs);83

Language

en

Location

Aalborg, Denmark

Licence

Exports

Logo branding

Licence

Exports