Publication
Groups synchronizing a transformation of non-uniform kernel
| dc.contributor.author | Araújo, João | |
| dc.contributor.author | Bentz, Wolfram | |
| dc.contributor.author | Cameron, Peter J. | |
| dc.date.accessioned | 2015-03-23T14:21:14Z | |
| dc.date.available | 2015-03-23T14:21:14Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | 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. | por |
| dc.identifier.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 | por |
| dc.identifier.doi | doi:10.1016/j.tcs.2013.06.016 | |
| dc.identifier.issn | 0304-3975 | |
| dc.identifier.uri | http://hdl.handle.net/10400.2/3794 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.relation.publisherversion | http://www.sciencedirect.com/science/article/pii/S0304397513004829 | por |
| dc.subject | Algebraic theory of languages and automata | por |
| dc.subject | Complexity classes | por |
| dc.subject | Computational methods | por |
| dc.subject | Finite automorphism groups of algebraic | por |
| dc.subject | Geometric, or combinatorial structures | por |
| dc.subject | Primitive groups | por |
| dc.subject | Pseudo-cores | por |
| dc.subject | Semigroups in automata theory | por |
| dc.subject | Semigroups of transformations | por |
| dc.subject | Shronizing automata | por |
| dc.title | Groups synchronizing a transformation of non-uniform kernel | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 15 | por |
| oaire.citation.startPage | 1 | por |
| oaire.citation.title | Theoretical Computer Science | por |
| person.familyName | Ribeiro Soares Gonçalves de Araújo | |
| person.familyName | Bentz | |
| person.givenName | João Jorge | |
| person.givenName | Wolfram | |
| person.identifier.ciencia-id | EC1F-273A-9F24 | |
| person.identifier.ciencia-id | BE11-F004-1168 | |
| person.identifier.orcid | 0000-0001-6655-2172 | |
| person.identifier.orcid | 0000-0003-0002-1277 | |
| rcaap.rights | openAccess | por |
| rcaap.type | article | por |
| relation.isAuthorOfPublication | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 | |
| relation.isAuthorOfPublication | 20420639-0e78-4226-a2e3-892cd2eaa7e8 | |
| relation.isAuthorOfPublication.latestForDiscovery | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 |