An Extended Efficient Algorithm of Pattern Matching for Partially Commutative Monoids
Abstract
Abstract The paper presents an extended efficient algorithm for pattern matching in partially commutative monoids. The complexity analysis and comparisons are provided using proper mathematical notation. The algorithm improves upon previous methods by reducing complexity from O(m2) to O(m × d), where m is the pattern length and d is the dependency degree. For text T and pattern P, the overall complexity of the suggested algorithm is O(|T | + |P |) which coincides with the complexity of pattern matching for free monoids. Meantime the complexity of algorithms based on thr Cartier–Foata canonical form is O(|T | × |P |).
Fields of Study & Subjects
semigroups and automata theory
Fuzzy and Soft Set Theory
Advanced Algebra and Logic
Publication details
- Journal / source
- Pattern Recognition and Image Analysis
- Publisher
- Pleiades Publishing Ltd
- Volume
- 36
- Issue
- 1
- Pages
- 152–162
- Publication date
- 1 March 2026
- Language
- EN