Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/3794
Título: Groups synchronizing a transformation of non-uniform kernel
Autor: Araújo, João
Bentz, Wolfram
Cameron, Peter J.
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
Data: 2013
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
Resumo: 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.
Peer review: yes
URI: http://hdl.handle.net/10400.2/3794
DOI: doi:10.1016/j.tcs.2013.06.016
ISSN: 0304-3975
Versão do Editor: http://www.sciencedirect.com/science/article/pii/S0304397513004829
Aparece nas colecções:Matemática e Estatística - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
2013Groups.pdf353,06 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.