Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages

Abstract

A language L is prefix-free if, whenever words u and v are in L and u is a prefix of v, then u=v. Suffix-, factor-, and subword-free languages are defined similarly, where "subword" means "subsequence". A language is bifix-free if it is both prefix- and suffix-free. We study the quotient complexity, more commonly known as state complexity, of operations in the classes of bifix-, factor-, and subword-free regular languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.

24 pages, 11 figures in .eepic format, 2 tables, llncs.cls style file. This version contains several new results, and Baiyu Li has been added as a co-author