McCammond's normal forms for free aperiodic semigroups revisited

This paper revisits the solution of the word problem for omega-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 c...

ver descrição completa

Detalhes bibliográficos
Autor principal: Almeida, Jorge (author)
Outros Autores: Costa, José Carlos (author), Zeitoun, Marc (author)
Formato: article
Idioma:eng
Publicado em: 2015
Assuntos:
Pseudovariety
Word problem
Aperiodic semigroup
Star-free language
McCammond normal form
Regular language
Ciências Naturais::Matemáticas
Ciências Naturais::Ciências da Computação e da Informação
Science & Technology
Texto completo:http://hdl.handle.net/1822/36665
País:Portugal
Oai:oai:repositorium.sdum.uminho.pt:1822/36665
Descrição
Resumo:This paper revisits the solution of the word problem for omega-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.

Registos relacionados