Scholarlink

Abstract <p>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(<i>m</i><sup>2</sup>) to O(<i>m</i> × <i>d</i>), where <i>m</i> is the pattern length and <i>d</i> is the dependency degree. For text <i>T</i> and pattern <i>P</i>, the overall complexity of the suggested algorithm is O(|<i>T</i> | + |<i>P</i> |) 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(|<i>T</i> | × |<i>P</i> |).</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An Extended Efficient Algorithm of Pattern Matching for Partially Commutative Monoids

  • 期刊论文

  • 发表日期：

    2026年3月1日

查看全文
  • Samvel Shoukourian,
  • Arsen Asatryan

摘要

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