String matching problems over free partially commutative monoids

DOI10.1016/0890-5401(92)90060-SzbMath0769.68063OpenAlexW2069104328MaRDI QIDQ1207940

Kosaburo Hashiguchi, Kazuya Yamada

Publication date: 16 May 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90060-s

zbMATH Keywords

string matchingfree partially commutative monoidsefficient polynomial time algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (1)

Pattern matching in trace monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On some equations in free partially commutative monoids
• On the decidability of some problems about rational subsets of free partially commutative monoids
• On recognizable subsets of free partially commutative monoids
• String overlaps, pattern matching, and nontransitive games
• Optimal off-line detection of repetitions in a string
• Recognizable closures and submonoids of free partially commutative monoids
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Notes on finite asynchronous automata
• Fast Pattern Matching in Strings
• Programming Techniques: Regular expression search algorithm

This page was built for publication: String matching problems over free partially commutative monoids