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}

^{*}.

- UNION-YES, INTER-YES, COMP-YES:

- CT: Reg, P, Poly Hier, PSPACE, Prim Rec, Decidable, Arithmetic Hier.

- HS: Set of all subsets of {a,b}
^{*}. OTHERS?

- CT: Reg, P, Poly Hier, PSPACE, Prim Rec, Decidable, Arithmetic Hier.
- UNION-YES, INTER-YES, COMP-NO:

- CT: NP (probably), R.E. OTHERS?

- HS: Set of all finite subsets of {a,b}
^{*}. OTHERS?

- CT: NP (probably), R.E. OTHERS?
- UNION-YES, INTER-NO, COMP-YES: NOT POSSIBLE.

- UNION-YES, INTER-NO, COMP-NO.

- CT: Context Free Langs. OTHERS?

- HS: Set of all infinite subsets of {a,b}
^{*}. OTHERS?

- CT: Context Free Langs. OTHERS?
- UNION-NO, INTER-YES, COMP-YES: NOT POSSIBLE.

- UNION-NO, INTER-NO, COMP-YES:

- CT: The set of all regular langs that are accepted by a DFA with ≤ 2 states. (Can replace 2 with any n ≥ 2.)

OTHERS?

- HS: Set of all subsets of {a,b}
^{*}that are infinite AND their complements are infinite. OTHERS?

- CT: The set of all regular langs that are accepted by a DFA with ≤ 2 states. (Can replace 2 with any n ≥ 2.)
- UNION-NO, INTER-YES, COMP-NO:

- CT: I can't think of any- OTHERS?

- HS: { emptyset, {a}, {b} }

- CT: I can't think of any- OTHERS?
- UNION-NO, INTER-NO, COMP-NO:

- 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?

- HS: I can't think if any- OTHERS?

- 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?

Why not something similar to 7 for 8?

ReplyDeleteYES- { {a}, {b} } works for a class that is NOT closed

Deleteunder UNION, INTER or COMP.

Still want a more natural example, or for that matter

just other examples of a different character.

THANKS!

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

DeletePerhaps 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.

For 7 CT, how about co-CFL?

ReplyDeleteGREAT- Yes that works.

ReplyDeleteAre there others? (Probabaly)

Are there others that are more natural (I hope so but I doubt it)

7HS: sets of size at most k.

ReplyDelete8HS: sets of size exactly k.

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.

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

AH- typo in my blog- here is what I meant.

DeleteSo- 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.

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:

DeleteUNION-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.

6-CT: The class of all deterministic context-free

ReplyDeletelanguages is closed under complements,

not closed under union, and hence not closed under intersection.

Amir Ben-Armram emailed me about DCFL but also emailed me some nice

ReplyDeletegeometric ones:

Set of all half-closed planes: NONE

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

If you mean only finite unions and intersections, we have

ReplyDelete2 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)