Semigroups, Automata and Languages

Presentations for Test-Semigroups for LG

Speaker: 

Lurdes Teixeira (DMat-UM / CMat-UM)

Date: 

Friday, 6 December, 2013 - 15:30

Venue: 

Room FC1030

In order to solve the k-word problem for the pseudovariety LG of local groups, we began constructing examples of local groups to separate some k-terms. This naturally guided us to the construction of a family of generators of LG, the called test-semigroups for LG, and, in parallel, to the definition of a canonical form of k-terms over LG.

Subword complexity and periodicity in two or more dimensions

Speaker: 

Julien Cassaigne (Institut de Mathématiques de Luminy)

Date: 

Wednesday, 3 November, 2004 (All day)

Venue: 

15h30; Sala 0.06

The subword complexity of an infinite string is the function $p(n)$ that counts, for every length $n$, the number of different subwords of length $n$ (blocks of $n$ consecutive symbols) that occur in the string. A classical theorem (Morse and Hedlund

On the homotopy type of a simplicial complex

Speaker: 

Pedro V. Silva (FCUP - CMUP)

Date: 

Friday, 8 November, 2013 - 15:30

Venue: 

Room FC1006, DMat-FCUP

The problem of determining the homotopy type of a simplicial complex is very much simplified if the complex happens to be shellable. This means that there exists an enumeration of the facets of a particularly favourable type. But when is a simplicial complex shellable? In general, there is no...

A geometric interpretation of the Schützenberger group of a minimal subshift

Speaker: 

Jorge Almeida (FCUP - CMUP)

Date: 

Friday, 11 October, 2013 - 13:30

Venue: 

Room FC1006, DMat-FCUP

To each irreducible subshift over a finite alphabet, one may naturally associate a regular J-class of the free profinite semigroup on the same alphabet, and thus a well-defined abstract profinite group, which is called the Schützenberger group of the subshift. In this talk, we provide a geometric...

Finite semigroups that are minimal for not being Malcev nilpotent

Speaker: 

Mohammad Hossein (CMUP)

Date: 

Monday, 22 July, 2013 - 13:30

Venue: 

Room M031, DMat-FCUP

Malcev and independently Neumann and Taylor have shown that nilpotent groups can be defined by using semigroup identities. This leads to the notion of a nilpotent semigroup (in the sense of Malcev). In this talk finite semigroups that are close to being nilpotent will be investigated. Obviously...

Quantitative synchronizing automata

Speaker: 

Mahsa Shirmohammadi (LSV, ENS de Cachan, France and ULB, Belgium)

Date: 

Friday, 5 July, 2013 - 13:30

Venue: 

Room M005, DMat-FCUP

Synchronizing automata has previously been studied for finite automata. In a finite automaton, a word is synchronizing if reading that word from any state of the automaton always leads to the same state. Synchronizing words have applications in security, biocomputing, planning, control of...

Syntactic invariants of flow equivalence of symbolic dynamical systems

Speaker: 

Alfredo Costa (FCTUC - CMUC)

Date: 

Friday, 19 July, 2013 - 13:30

Venue: 

Room M031, Mathematics Department

All information about a symbolic dynamical system X is contained in the language L(X) of its finite blocks. In formal language theory, the syntactic semigroup of a language often plays an important role. Here we consider the syntactic semigroup S(X) of L(X), and more precisely, a finite category...

A Language Theoretic Approach to Strongly Connected Synchronizing Automata

Speaker: 

Emanuele Rodaro (CMUP)

Date: 

Friday, 21 June, 2013 - 13:30

Venue: 

Room M029, DMat-FCUP

We present a recent attempt to place strongly connected synchronizing automata and Cerny's conjecture in a pure language theoretic framework. Crucial is the notion of reset left regular decomposition of an ideal regular language which gives an equivalence between the category of these...

Reaching the minimum ideal in a finite semigroup

Speaker: 

Nasim Karimi (FCUP)

Date: 

Friday, 31 May, 2013 - 13:30

Venue: 

Room M029, DMat-FCUP

Consider a finite semigroup S with a generating set A. By the length of an element s in S, with respect to A, we mean the minimum length of a sequence which represents s in terms of generators in A. Define the parameter N(S, A) to be the minimum length of elements contained in the minimum ideal...

Pseudosemilattices and graphs

Speaker: 

Luís Oliveira (CMUP / DMat-FCUP)

Date: 

Friday, 19 April, 2013 - 13:30

Venue: 

Room M006, DMat-FCUP

Pseudosemilattices are idempotent algebras that generalize the notion of semilattice. Although these algebras are not semigroups in general (the binary operation is generally non-associative), they derive from a particular class of semigroups, the locally inverse semigroups. On each locally...

Pages

Subscribe to RSS - Semigroups, Automata and Languages