×

Quotient complexity of bifix-, factor-, and subword-free regular languages. (English) Zbl 1324.68055

Summary: 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 by “subword”we mean “subsequence”, and a language is bifix-free if it is bothprefix- and suffix-free. These languages have important applications in coding theory. The quotient complexity of an operation on regularlanguages is defined as the number of left quotients of the result of the operation as a function of the numbers of left quotients of the operands. The quotient complexity of a regular language is the same as its state complexity, which is the number of states in thecomplete minimal deterministic finite automaton accepting the language. The state/quotient complexity of operations in the classes of prefix- and suffix-free languages has been studied before. Here, we studythe complexity of operations in the classes of bifix-, factor-, andsubword-free languages. We find tight upper bounds on the quotientcomplexity of intersection, union, difference, symmetric difference,concatenation, star, and reversal in these three classes of languages.

MSC:

68Q45 Formal languages and automata
Full Text: DOI