Loading…
The hardness of solving simple word equations
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). S...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Default Conference proceeding |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/2134/37618 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1818168604856680448 |
|---|---|
| author | Joel Day Florin Manea Dirk Nowotka |
| author_facet | Joel Day Florin Manea Dirk Nowotka |
| author_sort | Joel Day (5986415) |
| collection | Figshare |
| description | 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. |
| format | Default Conference proceeding |
| id | rr-article-9403886 |
| institution | Loughborough University |
| publishDate | 2017 |
| record_format | Figshare |
| spelling | rr-article-94038862017-12-01T00:00:00Z The hardness of solving simple word equations Joel Day (5986415) Florin Manea (7168022) Dirk Nowotka (7168028) Other information and computing sciences not elsewhere classified Word equations Regular patterns Regular constraints Information and Computing Sciences not elsewhere classified 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. 2017-12-01T00:00:00Z Text Conference contribution 2134/37618 https://figshare.com/articles/conference_contribution/The_hardness_of_solving_simple_word_equations/9403886 CC BY 3.0 |
| spellingShingle | Other information and computing sciences not elsewhere classified Word equations Regular patterns Regular constraints Information and Computing Sciences not elsewhere classified Joel Day Florin Manea Dirk Nowotka The hardness of solving simple word equations |
| title | The hardness of solving simple word equations |
| title_full | The hardness of solving simple word equations |
| title_fullStr | The hardness of solving simple word equations |
| title_full_unstemmed | The hardness of solving simple word equations |
| title_short | The hardness of solving simple word equations |
| title_sort | hardness of solving simple word equations |
| topic | Other information and computing sciences not elsewhere classified Word equations Regular patterns Regular constraints Information and Computing Sciences not elsewhere classified |
| url | https://hdl.handle.net/2134/37618 |