2017/01/13 by Robert Ferens, Ferens, Robert, Marek Szykuła +1
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1701.03768
20 pages, 1 figure, 4 tables
arxiv created 2017/01/13 · openalex publication_date 2017/01/13 · arxiv updated 2017/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that there exist a single ternary universal (stream of) bifix-free languages that meet all the bounds for the state complexity basic operations (Boolean operations, product, star, and reversal). This is in contrast with suffix-free languages, where it is known that there does not exist such a stream. Then we present a stream of bifix-free languages that is most complex in terms of all basic operations, syntactic complexity, and the number of atoms and their complexities, which requires a superexponential alphabet. We also complete the previous results by characterizing state complexity of product, star, and reversal, and establishing tight upper bounds for atom complexities of bifix-free languages. We show that to meet the bound for reversal we require at least 3 letters and to meet the bound for atom complexities n+1 letters are sufficient and necessary. For the cases of product, star, and reversal we show that there are no gaps (magic numbers) in the interval of possible state complexities of the languages resulted from an operation; in particular, the state complexity of the product Lm Ln is always m+n-2, while of the star is either n-1 or n-2.