1965 International Conference on Computational Linguistics 
SOME MATHEMATICAL ASPECTS ON SYNTACTIC DISCRIPTION 
Itiroo Sakai 
Project on Linguistic Analysis 
Ohio State University 
216 North Oval Drive 
Columbus, Ohio 43210 
U. S. A. 
Sakai 1 
Abstract. The purpose of this paper is to help linguists contruct a consistent, 
sufficient and less redundant syntax of language. 
An acceptable string corresponds to an expression or an utterance: it may 
be a natural text, a string of morphemes, a tree structure or any kind of 
representation. A sharp distinction is made between the syntactic function 
which is an attrib trin s and the distribution class which is a set of 
strings. Syntactic function of a continuous or discontinuous string is defined 
as the set of all the acceptable contexts of the string, and is called a com- 
plete neighborhood. Two contexts are equivalent if they accept or reject any 
given string at the same time. An elementary neighborhood is the set of all 
contexts equivalent to one context. 
Four simple distribution classes are proposed and their properties are discussed. 
Concatenation rules of a language can be described in terms of concatenated 
complete neighborhoods or concatenated distribution classes. Some possible 
representations and their consequences are discussed. 
Transformational rules are also described in a similar way. However, 
there is another problem of correspondence of original strings to their trans- 
forms. It is useful to establish subsets of elementary neighborhoods and this 
subclassification may contribute to a simplification of the clumsy represent- 
ation of derivational history. 
Finally, some trivial but practically useful conventions are described. 
1. Introduction. 
~he grammar of a language should be consistent throughout its whole 
system. No features should be left unformulated in order that the grammar be 
a complete one. At the same time, it is desirable to prepare the grammar as 
compact as possible. These are important requirements especially when the 
grammar is a machine-oriented one. The knowledge on the formal properties of 
syntax will help us construct an objective system of grammar. Every term used 
in a description should be rigorously defined and no ambiguous expressions are 
allowed. If the consequence of grammar rules deviates from the proper usage 
of the language~ we will be able to trace back the definitions and locate the 
source of trouble. 
When the grammar rules are given in terms of concatenated symbols, we 
must know the formal definition of the symbols before writing a program by 
which the rules are applied to the text. If a grammar rule describes the 
nature of a P-marker, the label given to each node in the P-marker must have 
an unambiguous definition which relates the meaning of the symbol to the strings 
supplied as texts. 
Sahai 2 
We need, at least, an objective criterion by which we can specify a 
language. This criterion will be a dichotomous decision whether or not a 
given symbol string belongs to the language in question. We leave the decision 
to native speakers and consider the acceptable strings undefined. A substring 
of an acceptable string is said to have a syntactic function or a part of 
speech. The syntactic function of a s~boi string is considered as the set 
of all acceptable utterances in which the string occurs. We eliminate the 
string in question and define its syntactic function as the set of all accept- 
able contexts of the string. The set of all acceptable contexts of a string 
is called a complete neighborhood. 
A distribution class can be defined as a set of strings whose complete 
neighborhoods are related to a given set of contexts in a specified way. We 
propose four simple definitions of distribution classes. 
With these fundamental concepts of parts of speech and distribution classes, 
we can proceed to a more formal system of syntactic description. However, a 
few questions may be immediately raised. Is it really possible to construct 
a grammar in such an elementary way? How can we list the elements of a set 
picking them up out of a practically infinite nmmber of strings even though 
each string is assumed to be of finite length? Is it not useless to establish 
such sets for a natural language, most of which are likely to have only one 
element? Etc. Etc. 
We should be better off if we were to create a new languaze by preparing 
a grammar and a lexicon. Unfortunately the situation is quite contrary when 
we are to handle a natural language. The language exists. We want to find 
out a grammar that accounts for all and only the acceptable strings of the 
language. We regard a language L as a set of strings generated by a machine M, 
whose internal structure is not known to us. We can observe only a part of 
the set of generated strings in a limited length of time. We want to construct 
a hypothetical machanism M' that generates all and only the strings in L. The 
internal structure of M and ~'~ may not be the same. ~%e output of M' is 
checked if it is an element of L, and strings are supplied to M' to see if M' 
accepts a string if and only if it is an element of L. To do this, we must 
have the set L, or a mechanism which tells us whether or not the given string 
belongs to L. We call this mechanism a normative device. It is a native 
speaker if a natural language is to be discussed. We simplify the situation 
by assuming a few separate strata in the mechanism. A string generated is 
supposed to have been transferred from a stratum to another before it becomes 
a string of natural language. An utterance has a few different forms corres- 
Sakai 3 
ponding to the strata. Each form has its own grammar. The normative device 
will be a linguist in this case. 
Since the number of strings is practically infinite, a linguist trying 
to constuct a grammar will find it advantageous to establish rules that hold 
for a set of strings or for a set of relevant facts. A linguistic phenomenon 
may be analyzed from various points of view which will help him avoid listing 
a tremendous number of phenomena and rules. He will attach certain markers 
to the stringm according to the way he considers consistent with his usage of 
language. He will then write down the rules in terms of the markers. He may 
also establish his rules in terms of sets of strings which share some common 
features in their mai~ers. The procedure of using these rules consists of two 
parts. ~%e one is a routine that compares a rule with the text and decides 
whether or not the rule is to be applied. The other is a transfer routine by 
which the relevant infon~ation is read out of the applicable rules and trans- 
ferred to the text. In these procedures, both comparison and transfer are 
carried out with the coded markers. It is important that the meaning of the 
codes is unambiguously defined so that the code obtained in the text is exactly 
what the linguist wants to mean. 
Some of his rules may account for a certain n~mber of texts he has examined 
but may fail to account for some others or to rule out similar but inconsistent 
facts. He will test his rules by applying them to a natural text or by generat- 
ing strings. The normative device will tell him whether or not a string sup- 
plied to it is acceptable but not tell him why. It is obvious that these pro- 
cedures can not be carried out practically on every string that may be supplied 
to a machine in the future, and that nobody will be able to predict what can 
occur when an arbitrary string is supplied to the machine. Nevertheless, it 
is required that a grammar may deal with most of the texts supplied in the 
future. 
His ~rammar is inevitably affected by the nature of the normative device. 
If the normative device is so strict as to reject every string which fails to 
meet such requirements as that its style must be just an ordinary one, the 
statement must be logically correct, the lexical usage must conform with the 
regular way of the language, etc., etc., then the linguist must prepare a 
separate rule for almost every string. He can break down the decision pro- 
cedure into a few separate steps. The first device will accept a string if it 
finds the internal relationship of the string is acceptable, regardless of the 
reality the string designates. If the grammar is to be applied to input texts 
Sakai 4 
whose structure is always grammatically correct and unambiguous, a grammar 
which satisfies the requirement of this device ~ wl~ be enough. However, it 
will give many unusual strings if it is used in random generation and many 
ambiguous alternatives if it is used for analysis, ~h¢ second device may 
reject tl%ose strings whose structure shows an unallowable combination of lexical 
elements, thus eliminating some of the ambiguous alternatives in analysis and 
suppressing the output with improper usage of lexical elements in synthesis. 
The third device may reject as unacceptable those strings which are not logic- 
ally consistent. If one wants to have more rigorous grammar that may be used 
for random generation of only non-surprising sentences, he may add more devices 
to the preceding ones, so that the grammar may be tested from such points of 
view. He will prepare his grammar keeping the characteristics of his normative 
device in mind. A number of digits will be assigned to the coded form of 
markers corresponding to each step of decision. ~ne procedure will be pro- 
grammed so as to handle these digits independently, thus allowing a number of 
rules to be applied to the same string, if certain digits are related to each 
other, and a particular combination ,of codes is to obey a particular rule, the 
rule will be prepared independently and the general procedure will be prohibit- 
ed. ~nis is done by a simple technique in coding and programming. 
As we see on the following pages, a number of similar but different 
representaions are possible. If we are not ready to understand the exact 
meaning of codes and rules and to prepare the right program for the represent- 
ation chosen, the rules established on the basis of ad hoc definitions will 
result in a chaos. The formal property is not confined to a certain language, 
but it is common to many, probably to all, languages. A grammar will not 
deviate greatly from its proper constuction if its formal property is carefully 
examined. 
~. Symbo!~ String; Language. 
2.__~I. Symbol is an undefined term. Morphs, morphemes, lexes, lexemes, or some 
other units may be regarded as symbols. Any unit consisting of a number of 
symbols is called a string. All the strings are possible strings. If a string 
is considered " ~ ~ meanln~u±, then it is an acceptable string. Each acceptable 
string is an undefined term. 
These definitions are quite fon~al. If we confine ourselves to the 
problems in morphotactics, the symbols are morphs and the acceptable strings 
are what are called expressions or utterances. A symbol may be a morpheme and 
a linear arrangement of morphemes is an acceptable string if it is reco~jnized 
as a mori:,hemio =,j ::'osentaticn of an u-ctu:'-.,<=e'. A string need not always be a 
linear a,~ra~gemen% of "~ ~-- " a l~mo. We may rega~t.~ labeled tree called a P-marker 
as a string~ and a labeled node as a re-0resu~rlon of the subsZrin~{ dominated 
by the node~ al~ouZ~.. ~e term strin~ seems inadequate in this oa~e A node 
represents a P-marRer consistin/ of all +~.he terminal and non-terminal nodes 
it dominates. We can regard a P-marker as a L='ee-l/ice strin Z of P-markers 
dominated by the former. "'- ~'~ .... " ~ ..... ,"~ :~o~e. x~nc of .......... es may be added to the syn- 
tactic tree in order Zo indicate the re!ationshi3 a~=on 1%he constituents. We 
call this renresentation a net~ provisionally. We l:~a y reoard a net as a 
string co~."sisting ~: ...... "~ -~ " ........... e. of labeled nouns, w;:ose arrangement is shovm by 
two kinds of branches. 
We define a langua='e as a see of accei=table .... ihc ~" ,. -'- _ s ~r~_njs. acce.n=a3~e string 
of a natural -'a,"-:,'<~ is considered =o have as ..... ~ " .... ..ly versions as the nusoer of 
strata established "bLr linouist. Ear=. v,~-.>;ion of at. accen, table s~cz~ing is an 
element of the language defined on the st,.~atm= i.n ou=,=~:;.,on. A transfer from 
one version to another is essentially a translation. 
2.p. Su~o'.~ose we have a Linear sz, r:Ln:j. !,',e ~,n°cer'r'a~oD the sLrzng by delet.n~ 
some of the s~.:ools therein and ..~. ~ ......... ~...n o" -" a s:p~bol of absence "to each point of 
deletion, if a symbol,, o- absence is foiio',Jed by another .,.,,,e&lauu.y, ~ .... "" ~"~' -~ne,y are 
contracted to one. A ~< .... . ..... e~z strin~ is continuous if it is not interrupted 
,%- ~ ~±~ the nodes in a syntactic tree are palatially ordered. A node includes 
a~ot~ ~ .... ...... if the linear str~_ng ..... covered 0y zne latter ms a part of the linear 
s~l~,a covered by the for='~er. A t:cee-iike strmn\[~\] is continuous~ if and only 
if (i\] all the nodes of the sLrin~ are included in one node D, and (2) there 
are no o d:er nodes which are not included ir~ D° 
• ~.~ • .~ ~*~ ~ • I A ;%et strln< is continuous, 4~ and only m~ ~.~e s~jntactmo tree is continu- 
ous and no branches of ~ne second ' 4 " -"~' ~'" ,~.nQ are broW<ell o.~. 
Any o. ~ ....... ~ ~. -~ ~,I ........ s 3~ a sLrin Z is called a se&~nent, it may be either continu- 
ous or U~CO~uoZnUOGo. ~ discoP.tiZlUOUS sec',',~enL consists of a few nar~s se.na- 
rated from each otl.er. Each o~,z~t of se<':::e:<% ::s Ca~__~,~ a fra-~,,lent which is 
necessarily con'~inuous (~-az-l<er-i.~-.odes~ itdl). 
~. boll ~el{ ~ : ......... (,~_ ,,.,,, ~,. 
5.£=- Context i :2.cce'-'-,<:3_e Conbe:,:=. 
Let r be a strin~ an& ~eL s be a seonenu of r. ~:,e s~.~,~ r may be con- 
tinuous or discontinuous. ;lhe other :taru~ c of z" _~s called the co~-'~c.~.~ of s 
...... ~.~.~u .... ~.~ Lf.eZ:i We ;.sa~, r c ~.s &i% ~c,..,.z.,~,_~u.~,~ OOl%Le\]<L O-" S~ or c 
is ....... -~ - acc~i~u~m~ to s. 
• . , f 
,~ > .q ~ i. O 
• f the discussion is confined to a co~.~-:.ee cr.rase scruczurc _an:Cu~je, 
it seems more convenient to modify the concepts acceptable string and context; 
any immediate constituent of an acceptable szring is also acceptable, and a 
context is acceptable to a string if the string, its context and the whole 
string are all acceptable, if the constituents are continuous, the situation 
becomes simpler. ~ne context c = r()t is acceptable to s, if r, s, t, aud rst 
are all acceptable. Either r or t may be absent. 
3.2. Neighborhood. 
A context is an interrupted string which becomes a continuous string if 
an appropriate segment is supplied to its points of interruption. Let 
y = set(cl,c2,---,c n) 
be a set of contexts and let s be a string. If all the contexts in y become 
acceptable strings when s is supplied to them, then the set y defines a pro- 
perty of s. We call the set y an acceptable neighborhood of s. If y is an 
acceptable neighborhood of strings Sl, s 2, s 3, for instance, then we say y is 
an acceptable neighborhood of 
S = set(sl,s2,s3), 
and we consider the set y represents a syntactic property common to all the 
strings in S. ~ote that our neighborhood is not the same as the okrjestnostj 
(Kulagina, 1958). A set of acceptable strings with a string s is called a 
paradigm of s (Parker-Rhodes, 1961); our neighborhood is a paradigm in which 
the string s is lacking. 
4. Eouivalence of Contexts. 
Let c and c be two contexts. Suppose a string s is acceptable to both z 3 
c and c., and another ..... "~ ~ • ~ing t is not acceptable to c. or c.. In this case, ! j i ,\] 
we can not tell the difference between c. and c as far as the acceptance of l 3 
the strings s and t are concerned. We say these contexts are equivalent to 
each other and write 
c i eqv c j, 
if the condition "c is acce~tabie to ~ ~ring s, if and only if c is accept- 
able to s" is satisfied for every possible string s of the language. ?he 
relation of equivalence is symmetric, reflexive, and transitive: 
(i) c. ecv c.; 
(2) if c i eqv cj, then c~ eqv ci; 
Sakai 7 
(3) if c i eqv c. and c eqv Ck, then c. eQv c k- j .i " 
~. Complete Neighborhood. 
~u~. Let y be an arbitrary set of contexts, it may include contexts which 
are not equivalent to each other and may not include all the contexts which 
are equivalent to some context in it. ~he comolete, n-'ei ''~..~o~nooa'~ " N(y) of y is 
the set of all contexts equivalent to some context c' in y: 
N(y) = set(c: c eqv c' ~ "~ C' in ~o~ some y;. 
A set of contexts is complete or is a complete neighborhood if and only if it 
is the complete neighborhood of itself. Take a string s and let C(s) be the 
set of all the contexts acceptable to it. We show ~u ~ C(s) is ~.a~ complete. 
(l) 
(2) 
If 
af 
then 
then 
then 
then 
therefore 
c 6 C(s), then c £ W(C(s)); that is C(s) c 
c A N(c(s)), 
c eqv c' for some c' in C(s), 
c eqv c' and c' is acceptable to s, 
c is acceptable to s, 
o g c(s), 
N(c(s)) C(s). 
From (i) and (2), we have 
: c(s). 
Therefore, C(s) is complete. We call C(s) the complete neighborhood of the 
string s. 
We may pick up an arbitrary segment of an acceptable string, call the 
other part the context of the segment and establish a complete neighborhood of 
the segment. This kind of complete neighborhood contributes nothing to a 
grammar but some redundant rules. These practically nonsensical complete 
neighborhoods give rise to no trouble, because they never appear in any rule 
of the language. 
?he complete neighborhood C(s) of a string s is considered to correspond 
to the syntactic function or the Dart of speech of the string s. The elements 
of C(s) shire a common property that every one of them can be an acceptable 
context of s, while no other context~ which do not belong to C(s) are acceptable 
to s. ?his property of C(s) leads us to the application of complete neighbor- 
hood to a given set of contexts supplied as text. 
Let S be an arbitrary set of contexts. Some elements of S may be accepted 
by s and some others may not. The elements accepted by s must, at the same 
time, belong ~o C(s), that is, Co C(s)~ S. If 
Sakai 8 
C(s) ~ s = 0, 
then the string s can not occur under the contextual condition defined by S, 
and vice versa. If 
C(s) D S = C(t) ~ S, 
then we have no means to distinguish the syntactic function of s and t with 
respect to the given S. If S is the set of all the possible contexts of the 
language, then 
c(s) N s = c(s) 
for any string s. If 
c(s) = c(t), 
then we have no means to d~stlngmlsn zne s~tactic function of s and t so far 
as only the acceptability is concerned. 
5.2. It occurs very often that a string r behaves like a string s under a 
certain condition, and like t under another condition. This phenomenon will 
be restated as follows: 
for some set S' of contexts, 
C(r) N s' = c(s) O s,, 
and for another set S" of contexts, 
C(r) n s,, = c(t) N s,,. 
We put x = C(r), 
y = C(s), 
z = c(t). 
~,~en, xN ~'N s,,= yqs, N s,, 
and xNs'N s"= ~O s',q s". 
Taking the union of these two, we have 
x('l s, .q s,, = (yd ~)Ns'lq s,,. 
This means that r acce~ots every context in ~' ~ S" ~ if it is acceptable to s or 
t. Now, we will see the behavior of r with respect to the context set 
S = S' ~ S". 
xN s = x ~ (s'd s") 
= (xqs')19 (xOs") 
= (yNS')U(z~s") 
~_(y.qS) U (zNS) 
t = (y U 7) O s. 
This result su~'>e~+~oo _~ that the behavior of r may be interpreted in terms of y 
and z, and that y and z may account for something lacking in x with respect to 
S. 
(yd z),q s = (ydz) ~ (s,d s,,) 
C ¸ ~_" 
= (yns')d (YO, s")W (z,~s') O(z Gs") 
: C< Ds') 0 (y ,~s,,) d (z f~s,) d (x ~O s,,) 
-= (x 0 (s' U ~')) O (y D s") U (z ~ s') 
,'r= H ~< q'.~ ,.., y,% - ~. ~\].,.<ig::'.ta~F ' • . 
o._. We zlave seen above Bhat a co:;:piete ;;eishborhood 
x : c(:~) 
is ir.~erpreted in te:m;~s of 
y : c(s) 
and z : ~< u). 
:','e ca'~ ex~pect ~s) and "" ~e a ~kL; :ray re-~-~ese=zazmon O7 a s',mp.er aria more 
specific syntactic func-cion, if 
C(r) : c(s) O c(t), 
c(~) / c(t), 
c(~) I o, 
c(~) I o, 
then, for some c in C(s) and some c in C(t), we have 
c. noz ecv c~. 
\]- o 
6.2. k se~ o£ all ....... ~- ,.ut~z~j equivalent contexts, called an elementary neighbor- 
hood, leads us to a concept of the ultimate unit of syntactic function. Given 
the elementary neighborhood e(i) with c. as an element is defined ! a context ci, 
as 
e(i) = set(c: c eqv c.). 
l 
Since the equivalence is symmetric, reflexive and transitive, any two distinct 
ele::;e-=~ary neizhborhoods have no elements in common. 
6.__~. Let x be a co,mi~iete neid_borhood and e(i) an elementary neighborhood. 
~ an element c in x ~s a ::,emoer of e(i)~ then 
e(i) r- ::, 
b~cause x is co'.rSie~e '" ~- . in " • ~a.~ an element c x; then there ms an e(i) such \]_ 
that 
• (). C ~ e i 
x : Ue(i) 
for all ek~)'s ~=ving at leas~ one element in x. Every elementary 
Sakai i0 
neighborhood is complete. An intersection of complete neighborhoods is complete. 
Every union of elementary neighborhoods is a complete neighborhood. 
2" Distribution Class. 
We have thus far discussed the syntactic function of symbol strings in 
terms of their acceptable contexts. A context is an environmental condition 
in which a string occurs. Given a context, we can classify the strings into 
two distinct categories: the one is a class of strings that can occur in the 
given environment and the other is the class of strings that can not occur 
therein. 
If there exists at least one context c in which both s and t can occur, 
then c ~C(s) and c ~C(t), 
that is c ~ C(s)N C(t) # O. 
We define the set of all strings t, that can replace s in some contexts, as 
G(C(s)) = set(t: C(t) N C(s) # 0). 
We introduce a convention 
A(=)B 
which means that the intersection of the two sets A and B is not empty: 
G(C(s)) = set(t: C(t) (=) C(s)). 
Suppose a string t can occur wherever s can occur, but s can not always 
occur in the contexts accepted by t. In this case, 
c(t) o C(s). 
We define 
H(C(s)) = set(t: C(t) O C(s)). 
The distribution class I(C(s)) is a set of all the strings t that can be 
always replaced by s: 
I(C(s)) = set(t: C(t) c C(s)). 
That the two strings s and t are mutually replaceable means that s can 
occur wherever t can occur and conversely t can occur wherever s can occur. 
In other words, any context c is accepted by t, if and only if it is accepted 
by s: 
c g C(t) if and only if c ~C(s), 
or C(t) = C(s). 
We indicate the set of such strings t by 
J(C(s)) = set(t: C(t) = C(s)). 
Other distribution classes are defined as sets of strings whose complete 
neighborhoods are related to a certain complete neighborhood in a specified 
way. Let x be an arbitrary complete neighborhood. The simple types of 
Sakai ll 
distribution classes mentioned above are written as 
G(x) = set(t: C(t) (=) x), 
H(x) = set(t: C(t) 2 x), 
I(x) = set(t: C(t) ~x), 
J(x) = set(t: C(t) = x). 
A distribution class is said to be real if it is not empty, and imaginary 
if it is empty. 
able strings 
and only these. 
and their contexts 
Suppose, for instance, that a language consists of the accept- 
they are (flying/red/making) planes, 
a (flying/red) saucer is an object, 
(flying/making) planes is an industry, 
We observe the strings 
s I = flying, 
s 2 = red, 
s 3 = making 
c I = they are () planes, 
c 2 = a () saucer is an object, 
c 3 = () planes is an industry. 
The complete neighborhoods of the strings are 
C(s l) = C(flying) = set(cl,c2~c3), 
C(s 2) = C(red) = set(cl, c2), 
C(s 3) = C(making) = set(cl,c3). 
The distribution classes are determined by these neighborhoods. 
types above are given in the table below. 
i: s I C(s.) G(C(s.)) I(c(s.)) l l l ! 
i: flying (Cl,C2,C 3) (Sl,S2,S 3) (s l) (Sl,S2,S3) 
2: red (Cl,C 2) (Sl,S2,S3) (Sl,S 2) (s 2) 
3: making (ci,c3) (Sl,S2,S3) (Sl,S3) (s 3) 
The simple 
J(C(s.)) 
l 
(s a) 
(s 3) 
Sakai 12 
The elementary neighborhoods 
e(i) = set(c: c eqv ci), i = i, 2, 3 
are found by consulting the table below, where "+" on the i-th row and J-th 
column means "cj is acceptable to si". 
: c I c 2 .c~ 
Sl: + ÷ + 
s2: + + - 
s3: + - + 
e(1) = set(c: c eqv c I) = set(cl), 
e(2) = set(c2), 
e(3) = set(c3). 
Therefore, 
C(s l) = e(1) ~e(2) ~ e(3), 
C(s 2) = e(1) U e(2), 
C(s~) = e(1) U e(3). 
,i. 
(i) J(x) = H(x),q Z(x); 
(2) H(x) U z(x) ~_ G(x), 
Proof. 
(1) t ~ J(x), 
if and only if C(t) = x, 
" C(t) ~ x and 
" t 6 H(x) and 
" t ~ H(x) N i(x). 
(2) t 6_ H(x) U Z(x), 
if and only if t ~ H(x) or 
" C(t) ~ x 
x#O. 
C(t) c x, 
t 6 I(x), 
t d i(x), 
or C(t):'x, 
for x / O, then C(t) (=) x 
if and only if t ~ G(x). 
7.2. Ale equality C(t) = C(s) of two sets is symmetric, reflexive and 
transitive. ~erefore, 
J(x) = J(y) 
if and only if J(x) (=) J(y). 
This means that any two different sets have no elements in common and, con- 
sequently, that every element belongs to one and only one set of the form J(x). 
7e3o 
If X is an elementary neighborhood, then 
G(x) = set(t: C(t) (=) x) 
= set(t: C(t) ~ x) m 
= :~(x) 
if x/ O; 
I(x) = set(t: C(t) C x) 
= set(t: C(t) = x) 
: J(x), 
so that C(t) is also elementary. 
7.3.2. 
then 
if 
Sakai 13 
If x is any complete neighborhood and if C(t) is elementary for all t, 
G(x) = set(t: C(t) (=) x) 
= set(t: C(t) ~ x) m 
= I(x); 
H(x) = set(t: C(t) D x) m 
= set(t: C(t) = x) 
: J(x) 
x / O, 
so that x is also elementary. 
7._~_~. If C(t) is elementary for all t and x is also elementary and non- 
empty, then 
7-4. If 
(1) 
(2) 
(3) 
Proof. 
(1) 
if and only if 
I! 
I! 
I! 
(2) 
if and only if 
I! 
G(x) = ~(x) = I(x) = J(x). 
X = y U z, then 
G(x) = G(y) U G(z), 
H(x) = a(y) ~ ~(z), 
I(x) ~ i(y) O I(z). 
t ~ G(x) = G(y ~ z), 
C(t) (=) x = y ~ z, 
c(t) (:) y or c(t) (:) z, 
t ~ G(y) or t ~ G(z), 
t 6 G(y) U G(z). 
t £ H(x), 
C(t) ox = yUz, 
C(t) 2Y and C(t)_Oz, 
t6H(y) and t~(z), 
It 
(3) 
if and only if 
then 
if and only if 
~.~A. 
(l) 
(2) 
Proof. 
(l) 
if and only if 
l! 
then 
if and only if 
(2) 
if and only if 
T! 
11 
I! 
8. 
8.1. 
t ~H(y) ~H(z). 
t~I(y) U I(z), 
c(t) ~ y or 
c(t) ~ y ~ z : x, 
t £ Z(x). 
If x : yN z, then 
G(x) ~ G(y) ~ G(z), 
Z(x) = Z(y) N Z(z). 
C(t) ~ z, 
t £ G(x), 
C(t) ~ x # O, 
c(t) ~ y ~ z / o, 
C(t) ~{ y # 0 and 
t ~G(y) ~d(z). 
t ~ I(x), 
c(t)C_x = yAz, 
C(t) ~y and , C(t)~ z, 
t ~ I(y) and t ~ I(z), 
tEl(y) ~ Z(z). 
-----~ r n 
Sakai 14 
Concatenation. 
Cqncatenation of Strings. 
Let p be a string and let r I, r 2, 
c~t) ~ z # 0, 
be segments of p which do not 
mutually overlap. A segment t consisting of r l, r 2, ---, rn is the concaten- 
ation of these segments. It is a segment of p, consisting of fragments of 
--- arranged in their relative order in the original string p. It r l, r 2, ,r n 
is convenient to assign a definite notational order to a concatenation in order 
to specify the arrangement of fragments. 
8.2. Concatenation of Contexts. 
Let 
r l, r 2, ---, r n 
be segments of p with no fragments in common. 
c (r) of r in p, p l l 
i = i, 2, ---, n 
correspond uniquely to the segments ri, 
'l~e contexts 
respectively, and so does c (t) to P 
the concatenation 
Sakai 15 
We write 
t = rlr2---r n. 
Cp(ri)Cp(r2)---Cp(r n) = Cp(t) 
if and only if t = rlr2---rn in 
8.3. Concatenation of Sets. 
Let a, b, c, --- be elements of sets. 
p. 
We call an ordered string of these 
elements a concatenation. Let A, B, C, --- be sets. We define the concate- 
nation,of sets as 
AB---D = set(ab---d: a~ A, b ~B, ---, d ~ D). 
In our present discussion, the elements are either all strings or all contexts. 
8.3.1. We confine ourselves to binary concatenations for simplicity. The fol- 
lawing discussions can be easily generalized to longer concatenations. An un- 
ambiguous concatenation, ABCD for instance, is considered as one of the three 
binary concatenations 
A(BCD), (AB)(CD), (ABC)D 
when the discussion is strictly binary. In a morphographemic description, 
however, this is not very important. One may assume one of these three accept- 
able and discard the other two as unacceptable. In a morphotactic description, 
some one of these three will be chosen so as to make the whole description of 
the language simpler. If any one of the sets which constitute a concatenation 
is empty, then the concatenation is also empty. 
We assume that the binary concatenations required by the grammar are 
(AB)(CD), A(BC), (BC)D 
and only these. The possible binary tree structures of ABCD are covered by 
ABCD = A(BCD) U (AB)(CD) U (ABC)D. 
Since we are to handle binary concatenations only, we consider two concatenations 
of elements are different if their structures are not the same: 
Then, the condition 
yields 
(i) 
(2) 
(3) 
By assumDtion , 
(AB)(CD) N A(BCD) = O, 
(AB)(CD) ~ (ABC)D = O. 
ABCD : (AB)(CD) 
(AB)(CO) I O, 
~erefore, 
(4) 
45) 
because 
Similarly, 
(6) 
(7) 
From (2), 
By (7) and (6), 
or, 
(8) 
From (3), 
By (4) and (5), 
(9) 
Sakai 16 
A(~C) J O, 
(A~)C : O, 
A(BC) N (,~)C : O. 
BCD = B(CD)\[_) (BC)D = (BC)D, 
(BC)D ~ O, 
B(CD) : O. 
A(BCD) : A(B(CD) h) (Be)D) : O. 
A(BCD) : 0 0 A((BC)D) : o, 
A # O, (~C)O # O, A((BC)O) : O. 
(ABC)D : (A(BC) O (AB)C)D : O. 
(ABC)D = (A(BC) ~ O)O : (A(BC))D = O, 
A(BC) # O, D # O, (A(BC))D = 0. 
Now, we can describe the syntax of these strings in terms of binary concate- 
nations only, if we establish the rules numbered from (1) to (9). 
8.3.2. The following formulas are frequently used. 
(1) AB = CD, if and only if A = C and B = D, 
because, for any ab in AB, 
AB = CD 
if and only if Cab ~ AB if and only if ab~ CD) 
" ((a ~ A, b@ B) if and only if (a ~ C, b~ D)) 
I! 
(a) 
because 
if and only if 
I, 
II 
r! 
(3) Similarly, 
(4) 
because 
if and only if 
V! 
11 
(a~ A if and only if a ~ C, 
bE B if and only if b ~ D) 
A = C and B = D. 
A(BU C) = ABU AC, 
ab ~ A(B U C) 
a 6A an~ b6BUC 
(a ~ A and b ~B) or 
ab 6 AB or ab 6 AC 
ab ~ AB ~ AC. 
(AOB)C: ACUBC. 
ABDCD= (Af\]C)(BDD), 
ab ~ AB tO CO 
ab ~ AB and ab ~ CD 
a ~ A and b ~ B and 
a~ A~C and 
(a ~ A and b 6 C) 
a&C 
b~B~D 
and b ~ D 
strings r and s, such that 
C(r) : x 
and C(s) = y. 
By definition, 
Sakai 17 
" ab ~ (A N C)(B lq D). 
Concatenation of Complete Neighborhoods.. 
If the distribution classes J(x) and J(y) are real, then there exist 
p(r i) = ---r.---l 
with the segment r. in it is acceptable if and only if 
p(r) .... r--- 
is acceptable, and the string 
p(s.) .... 2°--- 3 3 
.is acceptable if and only if 
p(s) .... s--- 
is acceptable. Suppose 
P(ris j) = ---ri---sj--- 
is a string with both r. and s. in it. Any such string ix acceptable if and l j 
only if the string 
p(r.s) : ---r.---s--- l l 
is acceptable, and P(ris) is acceptable if and only if 
p(rs) .... r---s--- 
is acceptable. ~nerefore, P(ris j) is acceptable if and only if p(rs) is 
acceptable. That is 
C(ris j) = C(rs). 
We define the concatenation C(r)C(s) of complete neighborhoods as the complete 
I % neighborhood C(rs) of the concatenated strings. Generally, we put 
xy : c(rs), r ~ J(x), s 6 J(y) 
for any com~plete neighborhoods x and y, where J(x) and J(y) may be real or 
imaginary. Note, however, that 
if x : C(r), y : c(s), 
C(r i) = x for all rl in J(x) 
and C(sj) = y for all s3 in J(y). 
Any string 
Sakai 18 
then xy = C(rs), 
while xy = C(rs) 
does not always result in 
x : C(r) or y = C(s). 
We have generalized and transferred the concatenation of strings to 
concatenated sets of strings and then to concatenated complete neighborhoods. 
The complete neighborhood representation provides us with a less complicated 
approach, especially when the strings are syntactically ambiguous. The dis- 
tribution class J(x) means the narrowest classification of strings and no 
further subclassification is possible, while its complete neighborhood x can 
be subclassified if x is not an elementary neighborhood. If 
rg J(x) and x = y Uz, 
then we can talk about imaginary strings r' and r", such that 
C(r') = y and C(r") = z. 
These imaginary strings, always referred to implicitly in terms of distribution 
classes, can be discussed explicitly in terms of complete neighborhoods. 
9.2. We make distinction between the concatenation 
xy : c(r)c(s) 
of complete neighborhoods and the complete neighborhood 
z : C(rs). 
~%e former means a set consisting of concatenated contexts. The properties of 
the language is introduced when it is written in the form 
xy= z 
or C(r)C(s) : C(rs), 
where the property x of r and the property y of s result in another property 
z of rs. Thus, z can be an empty set even if neither x nor y is empty, and 
ambiguous even if neither x nor y is ambiguous. 
9.3. We find it advantageous to have a system which represents every complete 
neighborhood in a unified way. We saw that a complete neighborhood x can be 
represented by a union of elementary neighborhoods e(i): 
x = Oe(i) with x ~ e(i) ~ O. 
Let us introduce coefficients x(i), such that 
x(i) : o if 
= i if 
and no other cases possibly occur. 
x(i)e(i) = e(i) 
=0 
e(i),Ox =o, 
e(i) -- x; 
We put 
if x¢i) : l, 
if x(i) : o. 
Sakai 19 
In virtue of these coefficients, we can write 
(1) If 
then 
If 
then 
~\]erefore, for 
we have 
(2) If 
then 
x = Dx(i)e(i), 
y = ~y(j)e(j), 
z = Uz(k)e(k). 
z=xOy, 
x U Y = (U x(i)e(i)) U (Oy(j)e(j)) 
= U(x(k) + y(k))e(k) 
= U z(k)e(k). 
e(k) c_ x or e(k) ~ y, 
e(k) ~_ z. 
x(k) + y(k) = z(k), 
0~-0=0, 
l+O =0 +l= 1 +l= 1. 
z = xy, 
z = (Ux(i)e(i))(~y(j)e(j)) 
= DU x(i)y(j)e(i)e(j) 
= UU z(i,j)e(i)e(j). 
By the definition of concatenation, 
e(i)e(j) ~ xy 
if and only if 
That is, 
if and only if 
Therefore, for 
we have 
e(i) C x and 
z(i, j) = 1 
x(i) = y(j) = 1. 
x(i)y(j) = z(i,j), 
1Xl=l, 
0 XO =0 Xl= IXO = O. 
e(j) c y. 
Writing 
we have 
if and only if e(i)e(j) ~ z 
Therefore, for the expression 
z(i,j)a(i,j,k) = z(k), 
we have 1 X 1 = l, 
e(i)e(j) = Ua(i,j,k)e(k)" 
Z = xy 
= U~ z(i,j)e(i)e(j) 
: UUU z(i,j)a(i,j,k)e(k) 
= Uz(k)e(k), 
e(k) ~ z 
and e(k) ~ e(i)e(j). 
(3) A concatenation of two elementary neighborhoods is a complete neighbor- 
hood, and it is also a union of elementary neighborhoods: 
Sakai 20 
10. 
i0. i. 
be cause 
if and only if 
11 
I! 
then 
,if and only if 
l0.2. 
because 
if and only if 
II 
It 
II 
I! 
then 
if and only if 
lo._.._5.5. 
because 
if and only if 
II 
It 
II 
I1 
then 
if and only if 
10.4. 
because 
if and only if 
11 
!I 
then 
if and only if 
0 XO =OXI= 1XO =0. 
Concatenation of Distribution Classes. 
G(u)G(v) ~G(uv), 
r~ £ G(u)~(v) 
r £ G(u) and s £ G(v) 
C(r) N U / 0 and C(s) ~ V / 0 
(C(r) ~ u)(C(s) ~ v) = C(r)C(s) N uv / o 
C(rs) ~uvJ0 
rs £G(uv). 
H(u)H(v) c ~(uv), 
rs E ~(u)~(v) 
r ~ H(u) and s g H(v) 
C(r) D u and C(s) ~ v 
C(r) ~ u =u and ~C(s) ~ v = v 
(C(r) ~ u)(C(s) N v) = C(r)C(s) N uv : uv 
C(r)C(s) ~ uv 
C(rs) 2 uv 
rs ~ H(uv). 
I(u)I(v) ~ I(uv), 
rs £ I(u)I(v) 
r ~ I(u) and s ~ I(v) 
C(r) c u and C(s) ~ v 
C(r) ~ u = C(r) and C(s) ~ v = C(s) 
(C(r) ~ u)(C(s) D v) : C(r)C(s) D uv : C(r)C(s) 
C(r)C(s) c uv 
m 
C(rs) c uv 
N 
rs 6 I(uv). 
J(u)J(v) C J(uv), 
rs ~ J(u)J(v) 
r ~ J(u) and 
C(r) = u and 
C(r)C(s) = uv 
C(rs) : uv 
rs £ J(uv). 
s 6 J(v) 
C(s) = v 
Sakai 21 
i!. Rules for Recognition and Generation. 
Each rule of a grammar indicates the arrangement of a few items to be 
concatenated, accompanied by some other necessary informations. We assume the 
items arranged in a rule are either complete neighborhoods or distribution 
classes. Let us see what happens during the generation and recognition of a 
string of symbols. 
In case a grammar is given in terms of complete neighborhoods, the input 
text is converted to a string of complete neighborhoods before the syntactic 
analysis begins. At the very end of generation, a terminal node accompanied 
by a complete neighborhood x is replaced by a string s whose complete neigh- 
borhood C(s) shares at least one elementary neighborhood with x. 
~nen the syntactic rules are expressed in terms of sets of strings, the 
input text to be analyzed is replaced by a string of distribution classes. 
If a symbol string belongs to more than two sets of strings, their meet 
replaces the symbol string. At the end of a generation, the synthesized out- 
put string is obtained by replacing the set of strings on @ach terminal node 
by a string which is a member of the' set. 
ll.1. An acceptable string can be generated and analyzed making use of a tree 
with its nodes marked by complete neighborhoods. The expansion of a node z 
to a concatenation xy of nodes x and y implies z ~ xy, because otherwise 
further expansion of x and y may yield a structure which can not be accepted 
by z. Transformational rules can be a}?plied more freely because a trans- 
formation does not imply such a restriction. However, attention ahould be 
paid not to add any other contexts to the complete neighborhoods attached to 
the nodes already generated. Finally, each terminal node is replaced by a 
lexical element. ~%e string obtained after applying all the obligatory 
rules must be an acceptable string. 
~ne analysis is carried out by testing all the possible transformations 
and trying all the possible contractions. At any rate, both generation and 
analysis can be carried out if we have a set of rules which gives concatenation 
z = x---y for any x, ---,y of the language, and the transform y(1)y(2)---y(n) 
of any string x(1)x(2)---X(m) of complete neighborhoods. 
ll.2. Acceptable strings are also generated by starting from the node P(O) 
which is the set of all acceptable strings. It is replaced by its subset 
P(1)P(2)---P(i)---P(m) ~ P(O) 
which is a concatenation of nodes P(i)'s. Each node P(i) also represents a 
set of strings, and it may or may not be replaced again by 
P(il)---P(ij)---P(in) ~ P(i). 
Sakai 22 
On each step of expansion, a choice is made by taking a subset of strings. 
~e possible choice becomes narrower and narrower. It is expected that the 
string obtained by applying obligatory rules and by replacing each terminal 
node by a lexical element is an acceptable string. 
~is is not always true if the replacement of a node is independent of 
the other nodes already generated. %his difficulty is overcome by executing 
a syntactic analysis after every step of expansion. If the analysis does not 
prove the possibility of obtaining an acceotable string, another subset should 
be chosen as a candidate. ~ne check by analysis should be tried after a 
transformation if it is a local or a generalized one. All the nodes, terminal 
and non-terminal, are sets of symbol strings. A generated string of nodes is 
analyzed by tracing back the path of generation. If the analysis goes back to 
P(O) which covers the whole string, the generation is acceptable, and not 
acceptable if otherwise. 
Any given string can be analyzed by applying rules to the string, in 
this case, however, the tree structure is not known. Rules should be tested 
on every possible combination of terminal and non-terminal nodes, so that the 
whole string may be covered by a single node and the possible derivational 
history may be accounted for by the concatenationai and transformational rules. 
11.3. ~ihe Rules for generation and those for recognition are essentially the 
same. They may be prepared in terms of complete neighborhoods or distribution 
classes. ~le rules will be prepared without any formal ambiguity if their 
definitions are carefully observed. Some formal systems are given in the 
following pages as examples of sin:pie types of grammar. 
.... Re,,resen~.~<~on ~ Concatenation Rklles !2. Conu~lete Neighborhood ~ ~-~ c ~ ,. 
We say a set of concatenation rules is con~plete if it gives the concate- 
nation 
Z = xy 
of any complete neighborhoods x and y of the language. It is not necessary, 
however, to list all the ioossible x's and y's. Much less number of rules 
can cover all ~he ~ossible com!iete nei~3hborhoods if their use is y rcper!y 
pro gramme d. 
We consider a rule f(uv;w) represents a relation between the concatenated 
complete neighborhoods uv and another complete neighborhood w. Each rule 
Sakai 23 
uv (=) w, 
UV :D W, 
UV ~ W, 
will give information to xy if x (=) u and y (=) v: 
(xN u)(yNv) : xy uv; 
which is a part of xy = z. 
In order to obtain th~ given concatenation xy, we determine a set R(xy) 
of rules applicable to xy. Each rule is decided whether or not it is applic- 
able to xy by the condition g, so that 
f(uv;w) 6 R(xy) 
if and only if g(x;u) and g(y;v). 
~%e term w is read out of the rules in R(xy) so that z = xy may be 
determined, it is obvious that there exist certain restrictions in choosing 
the type f of rules, the condition g for determining R(xy), and the procedure 
of finding z. We have to specify these three for the grammar to be written. 
When the complete neighborhood z is given and its expansion xy is to be 
found, the set E(z) of applicable rules is determined by the condition h(z;w): 
R(z) = set(f(uv;w): h(z;w)). 
The situation is a little complicated in this case. We can possibly expect a 
case where both 
z = xlY 1 and z = x2Y 2 
are true under the condition 
x I ~ x 2 = 0 and/or Yl ~ Y2 = O. 
Note that this is not the case of formal concatenation of sets 
N CO = (A N C)(BN O). 
The concatenations xiY I and x2Y 2 happened to be z by the syntactic reason of 
the language being studied. A storage space is assigned to each xiY i as soon 
as any rule in R(z) proves a possibility, and xiY i is modified every time a 
rule is applied to it. However, if 
x. ~ x. and Yi ~Yj' i - ~ 
then either xiY i or xjyj is just trivial. The choice depends upon the type of 
rules and the program which applies the rules to the text. Finally, we have 
a set of x i~ accompanied by the subset R(z;i) of R(z). Possible types of 
rules for this purpose will not be discussed here, because the principle is 
similar to the case of finding z from x and y. 
In order to see some properties of rules, we assume simple forms of f(uv;w): 
Sakai 24 
(i) 
if and only if 
T! 
(a) 
if and only if 
I! 
I'I 
(3) similarly, 
if and only if 
UV = W. 
The condition g will be assumed simply as 
(=), o_, c_, or =. 
The condition of constituents can be replaced by a condition imposed on 
the whole concatenation: 
xy (=) uv 
xyNuv = (x~ u)(yDv) /0 
x (=) u and y (=) v; 
xy E uv 
xyZ uv = (x~ u)(y Nv) = uv 
(4) 
if and only if 
u=xNu 
xDu 
xy ~_ uv 
X~ U 
xy = UV 
X = U 
and v = y ~ v 
and y~ v; 
and y ~ v; 
and y = v. 
12.1. Suppose we have the rules of the form 
uv (=) w, 
applicable to xy if 
x (=) u and y (=) v. 
Then, for such a rule, we have 
xy (=) uv (=) w. 
We can also assume the rules are applicable if 
xy ~ uv, 
xy ~_ uv, 
xy = UV. 
We can not decide which part of w belongs to uv, unless some other information 
is available. 
12.2. 
then 
12.2.1. 
UV ~ W 
be applicable to xy if and only if 
x ~ u and y ~_ v. 
~en xy ~ uv~w. 
This is true for any rule in 
R(xy) = set(uv ~ w: xy~uv). 
If each rule represents the relation 
uv~ w 
u 
(x~ u)(y~v) = xy~ uv~xyn w. 
Let the rules of the form 
If the set R(x~ has sufficient rules to give 
xy : Uw, 
we can find xy by simply taking the union of all the w's in R(xy). 
12~2,2. If the rule~ are applicable to xy when 
Sakai 25 
x ~_ u and y c_ v, 
xy c uv = w. 
We le%ow that a concatenation xy of any two neighborhoods is broken 
then 
doom to the concatenations of elementary neighborhoods e(i)e(j) and that each 
e(i)e(j) is represented as a union of elementary neighborhoeds. 
If x = e(1), 
y = e(2) 0 e(3) ~ e(4), 
for instance, and if we have the rules 
e(1)e(2) ~ e(5) 0 e(6), 
e(1)e(3) ~ e(5) 
and e(1)e(4) ~ e(6), 
then xy ~ e(5) U e(6). 
These rules will be broken down as 
e(1)e(2) ~ e(5) 
e(1)e(2) ~ e(6) 
e(1)e(3) ~ e(5) 
e(i)e(4) ~ e(6), 
and then contracted as 
e(l)(e(2) (+) e(3)) D e(5) 
e(1)(e(2) (t) e(4)) ~ e(6), 
where the symbol (+) means an alternative choice. 
~e number of elementary neighborhoods increases rapidly as the linguistic 
analysis becomes more precise, and hence a grammar prepared in terms of 
e~ementary neighborhoods comprises a great number of entries. However, this 
type of rules is preferred when a particular technique is available on machine 
(Opler et al., 1963). 
12_~.. Let us consider a set of rules of the form 
uv ~ W. 
We assume a rule is applicable to xy if 
x (:) u and y (:) v. 
We have, then, 
u)(y v) :xyOuv xy w. 
Sakai 26 
12.3.1. Suppose the rules of the form 
uv _~w 
are applicable to xy if and only if 
x ~ u and y ~ v. 
For all the rules in the set R(xy) of applicable rules, we have 
xy ~_ uv c w. 
12.3.2. Let the set R(xy) of applicable rules be 
R(xy) = set(uv~ w: x ~ u, y~ v). 
Then, for each rule in R(xy), we have 
xy ~ uv ~ w. 
Taking all the rules in R(xy), we can expect 
xy = Dw, 
and, if the set of rules is prepared so as to meet this condition, we can find 
xy by taking the intersection of w's in R(xy). 
12.4. Let the rules be given in the form 
UV = W~ 
and let R(xy) be the set of rules such that 
x (=) u and y (=) v. 
12.4.1. If R(xy) is the set of all the rules satisfying the condition 
x o u and y ~_ v, 
then we have 
xy ~ uv = w 
for all the rules in R(xy). Then, 
xy ~_ Uuv = U w, 
where the union is to cover all the rules in R(xy); if the rules are prepared 
so that 
xy = U uv, 
then we can find the concatenation simD1y by taking the union of w's of the 
rules in R(xy). 
12.4.2. if the rules are pre~fared so that they may be applied to xy when 
x ~_ u and y C v, 
then xy ~_ uv = w. 
If xy = ~ uv 
is true for all the rules in R(xy), then we can find the desired concatenation 
by 
xy = Nw. 
12.4.3. T= ~ the rules are represented in terms of elementary neighborhoods in 
Sakai 27 
the form 
e(i)e(j) = w(i,j), 
then, in virtue of the coefficients x(i) and y(j), we have 
x ~ U = X ~ e(i) = x(i)e(i), 
y ~ v y S e(j) ' )e(j) = = ykj , 
(X D u)(y~ V) = x(i)y(j)e(i)e(j). 
Therefore, a rule is applicable to ~y if 
x(i) = y(j) = i. 
The result z = xy is obtained as the union of all the w(i,j)'s of the 
applicable rules: 
z = Uw = ~x(i)y(j)w(i4j). 
12.5. The rules are prepared and used more freely according to the given 
condition and requirement. In the following scheme (S'akai, 1961), a com- 
plete neighborhood is represented by a code consisting of a number of digits 
and each digit is checked, modifiedand transferred independently. 
Suppose x and y are given and their concatenation z = xy is required. 
Both x and y can be syntactically ambiguous and their ambiguity is to be 
reduced in the course of finding z. Initially, z is assumed to be the set 
of all the possible contexts, x, y and z are transferred to a temporary 
storage space (xl,Yl,Zl). A rule is applicable if 
x (=) u, y (=) v and z (=) w, 
and the set (xl,Yl,Z l) is modified everytime a rule is applied. If a rule 
proves 
x I (=) u, Yl (=) v, z I0 w = O, 
then the rule is not applied to this set, and another set (x2,Y2,Z2) is 
stored in another storage space as another possible result. All the applic- 
able rules are applied one after another to all the possible sets of 
(xi,Yi,Zi). Similar procedure is repeated over again on two languages 
simultaneously, so that the syntactic structure can be transferred from the 
tree structure in one language to that of another language. ~he form of the 
tree is preserved but their nodes are marked by the labels specific to each 
language, input, intermediate or output language. 
13. Distribution Class Representation of Concatenation Rules. 
Possible concatenation of a language can be formulated as concatenated 
sets of strings. Let 
R = set(r: h(r)) 
Sakai 28 
and S = set(s: h(s)) 
be sets of strings satisfying the conditions h(r) and h(s), respectively, and 
let their concatenation have the property k(rs), so that 
rs E T = set(t: k(t)). 
We consider the concatenation rules of the form 
RS ~ T, 
which reads : 
if 
• then 
r 6 R and s £ S, 
rs K T. 
The point of this representation is that, 
and s 6 S h~ S i~--- OS k, 
then as many rules are applicable to rs and they give 
rs E N --- S% : 
The intersection T' has less number of elements and, if the rules are precise, 
the character of the strings in it is determined as precisely as required. Of 
course, these procedures are not to be done by listing up all the members of 
the sets. Each set in the rules is represented by a code. Every entry of the 
lexicon has a code and it can be determined whether or not the string belongs 
to any given set. These codes are to be generated and attached to rs to 
indicate that it belongs to the set T'. 
Practically, it is convenient to classify the strings in terms of their 
complete neighborhoods: 
R = set(r: h(C(r);u)) = R(u), 
S = set(s: h(C(s);v)) = S(v), 
T = set(t: k(C(t);w)) = T(w). 
A grammar of concatenation will be given as a set of rules of the form 
R(u)S(v) c 
with a relation 
f(uv;w), 
and the rules can be described in a number of different ways according to the 
choice of R(u)S(v), T(w) and f(uv;w). In order to see the principle, we 
simplify the situation by making use of the distribution classes G, H, I and 
J, and by assuming the relation f(uv;w) as 
uv(=)w, 
UV~ W~ 
Sakai 29 
EV ~ w, 
or uv = w. 
lhe type of T(w) is chosen so that the grammar may describe the language 
adequately. 
13.___~1. G Renresentation. 
If 
then 
then 
If 
then 
then 
If 
then 
If 
then 
Put 
~(u) = G(u), 
r E G(u), s E G(v), 
rs E G(u)G(v) ~ G(uv), 
C(rs) (=) uv (=) w. 
r ~ G(u), s ~ G(v), uv ~ w, 
rs E G(u)G(v) c G(uv), 
C(rs) (:) uv ~ w. 
r E G(u), s ~ ~(v), uv ~ w, 
rs 6 S(u)G(v) C G(uv) c G(w). 
r E G(u), s g G(v), uv = w, 
rs ~G(u)G(v) ~ G(UV) = G(w). 
s(v) = G(v). 
uv (=) w, 
necessarily elementary. 
13.2. H Re-oresentation. 
Put 
~(u) = :~(u), S(v) = ~(v). 
Even if a few rules are applicable to rs in these cases, that is, 
rs E G(w~) ~ G(w i) ~ --- ~ G(wx), 
we have no simple way to find C(rs) from w's. We can not specify a set of 
less members which adequately indic'ates the property of rs, unless more spe- 
cific information is available. 
13.1.1. Suppose, however, u and v are elementary. 
If C(r) (=) u and C(s) (=) v, 
then C(r) ~ u, C(s)~v. 
That is, r ~ G(u) = H(u), s ~G(v) = H(v). 
For further discussion, see "H Representation", where u or v is not necessa- 
rily elementary. 
13.1.2. Assume C(r) and C(s) are elementary. 
If C(r) (=) u and C(s) (=) v, 
then C(r) ~ u and C(s) ~ v. 
That is, r ~ l(u) and s E I(v). 
For further discussion, see " I Representation", where no neighborhoods are 
if 
then 
.z,3.2..l. 
then 
then 
then 
then 
We put 
If 
r ~ H(u), s 6H(v), 
rs 6 H(u)~(v) _~ H(uv). 
uv (=) w, 
rs ~ H(u)H(v) ~ H(uv), 
C(r~) o_ uv (=) w, 
C(rs) (=) w, 
rs 6 G(w). 
S~<ai 30 
~(w) = Q(w). 
However, there is no simple procedure of finding the intersection of G(w)'s. 
We can not specify the features of the strings by finding more rules applicable 
to rs, unless more specific informa{ion is available. 
13.2.2. If uv ~ w, 
then rs ~ H(u)H(v) ~ H(uv) ~ H(w), 
because H(uv) = H(w U wi) = H(w) ~ H(w') ~ H(w). 
We put T(w) = H(w) 
to have the rules of the form 
If a number of rules are applicable and 
rs £ H(uh)~(v h) c_ X(w,n) 
rs 6 H(ui)H(v i) ~-H(w i) 
rs ~ X(uk)~:(v k) c_ ~(wk), 
then rs £ H(w h) ~ H(w i) ~ --- OH(w k) 
= :~(wh C wi U --- Owk )' 
then C(rs) O_ w h U w iU --- Ow k" 
The rules of this type are essentially the same as the rules of 
complete neighborhoods 
xy ~ uv ~ w, 
although they are encoded as the sets of strings; 
13.2. 7 . If uv ~_ w, 
then C(rs) ~_ uv~_ w, 
then rs 6 G(w). 
13.2.4. Put 
UV = W. 
Then rs ~ H(u)H(v) ~ H(uv) = H(w). 
Sakai 31 
The situation is the same as the case above, where uv ~ w. 
13.3. ,I, Re, presentation., 
Put 
R(u) = i(u), S(v) = l(v). 
If r £ i(u), s 6 i(v), 
then rs ~ I(u)I(v) ~ l(uv). 
!3.3.1. If uv (=) w, 
then C(rs) c uv (=) w. 
No relationship is relevant between C(rs) and w. 
13.3.2. If urn_w, 
then C(rs) c uv ~ w. 
m 
No definite T(w) is available, such that I(u)l(v) ~_ T(w). 
13._~3.. We consider the rules of tie type 
i(u)I(v) 
with uv ~ w. 
If r£ i(u), s£1<v), 
then rs { I(uv) = i(w). 
If a nmmber of rules are applicable to rs, 
then rs £ I(w h) N I(wi)~ --- O I(wk) 
= I(w h ~ w i~ --- ~Wk). 
%herefore, the rules of this type are equivalent to those of the type 
xy C uv C w. 
13.3.4. Put 
• Then 
UV = W, 
rs ~ I(u)i(v) ~ I(uv) = I(w). 
This is the same to the case mentioned above. 
13.4. J Reoresentation. 
Put 
~(u) = J(u), S(v) = J(v). 
This type of grammar is not practical because every real distribution class 
J of the language must be listed in the rules, k~:is condition corresponds 
to the com}~lete neighborhood representation of rules f(uv;w) applicable to 
xy only if 
x = u and y = v. 
13.5. Practically, the rules can be written more freely and the program 
can be more flexible and efficient, provided that a more sophisticated 
Sakai 32 
scheme is introduced to the G Representation and the condition f(uv;w). ~is 
is realized by representing the sets of strings by codes, so that the union 
and the intersection of any two sets are determined by the operation on the 
codes. 
14. Some Remarks on Transformation. 
14.1. It is generally agreed that we generate acceptable strings by starting with 
an axiom and expanding it repeatedly into a string of constituents. This pro- 
cedure is taken care of by concatenation rules. After generating one or more 
strings by this procedure, they are transformed to yield another string. 
Let us imagine another function of our normative device. We give it a 
pair 
r = (r',r") 
of acceptable strings 
r' = r'(1)r'(2)---r'(i')---r'(m') 
and r" = r"(1)r"(2)---r"(i")---r"(m"). 
The pair r will be referred to as a string 
r = r(1)r(2)---r(i)---r(m) 
with m = m' + m". 
We put m" = 0 
if the string r" is absent. We then give it another acceptable string 
s = s(1)s(2)---s(j)---s(n), 
and ask it whether or not the string s as an expression is true if both r' 
and r" are true. If the device says "yes", we consider the string s is gene- 
rated from r by a transformation. We call r the original string and s its 
orano_o~.n. If it says ~'no", no such transformation exists. Conversely, we 
ask it whether or not r' and r" are true if s is true. If the device says 
T~Xr~f ~ , we consider an inverse transformation exists, such that s is expressed 
by r' and r". We can find many cases in which the device would say "yes" for 
transformation but "no" for inverse transformation. Some information is sup- 
posed to have been lost in generating the string s, which can not be retrieved 
unless appropriate, possibly non-linguistic, information is supplied. ~%is 
situation is beyond the scope of Syntaetics. 
A transformation or an inverse transformation is called singularly if r" 
in r is absent, and it is a generalized one if both r' and r" are present. If 
it is an embedding transformation, r' and r" are called matrix and constituent 
strings, respectively. 
If we understand the transformation in the sense mentioned above, the 
transfer of syntactic structure from one language to another is also a trans- 
Sakai 33 
formation (Gross, 1962). 
14.2. If it is known that r is transfor~ed to s, then ..... ~n~o fact ms used to 
generate a particular string. If r is known to be an inverse transform of s, 
then this is used to recognize s, giving a possible derivational history. 
if no other such transformations are found, r is the only nearest history. 
Otherwise, the ambiguous history is to be accounted for by other rules. 
If we find r and s such that r is true if and only if s is true, then we 
say r and s are equivalent and write 
r eqv s. 
Obviously, this equivalence is symmetric, reflexive, and transitive. A 
transformation that transforms a string into an equivalent string is called 
an equivalence transformation, if we have a grammar consisting of equivalence 
transformations only, it can be used for both synthesis and analysis. 
Let us confine ourselves to the equivalence transformations in order to 
simplify the discussion, and assume we have a set of rules or a normative 
device. A generalized transformation transforms a oair r = (r' r") of strings 
into one strin~ s. ~e inverse transformation by the same rule dissolves a 
string s into a pair of strings (r',r"). ~en, r' or r" is regarded as an s, 
and, if we find an appropriate rule, it is again dissolved into two acceptable 
strings. By repeating the same, we have a number of equivalence relations 
which can be arranged as a tree: 
s eqv (r(1),r(2)); 
r(1) eqv (r(ll),r(12)); 
r(2) eqv (r(21),r(22)); 
r(ll) eqv (r(lll),r(ll2)); 
r(12) eqv (r(121),r(122)); 
If an acceptable string t can no longer be dissolved into two acceptable 
strings, we call t a terminal or an atomic acceptable string. ~nroughout 
this procedure, the strings are expected to become shorter and simpler, because 
equivalent information is expressed by many separate strings. It will be 
still possible to transform an atomic string to another atomic string by means 
of a singulary transformation. We have different atomic strings which are 
mutually equivalent. We may pick up one of them and call it a kernel string. 
1~e sequence of inverse transformations is not always uniquely determined. 
There can be other orders of dissolving a given string into atomic strings. 
We can make the grammar less redundant by studying the possible sequences of 
Sakai 34 
inverse transformations. If the rules are all equivalence rules, there is no 
theoretical problem of ambiguity• ~ne investigation of these problems requires 
quite a different treatment, and will not be included in this paper. 
14.3. Sometimes, it is considered more linguistically reasonable to assume 
" S ~rln~ or that a string is not acceptable but its transform is an acceptable ~ " ~ 
~. a constituent of an acceptable string, in some other cases, a s~ing may be 
an acceptable string and its transform may not be an acceptable string or a 
constituent thereof In other wo~as, a transformation is applied to an un- 
acceptable string or a transformation results in an m%acceptable string. We 
may prepare the rules in such a way that a sequence of obligatory transform- 
ations is contracted to a single ~ale. This seems formally simpler and con- 
sistent. However~ it will result in a more entangled system of grammar. We 
admit some of such strings as potentially acceptable and indicate it by a 
marker, This convention is somet~nes useful not merely as a technique but also 
as a consistent and more plausible derivation of acceptable strings. It is 
known that a string of a Chinese dialect marked potentially acceptable for the 
derivation of apparently inconsistent strings is quite acceptable in another 
dialect (Wang, 1964). 
14.4. A generalized transformational rule consists of terms u and v, where 
u = (u',u") 
= u(1)u(2)---u(i)---u(m), 
u' = u,(1)u'(2)---u'(i')---u'(m'), 
u" = u,(1)u"(2)---u"(i")---u"(m"), 
m = m r. ~ m ~r, 
u becomes v~ 
v = v(!)v(2)---v(j)---v(n). 
Most rules are accompanied by a number of restrictions imposed on the 
original strings and their transforms as well as some manipulations of strings. 
~ese are classified into a few types and subroutines are to be prepared for 
them. Some of the operations are listed below, which have been picked up 
sporadically from the rules for generating Chinese strings (Hasimoto, 1964). 
(0) A routine supervising the subroutines takes care of the whole procedure 
of applying the rules to a string, if the rules are prepared in a defin- 
ite format, they are automatically checked and applied to the given string. 
(I) Certain segments r(h) and r(i) in the original string must or must not 
share a certain feature in common and/or a segment r(j) must or must not 
have a certain feature. 
Sakai 35 
(2) The segment r(i) of the original string and the segment ~(o) of the trans- 
form must or must not have the same feature specified by the rule. 
(3) Some segments in the transform must satisfy the condition similar to (I). 
(4) Absence and/or presence of particular segments must be ~ cne c~ed. 
(5) Positions of certain segments in the string must be found. 
(6) A check of the derivational history somet~les decides the recursive 
application of the rule~ 
(7) The tree structure must or must not be changed by the final procedure of 
a transformation. 
~. No rule describes a transformation of an individual string r into an 
individual string s. The rule says, if the string r has the feature 
u : u(1)u(2)---u(i)---u(m), 
then it is transformed to another string s which has the feature 
v : v(1)v(2)---v(j)---v(n). 
What are these features? They must be defined on the basis of the 
answers of our normative device. The program must be consistent with the 
features defined. Once a program is written and decided to be used, the 
program is the definition. If the program is modified, the rules and the 
lexicon are to be modified. 
Since the transformations are applied to P-markers, a string is considered 
to be a tree-like string, if it is a linear string of terminal nodes, the 
other non-terminal nodes and the branches are to be determined by virtue of 
the concatenation rules. We consider the labels u(i) and v(j) are complete 
neighborhoods, if the concatenation rules are written in terms of complete 
neighborhoods. If the concatenation rules are written in terms of distribution 
classes, u(i)'s and v(j)'s are considered to be distribution classes. 
14.6. The complete neighborhoods are defined on the basis of concatenated 
strings and we have to associate them with the labels given to the nodes of 
our transformational rules in order that the kernel strings can be transformed. 
Let us see what happens when the nodes are assumed to be complete neighbor- 
hoods. 
Let 
p = (p',p") 
be a pair of acceptable strings p' and p", and let 
r = r(1)---r(i)---r(m) 
be a segment of p. The pair p is transformed by T into 
Sakai 36 
q = T(p), 
and the segment appears in q as 
s = s(1)---s(j)---s(n). 
Some strings may have been added and some others may have been deleted. 
Put 
x(i) : C(r(i)), 
x : C(r)~ 
y(j) = C(s(j)), 
y : C(s). 
By definition, 
x : x(1)---x(i)---x(m), 
y = y(1)---y(j)---y(n). 
Any string belongs to one and only one distribution class J. 
instead of 
Therefore, 
T(r(1)---r(i)---r(n)) = s(1)---s(j)---s(n), 
we write 
T(J(x(1))---J(x(i))---J(x(m))) 
= J(y(1))---J(y(j))---J(y(n)). 
Since all the elements in a J has the same complete neighborhood, we rewrite 
the above as 
T(x(1)---x(i)---x(m)) = y(1)---y(j)---y(n). 
This is rewritten again by breaking down in the form 
X = x(1)---x(i)---x(m), 
y : T(x) 
= y(1)---y(j)---y(n). 
If we have a complete set of rules which gives the concatenation of any 
complete neighborhoods of the language, then we can find the complete neigh- 
borhood x. The transformation takes place when x is changed to y. The string 
y is to be generated in virtue of the information brought forward from x and 
the structural requirement of y itself. A transformation is then interpreted 
as: 
~ne complete neighborhood x of the node dominating the string 
x(!)---x(i)---x(m) 
of complete neighborhoods is transformed to another complete neighborhood y of 
the node dominating the string 
y(1)---y(j)---y(n). 
Sakai 37 
This interpretation, however, suggests a few problems, 
14_~. We know that 
J(x(1))---J(x(i))---J(x(m)) (J(x), 
J(y(1))---J(y(j))---J(y(n)) m J(Y)" 
The statement "x is transformed to y" is a generalization of the original 
fact, and this generalization is not always true. The text should be checked 
before a transformational rule is applied to it. Some separate steps for this 
purpose will save the machine time. 
(1) 
(2) 
(3) 
14.8. 
A text to be parsed must consist of segments specified by the rule. The 
correct segmentation can be done by finding the tree structure of the ! 
text. Therefore, the concatenation rules must be prepared so as to ~ 
account for the structure of any acceptable strinG. 
Not all the trees of the specified form undergo the inverse transformation 
so that the derivational history may be traced back. The nodes are 
labeled. A tree of a form can correspond to a number of trees whose nodes 
have different labels. 
When a string is being synthesized, the text is given as a pair of P- 
markers. A rule can be applied only if the P-markers meet the condition 
specified by the rule. 
We may regard the structure mentioned above as a representation of 
derivational history. The history can be recorded by listing all the deriv- 
ational steps the string has experienced. This representation, however, will 
be redundant and inefficient, because it is likely to occur that an identical 
series of transformations is applied to strings of different history. On the 
other hand, it is also possible that the strings p and q of different histories 
result in an identical string s by a transformation and the string s is am- 
biguous in that the s from p can undergo a sequence of transformations and the 
s from q another; thus the structure itself can not be an absolutely reliable 
marker. 
We think it more practical to associate the rules with the features in 
the P-marker to which the rules are applied. '~lese features should correspond 
to the series of transformations applicable to the P-marker in case of syn- 
thesis and the series of inverse transformations in case of analysis. We have 
some rules with notes on the type of transformations to which the resultant 
strings may be exposed (Hasimoto, 1964). 
15. Complete Neighborhppds and Transformational. Rules. 
Let us assume u(i)'s and v(j)'s are complete neighborhoods. 
Saka± 38 
~. Two strings r and s may replace th~ same non-terminal node to yield a 
longer acceptable string. However, when a transformation T is to be applied, 
they must hav~ the specified structure; thu~ the str!n~ p with r a~ a ~e~ment 
in it may be transformed by T, while the string q which differs from p only in 
that it has the segment s in the place of r may not. The lack of q by T means 
C(r) / C(s). 
1_~,2. Because of this complexity involved in natural languages, we encounter 
a difficulty when we try to prepare a set of syntactic data for practical 
purposes. We refine the definition of complete neighborhood in such a way that 
C(r) of a string r is the set of all contexts of r which appear in the strings 
to which no transformations have ever been applied during their derivation. 
The difference between r and s is found in their internal structure, if the 
machine is given only the input string to be parsed. In order to indicate this 
difference, we put 
c(r) U O(r) = 
where C(r) is defined over ~.,e sez of kernel strings, 
D(r) is defined over the set of transforms, 
E(r) is defined over the set of kernel strings and 
transforms. 
Let c(i) be an elementary neighborhood defined over the set of kernel 
strings, and let r be a real or imaginary string such that 
C(r) = o(i). 
Let d(i;j) be the elementary neighborhood defined over the set of all the 
possible transforms of which r is a segment, where j corresponds to the 
possible sequence of transformations. Putting 
c(i)~ d(i;j) = e(i;j), 
we have the elementary neighborhood e(i;j) defined over the set of kernel 
strings and transforms. These e(i;j)'s are no longer necessarily disjoint: 
e(i;j) ~e(i;j') ~ c(i). 
l_l_l~. ~e separation of kernel strings and transforms still involves a con- 
siderable complexity. Let q be a transform. It is a transform generated by 
a transformation in a sequence of transformations and it can be an original 
string to be transformed by the following transformation. 
A transformation is accompanied by the set P of original strings and the 
set Q of transforms: 
P = set(p: T is applicable to p), 
Sakai 39 
Q = set(q: q = T(p), p in P). 
We simplify the situation by defining the complete neighborhoods over P and 
over Q. The feature of T is shown more explicitly in this way. Let A be a 
node and imagine a derivation by the context sensitive rules 
A ~> BC 
B F / ---C 
c--> G / B--- 
where the s~nbols are assumed to be complete neighborhoods. Let B be replaced 
by F first to yield FC, and the third rule can no longer be applied because of 
the lack of its necessary environment B---. When these rules are to be used 
in analysis, none of the contexts ---C or B--- is relevant in the given string 
FG of complete neighborhoods. We can get rid of this difficulty by defining 
B and C over a set of strings and F and G over another, and by considering a 
transformation from BC to FG, prohibiting the operations on the strings FCand 
BG. 
l~t 
p = p(1)---p(i)---p(m) 
be a string in P, and let 
q = q(1)---q(j)---q(n) 
= T(p) 
be the transform of p by T. We define the complete neighborhood of ~(i) over 
P and that of q(j) over Q. By modifying the meaning of the notation, we put 
x(i) = C(p(i)) over P, 
y(j) = D(q(j)) over Q. 
The requirement that p(i) should appear as q(j) in Q gives 
p(i) = q(j), 
c(p(i)) # o, 
O(q(j)) 0; 
if p(i) does not occur in Q, then 
x(i) = C(p(i)) over P 
= E(p(i)) over P ~ Q; 
if q(j) does not occur in P, then 
y(j) = D(q(j)) over Q 
= E(q(j)) over P ~ Q. 
The relational conditions imposed on the segments p(i) of the original string 
Sakai 40 
and q(j) of the transform are indicated in terms of E(p(i)) and E(q(j)), or 
by a relation between C(p(i)) and D(q(j)). 
be set Q can include a part of the set P' of original strings to which 
another transformation T' can be applied. ~hus, we can classify the strings 
with respect to possible transformations. We have no positive grounds to 
assume any natural language has a stratified system of layers arranged one over 
another. • -~ 
15.4. Let 
u = (u' u") 
= u(i)---u(i)---u(z) 
be a pair of concatenations 
u' = u'(1)---u'(i')---u'(m') 
. and u" = u"(1)---u"(i")---u"(m") 
of complete neighborhoods u'(i')'s and u"(i")'s defined over P. If the string 
is linear, the non-terminal nodes are to be determined by concatenation 
rules. We assume the rules of the form 
f(T(u);v) 
mean, over Q, a relation between T(u) and v. We assume further a rule is 
applicable to the given pair of concatenated complete neighborhoods 
x = (x',x") 
= x(1)---x(i)---x(m) 
if the condition g(x;u) holds. That is, 
if g(x;u) over P, 
then f(T(u);v) over Q. 
We expect to find the transform T(x) in terms of v of the rules in the set 
R(x) = set(f(T(u);v): g(x;u)) 
of the applicable rules. 
Given the rules of the same form and a string represented by a concate- 
nation 
y = y(1)---y(j)---y(n) 
of complete neighborhoods, an inverse transformation is to be carried out by 
finding the set 
R(y) = set(f(T(u);v): h(y;v)) 
of applicable rules. 
With all the linguistic difference between the concatenation rules and 
transformational rules, they exhibit formal similarities when the labels are 
Sakai 41 
assumed to be the sets of contexts. We will not repeat a similar discussion 
on the choice of f(T(u);v), g(x;u), h(y;v) or the algorithm for finding x or 
y. 
16. Distribution Classes and Transformational Rules. 
Let p be a string and T(p) its transfo~n by the transformation T. Let P 
be a set of strings p to which T is applicable. We defined the transform T(P) 
of P as the set of all T(p)'s: 
T(P) = set(T(p): p in P). 
A rule will be written in the form 
f(T(P);Q) 
to indicate a relation between the sets T(P) and Q. 
In order to specify the sets a little closer to the form of rules usually 
prepared by linguists, we put 
p = p(1)p(a)---p(i)---p(m) 
q = q(1)q(2)---q(j)---q(n), 
where p(i)'s and q(j)'s are segments in p and q, respectively. Then we put 
P : P(1)---P(i)---P(m) 
Q = Q(1)---Q(j)---Q(n), 
which are to be understood as concatenated sets if strings. 
A rule of the form f(T(P);Q) is applicable to the string p, if 
p(i) ~ P(i) for i = i, 2, ---, m, 
giving T(p) 6 T(P), 
so that f(T(P);Q) 
provides us with the information governed by this rule. Each string in the 
lexicon and each constituent in the string under analysis or synthesis is 
given a marker which indicates whether or not it belongs to any set of strings, 
provided that the sets are established systematically. Because of the ambiguous 
property of real strings, the markers will be given interms of complete neigh- 
borhoods defined over the set of (potentially) acceptable strings. 
17. Establish!~ent and Representation of Complete Neighborhoods. 
A syntactic function is called a complete neighborhood if it is defined 
as a set of contexts. We use conventional terms and redefine them as symbols 
assigned to complete neighborhoods.. 
17.1. In establishing a set of complete neighborhoods of a natural language, 
we assize a few of them as undefined terms and derive the others by hypothetical 
concatenation rules. Sometimes, there will be a choice among a few hypothetical 
Sakai 42 
rules. We take one of them to define a complete neighgorhood and regard the 
others as the property of the complete neighborhood defined by the former. 
Thus, we distinguish two kinds of rules: definition rules and property rules. 
Let 
axb = c 
and xd = f 
be hypothetical rules. If one decides to regard the former as the definition 
of x, the latter is a property of x. ~%is method is applied not only to phrase 
structure grammar but also to transformational o~ammar, because both trans- 
formations and inverse transformations are applied to a (pair of) P-marker(s) to 
yield another (pair of) P-marker(s). 
Every time a definition rule is established as a hypothesis, it must be tested 
as to whether or not it contradicts any other definition rules. "~ ~,o property 
rules should contradict any other rules. %~nenever a contradiction is found, 
the source of trouble must be found out by tracing back the definition rules, 
and the hypothesis that has given rise to the trouble must be modified. 
17.___~2. The complete neighborhoods of all the acceptable strings (as distin- 
guished from the other ambiguous interpretations of the same string) are 
identical to each other and consist of one element indicating that the strings 
are acceptable. It seems adequate, for most of the natural languages, to 
admit two complete neighborhoods, nominals and verbals, although there are no 
rigid grounds. Many others are derived from hypothetical concatenations that 
can occur in acceptable strings. 
The prepositions in many European languages are subclassified by the case of 
thenominals they govern, and the nominals by their case, gender and number. 
A rule for yielding prepositional phrases will be stated as follows: a pre- 
position that governs nominals of case c, followed by a nominal of case c', 
of any gender and of any number, results in a prepositional phrase, provided 
the cases c and c' are the same. As suggested in this example, subclassific- 
ation and desubclassification are useful to describe syntax. A number of 
indices are made use of in subclassifying a broadly defined complete neighbor- 
hood. The example above will be rewritten, by introducing the indices c for 
case, g for gender and n for nu~nber, and a coefficient d(c,c'), in the form 
prep(c) n(c';g;n) = d(c,c') prep-n, 
where d(c,c') = 1 if c = c', 
= 0 if c ~ c'. 
Sakai 43 
%he indices g and n are arbitrary if the preposition in question takes nominals 
of any gender and of any number. 
Usually, a linguist will define complete n,~g~noornoocs broadly so that 
the majority of acceptable ..... ....... ~rmn~ may be generated and recognized correctly. 
As his analysis proceeds further in c~eoa1~, he ~ill take an exa~mT~le that is 
not generated or recognized correctly by his broadly defined complete neigh- 
borhoods: generation may give him some unacceptable strings or the syntactic 
analysis may give him erroneous or unnecessarily ambiguous interpretations. 
He will then trace back the definitions and find out some of his rules hold in 
his example with respect to a subset of one of his complete neighborhoods. 
Suppose he has a set R(xy) of rules to concatenate x and y. His new example 
will indicate that the rules are not always true. He may then establish the 
subsets x', x", y', y", and a new set of rules which allows x'y' and x"y ~', 
for instance, but not x'y" or x"y'. 
17.3. Let a broadly classified complete neighborhood be shown by a symbol, 
say, v. If a subclassification thereof is desired, we introduce an index p, 
such that 
v : v(p l) U v(p 2) U--- Uv(pn). 
When the subclassification is not necessary, we put p = O; 
v(o) : Uv(pi ), i : l, e, ---, n. 
The union of a few subsets are written as 
v<Pl,P3,P 5) : v(P I) U v(P 3) U V(Ps), 
etc. 
If a complete neighborhood is to be subclassified from a few different points 
of view, ~s many indices are introduced: 
v(p;q), v(p;q;r), etc; 
v(Pl,P2; q) = v(Pl; q) ~ v(P2;q), 
v(p;ql,q a) : v(~;q l) U v(p;qa), 
v(p;o) n v<o;q) : (Uv(p~qj)) ~ (Uv(pi~q)) 
= v(p;q), 
etc. 
Hence, for the distribution classes 
~(V(Pl,pa;~)) : H(V(~l;q)) N X(v(Pa;q)), 
I(v(p;q)) = !(v<p;o)) ~\]i(v(o;q)), 
Sakai 44 
etc. 
Sometimes, an index depends upon other indices: 
v(p;q(r;~;t)), 
for example. ~%e meanings of r, s and t depend upon the meaning of q. 
The above scheme may be further generalized. Let a complete neighborhood 
be represented by a number of indices 
(a;b;c;---;n), 
where the broad class symbol is one of the indices and each index represents 
a classification from a certain point Of view. 
It will be of interest to compare these indices with the concept of 
"razbijenije", "okrjestnostj" (Kulagina, 1958) or "sememe" (lamb, 1962). ~nis 
kind of representation, used by many research groups, enables us to describe 
the syntax of a language systematically. Each digit can be regarded as an 
indication of a certain feature common to some elementary neighborhoods, and 
classifies them according to their specific features. 
1_~.4. Suppose a concatenation rule f(uv;w) is to be applied to a text xyof 
complete neighborhoods to determine z = xy, and the complete neighborhoods are 
represented by the indices in the form 
x = (a(x);b(x);---;n(x)), 
y = (a(y);b(y);---;n(y)), 
z = (a(z);b(z);---;n(z)), 
u : (a(u);b(u);---;n(u)), 
v = (a(v);b(v);---;n(v)), 
w = (a(w);b(w);v--;n(w)). 
If a rule indicates the relation between the pair (i(u),j(v)) of indices and 
an index k(w), and if all the others are independent of these, we have 
u = (o;---;o;i(u);O;---;o), 
v : (o;---;O;j(v);O;---;O), 
F w = (O;---;O;k~w);O;---;O). 
If the pairs (i(x),i(u)), (j(y),j(v)) and (k(z),k(w)) satisfy the condition 
specified by the grammar system being used, the rule is applied to xy and 
gives a z modified by this rule. ~ne rule gives no information as for the 
other indices. This information should not be lost if it is in x or y. 
We have to indicate in the rule how to transfer the information to z from x 
or y. A simple method was used in a translation program (Sakai, 1961). 
A transformational rule requires that certain features of the original 
Sakai 45 
string are carried forward to its transform. ~lis requirement is usually 
indicated by the identity of features of certain segments in the original 
string and its transform. The use of rules is to be programmed in such a way 
that, if the rules are applicable to the string regardless of a certain index, 
the value of the index in the original string is transferred to the corres- 
ponding index of the transform, and vice versa in case of an inverse trans- 
formation. 
17_~.. An extremely simplified example is given. %~ne complete neighborhoods 
are no longer treated as sets. The symbol ~'+" means "or". The symbol "=" 
does not necessarily mean an identity: it can be replaced by an arrow. The 
segments of the string 
~hey are red ~ianes 
1 2 3 4 
are rePresented in the form (h,k): 
(i,i) = they, 
(1,3) = they are red 
(2,3) = are red, 
etc. 
Both (h,i)(j,k) and (h,i) * (j,k) mean the concatenation of the strings (h,i) 
and (j,k). The following abbreviations are used. 
adj: adjective 
adj-pred: adjectival predicate 
anim: animate 
compl: complement 
inanim: inanimate 
m: masculine 
n: nominal 
n/n: modifier of nominal 
nom: nominative 
pl: plural 
pn: pronoun 
s: sentence 
v: verbal 
-k: ends with k 
-t: ends with t 
Sakai 46 
Input Langua ~e ..... 
(l,4)(v;s) = (l,1)(pn;3rd "'~),~.- ~ (2,2)(v;be;pres;3rd;pl) * (3,4)(n;p!) 
(3,4)(n;pl) : (~,3)(ac, j) ~ (4,~)(:~,;'?l) 
Intermediate Renresentaion. 
(l,4)(v) = (i,l)(pn;3rd',p-,;'nom) '~ (2,2)(conula;pres). * (3,&)(n;compl;p i) 
(3,4)(n;comp!;pl) = (3~3)(n/n) * (4,4)(n;compi;pi) 
Output Lan~ua{e (Russian) 
(i,l)(pn;3rd;pl;nom) = on(Dl;nom) = oni 
(2,2)(copula;pres) = () 
(3,3)(red)(n/n) = krasn(adj;hard) 
(4,4) (plane)(n;comp!;}l) = (rubank(-k) ~ samoljet(-t))(n;m;pl;nom) 
= (rubanki + samcijety)(n;m;pi;nom) 
(3,4)(n;compl;pl) = (b,b)ta~:;na;~J ~ (4, ~)(n;m;pl;nom) = (3,3)-yje(4,4) 
' ...... ' " " I"UO~'.-~ -i- = ,') = ~ samoljety) (i,4)(v) (i,i)~,~,)<~ . onto k~'asnvje ( ....... 
Output L~n,':ua::e :- " " 
(1,1)(pn;Srd;pl;nom) = (i~are(anim) ~ sore(inanim))(pn;pl;nom) 
(2,2)(copula;pres) = ar(v;%;pres:final) = ar-u 
(3,3) (red)(n/n) = aka(adj-pred~n/n) 
(4,4) (plane) (n;compl;p!) = (keimen ¢ hikooki) (n;inanim;compl) 
(3,4)(n;compl;pl) = ((3,.-5)-i(4,4))(n;inanim)-de 
(l,4)(V) = (l,!)(anim,:inanim~pn;pi;nom) * (~,4)(n;inanim)-de * 
( 2,2 ) (v; %; lores ; ~inai) 
= (l,i)tlnan~m;pn;ip;nomj * <p,4)(u;mz~onmm)-~e * (2,2)(v;4;pres;final) 
= sorera (ga ~ wa) akai (heimen + hikooki) de aru 
17.6. We observe in ~he above example ~hat the index of an animate or an 
inanimate object affects the choice of a lexicai element in Japanese while it 
is not relevant in ~zlzsn. if'his phenomenon may be considered syntactic in 
one lauguage and semantic in another. Take two languages A and B, and suppose 
A has a syntactic marker o '~ qender and '5 does not. The gender is considered 
syntactic in A and sema:r~ic iu S. The syntactic genders are sometimes arbi- 
trary and can not be al'.~-,?/~ nrcse::'vec i'a the ~ranszer process from one language 
to another. We will ,:~v~ -~= t;o --'~*e.,~ar<.~~: - ~ two se;oarate_ procedures for handling 
.~r;.~ ....... armse ~.~.~ res::~ec~ to ozher indices gender. Si::;ilar ~-" - ~ ...... : 
~e choice of iexical elements de\]cends greatly upon the habitual usage 
~.~on is si;t;iiar when we observe some combinations of of language, k~ne =-' ~ ....... 
longer constituents.. The ch,:,.ice of constituents is limited by logical, 
semantic or habitual reasons as indicated by the branches of' the second kind 
Sakai 47 
in the net strings. Sometimes the choice is quite capricious. It seems more 
practical to handle this kind of information separately (Matthews, 1965), 
corresponding to the separate normative devices the lin&~ist has conjectured. 
Acknowledgment. 
The need of defining distribution classes was recognized when I was with 
the Machine Translation Project, bniversity of California. The basic approach 
was worked out at the First Research Center, Defense Agency of Japan, and was 
refined and finished at the Project on Linguistic Anaiysis, Ohio State 
University. I appreciate the encouragement of these organizations. 
Sakai 48 
Appendices. 
A-I. Sets. 
a ~ A; ~ in A: ~ is an element of the set A; ~ belongs to A; ~ is in A. 
a~A; ~ not in A: a~A is not true. 
A (=) B: there is at least one element which belongs to both A and B. 
A~ B; B~ A: if a ~ A, then a~ B; A is a subset of B; B is a superset of A. 
A = B: a ~ A if and only if a ~ B; A~B and A~B. 
A # B: A = B is not true. 
A = O: there is no element in the set A; the set A is empty. 
A = set(a,b,c,d): A is a set whose elements are a,b,c and d. 
A = set(ai: i = 1,2,---): A = set(al,a2,---). 
A = set(a: f(a)): a~ A if and only if f(a) is true. 
A = B ~ C: A = set(a: a ~ B or a ~ C); A is the union of B and C. 
A = Us i, i = l,a,---: ~ : BIU B 2U--- • 
A = U B for f(B): A is the union of all B's satisfying f(B). 
A = B~ C: A = set(a: a ~ B and a ~ C); A is the intersection or meet of B and C. 
A = D i' i = 1,2,---: , = n B 2 n -- 
A = ~B for f(B): A is the intersection of all B's satisjying f(B). 
A-2. Boolean Coefficients. 
We introduce coefficients which indicate presence or absence of sets. 
The value of a coeffi- 
ax = 0 = empty set, if a = O, 
=x, if a =!. 
The sum a ÷ b and the product ab = a X b are determined by 
axU bx = (a + b)x = x, if a = I or b : l, 
= O, if a = b = O, 
and ax ~ by = ab(x D Y) = (a X b)(x ~ y) = x D Y, if a = b : i, 
= O, if a = 0 or b = O. 
Therefore, the coefficients are Boolean: 
0 + 0 = O, 0 + i = i + 0 = i + i = i, 
0 X 0 = 0 X I = i X 0 = O, I X i = i. 
Consequently, for concatenation, we have 
(ax)(by) = abxy. 
Let a, b, etc. be the coefficients and x, y, etc. sets. 
cient is either 0 or i: 
Sakai 49 
Table of Contents 
1. 
2. 
3. 
4. 
5. 
. 
7. 
8. 
9. 
lO. 
ll. 
12. 
13. 
14. 
15. 
16. 
17. 
Introduction. 
Symbol; String; Language. 
Context: Neighborhood. 
Equivalence of Contexts. 
Complete Neighborhood. 
Elementary Neighborhood. 
Distribution Class. 
Concatenation. 
Concatenation of Complete Neighborhoods. 
Concatenation of Distribution Classes. 
Rules for Recognition and Generation. 
Complete Neighborhood Representaticn of Concatenation Rules. 
Distribution Class Representation of Concatenation Rules. 
Some Remarks on Transformation. 
Complete Neighborhoods and Transformational Rules. 
Distribution Classes and Transformational Rules. 
Establishment and Representation of Complete Neighborhoods. 
Acknowledgment. 
References. 
Appendices. 
Table of Contents. 

References

Gross, M.: On the Equivalence of Models of Languages Used in the Fields of 
Mechanical Translation and Information Retrieval, NATO Advanced Study 
Institute on Automatic Translation of Languages, Venice, 1962. 

Hasimoto, A. Y.: Revised Rules of Mandarin Grammar, Project on Linguistic 
Analysis, Ohio State University, Columbus, Ohio, 1964. 

Kulagina, O. S.: Ob Odnom Sposobje Oprjedjeljenija Grammaticeskix Ponjatij 
na Bazje Tjeorii ~ho~estv, Probljemy Kibjernjetiki, Vypusk i, Moskva, 
1958. 

Lamb, S. M.: Outline of Stratificational Grammar, University of California, 
Berkeley, California, 1962. 

~tthews, P. H.: Problems of Selection in Transformational Grammar, private 
circulation, indiana University, to appear in the Journal of Linguistics, 
No. l, 1965. 

Opler, A.; Silverstone, R.; Saleh, Y.; Hildebran, M.; Slutzky, I.: The Applic- 
ation of Table Processing Concept to the Sakai Translation Technique, 
Mechanical Translation, vol. 7, No.2, 1963. 

Parker-Rhodes, A. F.: A New Model of Syntactic Description, 1961 International 
Conference on Machine Translation of Languages and Applied Language 
~alysis, Her Majesty's Stationary Office, London. 

Sakai, I.: Syntax in Universal Translation, 1961 International Conference 
(See above). 

Wang, W. S.: Two Aspect Markers in Mandarin, Project on Linguistic Analysis 
(See above), Report No. 8, 1964. 
