Simon's congruence pattern matching

DOI10.1016/J.TCS.2024.114478MaRDI QIDQ6204538zbMATH OpenFDO

Authors Sung-Min Kim, Sang-Ki Ko, Yo-Sub Han

Publication date 28 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114478

zbMATH Keywords

data structurepattern matchingstring algorithmSimon's congruence

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Trees (05C05) Data structures (68P05) Quantum computation (81P68) Real analysis on time scales or measure chains (26E70) Length, area, volume, other geometric measure theory (28A75) Strings (74K05) Theory of computing (68Qxx) Algorithms on strings (68W32)

Recommendations

• On Simon's congruence closure of a string
• On Simon's string searching algorithm
• Normal forms under Simon's congruence
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• scientific article; zbMATH DE number 2038765

Cites work

• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 2087227 (Why is no real title available?)
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• Application of longest common subsequence algorithms to meshing of planar domains with quadrilaterals
• Efficient algorithms for finding a longest common increasing subsequence
• Longest Common Subsequence with Gap Constraints
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• On Arch Factorization and Subword Universality for Words and Compressed Words
• On Simon's congruence closure of a string
• On the Simon's congruence neighborhood of languages
• Scattered Factor-Universality of Words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• Testing Simon's congruence

Cited in

(5)

• Generalized Parikh matrices for tracking subsequence occurrences
• On strings having the same length-k substrings
• Tight bounds for the number of absent subsequences
• Jumbled scattered factors
• Pattern mining under Simon's congruence

This page was built for publication: Simon's congruence pattern matching

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