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

Diekert, Volker
Jez, Artur
Plandowski, Wojciech

dblp
dblp
dblp

Not MPG Author(s):

Diekert, Volker
Plandowski, Wojciech

Editor(s):

Hirsch, Edward
Kuznetsov, Sergei
Pin, Jean-Eric
Vereshchagin, Nikolai

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Hirsch, Edward
Kuznetsov, Sergei
Pin, Jean-Eric
Vereshchagin, Nikolai

BibTeX cite key*:

Jez2014CSR

Title, Booktitle

Title*:

Finding All Solutions of Equations in Free Groups and Monoids with Involution

Booktitle*:

9th International Computer Science Symposium in Russia (CSR 2014)

Event, URLs

URL of the conference:

http://logic.pdmi.ras.ru/csr2014/

URL for downloading the paper:


Event Address*:

Moscow, Russia

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

7 June 2014

Event End Date:

11 June 2014

Publisher

Name*:

Springer

URL:

www.springer.com

Address*:

Berlin

Type:

Extended abstract

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

8476

Number:


Month:

June

Pages:

1-15

Year*:

2014

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

The aim of this paper is to
describe the set of all solutions of equations in free groups and monoids with involution in the presence of
rational constraints. This became possible due to the recently invented recompression technique of the second author.
He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is powerful enough to simplify proofs for many existing results in the literature. In particular, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints
(Diekert, Hagenah and Guti{\'e}rrez 2001). As a byproduct we obtain a direct proof that it is
decidable whether or not the solution set is finite.



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{Jez2014CSR,
AUTHOR = {Diekert, Volker and Jez, Artur and Plandowski, Wojciech},
EDITOR = {Hirsch, Edward and Kuznetsov, Sergei and Pin, Jean-Eric and Vereshchagin, Nikolai},
TITLE = {Finding All Solutions of Equations in Free Groups and Monoids with Involution},
BOOKTITLE = {9th International Computer Science Symposium in Russia (CSR 2014)},
PUBLISHER = {Springer},
YEAR = {2014},
TYPE = {Extended abstract},
VOLUME = {8476},
PAGES = {1--15},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Moscow, Russia},
MONTH = {June},
}


Entry last modified by Artur Jez, 12/15/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
11/24/2014 02:21:57 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
11/24/2014 04:34:14 PM
11/24/2014 02:21:57 PM