Xref: utzoo sci.math:17355 comp.theory:1967
Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: sci.math,comp.theory
Subject: Re: Formal Languages Question
Keywords: Decidability, Inclusion
Message-ID: <3281@ylum.Morgan.COM>
Date: 11 May 91 23:36:44 GMT
References: <12991@pt.cs.cmu.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 17

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