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)