What question did this study set out to answer?

This research aims to introduce an extended algorithm for efficient pattern matching in partially commutative monoids.

May 22, 2026

An Extended Efficient Algorithm of Pattern Matching for Partially Commutative Monoids

Key Points

This research aims to introduce an extended algorithm for efficient pattern matching in partially commutative monoids.
Presented a new algorithm reducing complexity from O(m²) to O(m × d) where m is pattern length and d is dependency degree.
Conducted complexity analysis and comparisons with existing algorithms using mathematical notation.
Achieved overall complexity of O(|T| + |P|) for text T and pattern P, similar to free monoids.
Demonstrated that prior algorithms based on Cartier–Foata form had a complexity of O(|T| × |P|).

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 |).

Demander à l'IA

Bookmark

Cite This Study

Shoukourian et al. (Sun,) studied this question.

synapsesocial.com/papers/6a0ff1dbd674f7c03778afa3 https://doi.org/https://doi.org/10.1134/s1054661825701408

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Demander à l'IA

Bookmark