Recompression: a simple and powerful technique for word equations

DOI10.1145/2743014zbMATH Open1403.68374OpenAlexW2161510308MaRDI QIDQ3177761FDOQ3177761

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

Recommendations

• scientific article
• 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

zbMATH Keywords

string unificationword equationssemantic unificationexponent of periodicity

Mathematics Subject Classification ID

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

Cited In (24)

• On the Complexity of Solving Restricted Word Equations
• Title not available (Why is that?)
• Equations over free inverse monoids with idempotent variables
• The hardness of solving simple word equations
• On the Solvability Problem for Restricted Classes of Word Equations
• Solution sets for equations over free groups are EDT0L languages
• The complexity of solution sets to equations in hyperbolic groups
• On PSPACE generation of a solution set of a word equation and its applications
• Word equations in synergy with regular constraints
• On the complexity of the smallest grammar problem over fixed alphabets
• Internal dictionary matching
• On the structure of solution-sets to regular word equations
• Internal pattern matching queries in a text and applications
• Word equations in the context of string solving
• Approximation of smallest linear tree grammar
• Finding all solutions of equations in free groups and monoids with involution
• Title not available (Why is that?)
• Program specialization as a tool for solving word equations
• Word equations in non-deterministic linear space
• Title not available (Why is that?)
• The Diophantine problem in the classical matrix groups
• Decision procedures for sequence theories
• Diophantine problems in solvable groups
• Solutions to twisted word equations and equations in virtually free groups

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)