Suponhamos que um conjunto de dados (palavras) pertencentes a uma linguagem L são transmitidos através de um canal de comunicação com possíveis erros. Formalmente, o canal é definido por um conjunto de pares de palavras que representam os possíveis input/output. Se assumirmos que o canal...

(Work with Jorge Almeida) Bret Tilson proposed in the 1987 paper "Categories as algebra: an essential ingredient in the theory of monoids" to see small categories and semigroupoids as partial algebras generalizing the concepts of monoid and semigroup, respectively. The results in Tilson's paper...

Finite automata are the simplest model of computing machines. At the
...

Semigroups generated by idempotents arise naturally in many parts of semigroup theory and its applications. In some sense they are as far away from groups as possible and thus require tools of study that are particular to semigroup theory. In this talk, we begin with a brief survey on ...

Using bi-machines and matrices with coefficients in certain semi-rings, we prove an algebraic version of Cook's Theorem.

Na manipulação simbólica de autómatos finitos é importante ter uma representação compacta que os caracterize univocamente, de forma a ser fácil determinar a igualdade entre objectos ou propriedades relacionadas. Apresentamos uma representação por palavras (strings) de autómatos finitos...

Any semigroup S can be embedded into a semigroup, denoted \phi S, having some remarkable properties. For general semigroups there exists a strong relationship between local submonoids of S and \phi S. For a number of usual properties P, S and \phi S simultaneously satisfy P or not, this does not...

The recurrence function $R(n)$ of an infinite word $u$ counts how long one has to wait to see every word of length $n$ that occurs in $u$. Morse and Hedlund studied the behaviour of this function for Sturmian words in 1940, and asked the following question: can $R(n)\over n$ have a finite limit,...

Existem duas classes de semigrupos que surgem naturalmente quando se pretende generalizar o conceito de grupo, enfraquecendo, para isso, a noção de inverso: os semigrupos inversos e os semigrupos regulares, sendo os primeiros um caso particular dos segundos. Os semigrupos inversos têm sido...

(join work with H. Straubing) In an earlier paper, H. Straubing generalized Eilenberg's variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. Our results permit a unified...