A carregar...
Publicação
Groups synchronizing a transformation of non-uniform kernel
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 353.06 KB | Adobe PDF |
Orientador(es)
Resumo(s)
Suppose that a deterministic finite automata A = (Q ,Σ) is such that all but one letters
from the alphabet Σ act as permutations of the state set Q and the exceptional letter acts as a transformation with non-uniform kernel. Which properties of the permutation group G generated by the letters acting as permutations ensure that A becomes a synchronizing automaton under every possible choice of the exceptional letter (provided the exceptional letter acts as a transformation of non-uniform kernel)? Such permutation groups are called almost synchronizing. It is easy to see that an almost synchronizing group must be primitive; our conjecture is that every primitive group is almost synchronizing.
Clearly every synchronizing group is almost synchronizing. In this paper we provide two
different methods to find non-synchronizing, but almost synchronizing groups. The infinite
families of examples provided by the two different methods have few overlaps.
The paper closes with a number of open problems on group theory and combinatorics.
Descrição
Palavras-chave
Algebraic theory of languages and automata Complexity classes Computational methods Finite automorphism groups of algebraic Geometric, or combinatorial structures Primitive groups Pseudo-cores Semigroups in automata theory Semigroups of transformations Shronizing automata
Contexto Educativo
Citação
Araújo, João; Bentz, Wolfram; Cameron, Peter - Groups synchronizing a transformation of non-uniform kernel. "Theoretical Computer Science" [Em linha]. ISSN 0304-3975. Vol. 498 (2013), p. 1-15