首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:Hardness Results for Constant-Free Pattern Languages and Word Equations
  • 本地全文:下载
  • 作者:Aleksi Saarela
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:168
  • 页码:140:1-140:15
  • DOI:10.4230/LIPIcs.ICALP.2020.140
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study constant-free versions of the inclusion problem of pattern languages and the satisfiability problem of word equations. The inclusion problem of pattern languages is known to be undecidable for both erasing and nonerasing pattern languages, but decidable for constant-free erasing pattern languages. We prove that it is undecidable for constant-free nonerasing pattern languages. The satisfiability problem of word equations is known to be in PSPACE and NP-hard. We prove that the nonperiodic satisfiability problem of constant-free word equations is NP-hard. Additionally, we prove a polynomial-time reduction from the satisfiability problem of word equations to the problem of deciding whether a given constant-free equation has a solution morphism α such that α(xy) ≠α(yx) for given variables x and y.
  • 关键词:Combinatorics on words; pattern language; word equation
国家哲学社会科学文献中心版权所有