首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题:The Hardness of Solving Simple Word Equations
  • 本地全文:下载
  • 作者:Joel D. Day ; Florin Manea ; Dirk Nowotka
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:83
  • 页码:18:1-18:14
  • DOI:10.4230/LIPIcs.MFCS.2017.18
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Word Equations; Regular Patterns; Regular Constraints
国家哲学社会科学文献中心版权所有