Recompression: Word Equations and Beyond

Jeż, Artur

doi:10.1007/978-3-642-38771-5_2

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Recompression: Word Equations and Beyond

MPS-Authors

/persons/resource/persons79297

Jeż, Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Jeż, A. (2013). Recompression: Word Equations and Beyond. In M.-P. Beal, & O. Carton (Eds.), Developments in Language Theory (pp. 12-26). Berlin: Springer. doi:10.1007/978-3-642-38771-5_2.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0015-3F32-8

Abstract

We present the technique of local recompression on the example of word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a `fresh' letter, which can be seen as a bottom-up building of an SLP (Straight-Line Programme) for the solution of the word equation, i.e. a compression. Using this technique we give a simple proof that satisfiability of word equations is in PSPACE. Furthermore we sketch the applications for some problems regarding the SLP compressed strings.