Syntactic complexity of suffix-free languages

Research paper by Janusz A.Brzozowskia, MarekSzykułab

Indexed on: 11 Nov '17Published on: 01 Sep '17Published in: Information and Computation


We solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a suffix-free language with n left quotients (that is, with state complexity n) is at most (n−1)n−2+n−2<math class="math"><msup is="true"><mrow is="true"><mo stretchy="false" is="true">(</mo><mi is="true">n</mi><mo is="true">−</mo><mn is="true">1</mn><mo stretchy="false" is="true">)</mo></mrow><mrow is="true"><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn></mrow></msup><mo is="true">+</mo><mi is="true">n</mi><mo is="true">−</mo><mn is="true">2</mn></math> for n⩾6<math class="math"><mi is="true">n</mi><mo is="true">⩾</mo><mn is="true">6</mn></math>. Since this bound is known to be reachable, this settles the problem. We also reduce the alphabet of the witness languages reaching this bound to five letters instead of n+2<math class="math"><mi is="true">n</mi><mo is="true">+</mo><mn is="true">2</mn></math>, and show that it cannot be any smaller. Finally, we prove that the transition semigroup of a minimal deterministic automaton accepting a witness language is unique for each n.