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.ICALP.2020.140
URN: urn:nbn:de:0030-drops-125472
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12547/
Go to the corresponding LIPIcs Volume Portal

Saarela, Aleksi

Hardness Results for Constant-Free Pattern Languages and Word Equations

pdf-format:
LIPIcs-ICALP-2020-140.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{saarela:LIPIcs:2020:12547,
  author =	{Aleksi Saarela},
  title =	{{Hardness Results for Constant-Free Pattern Languages and Word Equations}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{140:1--140:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12547},
  URN =		{urn:nbn:de:0030-drops-125472},
  doi =		{10.4230/LIPIcs.ICALP.2020.140},
  annote =	{Keywords: Combinatorics on words, pattern language, word equation}
}

Keywords: Combinatorics on words, pattern language, word equation
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

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