FOM: expr. power of syntax

[Steve Stevenson]

Thomas Forster writes:
 > Yes, that's the easy bit.  The harrd bit is to find a formal way
 > of saying something like: no language with the expressive power of
 > propositional logic can be regular.  It's pretty clear that something
 > like that must be true, but i'm not sure how to state it!

If I think of this as a "programming language" problem then it seems
to me you have to be careful. Can you legitimately separate the syntax
and the semantics when you ask about expressive power?

If you express "logic notation" in polish postfix, then the
parentheses and precedents disappear and you can push the correctness
into the evaluation (one way) but you continue to tree-like (context
free) evaluation.

It seems to me that the question is "What is the weakest evaluation
function?" Taking a cue from the Chomsky Normal Form, a "regular"
evaluation function would have one value (the state) and then one
operator (the transition) as in a form of a chain. "Context free"
evaluation needs a recursive function (restricted to finite DAGs). For the
syntax to lead to a regular function, whatever syntax processor you
have would build a structure guaranteed to be a chain. The chain idea
shows up in various guises...they're not what we have in mind.

steve