Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/28883
Título: | Canonical forms for free k-semigroups |
Autor(es): | Costa, José Carlos |
Palavras-chave: | Pseudovariety Implicit signature k-term Word problem McCammond's normal form Finite semigroup k-semigroup Regular language kappa-term kappa-semigroup ?-semigroup ?-term |
Data: | Mar-2014 |
Editora: | Jens Gustedt |
Revista: | Discrete Mathematics and Theoretical Computer Science |
Resumo(s): | The implicit signature kappa consists of the multiplication and the (omega-1)-power. We describe a procedure to transform each kappa-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of construction of the canonical forms, which is inspired in McCammond's normal form algorithm for omega-termsninterpreted over the pseudovariety A of all finite aperiodic semigroups, consists in applying elementary changes determined by an elementary set Sigma of pseudoidentities. As an application, we deduce that the variety of kappa-semigroups generated by the pseudovariety S of all finite semigroups is defined by the set Sigma and that the free kappa-semigroup generated by the alphabet A in that variety has decidable word problem. Furthermore, we show that each omega-term has a unique omega-term in canonical form with the same value over A. In particular, the canonical forms provide new, simpler, representatives for omega-terms interpreted over that pseudovariety. |
Tipo: | Artigo |
URI: | https://hdl.handle.net/1822/28883 |
ISSN: | 1365-8050 |
Versão da editora: | http://www.dmtcs.org/ |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: | CMAT - Artigos em revistas com arbitragem / Papers in peer review journals |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Costa2014-cffks.pdf | Documento principal | 449,71 kB | Adobe PDF | Ver/Abrir |