McCammond's normal forms for free aperiodic semigroups revisited

doi:10.1112/S1461157014000448

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

Registo completo

Campo DC	Valor	Idioma
dc.contributor.author	Almeida, Jorge	por
dc.contributor.author	Costa, José Carlos	por
dc.contributor.author	Zeitoun, Marc	por
dc.date.accessioned	2015-08-31T10:44:24Z	-
dc.date.available	2015-08-31T10:44:24Z	-
dc.date.issued	2015	-
dc.identifier.issn	1461-1570	por
dc.identifier.uri	https://hdl.handle.net/1822/36665	-
dc.description.abstract	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.	por
dc.description.sponsorship	Pessoa French-Portuguese project Egide-Grices 11113YM	por
dc.description.sponsorship	European Regional Development Fund, through the programme COMPETE	por
dc.description.sponsorship	European Community Fund FEDER	por
dc.description.sponsorship	ANR 2010 BLAN 0202 01 FREC	por
dc.language.iso	eng	por
dc.publisher	London Mathematical Society	por
dc.relation	PEst-C/MAT/UI0144/2013	por
dc.relation	PEst-OE/MAT/UI0013/2014	por
dc.relation	info:eu-repo/grantAgreement/FCT/5876-PPCDTI/65481/PT	por
dc.rights	openAccess	por
dc.subject	Pseudovariety	por
dc.subject	Word problem	por
dc.subject	Aperiodic semigroup	por
dc.subject	Star-free language	por
dc.subject	McCammond normal form	por
dc.subject	Regular language	por
dc.title	McCammond's normal forms for free aperiodic semigroups revisited	por
dc.type	article	por
dc.peerreviewed	yes	por
dc.relation.publisherversion	The original publication is available at http://journals.cambridge.org/action/displayJournal?jid=JCM	por
sdum.publicationstatus	published	por
oaire.citationStartPage	130	por
oaire.citationEndPage	147	por
oaire.citationIssue	1	por
oaire.citationTitle	LMS Journal of Computation and Mathematics	por
oaire.citationVolume	18	por
dc.identifier.doi	10.1112/S1461157014000448	por
dc.subject.fos	Ciências Naturais::Matemáticas	por
dc.subject.fos	Ciências Naturais::Ciências da Computação e da Informação	por
dc.subject.wos	Science & Technology	por
sdum.journal	Lms Journal of Computation and Mathematics	por
Aparece nas coleções:	CMAT - Artigos em revistas com arbitragem / Papers in peer review journals

Ficheiros deste registo:

Ficheiro	Descrição	Tamanho	Formato
ACZ-McCammondNF.pdf		327,46 kB	Adobe PDF	Ver/Abrir

Ver registo simples Sugerir correção Estatísticas

Citations

Altmetrics