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):

Portier, Natacha
Wilke, Thomas

dblp
dblp

Not MPII Editor(s):

Portier, Natacha
Wilke, Thomas

BibTeX cite key*:

Jez2013STACS

Title, Booktitle

Title*:

Recompression: a simple and powerful technique for word equations


25.pdf (532.37 KB)

Booktitle*:

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Event, URLs

URL of the conference:

http://www.stacs2013.uni-kiel.de/

URL for downloading the paper:

http://drops.dagstuhl.de/opus/volltexte/2013/3937

Event Address*:

Kiel, Germany

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

27 February 2013

Event End Date:

2 March 2013

Publisher

Name*:

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

URL:

http://www.dagstuhl.de/publikationen/

Address*:

Dagstuhl, Germany

Type:


Vol, No, Year, pp.

Series:

Leibniz International Proceedings in Informatics (LIPIcs)

Volume:

20

Number:


Month:

February

Pages:

233-244

Year*:

2013

VG Wort Pages:


ISBN/ISSN:

978-3-939897-50-7

Sequence Number:


DOI:

10.4230/LIPIcs.STACS.2013.233



Note, Abstract, ©


(LaTeX) Abstract:

We present an application of a local recompression technique,
previously developed by the author in the context of compressed membership problems
and compressed pattern matching, to 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 compression of the solution
of the given word equation, to be more specific, building an SLP (Straight-Line Programme)
for the solution of the word equation.


Using this technique we give new self-contained
proofs of many known results for word equations:
the presented nondeterministic algorithm
runs in $O(n \log n)$ space and in time polynomial in $\log N$ and $n$,
where $N$ is the size of the length-minimal solution of the word equation.
It can be easily generalised
to a generator of all solutions of the word equation.
A further analysis of the algorithm yields a doubly exponential
upper bound on the size of the length-minimal solution.
The presented algorithm does not use
exponential bound on the exponent of periodicity.
Conversely, the analysis of the algorithm yields
a new proof of the exponential bound on exponent of periodicity.
For $O(1)$ variables with arbitrary many appearances
it works in linear space.

Keywords:

Word equations, exponent of periodicity, string unification



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

External Affiliations:

Institute of Computer Science, University of Wroclaw

Audience:

popular

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{Jez2013STACS,
AUTHOR = {Jez, Artur},
EDITOR = {Portier, Natacha and Wilke, Thomas},
TITLE = {Recompression: a simple and powerful technique for word equations},
BOOKTITLE = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
PUBLISHER = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
YEAR = {2013},
VOLUME = {20},
PAGES = {233--244},
SERIES = {Leibniz International Proceedings in Informatics (LIPIcs)},
ADDRESS = {Kiel, Germany},
MONTH = {February},
ISBN = {978-3-939897-50-7},
DOI = {10.4230/LIPIcs.STACS.2013.233},
}


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
02/25/2013 04:14:01 PM
Revisions
2.
1.
0.

Editor(s)
Artur Jez
Artur Jez
Artur Jez

Edit Dates
01/21/2014 03:15:44 PM
01/21/2014 03:14:28 PM
02/25/2013 04:14:01 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
25.pdf