License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.18
URN: urn:nbn:de:0030-drops-81233
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8123/
Go to the corresponding LIPIcs Volume Portal

Day, Joel D. ; Manea, Florin ; Nowotka, Dirk

The Hardness of Solving Simple Word Equations

pdf-format:
LIPIcs-MFCS-2017-18.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{day_et_al:LIPIcs:2017:8123,
  author =	{Joel D. Day and Florin Manea and Dirk Nowotka},
  title =	{{The Hardness of Solving Simple Word Equations}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8123},
  URN =		{urn:nbn:de:0030-drops-81233},
  doi =		{10.4230/LIPIcs.MFCS.2017.18},
  annote =	{Keywords: Word Equations, Regular Patterns, Regular Constraints}
}

Keywords: Word Equations, Regular Patterns, Regular Constraints
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI