SCIENCE@home

Quotient Complexity of Closed Languages

J. Brzozowski,Galina Jirásková,Chenglong Zou

Published 2009 in Theory of Computing Systems

ABSTRACT

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-32 of 32 references · Page 1 of 1

CITED BY

Showing 1-50 of 50 citing papers · Page 1 of 1