Recompression: a simple and powerful technique for word equations

DOI10.1145/2743014MaRDI QIDQ3177761zbMATH OpenOpenAlexFDO

Authors Artur Jeż

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2743014

zbMATH Keywords

exponent of periodicitysemantic unificationstring unificationword equations

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 6678923
• Recompression: word equations and beyond
• Recompression: technique for word equations and compressed data
• Word equations in nondeterministic linear space
• Word equations in non-deterministic linear space

Cited in

(39)

• On the complexity of the smallest grammar problem over fixed alphabets
• Internal dictionary matching
• The complexity of solution sets to equations in hyperbolic groups
• Word equations in the context of string solving
• Word equations in non-deterministic linear space
• On PSPACE generation of a solution set of a word equation and its applications
• On the Solvability Problem for Restricted Classes of Word Equations
• Solution sets for equations over free groups are EDT0L languages
• scientific article; zbMATH DE number 6678923 (Why is no real title available?)
• Solutions to twisted word equations and equations in virtually free groups
• Approximation of smallest linear tree grammar
• Finding all solutions of equations in free groups and monoids with involution
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• On the complexity of solving restricted word equations
• Diophantine problems in solvable groups
• The Diophantine problem in the classical matrix groups
• Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE
• The hardness of solving simple word equations
• Word equations in nondeterministic linear space
• Recompression: word equations and beyond
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Solving word equations (and other unification problems) by recompression (invited talk)
• Word equations in synergy with regular constraints
• Decision procedures for sequence theories
• On the structure of solution-sets to regular word equations
• Internal pattern matching queries in a text and applications
• Program specialization as a tool for solving word equations
• Hardness results for constant-free pattern languages and word equations
• On the structure of solution sets to regular word equations
• Dynamic longest common substring in polylogarithmic time
• On solving string equations via powers and Parikh images
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Expressive completeness of separation logic in block-based cloud storage systems
• Reachability and bounded emptiness problems of constraint automata with prefix, suffix and infix
• Solving one variable word equations in the free group in cubic time
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Word equations in synergy with regular constraints (extended version)
• Quadratic equations in graph products of groups and the exponent of periodicity
• Recompression: technique for word equations and compressed data

This page was built for publication: Recompression: a simple and powerful technique for word equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177761)