{"docId":3709,"paperId":1280,"url":"https:\/\/dmtcs.episciences.org\/1280","doi":"10.23638\/DMTCS-19-1-17","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":303,"name":"Vol. 19 no. 1"}],"section":[{"sid":5,"title":"Automata, Logic and Semantics","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01184460","repositoryVersion":3,"repositoryLink":"https:\/\/hal.archives-ouvertes.fr\/hal-01184460v3","dateSubmitted":"2017-06-12 12:55:22","dateAccepted":"2017-06-20 11:34:29","datePublished":"2017-06-20 11:34:52","titles":{"en":"Composing short 3-compressing words on a 2-letter alphabet"},"authors":["Cherubini, Alessandra","Frigeri, Achille","Liu, Zuhua"],"abstracts":{"en":"A finite deterministic (semi)automaton A = (Q, \u03a3, \u03b4) is k-compressible if there is some word w \u2208 \u03a3 + such that theimage of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is calleda k-compressing word for A and A is said to be k-compressed by w. A word is k-collapsing if it is k-compressing foreach k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata withk+1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabetis 3-compressed at least by a word in W. Then we construct a shortest common superstring of the words in W and,with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we showthat the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 \u2264 c(2, 3) \u2264 53 for the length c(2, 3) of the shortest 3-collapsing word on a two-letter alphabet."},"keywords":[["deterministic finite automaton"],["collapsing word"],["synchronizing word"],"[MATH.MATH-CO] Mathematics [math]\/Combinatorics [math.CO]"]}