The homomorphism problem for the free monoid

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

Authors

Pedro V. Silva (Author) FCUP

Journal

Title: Discrete Mathematics

Vol. 259

Pages: 189-200

ISSN: 0012-365X

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 4 Citations

ISI Web of Science

Scopus - 4 Citations

Scientific classification

FOS: Natural sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12