[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
of?
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