Utilize este identificador para referenciar este registo: http://hdl.handle.net/1822/36665

TítuloMcCammond's normal forms for free aperiodic semigroups revisited
Autor(es)Almeida, Jorge
Costa, José Carlos
Zeitoun, Marc
Palavras-chavePseudovariety
Word problem
Aperiodic semigroup
Star-free language
McCammond normal form
Regular language
Data2015
EditoraLondon Mathematical Society
RevistaLms Journal of Computation and Mathematics
Resumo(s)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.
Tipoarticle
URIhttp://hdl.handle.net/1822/36665
DOI10.1112/S1461157014000448
ISSN1461-1570
Versão da editoraThe original publication is available at http://journals.cambridge.org/action/displayJournal?jid=JCM
Arbitragem científicayes
AcessoopenAccess
Aparece nas coleções:CMAT - Artigos com arbitragem/Papers with refereeing

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ACZ-McCammondNF.pdf327,46 kBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu Currículo DeGóis