Subject: RE: [e-lang] "Stronger" vs "More Permissive" (was: Modelling Blindness)

From: "Brett Procter" <brett@config.com.au> · Date: Fri, 13 Dec 2002 10:46:45 +1100

> From: e-lang-admin@mail.eros-os.org
[mailto:e-lang-admin@mail.eros-os.org]
> On Behalf Of Mark S. Miller
> Sent: Friday, 13 December 2002 6:59 AM
> To: e-lang@mail.eros-os.org
> Subject: [e-lang] "Stronger" vs "More Permissive" (was: Modelling
> Blindness)
> 
> At 11:40 AM 12/12/2002 Thursday, David Wagner wrote:
> >In article <1039717957.726.212.camel@deskjob.eros-os.org> you write:
> >>On Thu, 2002-12-12 at 07:41, Tyler Close wrote:
> >>> > On Wed, 2002-12-11 at 15:55, Tyler Close wrote:
> >>> > > Can you suggest a textbook that defines this modeling jargon?
> >>>
> >>> This would still be useful.
> >>
> >>I agree, but I am unaware of a suitable textbook. This stuff is a bit
> >>afield for me, and most of it isn't taught from textbooks in any case.
> >>David Wagner might have an idea. David?
> >
> >No clue.  Sorry; I've never done any of this modelling stuff, so if
> >there was a good textbook, I probably wouldn't know of it, unfortunately.
> 
> At this point, I'm willing to believe that this use of the world
> "stronger"
> is obscure, in addition to being a rhetorical disaster. I suggest that the
> phrase "more permissive" is at least as clear and accurate to the theorist,
> and, unlike "stronger", gets the sign right for the lay person.
>

  Perhaps "academic" in place of obscure? 

  I believe the term "stronger" arises from "more *expressive*", as in
there are more things, and more *types* of things, that you can say. 
For me, it stems from my undergrad "computation and automata" class
which dealt with expressions, regular expressions and grammar.

  To wit, machine code is "stronger" than Java, because I can
dereference any machine address I like in machine code,  whereas the set
of pointers I can create and dereference in Java is limited to the items
that have been declared (instantiated).

  Note that dereferencing random pointers in a machine can lead to all
sorts of problems and that Java is probably quite well advised to not 
allow the programmer to express it, but the wisdom of an operation is
not in context when discussing the expressiveness - strength - of a
language.

  To give a more "both sides are valid" example and some modelling
links, consider automata which recognize strings. 

  ... 

  I started to give a rather long expose on automata and grammars here,
but thought better of it.   Those interested may consult
"Theory of Computation - Formal Languages, Automata, and Complexity"
J. Glenn Brookshear, 1989, Benjamin Cummings Publishing Company, Inc

  I'm happy to write a brief of this to the list if someone wants to see
it.   The really short version is that Finite Automata can recognise
regular expressions, but not expressions of the form "a^n,b^n" since
they have no way to count up to "n" "a"'s and then check off "n" "b"'s.
Push-down automata can since they have storage to play with to store the
number "n".  Push-down automata can recognise context-free grammars, and
therefore are "strictly more powerful" than Finite Automata.

Brett Procter
Config Systems Pty Ltd 
brett@config.com.au

> -----Original Message-----
> 
> ----------------------------------------
> Text by me above is hereby placed in the public domain
> 
>         Cheers,
>         --MarkM
> 
> _______________________________________________
> e-lang mailing list
> e-lang@mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/e-lang

_______________________________________________
e-lang mailing list
e-lang@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/e-lang