Quotient complexity of ideal languages

Details Quotient complexity of ideal languages Quotient complexity of ideal languages

2009-08-14

arxiv.org/abs/0908.2083v1

Computer Science

Formal Languages and Automata Theory

24 pages, 9 .eepic figures, 2 tables, use llncs.cls

Scientific paper

We study the state complexity of regular operations in the class of ideal languages. A language L over an alphabet Sigma is a right (left) ideal if it satisfies L = L Sigma* (L = Sigma* L). It is a two-sided ideal if L = Sigma* L Sigma *, and an all-sided ideal if it is the shuffle of Sigma* with L. We prefer the term "quotient complexity" instead of "state complexity", and we use derivatives to calculate upper bounds on quotient complexity, whenever it is convenient. We find tight upper bounds on the quotient complexity of each type of ideal language in terms of the complexity of an arbitrary generator and of its minimal generator, the complexity of the minimal generator, and also on the operations union, intersection, set difference, symmetric difference, concatenation, star and reversal of ideal languages.

Affiliated with

Also associated with

No associations

Rating

Quotient complexity of ideal 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 ideal languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quotient complexity of ideal languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-272616