2016/04/23 by Marek Szykuła, Szykuła, Marek, John Wittnebel +1
Computer Science · #semigroups and automata theory #Algorithms and Data Compression #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1604.06936
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)2n-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)2n-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.