English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Finding All Solutions of Equations in Free Groups and Monoids with Involution

Diekert, V., Jeż, A., & Plandowski, W. (2014). Finding All Solutions of Equations in Free Groups and Monoids with Involution. In E. Hirsch, S. Kuznetsov, J.-E. Pin, & N. Vereshchagin (Eds.), Computer Science - Theory and Applications (pp. 1-15). Berlin: Springer. doi:10.1007/978-3-319-06686-8_1.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-559E-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A3CD-7
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Diekert, Volker1, Author
Jeż, Artur2, Author           
Plandowski, Wojciech1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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érrez 2001). As a byproduct we obtain a direct proof that it is decidable whether or not the solution set is finite.

Details

show
hide
Language(s): eng - English
 Dates: 20142014-06
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Jez2014CSR
DOI: 10.1007/978-3-319-06686-8_1
 Degree: -

Event

show
hide
Title: 9th International Computer Science Symposium in Russia
Place of Event: Moscow, Russia
Start-/End Date: 2014-07-07 - 2014-07-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Computer Science - Theory and Applications
  Subtitle : 9th International Computer Science Symposium in Russia, CSR 2014 ; Moscow, Russia, June 7-11, 2014 ; Proceedings
  Abbreviation : CSR 2014
Source Genre: Proceedings
 Creator(s):
Hirsch, Edward1, Editor
Kuznetsov, Sergei1, Editor
Pin, Jean-Eric1, Editor
Vereshchagin, Nikolai1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1 - 15 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 8476 Sequence Number: - Start / End Page: - Identifier: -