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/
Jez, Artur
Recompression: New Approach to Word Equations and Context Unification (Invited Talk)
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 |