Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!lll-winken!csd4.milw.wisc.edu!bionet!ig!arizona!gudeman
From: gudeman@arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Re: Expressive Power - What is it ?
Message-ID: <11315@megaron.arizona.edu>
Date: 2 Jun 89 19:34:30 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 29

In article  <483@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt        ) writes:
]> In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes:
]> >
]> >	Can anyone provide or (preferably) point-to a definition of,
]> >	or discussion about, the oft-heard term "Expressive Power" ?
]> 
]> No, this doesn't seem to hold water as a complete definition.  Suppose
]> that in language A I can form statements of the type S1, S2 and S3.  In
]> language B I can form statements of the type S2, S3, S4,S5, ... 
]> S100000. 
]
]There have been NO languages such as A and B that have ever been discovered.
]If I remember correctly there are only three or four classes of expressive power
]that have been discovered.  None of these classes intersect, they either contain
]a class or are contained in another task.

Actually, there is an unbounded number of classes of languages with
different expressive powers, some of which intersect with each other
with neither including the other.  As an example, let X be the subset
of regular expressions without closure, and let Y be the subset of
regular expressions without alternation.  Let A be the class of
languages that can be described with X and let B be the class of
languages that can be described with Y.  I claim that the language
classes A and B intersect, but that neither contains the other.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@arizona.edu
Tucson, AZ 85721                 {allegra,cmcl2,ihnp4,noao}!arizona!gudeman