MPI-INF D1 Publications: Proceedings Article: One-Variable Word Equations in Linear Time

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor

Author(s):

Jez, Artur

dblp

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

URL of the conference:	http://www.icalp2013.lu.lv/
URL for downloading the paper:	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:	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

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