[FOM] Formal grammar question

[A. Mani]

On Tuesday 08 November 2005 12:25, A.P. Hazen wrote:
> Ignorance speaking, here!
> It seems to me that most of us HUMANS find it easier to read
> conventional (lots of parentheses, infixed operators) logical
> notation than we do parenthesis-free ("Polish") notation.  Are there
> results about computational difficulty that this might be a symptom
> of?

Your question appears to relate more to human cognition.  But if you want an 
explanation with respect to the more common way in which we write and explain 
formal logic, then it might appear to be more computation intensive. But we 
are assuming a semantic basis here, which is not universally justifiable.

> For instance: the usual, go left to right counting the parentheses
> (adding 1 for left parens, subtracting for right), way of checking a
> formula for well-formedness in conventional notation amounts to
> having the human checker simulate the operation of a push-down
> automaton making a single pass through the string. 

Human beings do not read that way. At least that is what most research on 
cognition suggests. Typically they read big blocks and in my 
view use different approximation dialectics for recognition. Reading formal 
expressions involves much training over such a basis.   

> At least the 
> obvious intuitive way of checking Polish formulas involvesd more
> back-and-forthing.  Is this essential?

Even though the primitives are the same, the difference in ease between the 
two notations is more related to conditioning and training. If you are seeing 
a formula for the nth time, you will read it faster.
 
> Again, the definition of well-formed formula given by Goodman and
> Quine in "Steps Toward a Constructive Nominalism" (JSL v. 12 (1947),
> pp. 105-122) makes essential reference to numbers of parentheses in
> strings, and it isn't IMMEDIATELY obvious how to define
> well-formedness for polish notation on their basis.
> ---
<snip>

A. Mani
Member, Cal. Math. Soc