Doubly-periodic string comparison

DOI10.4230/LIPICS.CPM.2025.13MaRDI QIDQ7299447zbMATH OpenFDO

Authors Nikita Gaevoy, Boris Zolotov, Alexander Tiskin

Publication date 17 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2025.13

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A fast algorithm for multiplying min-sum permutations
• A faster algorithm computing string edit distances
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Affine symmetric group
• Algorithmics on SLP-compressed strings: a survey
• Combinatorics of Coxeter Groups
• Coxeter groups, Coxeter monoids and the Bruhat order
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fast and compact regular expression matching
• Fast distance multiplication of unit-Monge matrices
• Faster subsequence recognition in compressed strings
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Introduction to algorithms
• Periodic String Comparison
• Periodic words, common subsequences and frogs
• Querying and Embedding Compressed Texts
• Representation and classification of Coxeter monoids
• Semi-local longest common subsequences in subquadratic time
• Semi-local string comparison: algorithmic techniques and applications
• The String-to-String Correction Problem
• Tight hardness results for LCS and other sequence similarity measures
• Unified compression-based acceleration of edit-distance computation

This page was built for publication: Doubly-periodic string comparison

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