Č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 were defined for investigating forests [ordered sequences] of unranked trees, where a node may have more than two [ordered] successors . 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.
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.
Daniele D’Angeli (Graz University of Technology, Austria)
Friday, 25 July, 2014 - 14:30
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.
Mikhail Volkov (Ural Federal University, Ekaterinburg, Russia)
Friday, 25 July, 2014 - 13:30
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.
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.
Thompson groups F, T and V were defined by Richard Thompson in connection to his work in logic in the process of building a group with unsolvable word problem and T and V provide the first known examples ...
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.
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.