Semigroups, Automata and Languages

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

Speaker: 

Mikhail Volkov

Date: 

Wednesday, 6 December, 2017 (All day)

Venue: 

Room FC1 030, DMat-FCUP at 14:30

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

Speaker: 

Nora Szakacs

Date: 

Friday, 24 November, 2017 (All day)

Venue: 

Room FC1 004, DMat-FCUP at 14:30

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.

Speaker: 

Alexander Zakharov

Date: 

Friday, 3 November, 2017 (All day)

Venue: 

Room FC1.030, DMat-FCUP at 14:30

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.

When are right-angled Artin groups similar?

Speaker: 

Montse Casals

Date: 

Friday, 20 October, 2017 (All day)

Venue: 

Room FC1.030, DMat-FCUP at 15:00

Right-angled Artin groups arise naturally in different branches of mathematics and computer science. In this talk we will introduce the class of right-angled Artin groups and discuss when they are algebraically, geometrically and logically similar, or, more formally, when they are commensurable, quasi-isometric and universally equivalent.

The image of a representation of pseudowords over the aperiodics.

Speaker: 

Alfredo Costa

Date: 

Friday, 27 October, 2017 (All day)

Venue: 

Room FC1.005, DMat-FCUP at 14:30

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.

Speaker: 

M. Hossein Shahzamanian C.

Date: 

Friday, 13 October, 2017 (All day)

Venue: 

Room FC1.005, DMat-FCUP at 14:30

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

Speaker: 

Jorge Almeida

Date: 

Friday, 14 July, 2017 (All day)

Venue: 

Room FC1.030, DMat-FCUP at 14:30

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.

Speaker: 

José Carlos Costa

Date: 

Friday, 7 July, 2017 (All day)

Venue: 

Room FC1.005, DMat-FCUP at 14:30

[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

Speaker: 

Pedro V. Silva

Date: 

Friday, 9 June, 2017 (All day)

Venue: 

Room FC1.004, DMat-FCUP at 14:30

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

Speaker: 

Henrik Björklund

Date: 

Friday, 26 May, 2017 (All day)

Venue: 

Room FC1.004, DMat-FCUP at 15:30

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.

Pages

Subscribe to RSS - Semigroups, Automata and Languages