Publication
Between primitive and 2-transitive: synchronization and its friends
| dc.contributor.author | Araújo, João | |
| dc.contributor.author | Cameron, Peter J. | |
| dc.contributor.author | Steinberg, Benjamin | |
| dc.date.accessioned | 2018-02-09T17:37:39Z | |
| dc.date.available | 2018-02-09T17:37:39Z | |
| dc.date.issued | 2017-12-10 | |
| dc.description.abstract | An automaton is said to be synchronizing if there is a word in the transitions which sends all states of the automaton to a single state. Research on this topic has been driven by the Černý conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing n-state automaton has a reset word of length at most (n-1)2. The transitions of an automaton generate a transformation monoid on the set of states, and so an automaton can be regarded as a transformation monoid with a prescribed set of generators. In this setting, an automaton is synchronizing if the transitions generate a constant map. A permutation group G on a set Ω is said to synchronize a map f if the monoid ⟨G,f⟩ fi generated by G and f is synchronizing in the above sense; we say G is synchronizing if it synchronizes every non-permutation. The classes of synchronizing groups and friends form an hierarchy of natural and elegant classes of groups lying strictly between the classes of primitive and 2-homogeneous groups. These classes have been floating around for some years and it is now time to provide a unified reference on them. The study of all these classes has been prompted by the Černý conjecture, but it is of independent interest since it involves a rich mix of group theory, combinatorics, graph endomorphisms, semigroup theory, finite geometry, and representation theory, and has interesting computational aspects as well. So as to make the paper self-contained, we have provided background material on these topics. Our purpose here is to present results that show the connections between the various areas of mathematics mentioned above, we include a new result on the Černý conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems. | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.doi | 10.4171/EMSS/4-2-1 | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10400.2/7114 | |
| dc.language.iso | eng | pt_PT |
| dc.peerreviewed | yes | pt_PT |
| dc.publisher | European Mathematical Society Surveys in Mathematical Sciences | pt_PT |
| dc.subject | Permutation groups | pt_PT |
| dc.subject | Transformation semigroups | pt_PT |
| dc.subject | Automata | pt_PT |
| dc.subject | Synchronization | pt_PT |
| dc.subject | Primitivity | pt_PT |
| dc.title | Between primitive and 2-transitive: synchronization and its friends | pt_PT |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 184 | pt_PT |
| oaire.citation.startPage | 101 | pt_PT |
| oaire.citation.title | EMS Surveys in Mathematical Sciences | pt_PT |
| oaire.citation.volume | Vol. 4, Nº 2 | pt_PT |
| person.familyName | Ribeiro Soares Gonçalves de Araújo | |
| person.givenName | João Jorge | |
| person.identifier.ciencia-id | EC1F-273A-9F24 | |
| person.identifier.orcid | 0000-0001-6655-2172 | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | article | pt_PT |
| relation.isAuthorOfPublication | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 | |
| relation.isAuthorOfPublication.latestForDiscovery | 1f7b349c-3251-480d-a3ac-e3cb4ef44f22 |