English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Recompression: Word Equations and Beyond

Jeż, A. (2013). Recompression: Word Equations and Beyond. In M.-P. Beal, & O. Carton (Eds.), Developments in Language Theory (pp. 12-26). Berlin: Springer. doi:10.1007/978-3-642-38771-5_2.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3F32-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-9CC2-1
Genre: Conference Paper
Latex : Recompression: {Word} Equations and Beyond

Files

show Files
hide Files
:
recompression_DLT.pdf (Any fulltext), 436KB
 
File Permalink:
-
Name:
recompression_DLT.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Jeż, Artur1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We present the technique of local recompression on the example of word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a `fresh' letter, which can be seen as a bottom-up building of an SLP (Straight-Line Programme) for the solution of the word equation, i.e. a compression. Using this technique we give a simple proof that satisfiability of word equations is in PSPACE. Furthermore we sketch the applications for some problems regarding the SLP compressed strings.

Details

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: 836DB038AE110EFEC1257C67004F0785-Jez2013DLTII
DOI: 10.1007/978-3-642-38771-5_2
BibTex Citekey: Jez2013DLTII
 Degree: -

Event

show
hide
Title: 17th International Conference on Developments in Language Theory
Place of Event: Marne-la-Vallée, France
Start-/End Date: 2013-06-18 - 2013-06-21

Legal Case

show

Project information

show

Source 1

show
hide
Title: Developments in Language Theory
  Abbreviation : DLT 2013
  Subtitle : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings
Source Genre: Proceedings
 Creator(s):
Beal, Marie-Pierre1, Editor
Carton, Olivier1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 12 - 26 Identifier: ISBN: 978-3-642-38770-8

Source 2

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