Syntactic complexity of bifix-free regular languages

摘要

We study the properties of syntactic monoids of bifix-free regular languages. In particular, we solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a bifix-free language with state complexity n is at most (n - 1)(n-3) + (n - 2)(n-3) (n - 3)2(n-3) for n >= 6. The main proof uses a large construction with the method of injective function. Since this bound is known to be reachable, and the values for n <= 5 are known, this completely settles the problem. We also prove that (n -2)(n-3) (n - 3)2(n-3) -1 is the minimal size of the alphabet required to meet the bound for n >= 6. Finally, we show that the largest transition semigroups of minimal DFAs which recognize bifix-free languages are unique up to renaming the states. (C) 2019 Elsevier B.V. All rights reserved.