Two recognizable string-matching problems over free partially commutative monoids

DOI10.1016/0304-3975(92)90136-4MaRDI QIDQ1190454zbMATH OpenOpenAlexFDO

Authors Kosaburo Hashiguchi, Kazuya Yamada

Publication date 26 September 1992

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

Full work available at URL https://doi.org/10.1016/0304-3975(92)90136-4

zbMATH Keywords

string-matching algorithms

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Review text

An efficient (linear-time) algorithm for the following problem is given. For two strings \(x,y\) determine if \([x]\) is a factor of \([y]\), where \([z]\) denotes an element of a free partially commutative monoid generated by a word \(z\). Moreover, some variants of this basic problem are examined.

Recommendations

• String matching problems over free partially commutative monoids
• On recognizable subsets of free partially commutative monoids
• scientific article; zbMATH DE number 3956459
• Efficient solution of some problems in free partially commutative monoids
• scientific article; zbMATH DE number 5953970
• Pattern matching in trace monoids (extended abstract)
• String rewriting and homology of monoids
• A decision procedure on partially commutative free monoids
• Efficiency and penalty factors on monoids of strings
• Recognizable closures and submonoids of free partially commutative monoids

Cites work

• Combinatorial problems of commutation and rearrangements
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3917745 (Why is no real title available?)
• scientific article; zbMATH DE number 3970130 (Why is no real title available?)
• scientific article; zbMATH DE number 3972221 (Why is no real title available?)
• Notes on finite asynchronous automata
• On recognizable subsets of free partially commutative monoids
• On some equations in free partially commutative monoids
• On the computational power of pushdown automata
• Recognizable closures and submonoids of free partially commutative monoids
• Two recognizable string-matching problems over free partially commutative monoids

Cited in

(4)

• Two recognizable string-matching problems over free partially commutative monoids
• A string-matching interpretation of the equation x^ m y^ n = z^ p
• Efficient special cases of pattern matching with swaps
• Pattern matching in trace monoids (extended abstract)

This page was built for publication: Two recognizable string-matching problems over free partially commutative monoids

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