Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-12-05
Computer Science
Formal Languages and Automata Theory
12 pages, 5 eps figures, uses llncs
Scientific paper
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 the same way, where by subword we mean subsequence. We study the quotient complexity (usually called state complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the prefix-, suffix-, factor-, and 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 application of positive closure and complement to a closed language results in at most four distinct languages, while Kleene closure and complement gives at most eight languages.
Brzozowski Janusz
Jiraskova Galina
Zou Changling
No associations
LandOfFree
Quotient Complexity of Closed Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quotient Complexity of Closed Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quotient Complexity of Closed Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-706661