Campus Event Calendar
Event Entry
What and Who
One variable word equations in linear time
Artur Jeż
Max-Planck-Institut für Informatik - D1
Lecture
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 5 February 2013
13:00
30 Minutes
E1 4
021
Saarbrücken
Warning: New Room!
Abstract
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 + #X log n), where #X is the number of appearances of the variable in the equation. This matches the previously-best algorithm due to Dabrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis the running time is lowered to O(n) (in RAM model).
Contact
Artur Jez
--email hidden
passcode not visible
logged in users only
Artur Jez, 01/30/2013 18:04 -- Created document.