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

Janusz Brzozowski, Galina Jirásková, Baiyu Li, Joshua Smith

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment