Na tentativa de generalizar um resultado de Groves e Smith, onde se obtém um sistema de reescrita completo para um grupo partindo de um tal sistema para um seu subgrupo de índice finito, chegamos ao conceito de semigrupos (0-)univocamente factorizáveis. Esta generalização permitiu, em particular,...

Centrally labeled Rauzy graphs are Rauzy graphs of subshifts such that the vertices are factors of even length, and such that the edges are labeled by its middle letter (this makes sense, since the edges are factors of odd length). As automata devices, centrally labeled Rauzy graphs have a...

Um semigrupo regular S é um semigrupo no qual para qualquer s de S, existe um elemento t tal que s = sts. Assumimos que existe um subsemigrupo T de S que contém exactamente um associado de s, para todo o elemento s de S. Em 1994, Blyth, Giraldes e Marques-Smith provaram que T é, de facto, um...

Imaginamos que um conjunto de dados (palavras) pertencentes a uma
...

Seja K um anel comutativo com unidade. Se S for um semigrupo inverso, então a álgebra KS
...

Under a standard hardness assumption we exactly characterize the
worst-case running time of languages that are in average polynomial-time
over all polynomial-time samplable distributions.
This is a joint work with Lance Fortnow.

Certas formas normais de funções Booleanas, e.g. formas normais conjuntivas, disjuntivas e polinomiais, podem ser vistas como certas factorizações do clone $\Omega $ de todas as funções Booleanas em clones minimais (i.e., clones que cobrem o clone das projecções). Este facto foi o ponto de...

Dado um conjunto não vazio X, dizemos que uma transformação
...

There has been much interest in characterizing the DNA rearrangment capacity of ciliates both for a better general understanding of the biological processes involved and for the purposes of molecular computing. Much of the work describing the formal language theoretic aspects of ciliate DNA...

Uma extensão por ideais de um semigrupo S sobre um semigrupo Q com 0 é um semigrupo T contendo S como um ideal tal que o quociente de Rees T/S é isomorfo a Q. O estudo destas extensões teve um grande impulso nas décadas de 60 e 70 e o conceito de extensão por ideais densa desempenhou um papel...