About: In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation [Formula: see text], where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space. The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications.

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation [Formula: see text], where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space. The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications. Goto Sponge NotDistinct Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	abstract
value	In this talk I will present the recompression technique on the running example of word equations. In word equation problem we are given an equation [Formula: see text], where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. The recompression technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. The simple analysis focuses on the size of the instance and not on the combinatorial properties of words that are used. The recompression-based algorithm for word equations runs in nondeterministic linear space. The approach turned out to be quite robust and can be applied to various generalized, simplified and related problems, in particular, to problems in the area of grammar compressed words. I will comment on some of those applications.
subject	Algorithms Mathematical logic Theoretical computer science Computational resources Complexity classes
part of	Recompression: Technique for Word Equations and Compressed Data
is abstract of	Recompression: Technique for Word Equations and Compressed Data
is hasSource of	covid:ann/target/872326fa3892b9c6b144fb12d6d31c130880656c covid:ann/target/8ed9ad544be7c607d793062ebda889dd8fad3c61 covid:ann/target/05092fc522c3cf6285a5a69078a02372f3b260a0 covid:ann/target/fc1040d6abdd02c2ca68f51b987d8f8564ebbeab covid:ann/target/fa9caee9858d354381bf7b6247ca4c28789b8d39 »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software