Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2018) | last year (2017) | two years ago (2016) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Jez, Artur

dblp



Editor(s):

Beal, Marie-Pierre
Carton, Olivier

dblp
dblp

Not MPII Editor(s):

Beal, Marie-Pierre
Carton, Olivier

BibTeX cite key*:

Jez2013DLTII

Title, Booktitle

Title*:

Recompression: Word Equations and Beyond

Booktitle*:

17th International Conference on Developments in Language Theory (DLT 2013)

Event, URLs

URL of the conference:

http://dlt2013.sciencesconf.org/

URL for downloading the paper:

http://dx.doi.org/10.1007/978-3-642-38771-5_2

Event Address*:

Marne-la-Vallée, France

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

18 June 2013

Event End Date:

21 June 2013

Publisher

Name*:

Springer

URL:

http://link.springer.com/

Address*:

Heidelberg, Germany

Type:

Invited paper

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

7907

Number:


Month:


Pages:

12-26

Year*:

2013

VG Wort Pages:


ISBN/ISSN:

978-3-642-38770-8

Sequence Number:


DOI:

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



Note, Abstract, ©


(LaTeX) 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.

Keywords:

Compression, Recompression, Word equations, Algorithms for compressed data



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Jez2013DLTII,
AUTHOR = {Jez, Artur},
EDITOR = {Beal, Marie-Pierre and Carton, Olivier},
TITLE = {Recompression: Word Equations and Beyond},
BOOKTITLE = {17th International Conference on Developments in Language Theory (DLT 2013)},
PUBLISHER = {Springer},
YEAR = {2013},
TYPE = {Invited paper},
VOLUME = {7907},
PAGES = {12--26},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Marne-la-Vallée, France},
ISBN = {978-3-642-38770-8},
DOI = {10.1007/978-3-642-38771-5_2},
}


Entry last modified by Artur Jez, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/21/2014 03:23:12 PM
Revision
0.



Editor
Artur Jez



Edit Date
01/21/2014 03:23:12 PM