Semigroups, Automata and Languages

Research in this area ranges from algebraic topics such as semigroups and groups (finite, profinite, or general) to mathematical models used in computer science, namely various flavors of automata and formal languages. Current work aims not only to contribute to the theories of each of the topics but also to explore the connections between them, with applications in both directions.

The beginning of the area of semigroups, automata and languages (SAL) at CMUP can be traced back to 1987, when Jorge Almeida joined the Pure Mathematics Department at the Faculty of Sciences of the University of Porto. His pioneering work on the profinite approach to finite semigroup theory, which was then starting to flourish, eventually earned him and his school wide international recognition. Several of his doctoral students not only contributed significantly to the area but also eventually proved their autonomy by pursuing different branches of Mathematics. This reflects, in part, the interaction with other areas of Mathematics that Jorge Almeida has always sought, among which deserve particular mention universal algebra, profinite group theory, and symbolic dynamics.

In the early 1990s, another path to this group was opened by the Master's degree in Algebra at the University of Lisbon, which eventually led to four doctorates in the algebraic theory of semigroups (three in the United Kingdom and one in the United States) who integrated the SAL group. Among them, Pedro V. Silva, whose post-doctoral work ranges mostly from combinatorial semigroup and group theory, essentially using automata and language theory methods, to geometric group theory, has deserved widespread international recognition. Another member of the group with the same roots is Luís Oliveira, whose research interests have been mainly focused on locally inverse and regular idempotent generated semigroups. In recent years, he has also been interested in the structure of regular semigroups weakly generated by a set of elements.

After thesis and post-doctoral work on the profinite approach to semigroup theory, since around 2005 Manuel Delgado started developing tools for computing with automata, finite semigroups, and numerical semigroups within the computational algebra software GAP. His non-computational work since then, which has concentrated mostly on numerical semigroups, has been developed in close connection with his computational tools, which have served to discover and test combinatorial and number theoretical phenomena which were hitherto inaccessible.

In 2011, three researchers from the Computer Science Department interested in more computer-science oriented aspects of automata and formal language theory originating from LIACC (Artificial Intelligence and Computer Science Laboratory) joined the SAL line of CMUP. While Nelma Moreira and Rogério Reis have concentrated mostly on the worst-case and average-case descriptional complexity of formal languages, Sabine Broda has also collaborated in part of that work and has interests in richer computational models such as timed automata and Petri nets. Another addition to the group is the number-theorist by formation, António Machiavelo, who has already been involved in collaboration with the colleagues from the Computer Science Department, notably on the average-case descriptional complexity of regular languages and on cryptographic systems.

Hossein Shahzamanian first joined this area as an FCT post-doc and is currently a researcher at CMUP. He works on finite semigroups, and, in particular, in its classification in pseudovarieties and Mal'cev like conditions for nilpotency, as well as representation theory of finite monoids.