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

Jeż, Artur

Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk)

pdf-format:
LIPIcs-CSL-2020-3.pdf (0.5 MB)

Abstract

In word equation problem we are given an equation u = v, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. This problem was first solved by Makanin and a different solution was proposed by Plandowski only 20 years later, his solution works in PSPACE, which is the best computational complexity bound known for this problem; on the other hand, the only known lower-bound is NP-hardness. In both cases the algorithms (and proofs) employed nontrivial facts on word combinatorics.
In the paper I will present an application of a recent technique of recompression, which simplifies the known proofs and (slightly) lowers the complexity to linear nondeterministic space. The technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. In particular, no combinatorial properties of strings are used.
The approach turns out to be quite robust and can be applied to various generalizations and related scenarios (context unification, i.e. equations over terms; equations over traces, i.e. partially ordered words; ...).

BibTeX - Entry

@InProceedings{je:LIPIcs:2020:11646,
  author =	{Artur Je?},
  title =	{{Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk)}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11646},
  URN =		{urn:nbn:de:0030-drops-116468},
  doi =		{10.4230/LIPIcs.CSL.2020.3},
  annote =	{Keywords: word equation, context unification, equations in groups, compression}
}

Keywords: word equation, context unification, equations in groups, compression
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

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