Semigroups, Automata and Languages

Nilpotency and strong nilpotency for finite semigroups.

Nilpotent semigroups in the sense of Mal'cev are defined by semigroup identities. Finite nilpotent semigroups constitute a pseudovariety, MN, which has finite rank. The semigroup identities that define nilpotent semigroups, lead us to define strongly Mal'cev nilpotent semigroups. Finite strongly Mal'cev nilpotent semigroups constitute a non-finite rank pseudovariety, SMN. The pseudovariety SMN is strictly contained in the pseudovariety MN but all finite nilpotent groups are in SMN.

Towards a pseudoequational proof theory

A new scheme for proving pseudoidentities from a given set Σ of
pseudoidentities, which is clearly sound, is also shown to be complete
in many instances, such as when Σ defines a locally finite variety, a
pseudovariety of groups or, more generally, of completely simple
semigroups. Many further examples when the scheme is complete are
given when Σ defines a pseudovariety V which is σ-reducible for the
equation x = y, provided Σ is enough to prove a basis of identities
for the variety of σ-algebras generated by V. This gives ample

Semidirect products with the pseudovariety D and tameness.

[This is joint work with Conceição Nogueira and M. Lurdes Teixeira.] The semidirect product is a fundamental operation in the theory of pseudovarieties of semigroups. In turn, the pseudovarieties of the form V*D, where D is the pseudovariety of all finite semigroups whose idempotents are right zeros, are among the most studied semidirect products. The concept of tameness of a pseudovariety was introduced by Almeida and Steinberg as a tool for proving decidability of the membership problem for semidirect products of pseudovarieties.

On the subsemigroup complex of an aperiodic Brandt semigroup

Taking as departure point an article by Cameron, Gadouleau, Mitchell and Peresse on maximal lengths of subsemigroup chains, we introduce the subsemigroup complex H(S) of a finite semigroup S as a (boolean representable) simplicial complex defined through chains in the lattice of subsemigroups of S. The rank of H(S) is the above maximal length minus one and H(S) provides other useful invariants concerning the lattice of subsemigroups of S. We present a research program for such complexes, illustrated through the particular case of combinatorial Brandt semigroups.

Ordered DAG Grammars and Parsing Complexity

Hyperedge Replacement Grammars are a useful and expressive formalism for generating graph languages. Unfortunately, the uniform parsing problem for such grammars is NP-hard. We investigate restrictions which allow polynomial time parsing while still retaining enough expressive power to generate interesting languages. In particular, our search for suitable restrictions is guided by applications in natural language processing.

Revisiting concatenation hierarchies of regular languages

This talk addresses the following question: which languages can we define over a finite alphabet, starting from the class consisting of the empty set only, and alternating two operations a prescribed number of times: (1) Boolean closure and (2) polynomial closure? This basic problem, strongly related to logical definability in first-order logic, is wide open since the early 70s. I will introduce a strengthening of this question, and argue that this harder problem is actually easier to deal with than the original one.

Stone Duality and the Substitution Principle.

Finite and profinite monoids have proved to be a powerful tool in the study of regular languages. In particular, understanding the interplay between the topological and algebraic structures of these objects has been crucial. However, many of the classes of languages that are of interest to study are not regular, and so, those theories no longer apply. Boolean spaces with biactions of monoids were recently proposed as suitable objects to handle classes of (not necessarily regular) languages.

Computing topological closures through algebraic recognition.

One of the key problems that has been considered on a pseudovariety V of finite monoids consists in deciding whether a given finite system of equations with rational constraints has a solution in every monoid from V. An instance of this problem is the separation problem, which has received considerable attention lately due to its role in investigations on the Straubing-Thérien hierarchy of star-free languages.



Subscribe to RSS - Semigroups, Automata and Languages