McCammond's normal forms for free aperiodic semigroups revisited

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

Autores

Almeida, J (Autor) FCUP; Zeitoun, M. (Autor) Outra; Costa, J. C. (Autor) Outra

Revista

Título: LMS Journal of Computation and Mathematics

Vol. 18

Páginas: 130-147

ISSN: 1461-1570

Editora: Cambridge University Press

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 5 Citações

Outras Informações

ID Authenticus: P-00G-6CA

DOI: 10.1112/s1461157014000448

Abstract (EN): This paper revisits the solution of the word problem for w-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond's algorithm, based on normal forms for such terms, uses McCammond's solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond's algorithm, based on properties of certain regular languages associated with the normal forms. This method leads to new applications.

Idioma: Inglês

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

Nº de páginas: 18