The homomorphism problem for trace monoids

• Type: Article in International Scientific Journal
• Date: 2003

Authors

Pedro V. Silva (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 307

Pages: 199-215

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 0 Citations

ISI Web of Science

Scopus - 0 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-F4B

DOI: 10.1016/s0304-3975(03)00101-4

Abstract (EN): It is proved to be decidable, for any given finite subset F of X* dependency alphabet (Y, tau) and mapping rho : F --> Y*, whether or not rho can be extended to a monoid homomorphism (p) over tilde : F* --> M(Y,tau). This contrasts with the undecidability of the symmetric problem, when we consider the dependency alphabet (X, tau) instead. Some other particular cases of homomorphism and isomorphism problems among trace monoids are also discussed.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17