Loading...
Publication
Groups synchronizing a transformation of non-uniform kernel
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 353.06 KB | Adobe PDF |
Advisor(s)
Abstract(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.
Description
Keywords
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
Pedagogical Context
Citation
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