Semigroups, Automata and Languages

An approach to Černý's conjecture via the Wedderburn-Artin Theory.

Speaker: 

Emanuele Rodaro (CMUP)

Date: 

Friday, 28 November, 2014 - 14:30

Venue: 

Room FC1.030, DMat-FCUP

Černý's conjecture is one of the most longstanding open problems in the theory of finite automata (stated by Černý in 1964). This conjecture claims that a deterministic finite automaton with n states and synchronizing, has always a synchronizing word of length (n-1)^2. In this seminar, I am going to show an approach to Černý 's conjecture using the Wedderburn-Artin theory. First I introduce the notion of a radical ideal of a synchronizing automaton, and then the natural notion of semisimple synchronizing automata.

Forest Algebras, $\omega$-Algebras and A Canonical Form for Certain Relatively Free $\omega$-Algebras.

Speaker: 

Saeid Alirezazadeh (FCUP)

Date: 

Friday, 17 October, 2014 - 13:30

Venue: 

Room FC1.030, DMat-FCUP

Forest algebras were defined for investigating forests [ordered sequences] of unranked trees, where a node may have more than two [ordered] successors [2]. The number of nodes, the number of connected parts, the set of labels of nodes, the depth, and the set of labels of roots of an element in the free forest algebra are defined by morphisms from the free forest algebra into algebras which retain the equational axioms of forest algebras. We present finiteness conditions for forest algebras.

Takahashi's theorem and periodic points of group endomorphisms.

Speaker: 

Pedro V. Silva (FCUP / CMUP)

Date: 

Friday, 19 September, 2014 - 14:00

Venue: 

Room FC1.030, DMat-FCUP

A famous theorem of Takahashi states the following:

 

Theorem. Let $F$ be a free group and let $K_1 \leq K_2 \leq \ldots$ be an ascending chain of finitely generated subgroups of $F$. If the rank of the subgroups in the chain is bounded, then the chain is stationary.

 

One of the applications of this theorem is to provide a bound for the size of the periodic orbits of a free group endomorphism.

Open problems in automata groups.

Speaker: 

Daniele D’Angeli (Graz University of Technology, Austria)

Date: 

Friday, 25 July, 2014 - 14:30

Venue: 

Room FC1.006, DMat-FCUP

After the introduction of the (first) Grigorchuk group, that was the first example of a group with intermediate growth, automata groups became a very popular topic in geometric group theory, giving rise to many examples of groups with special and exotic properties and showing interesting and surprising connections with other branches of Mathematics.

A nonfinitely based semigroup of triangular matrices.

Speaker: 

Mikhail Volkov (Ural Federal University, Ekaterinburg, Russia)

Date: 

Friday, 25 July, 2014 - 13:30

Venue: 

Room FC1.006, DMat-FCUP

Auinger, Chen, Hu, Luo, and the speaker have recently found a new sufficient condition under which a semigroup is nonfinitely based and have applied this condition to certain important classes of infinite semigroups. In the present talk we demonstrate yet another application; its interesting feature is that it requires the full strength of the main result by Auinger et al. Namely, we prove that the absence of a finite identity basis for the semigroup of all upper triangular real 3x3-matrices with 0s and/or 1s on the main diagonal.

Reconstructing functions from identification minors.

Speaker: 

Erkko Lehtonen (CAUL)

Date: 

Thursday, 12 June, 2014 - 13:15

Venue: 

Room FC1.030, DMat-FCUP

This talk deals with the problem whether a function $f \colon A^n \to B$ is uniquely determined, up to equivalence, by its identification minors, i.e., by the functions derived from $f$ by identifying a pair of its arguments. Some recent results, both positive and negative, about this reconstruction problem are discussed (see [1, 2, 3, 4]). For example, totally symmetric functions and affine functions over finite fields are reconstructible. On the other hand, the class of order-preserving functions is not reconstructible, not even weakly. Some open problems are also presented.

 

The full transformation semigroups and amalgamation bases for finite semigroups.

Speaker: 

Kunitaka Shoji (Department of Mathematics, Shimane University, Matsue, Shimane, 690 Japan)

Date: 

Wednesday, 26 March, 2014 - 14:30

Venue: 

Room FC1.029, DMat-FCUP

The purposes of this talk are to show that the full transformation semigroup on a finite set is an amalgamation base for finite semigroups and to mention relationship ...

 
 

Universal witnesses for descriptional complexity and their (partial) explanation.

Speaker: 

Rogério Reis (DCC-FCUP / CMUP)

Date: 

Friday, 14 March, 2014 - 14:30

Venue: 

Room FC1.029, DMat-FCUP

When studying descriptional complexity of operations over automata it is not only needed to find an algorithm to perform such operation in the most succinct way, but one also needs to find a witness that reaches that complexity, showing that what was done is the best possible, that the bound is tight.

Automaticity, finite complete rewriting systems, and finite derivation type for homogeneous monoids.

Speaker: 

Alan Cain (CAUL)

Date: 

Friday, 17 January, 2014 - 14:30

Venue: 

Room FC1.030, DMat-FCUP

In recent work with Gray and Malheiro, I proved that finite-rank plactic monoids admit presentations via finite complete rewriting systems and are biautomatic. This seminar will discuss the next stage of this work.

Pages

Subscribe to RSS - Semigroups, Automata and Languages