On recognizable subsets of free partially commutative monoids

DOI10.1016/0304-3975(88)90027-8zbMath0658.20031OpenAlexW1576513528MaRDI QIDQ1111703

Yves Métivier

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90027-8

zbMATH Keywords

wordsfinite alphabetrecognizablefree partially abelian monoid

Mathematics Subject Classification ID

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

Related Items (11)

Asynchronous automata versus asynchronous cellular automata ⋮ Permutation rewriting and algorithmic verification ⋮ Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable ⋮ Parties reconnaissables de monoïdes définis par générateurs et relations ⋮ Recognizable closures and submonoids of free partially commutative monoids ⋮ Shared-Memory Systems and Charts ⋮ Two recognizable string-matching problems over free partially commutative monoids ⋮ Computing the closure of sets of words under partial commutations ⋮ String matching problems over free partially commutative monoids ⋮ Infinite-state high-level MSCs: model-checking and realizability ⋮ An extension of Kleene's and Ochmański's theorems to infinite traces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximal serializability of iterated transactions
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Inhomogeneous sorting

This page was built for publication: On recognizable subsets of free partially commutative monoids