On some equations in free partially commutative monoids

DOI10.1016/0304-3975(86)90028-9zbMath0605.20062OpenAlexW2066971229MaRDI QIDQ1084189

Christine Duboc

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90028-9

zbMATH Keywords

free partially commutative monoidsconjugacy relationproduct of free monoidsrecognizabletransposition relation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Lyndon traces and shuffle algebras ⋮ Undecidability of the trace coding problem and some decidable cases ⋮ Pattern matching in trace monoids ⋮ Mixed product and asynchronous automata ⋮ Overlaps in free partially commutative monoids ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids ⋮ The word problem for free partially commutative groups ⋮ The power word problem in graph products ⋮ Solving trace equations using lexicographical normal forms ⋮ On confluence of one-rule trace-rewriting systems ⋮ Semi-trace morphisms and rational transductions ⋮ One-rule trace-rewriting systems and confluence ⋮ The monoid of queue actions ⋮ Solving word equations modulo partial commutations ⋮ Recognizable closures and submonoids of free partially commutative monoids ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ On some decision problems for trace codings ⋮ Two recognizable string-matching problems over free partially commutative monoids ⋮ The free partially commutative Lie algebra: Bases and ranks ⋮ String matching problems over free partially commutative monoids ⋮ On a conjecture about finite fixed points of morphisms ⋮ The lattices of prefixes and overlaps of traces ⋮ Logspace computations in graph products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Maximal serializability of iterated transactions
• Some properties of commutation in free partially commutative monoids
• On regular trace languages
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif