Monday, November 26, 2012

Inverse Closure Problem

In the undergraduate complexity course we spend some time on closure properties such as (1) REG closed under UNION, INTER, COMP and (2) R.E. closed under UNION and INTER but NOT COMP.

I propose the following inverse problem: For all possible assignments of T and F to UNION, INTER, COMP, find (if it is possible) a class of sets that is closed exactly under those that are assigned T. I would like the sets to be natural. I would also like to have some from Complexity theory, which I denote CT (e.g., Reg, P, R.E.) and some not (e.g., set of all infinite sets) which I denote HS for High School Student could come up with it. If I want other examples I will say OTHERS? We assume our universe is {a,b}*.

  1. UNION-YES, INTER-YES, COMP-YES:
    1. CT: Reg, P, Poly Hier, PSPACE, Prim Rec, Decidable, Arithmetic Hier.
    2. HS: Set of all subsets of {a,b}*. OTHERS?
  2. UNION-YES, INTER-YES, COMP-NO:
    1. CT: NP (probably), R.E. OTHERS?
    2. HS: Set of all finite subsets of {a,b}*. OTHERS?
  3. UNION-YES, INTER-NO, COMP-YES: NOT POSSIBLE.
  4. UNION-YES, INTER-NO, COMP-NO.
    1. CT: Context Free Langs. OTHERS?
    2. HS: Set of all infinite subsets of {a,b}*. OTHERS?
  5. UNION-NO, INTER-YES, COMP-YES: NOT POSSIBLE.
  6. UNION-NO, INTER-NO, COMP-YES:
    1. CT: The set of all regular langs that are accepted by a DFA with ≤ 2 states. (Can replace 2 with any n ≥ 2.)
      OTHERS?
    2. HS: Set of all subsets of {a,b}* that are infinite AND their complements are infinite. OTHERS?
  7. UNION-NO, INTER-YES, COMP-NO:
    1. CT: I can't think of any- OTHERS?
    2. HS: { emptyset, {a}, {b} }
  8. UNION-NO, INTER-NO, COMP-NO:
    1. CT: The set of all reg language accepted by a DFA with ≤ 3 states and ≤ 2 accepting states. (Can replace (3,2) with other pairs) OTHERS?
    2. HS: I can't think if any- OTHERS?

12 comments:

  1. Why not something similar to 7 for 8?

    ReplyDelete
    Replies
    1. YES- { {a}, {b} } works for a class that is NOT closed
      under UNION, INTER or COMP.

      Still want a more natural example, or for that matter
      just other examples of a different character.

      THANKS!

      Delete
    2. For 8. UNION-NO, INTER-NO, COMP-NO:

      Perhaps the set of all 1-element subsets of N.
      Or the set of all 3-element subsets of N.

      Or the set of all circles (interpreted as point sets).
      Or the set of all lines.

      Delete
  2. For 7 CT, how about co-CFL?

    ReplyDelete
  3. GREAT- Yes that works.
    Are there others? (Probabaly)
    Are there others that are more natural (I hope so but I doubt it)

    ReplyDelete
  4. 7HS: sets of size at most k.
    8HS: sets of size exactly k.

    ReplyDelete
  5. 8-CT is actually closed under complement. For any language represented by a DFA with >= 1 accepting state, just complement the set of accepting states. The only language represented by a DFA with 0 accepting states is the empty language, whose complement can be represented with a single state.

    I think the pair (k+2,k) might be immune to this problem, but (k+1, k) is always closed under complement.

    ReplyDelete
    Replies
    1. AH- typo in my blog- here is what I meant.
      So- does this work:

      Let a<b

      set of regular langs such that the minimal DFA for it
      has b states of which a are accepting.

      Delete
    2. Amir Ben-Amram emailed me the following but is having a hard time convincing the blog that he is not a robot, so I post for him:

      UNION-NOT, INTER-NOT, COMP-NOT: Set of all reg langs
      that have a MIN DFA with exactly 1 accepting state.
      (1 can be replaced by other numbers)

      UNION-NOT, INTER-YES, COMP-NOT: Set of all reg langs
      that have a DFA (not necc minimal) with exactly 1 accepting
      state. Note that the accepting state need not be reachable.

      Delete
  6. 6-CT: The class of all deterministic context-free
    languages is closed under complements,
    not closed under union, and hence not closed under intersection.

    ReplyDelete
  7. Amir Ben-Armram emailed me about DCFL but also emailed me some nice
    geometric ones:

    Set of all half-closed planes: NONE

    Set of all lattice points in half-closed planes: Only COMP

    ReplyDelete
  8. If you mean only finite unions and intersections, we have

    2 HS all closed subsets of R^D
    2 HS all open subsets of R^D
    2 HS all countable subsets of R^D

    4 HS all uncountable subsets of R^D

    7 HS++ subspaces of a vector space
    7 HS++ ideals in a ring (generalization of subspaces and vector spaces)

    ReplyDelete