The homomorphism problem for the free monoid

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

Autores

Pedro V. Silva (Autor) FCUP

Revista

Título: Discrete Mathematics

Vol. 259

Páginas: 189-200

ISSN: 0012-365X

Editora: Elsevier

Indexação

ISI Web of Knowledge - 4 Citações

Scopus - 4 Citações

Outras Informações

ID Authenticus: P-000-M0W

DOI: 10.1016/s0012-365x(02)00380-1

Abstract (EN): It is proved to be decidable, for any given finite subset F of X* and mapping (P:psi:F-->X*, whether or not psi can be extended to an (injective) monoid homomorphism (ψ) over bar :F*-->X*. As a corollary, an alternative algorithm for the isomorphism problem for the free monoid is also provided: for any given finite subsets F, G of X*, it is decidable whether or not F*similar or equal toG*.

Idioma: Inglês

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

Nº de páginas: 12