Overlaps in free partially commutative monoids

DOI10.1016/0022-0000(91)90010-3zbMath0719.20030OpenAlexW1973868187MaRDI QIDQ2639969

Friedrich Otto, Celia Wrathall

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90010-3

zbMATH Keywords

algorithmconnected componentslengthlatticesfree partially commutative monoidsdirect productfinite alphabetcongruence classescommutation rulesThue congruenceindependence relationmaximum overlapconnected elementoverlaps in free monoidsoverlaps of elementsprefix-orderingtime linear

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorics on words (68R15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Pattern matching in trace monoids ⋮ Overlaps in free partially commutative monoids ⋮ On confluence of one-rule trace-rewriting systems ⋮ One-rule trace-rewriting systems and confluence ⋮ The lattices of prefixes and overlaps of traces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximal serializability of iterated transactions
• On some equations in free partially commutative monoids
• Rewriting systems and word problems in a free partially commutative monoid
• The lattices of prefixes and overlaps of traces
• Recognizable subsets of some partially Abelian monoids
• Overlaps in free partially commutative monoids
• Efficient solution of some problems in free partially commutative monoids
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• A note on thue systems with a single defining relation
• A note on special thue systems with a single defining relation