𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The homomorphism problem for trace monoids

✍ Scribed by Pedro V. Silva

Book ID
104325793
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
278 KB
Volume
307
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved to be decidable, for any given ΓΏnite subset F of X * , dependency alphabet (Y; ) and mapping ' : F β†’ Y * , whether or not ' can be extended to a monoid homomorphism ' : F * β†’ M (Y; ). This contrasts with the undecidability of the symmetric problem, when we consider the dependency alphabet (X; ) instead. Some other particular cases of homomorphism and isomorphism problems among trace monoids are also discussed.

πŸ“œ SIMILAR VOLUMES

Two techniques in the area of the star p
Two techniques in the area of the star problem in trace monoids
✍ Daniel Kirsten; Jerzy Marcinkowski πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 565 KB

This paper deals with decision problems related to the star problem in trace monoids which means to determine whether the iteration of a recognizable trace language is recognizable. Due to a theorem by Richomme (in: I.

On the restricted homomorphism problem
On the restricted homomorphism problem
✍ Richard C. Brewster; Timothy Graves πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 188 KB