Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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