(SANITIZED)UNCLASSIFIED ENGLISH-LANGUAGE CZECHOSLOVAK PAPERS ON MATHEMATICS(SANITIZED)

• Document Type: CREST
• Collection: General CIA Records
• Document Number (FOIA) /ESDN (CREST): CIA-RDP80-00247A003100530001-7
• Release Decision: RIPPUB
• Original Classification: C
• Document Page Count: 21
• Document Creation Date: December 27, 2016
• Document Release Date: March 4, 2014
• Sequence Number: 1
• Publication Date: October 29, 1964
• Content Type: REPORT

Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
R
50X1 -HUM
Next 2 Page(s) In Document Denied
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
?
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
Applications of graph theory to Liathsoatical gio and lingalsties
? First of alit) graphs *lose vertices al,,e wt.raor,ie Leiacnts
of a free semigroup2 will be,considared., Thell sou,e labellea graphs
will be mentioned; and an example of u qoubln graph of a set
with two binary relationsviii be egtibited Finallyn ordinary und
rected graphs will also be treata/.
Tiathematical lo Iic end theory of lapa,eFs
The main aim of mathelltical logic is the stud of ths binary
/relation of dedu.cibilitr in various logical foralloms or abstract
law-macee. srou a quite general point of view the situation r be
ciescribed e foliows?
-A finite_al '..211..&E.k. (or vocabulaxo V is given; the universal.
language V
\
is the free semigroup of strings (or words or sentences
over V under the operation of concatenation with the identity ele-
*.*........-....-~????????
? (
merit JV Furter, a finite set of proper rules ioteV?Q A )1 43-*
la given. ie we have a graPh 2, and (1,4r41?q, ) 64. 1r)
lr) inCt
for all
(8) If CW4 49 led E otit for ; then (iti..f 44:&17 ct
- If is clear that condition (7) is unsuitable because it
concerns the infinite relation cn 0\ On the other hand (7) is very
similar to the condition of atransitivity. A binary relation it
is said to be Wansitive if it satisfies
(9) if C )E it then ta
49 such that 4?- L.
and there is no path Cat )
41;
If en is an atran ^,
sitive binary' relation then ,not be
atran itive i.e the property. of etransitivity is not n?.(lant:
under the context operator
pairs NI: /
and
Ase, 443 ve.,"
Bog" let 4 contain tnc
/Al' a ar4r4z,, 0,104'
f 4
or 4--g where
4.*
?e Now by (1)1 (gox4 cn,te-)Ecet
0141,)e c 9 And of course also(
from (9) i follows that CA is not atransiti4e..The condition for
Xt which corresponds to atransitivity of. CA; seems rather complir,
Originally I WQ0 led to these questions by inv'ectigations
of the axiomatic system for phrase structure grammars of N. Chomsky
i:43 where the axioms and the restrictions express some properties of
C t? It X'19 raits3e to reformulate these OXiCTJAE SO LIS to concern
the finite relation only. It was .2hwL9that3 new axiom
must be added in order to obtain an equivalent axiomatic t tem.
A
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04 : CIA-RDP80-00247A003100530001-7
S2tactiO structure of sentences
There are two important' modifications, of ?Semalgerithms3
a) the alphabet V is decomposed into two 'disjoint part .T and N
which are said to be the terminal (peeper) and nonterminal ( uxiliary)
alph bets (4.7E, ; and 7b)." if E ,., then
is a. single letter,, In this cas.e the ,eerni?lgorigm2 is de'mined by
a more special condition
(2:') ,s("Aw
This semialgorithm
; there is
and ths
?such?th4t
t.-.-y2?tv.auF, soo :Lee the sets of
strings generated by it, are called
conte: free
......agwyrrt.tialsusaiMMEWAreievret.,,
A very impo
,tant exwaple, le the programming lerzuage ALGOL OTLOJ, where the
elelueints of N or
said to be the metal,:irkfruist._c variables or
....rstrwIlawcy.f.anwor.mp.1,11ravaunareare .9?173*INSiM
.1.22?131sA913 respectively? end it contains about 150 proper rules
which are determined by the syntactic definitions Then for program
E N 9 'the language $ ( program" ) is the set of all progztams
written in ALGOL 60?
In .automatic prok,oramming, it is necessary to recognize the
? syntactic structure of each particular program .p S (z program)
Ii order to translate it into the computer language,, The syntactic
structure. of p i d termined by a derivation such
that Z,Iifi4,
and *U#
< program> ; unfortunately however, there
often are several derivations, distinct as sequences of strings 'vzhich
determine the same syntactic structure A necessary equivalence rela-
tion concerning the set of derivations may be introduced using the
notion of isomorphism of _labelled doable graphs as follows.
If and which is
?Ileum .In the directed graph 6> the relation is
atransitiVe and acyclic an the the input or output degree of the, Ver;t7.
r
4?
if and ?only if
_or
root) and (4,9
resp. If -
= rooi) are
rooted ljatM in
hut
Cor i:L
_
and on4.y
/-
for reap., then
/ and eithe
0, 4
the
for the azin.al thdex t such that
Both the
,
el..c,ns it Is p )soible to prove the following
A
:or(11,11.i t!;' a?..qwme%L ar_d traneitiven.
' is it )6t. Ponc,4 (Lai(.. two two vertIcrk.i?
?
7-6 oatl t 'followinG
(11 e4i and
t? then -there alwa
the following pot; cx fm?
rt her
- there
and..
then .
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
,
The labelled double graph and contains elementary syntactic defini-
tions = r mi (the metasymbol , ( meaning "or" is omitted).
Let L._ be the language generated by C and let 12 be the set
of all phrase markers of elements in L_ The phrase markers were
intriduced by N.Choms4 and in are defined as double graphs
the vertices of which are labelled by symbols of To Ai
If we identify two nonterminal symbols .z and 7 9 i.e.
if we substitute 4 instead of in all places in all rules
of and if we omit from P12 we get a new grammar 0.
It is easy to see that L! L_ and the mapping of into
is determined by the mentioned substitution. If is a
mapping onto 12 then .i./e and are said to be interchan-
? geable in G.E.g. if to each (42,0 al, cuz.. ) 6 g where
wo = h (orao= ) exists another rule ( Ifw/
such that a)v= 01, =(or A = .16 ) and for each d6 4
either 0?)v. or tak A. 6 [,,e, Aq 9 then .4 and 3p, are in
terchangeable.
The homomorphism of a grammar GI onto a grammar is
a mapping T of 1; 4.1 onto 194 1.) Atz such that 1) y is
an one-to-one mapping of onto 2 ) (0,0 I abi Ouz Cbmi)6
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
tfl
Lipl i 0 s (NO? )(61,i) ? ? 0114
3) g induces
the mapping of / onto 2. 0 Two grammars are
. iv
said to be equivalent if lt/'possible to map them homomorphi-
cally onto the same gramear.
Another way how to chamge the grammars are extensions
and reductions. A grammar 6:0 is an extension of the grammar
F /1
G
0 if thoto are gra=ars 4f1 6,i1.-.1 ef,4 such that the
following conaition holds for each iii/Iiii 4 : there exists
, aii.--1 ,
a rule (64/0 1 (2/4 ail, . " a/44,)6 Zoi;...40 a syzboi 4.- II (4u r
? -t-mi ) )
an index 4,. e.r.,,,, and an integer I, .), 0, 4 j? ? ik, _,:t. Ay
such that
k-4
. a/ 4 /PIZ tlif 4 ? e . CV,,,,Aaioi 0, , 4_4. - ap )i and .Sdi ---= Si_ 4 .
r r / JP?
Eeto it may be no. _{(S ,,tik:6), (s, ,e14di and
(SA,G)/(16/ it )3 e In this case ,le, and are interchanc,eable
but they do not satisfy the above mentioned sufficient condition.
The composition + of two sets of rules and .1, is
defined as fo11ows:?=mg0/0/X;04' 0,0? Z. and /1
l? m/ ; ,
are some strings such that there are (a,; 841, bAtv
nda 6(A. 44,??) 72j for some symbols 4 and for each
/
4 /hi j -
A nontorminal symbol A of the grammar 6 is said to be
reductible if thereino rule in A of the form ( ) where
is a string containing .0 . The sy.abol ,e is reductible
if and only if i 1W f$1 n al ia no -. containing )4 where 9,4;
and aft,
their right and left side reap.
Let h be a nonterminal reductible symbol in G It is
natural to construct a new grammaras follows: )61
12*
9
are the sets of all rules in
containing I in
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7
..1741 ?
4/7f. /1V fr.& (14' *
and rv = ku-uuku4 frku4() 4J)Gis said to be direct reduc-
tion of G . A grammar 6 is called reduction of the ram-
mar Go if there are 4, Ga, i , . 671,... 4is
such that GA;
direci'reduction of (J?&_4 for each k, k z .'.p . Some simple
examples of the reduction in ALGOL 60 are shown in DI .
Now two grammars are said to be strong or week similar if
they have equivalent extensions or reductions reap.
If ,4 and are interchangeable in 61 and 6 is direct
reduction of G with the reduced symbol Ot,,Ar,f /Ai+ 9 then AO
and61*4
are interchangeable in again. If two grammars are
strong similar then they are week similar too, but not conver-
sally, E0g0A- [(Sotiz)/(i,47) j And 0g1,4ge fati:C), ((.. 74,c,)_1
are week similar because It =*-[(Sil 'ii )J is their common
reduction, but there are evidentely no equivalent extensions of
them. There are some lattice properties of the greatest extensions
and smallest reductions in regard to the equivalence relation
among the grammars.
KAulik: Applications of graph theory to mathematical
logic and linguistics, Theory of graphs and its applications,
NK.dulik: Formal structure of ALGOL and .simplication of
its description, 75-82, Symbolic languages in data processing,
(Roma 1962), Gordon-Breach, N.I. l963.
Aress: Mathematical Institute of Czech.Acad.of Sciences
Prague, Jan.28.th,1964.
Declassified in Part - Sanitized Copy Approved for Release 2014/03/04: CIA-RDP80-00247A003100530001-7