FORMAL PROPERTIES OF RULE ORDERINGS IN LINGUISTICS 
Francis Jeffry Pelletier 
Dept. Philosophy, Univ. Alberta, Edmonton Alberta Canada 
Abs tract 
The discovery in the late 1960's that standard 
linguistic theory (of Chomsky's Aspects) was 
equivalent in generative power to unrestricted 
rewrite rules caused linguists to search for a 
"stronger linguistic metatheory". It seemed to 
some of these researchers that this meant 
describing linguistic theory by means of rules 
which were more restricted than type 0 lan- 
guages. Such a view we call the L-view of 
constraints on linguistic theory: it advocates 
constraining the allowable rules in such a way 
that legitimate grammars can no longer gener- 
ate arbitrary r.e. sets, but only some subset 
of them. To other researchers this discovery 
meant rather that one should place restrictions 
on linguistic theory so that the kinds of gram- 
mars allowed would be limited, regardless of 
whether such limitations affected the generative 
power of the theory. We call this the G-view 
of constraints. The L- and G-views are not 
equivalent limitations. For example, a G-view 
limitation on the class of regular grammars 
that any legitimate grammar be right-embed- 
ding is not thereby a L-view limitation, since 
this does not effect an alteration in generative 
power of the grammars allowed. The G-view 
is avowedly psychological; according to it, the 
point of placing constraints on grammars is to 
lessen directly the language learner's burden 
of choosing the correct grammar from all the 
possible ones. For the L-view, this is a side 
effect of disallowing whole classes of gram- 
mars in the first place. 
One area in linguistics where restrictions on 
linguistic theory have been advocated is in the 
ordering (within the cycle) of the application of 
the rules which generate the language. Here 
are eight proposals that have been aired in 
linguistics about how the rules might be order- 
ed. 
Total Ordering: there is a unique first rules 
a unique second ..... a unique last rule. 
Every derivation applies the rules in this 
order. 
Partial Ordering: there is a unique first rule, 
but thereafter at every stage of a deriva- 
tion there are two rules which are candi- 
dates for application: the rule which was 
just applied and the (unique) next different 
rule. 
Semi Ordering: the rules are given a total 
ordering, but different derivations may 
start at different places in the ordering and 
choose any "later" rule as the next rule to 
be applied. 
Semi Partial Ordering: the rules are given a 
partial ordering, but different derivations 
may start at different places in the order- 
ing and choose either the last-applied rule 
or else any "later" rule as the next rule 
to be applied. 
Unorderings: any derivation can apply the 
rules in any order, subject only to the 
constraint that once a rule has been applied 
in a derivation, it is no longer eligible for 
application at a later stage of that deriva- 
tion. 
Quasi Ordering: any derivation can apply the 
rules in any order, subject only to the 
constraint that once a rule has been applied 
in a derivation, the only other time it may 
be applied in that derivation is to its own 
output. 
Random Ordering: there is no order imposed 
on the rules; any derivation can apply the 
rules in any order. 
Simultaneous Application: the entire set of 
rules is applied to an input "all at once"; 
this prevents some of the rules from creat- 
ing or destroying part of the input in such 
a way as to affect the applicability of other 
rules. 
Advocates of one or another of these rule 
orderings have adopted the G-view, and feel 
that the rule ordering restrictions they desire 
will directly lessen the psychological task of 
learning the correct grammar. The arguments 
for this conclusion are canvassed and found to 
be inconclusive (at best). The present paper 
adopts the L-view and, consequently, investi- 
gates the issue of generative power of the 
various theories of rule orderings. We are 
really interested in more than just the weak 
generative power of these theories: we would 
want to know whether every empirical claim 
(such as ambiguity, paraphrase, etc.) which 
can be made by one theory could also be made 
by another (their strong generative capacity). 
We trust that if, for any grammar obeying rule 
ordering conditions A there is a grammar 
obeying rule ordering conditions B such that 
they both obey standard linguistic strictures 
-412 - 
on the correctness of rules and such that the 
two contain exactly the same class of deriva- 
tions, then rule ordering theory B is at least 
as powerful in strong generative capacity as 
rule ordering theory A. If the converse can 
also be established, then they are equivalent 
in strong generative capacity~ if the converse 
cannot also be established then rule ordering 
theory B is more powerful in strong generative 
capacity than rule ordering theory A. If they 
can each be shown to generate empirical claims 
the other can't, then they are non-comparable 
i_nq strong generative capacity. A series of 
theorems are proved resulting in the relation- 
ships illustrated in Figure 1 (attached). 
Some linguists who advocate "random ordering" 
actually have in mind random ordering plus 
some "universal principles". These universal 
principles are intended to rule out certain 
derivations - - those derivations in which 
pairs of rules are not applied in the order 
specified by the principles. (Also, since their 
proponents hold the G-view, these principles 
are supposed to correspond to psychologically 
plausible learning/processing strategies). We 
investigate the effect of four of these principles 
from the standpoint of the L-view, showing 
that two of them are strongly equivalent to total 
orderings and that two of them are intermediate 
between total and partial orderings. 
We close with an indication of what the role of 
mathematical linguistics Should be for the 
ordinary working linguist. 
RANDOM ORDERINGS 
QUASI ORDERINGS 
UNORDERINGS SEMI PARTIAL 
SEMI ORDERINGS PARTIAL 
ORDERINGS \ / 
TOTAL ORDERINGS 
(= "NON-CONTRADICTORY" 
SIMULTANEOUS APPLICATION) 
FIGURE 1 : Relative Strong Generative 
Capacities of Various Theories of 
Rule Orderings. X---~Y means 
that theory X is stronger than 
theory Y. ( -~ is transitive). 
- 413-- 
