Two recognizable string-matching problems over free partially commutative monoids
type: Item
instance of: scholarly article
title: Two recognizable string-matching problems over free partially commutative monoids
zbMATH Open document ID: 0752.68042
DOI: 10.1016/0304-3975(92)90136-4
author: Kosaburo Hashiguchi
author: Kazuya Yamada
published in: Theoretical Computer Science
publication date: 1992-09-26T00:00:00Z
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.
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 55519
zbMATH Keywords: string-matching algorithms
reviewed by: Wiesław Zielonka
MaRDI profile type: Publication
full work available at URL: 0304-3975(92)90136-4
OpenAlex ID: W2025754710
cites work: On the computational power of pushdown automata
cites work: Combinatorial problems of commutation and rearrangements
cites work: Q3736919
cites work: Q3692898
cites work: On some equations in free partially commutative monoids
cites work: Recognizable closures and submonoids of free partially commutative monoids
cites work: Fast Pattern Matching in Strings
cites work: On recognizable subsets of free partially commutative monoids
cites work: Q3738586
cites work: Notes on finite asynchronous automata
Recommended article: String matching problems over free partially commutative monoids
Recommended article: On recognizable subsets of free partially commutative monoids
Recommended article: Q3725561
Recommended article: Efficient solution of some problems in free partially commutative monoids
Recommended article: Q3172131
Recommended article: Pattern matching in trace monoids
Recommended article: String rewriting and homology of monoids
Recommended article: A decision procedure on partially commutative free monoids
Recommended article: Efficiency and penalty factors on monoids of strings
Recommended article: Recognizable closures and submonoids of free partially commutative monoids
description: scientific article; zbMATH DE number 55519