The homomorphism problem for trace monoids.
type: Item
instance of: scholarly article
title: The homomorphism problem for trace monoids.
zbMATH Open document ID: 1042.20042
DOI: 10.1016/S0304-3975(03)00101-4
author: Pedro V. Silva
published in: Theoretical Computer Science
publication date: 2004-03-14T00:00:00Z
review text: The free monoid on an alphabet \(X\) is denoted by \(X^*\). A congruence \(\tau\) on \(X^*\) is called a dependency relation on \(X^*\) if \(\tau\) is generated by a subset of \(\{(xy,yx)\mid x,y\in X\}\). In such case, \((X,\tau)\) is called a dependency alphabet. The monoid \(X^*/\tau\) is called the trace monoid defined by the dependency alphabet \((X,\tau)\) and is denoted by \(M(X,\tau)\). In this paper, the author proves the nontrivial homomorphism problem for trace monoids, that is, for any given finite subset \(F\) of \(X^*\), dependency alphabet \((Y,\tau)\), and mapping \(\varphi\colon F\to Y^*\), it is decidable whether or not \(\varphi\) can be extended to a monoid homomorphism from \(F^*\) to \(M(Y,\tau)\). This result extends previous work done by the author on the homomorphism problem for the free monoid [\textit{P. V. Silva}, Discrete Math. 259, No. 1-3, 189-200 (2002; Zbl 1022.20027)].
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 20M15
zbMATH DE Number: 2056480
zbMATH Keywords: trace monoids
zbMATH Keywords: homomorphisms
zbMATH Keywords: decidability
reviewed by: F. Blanchet-Sadri
MaRDI profile type: Publication
cites work: Some algorithms on the star operation applied to finite languages
cites work: Q4430300
cites work: Q4003861
cites work: A note on decidability questions on presentations of word semigroups
cites work: Synchronized rational relations of finite and infinite words
cites work: Q4839155
cites work: Q5592246
cites work: Q5513066
cites work: On finitely generated subsemigroups of a free semigroup
cites work: Easy multiplications. I: The realm of Kleene's theorem
cites work: The homomorphism problem for the free monoid
cites work: Quelques constructions et algorithmes rélatifs aux sous-monoides d'un monoide libre
cites work: On graph products of automatic monoids
full work available at URL: s0304-3975(03)00101-4
OpenAlex ID: W2059616690
description: scientific article; zbMATH DE number 2056480