On lexicographic semi-commutations
type: Item
instance of: scholarly article
title: On lexicographic semi-commutations
zbMATH Open document ID: 0654.68095
DOI: 10.1016/0020-0190(87)90037-8
author: Edward Ochmański
author: Yves Métivier
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: We give a characterization of the communication graphs for which there exists a complete semi-commutation system. From this, we deduce a characterization of semi-commutation systems for which the set of minimal words and the set of irreducible words are equal.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4068325
zbMATH Keywords: commutation monoid
zbMATH Keywords: complete rewriting system
zbMATH Keywords: lexicographic order
zbMATH Keywords: trace
zbMATH Keywords: communication graphs
zbMATH Keywords: semi-commutation
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90037-8
OpenAlex ID: W2034001113
cites work: Combinatorial problems of commutation and rearrangements
cites work: Semi-commutations
cites work: Recognizable subsets of some partially Abelian monoids
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q3725561
cites work: Q3738586
description: scientific article; zbMATH DE number 4068325