English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  One-variable Word Equations in Linear Time

Jeż, A. (2013). One-variable Word Equations in Linear Time. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, Languages, and Programming (pp. 324-335). Berlin: Springer. doi:10.1007/978-3-642-39212-2_30.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0015-3F4B-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AA21-4
Genre: Conference Paper

Files

show Files
hide Files
:
onevar_submission.pdf (Any fulltext), 414KB
 
File Permalink:
-
Name:
onevar_submission.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: 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).

Details

show
hide
Language(s): eng - English
 Dates: 20132013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: A1BEC266D007CE81C1257C670050C4BF-Jez2013ICALP
DOI: 10.1007/978-3-642-39212-2_30
BibTex Citekey: Jez2013ICALP
 Degree: -

Event

show
hide
Title: 40th International Colloquium on Automata, Languages, and Programming
Place of Event: Riga, Latvia
Start-/End Date: 2013-07-08 - 2013-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages, and Programming
  Abbreviation : ICALP 2013
  Subtitle : 40th International Colloquium, ICALP 2013 ; Riga, Latvia, July 8-12, 2013 ; Proceedings, Part II
Source Genre: Proceedings
 Creator(s):
Fomin, Fedor V.1, Editor
Freivalds, Rūsiņš1, Editor
Kwiatkowska, Marta1, Editor
Peleg, David1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 324 - 335 Identifier: ISBN: 978-3-642-39211-5

Source 2

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