[FOM] Formal grammar question

A.P. Hazen a.hazen at philosophy.unimelb.edu.au
Tue Nov 8 01:55:32 EST 2005

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 
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.  At least the 
obvious intuitive way of checking Polish formulas involvesd more 
back-and-forthing.  Is this essential?
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.
Allen Hazen
Philosophy Department
University of Melbourne

More information about the FOM mailing list