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.
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
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...
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...
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...
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...
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...
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...
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 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...