Semigroups, Automata and Languages

On the problem of counting numerical semigroups by genus.

A numerical semigroup is a submonoid of the non-negative integers, under addition, whose complement in IN is finite. The cardinality of this complement is said to be the genus of the numerical semigroup. In 2008 Bras-Amorós conjectured that the sequence $(n_g)_g$, where $n_g$ is the number of numerical semigroups of genus $g$, behaves like the Fibonacci sequence.

On the Dowling and Rhodes lattices and wreath products.

Dowling and Rhodes defined different lattices on the set of triples (Subset, Partition, Cross Section) over a fixed finite group G. Although the Rhodes lattice is not a geometric lattice, it defines a matroid in the sense of the theory of Boolean representable simplicial complexes. This turns out to be the direct sum of a complete matroid with a lift matroid of the complete biased graph over G. As is well known, the Dowling lattice defines the frame matroid over a similar biased graph.

Rational Embeddings of Hyperbolic Groups.

For a finitely generated group, the Cayley graph is a metric space encoding the structure of the group. Gromov introduced the notion of a $\delta$-hyperbolic group, a finitely generated group with a negatively curved Cayley graph, that is, for any triangle in the graph with geodesic sides, each side is contained in the $\delta$-neighborhood of the union of the two other sides. Hyperbolic groups are "prevalent" among finitely generated groups.

Automaton (semi)groups: on the undecidability of some problems.

We consider algorithmic problems for automaton semigroups and automaton groups of the freeness and finiteness kind. We first show that checking whether an automaton group has empty set of positive relations is undecidable. Moreover we prove that the emptyness of the set of positive relations is equivalent to the dynamical property of having all the orbital graphs centred at the non-singular points which are acyclic. We also settle the problem of checking the freeness for the semigroup defined by an automaton group by proving that such problem is undecidable.

The Catalan monoid C_5 is inherently nonfinitely based relative to finite J-trivial semigroups.

Recall that a finite semigroup S is said to be inherently nonfinitely based (INFB) if S does not belong to any finitely based locally finite variety. In 1987, Mark Sapir proved that the 6-element Brandt monoid B_2^1 is INFB; later he gave an algorithmically efficient description of INFB semigroups. Sapir's description implies, in particular, that no finite J-trivial semigroup is INFB.

Inverse monoids and immersions of cell complexes

In the talk, we study immersions between cell complexes using inverse monoids. By an immersion f : D -> C between cell complexes, we mean a continous map which is a local homeomorphism onto its image, and we further suppose that commutes with the characteristic maps of the cell complexes. We describe immersions between finite-dimensional connected Delta-complexes by replacing the fundamental group of the base space by an appropriate inverse monoid.

Right-angled Artin groups: commensurability classification and subgroup intersection problem.

Two groups are called commensurable if they have isomorphic subgroups of finite index. In the first part of the talk I will discuss our results with Montse Casals-Ruiz and Ilya Kazachkov on the commensurability classification of right-angled Artin groups (RAAGs) defined by trees. In the second part of the talk I will mention some algorithmic properties of RAAGs and discuss our results with Jordi Delgado and Enric Ventura on the subgroup intersection problem for Droms RAAGs.

The image of a representation of pseudowords over the aperiodics.

The pseudowords in a finitely generated free profinite aperiodic semigroup
are faithfully represented by labeled linear orders induced by the factorizations of the pseudowords.

We address the problem of knowing which labeled linear orders are in the image of this representation (This is joint work with Jorge Almeida, José Carlos Costa and Marc Zeitoun).

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.

Pages

Subscribe to RSS - Semigroups, Automata and Languages