[FOM] Formal grammar question
urquhart at cs.toronto.edu
Mon Nov 21 15:52:15 EST 2005
In response to Herb Enderton's query about the
history of the algorithm for discovering whether
an expression in Polish notation is well-formed,
I did a little research.
The mathematical criterion for an expression to
be well formed for the implication-negation calculus
was first given by Jaskowski, as stated in footnote
5 of a paper by Lukasiewicz from 1931. The criterion
is given by Lukasiewicz in his 1939 paper on the
equivalential calculus as:
1. The number of E's in the expression is one less
than the number of small letters;
2. In every final segment of the expression, the number
of E's must be less than the number of small letters.
In the 1939 paper, Lukasiewicz restates this rule as
a (right-to-left) algorithm, attributing it to "-- as far
as I know -- a student of L. Chwistek."
The criterion was also discovered for binary connectives
by Karl Menger (Ergebnisse 1932). The general case
is due to Karl Schröter (see review by Bernays
JSL Volume IX, p. 69). Schröter's result was rediscovered
by Gerneth (see review by Church, JSL Volume XIII, p. 224).
More information about the FOM