MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Jez, Arturdblp
Editor(s):
Fomin, Fedor V.
Freivalds, Rusins
Kwiatkowska, Marta Z.
Peleg, David		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Fomin, Fedor V.
Freivalds, Rusins
Kwiatkowska, Marta Z.
Peleg, David
BibTeX cite key*:
Jez2013ICALP
Title, Booktitle
Title*:
One-Variable Word Equations in Linear Time
Booktitle*:
40th International Colloquium on Automata, Languages, and Programming (ICALP 2013)
Event, URLs
Conference URL::
http://www.icalp2013.lu.lv/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-39212-2_30
Event Address*:
Latvia, Riga
Language:
English
Event Date*
(no longer used):
Organization:
European Association for Theoretical Computer Science
Event Start Date:
8 July 2013
Event End Date:
12 July 2013
Publisher
Name*:
Springer
URL:
http://link.springer.com/
Address*:
Heidelberg, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
7966
Number:
Month:
Pages:
324-335
Year*:
2013
VG Wort Pages:
ISBN/ISSN:
978-3-642-39211-5
Sequence Number:
DOI:
10.1007/978-3-642-39212-2_30
Note, Abstract, ©
Note:
Full version available at http://arxiv.org/abs/1111.3244
(LaTeX) Abstract:
In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations,
is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is $O(n)$ (in RAM model).
Keywords:
Word equations, String unification, One variable equations
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{Jez2013ICALP,
AUTHOR = {Jez, Artur},
 EDITOR = {Fomin, Fedor V. and Freivalds, Rusins and Kwiatkowska, Marta Z. and Peleg, David},
 TITLE = {One-Variable Word Equations in Linear Time},
 BOOKTITLE = {40th International Colloquium on Automata, Languages, and Programming (ICALP 2013)},
 PUBLISHER = {Springer},
 YEAR = {2013},
 ORGANIZATION = {European Association for Theoretical Computer Science},
 VOLUME = {7966},
 PAGES = {324--335},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Latvia, Riga},
 ISBN = {978-3-642-39211-5},
 DOI = {10.1007/978-3-642-39212-2_30},
 NOTE = {Full version available at http://arxiv.org/abs/1111.3244},
}

Entry last modified by Artur Jez, 02/17/2014
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:42:12 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
01/21/2014 04:04:09 PM
01/21/2014 03:42:12 PM