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.STACS.2017.2
URN: urn:nbn:de:0030-drops-70280
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7028/
Go to the corresponding LIPIcs Volume Portal

Jez, Artur

Recompression: New Approach to Word Equations and Context Unification (Invited Talk)

pdf-format:
LIPIcs-STACS-2017-2.pdf (0.3 MB)

Abstract

Word equations is given by two strings over disjoint alphabets of letters and variables and we ask whether there is a substitution that satisfies this equation. Recently, a new PSPACE solution to this problem was proposed, it is based on compressing simple substrings of the equation and modifying the equation so that such operations are sound. The analysis focuses on the way the equation is stored and changed rather than on the combinatorics of words. This approach greatly simplified many existing proofs and algorithms. In particular, unlike the previous solutions, it generalises to equations over contexts (known for historical reasons as context unification): contexts are terms with one special symbol that represent a missing argument and they can be applied on terms, in which case their argument replaces the special constant.

BibTeX - Entry

@InProceedings{jez:LIPIcs:2017:7028,
  author =	{Artur Jez},
  title =	{{Recompression: New Approach to Word Equations and Context Unification (Invited Talk)}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7028},
  URN =		{urn:nbn:de:0030-drops-70280},
  doi =		{10.4230/LIPIcs.STACS.2017.2},
  annote =	{Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression}
}

Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

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