Um semigrupo numérico é um submonóide dos inteiros não negativos, com a adição. Depois de dar todas as definições a usar ao longo do seminário, como o "número de falhas" ou o "número de Frobenius", procurarei apresentar a minha motivação para criar uma base de dados de semigrupos numéricos e...
The recent developments in the regular language theory motivate us to study classes of homomorphisms from free monoids onto monoids. Such objects can be treated as a pairs (M, A) where M is a monoid and A is a subset of M generating M. This generalizes the classical universal algebra. In our case...
Ondrej Klima (Dept. Mathematics, Masaryk University, Brno, Czech Republic)
Date:
Wednesday, 28 November, 2007 - 14:15
Venue:
Sala 0.04 (DMP - FCUP)
The topic of the talk is an algebraic language theory. It is well known that a language is piecewise testable if and only if its syntactic monoid is finite and J-trivial. We describe several classes of piecewise testable languages and we give characteristic properties of their syntactic structures.
Ondrej Klima and Libor Polak (Dept. Mathematics, Masaryk University, Brno, Czech Republic)
Date:
Monday, 26 November, 2007 - 16:00
Venue:
Sala 0.04 (DMP - FCUP)
Part 1. Eilenberg's variety theorem gives a bijective correspondence between varieties of languages and varieties of finite semigroups. The second author gave a similar relation between conjunctive varieties of languages and varieties of semiring homomorphisms. In this paper, we add a third...
A relação de Green generalizada L* define-se do modo seguinte: diz-se que dois elementos estão L*-relacionados no semigrupo S se existe um semigrupo T tal que S é subsemigrupo de T e os dois elementos estão L-relacionados em T, onde L denota a relação de Green usual. A relação de Green...
Uma pseudovariedade diz-se decidível se existe um algoritmo que decida se um dado semigrupo pertence à pseudovariedade. Um dos problemas centrais da teoria de semigrupos finitos é o de estabelecer a decidibilidade (ou a indecibilidade) de pseudovariedades, sendo motivado principalmente pelo...
We present an O(m \log n)-time minimization algorithm for almost of finite-type automata, where n is the number of states of the automaton and m its number of edges. (This is joint work with Maxime Crochemore). We then give a linear time construction of a constrained channel with periodic...
Nos últimos anos tem havido muito desenvolvimento na área de monóides profinitos livres, principalmente devido ao trabalho de Almeida, Rhodes, Volkov e do orador, entre outros. Nessa palestra falaremos das resoluções dos problemas antigos seguintes:
...
The problem of the enumeration of minimal (non-isomorphic) n state acyclic deterministic finite automata (MADFAs) is an open problem that recently has been considered by several authors. Domaratzki presented a characterization of MADFAs, gave a lower bound and an upper bound for these values....