sreeniva@fas.ri.cmu.edu (R S Sreenivas) (05/10/91)
I am looking for a family of languages F such that: (i) F strictly includes the family of regular languages, and (ii) "Inclusion" must be decidable in F... that is, if L, M are languages in F, L \subseteq M should be decidable in F. Any help will be appreciated. Thanks in advance! -R.S.
sethb@Morgan.COM (Seth Breidbart) (05/12/91)
In article <12991@pt.cs.cmu.edu> sreeniva@fas.ri.cmu.edu (R S Sreenivas) writes: >I am looking for a family of languages F such that: > > (i) F strictly includes the family of regular languages, and > (ii) "Inclusion" must be decidable in F... that is, if L, M are > languages in F, L \subseteq M should be decidable in F. Consider the family of languages F={regular languages} U {P}, where P is the language 1*prime (that is, a prime number of 1's). Inclusion is just as easy to test in this family as in the regular languages. >Any help will be appreciated. Thanks in advance! ^^^ Seth sethb@fid.morgan.com