The homomorphism problem for trace monoids

• Tipo: Artigo em Revista Científica Internacional
• Data: 2003

Autores

Pedro V. Silva (Autor) FCUP

Revista

Título: Theoretical Computer Science

Vol. 307

Páginas: 199-215

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17