128 loN RAS,4.
I
MATHEMATICA_
REVUE D'ANALYSE NUMÉRIAÚE ET DE TI.IEORIE DE L'APPROXIMATIONBIRLIOGRAPIIIÞ I,'AI"JALYSE NUIVIERIQUII]
ET
T-A T}IEORITìDE
L'APPROXIMA'Í'IONTorne 1+, NÐ
2,
1975,pp.
t79-
200[1] Àr a m a, O., Proþrietdlí þriui+rd ntonolouia giru.l'tti þoliøoøtnelov ltti S' N. B.ERNS?-E-fN çd aþli,carea lor la stud'iul. øþroùrnärii futtc/iilor. Studii qi Cerc. (Cluj), \¡IIIr nr.
3-4, 195 210 (1es7).
[2] Popoviciu, Elena, Teo.yemc d,e med,ic din ønaliza ntalemali'cd' çi lcgã'twra lor cr,t
teori.ø interþold"vii. Éditura Dacia, Cluj (1972)'
[3] Popoviciu, .fiberiu, Sur !,e reste d,ans aerta'ines formules linéaives tl'øþþroxirnatiott de I'analyse. Mathematica (Cluj), 1 (24), 95-143 (1959).
t4l Rényi, Alf récl, Probøbility Theory. Akadénriai Kiadó, Budapest, 1970.
l5) Z i e gl e r, Z v i, Lineøy Aþþroxímøtion sntl Generalizer) Conuexily. J. Äpproximation Theory, 1, 420-443 (1968).
Reçu le 25. V. 1976.
SOME OBSERVATIONS CONCERNING THE ALGEBRAIC
TREATING OF THE FORMAI-. I,ANGUAGES
by 1'EODOR RUS (Cluj
-
Napoca)'lhe
necessityof a formal
device suitable for solving the problems ofrelaiions
between programming languagesand
betu'eenthem and
com-puting
systems, becomesvery
urgent. T'he paperis an atternpt on
thisway. Having in
vicrv on o11e sidethe form of
$'ord. free strücturesof
theprogramning
languages, generateclby their data
base structures,pfimi- tive
operations and control seqllences, using some syntactical rules, givenby
operator schemes,similar to te
operationsin a
word free algebra, and onthe
other sidethe
observations,the
operations schemesin this
case are concerningthe
heterogeneotls operations,irr the
paper we have the follo-w1119 prlfposes :
l,
Oiganizea formal
languagein the form of
heterogeneous wordfree
algebra, o11 levels.2, A formal
clefinitionof the
semantic clomain associateclto
a formal language.- 3.
-To give a way of formal
representationof
stlch ¿tstrtlcture in
anothcr
one, r,vhich generalisesthe notion of
homomorphism,for a
formaldefinition of
semantic preservillgtranslation
algoritlims.The
solutionsof the
above problemsare
presentedirr
sectioLTs 2,3.Section
I is
devotedto the definition of the formal
languageby
meansof
X-categories, used-in
sequel.1, A
CATEGORIAI-/CHARACTERIZATION OF THE
FORMAI, LANGUAGESl.l.
General considcrationson the relvriting
systentThe
pair (t, P) is a rewriting
systeil. (semi-l'hue system)when I
isan
alphabetaàd P'is a
setof productions. (), P) is an
indexed rewri-ting
systemwhen P is an injection from an initial
segmentof
nals¡"11sé
numbers
to
X* XX*. In this way
everyproduction
o(-r I e P is
distin-guishable
by its
index, sothat P(n):
d+p
can bewritten
^, o3 p.
Therelation -> can be extend.ed.
to
=+by
concatenationin the following way:
If 0, t|l e >*,0:"{F, ü:vpp
and.ø-PeP then0+{.,Let
us
consid.erthe transitive reflexive closure
of+ and
clenoteit
bVå.
For V*
= 2*,
V7c 2, the quadruple (>*,
V¡¡,Vy, P) will
becalled grammar and the
language generatedby G: (>*,
VN,Vr,
P)is
definedas
follows:L(G)
: {u e Vi ll o = V*,
o-!7u}The
extensionsof the
relations defineclby P from
--+ to+
and to -!2 d.efinea
category.Let us
denotethis
categoryby
F.The objects O of
F
arethe
elementsof 2*.
The setM of
morphismsof F is
definedby:
(i). the length zero
derivatiorrs,aj>
u", d.e !*
are identitiesin
MI,denoted
by
1o.(ii). If þ = P
thenþ is
considered'as a
morphismof length I
andbelongs
to M.
So,P c M.
When Pis
an indexed set,then (n,
a!>
pSe
e Pand
"39 e
A4.îhe
domain of.q.!, p will
be øand the
cod.omainor a3 B will be
p.(iii) For
everypair of
id.entitiesin M, 1*, lu and every
morphism,.3þeM the morphism 1u*(a39)*
1"eM
andis
determined uni-luely by
¡-r,,v
ancL o.3 9,
wherex is the
concafenationof
morphisms.(iv). For
eachx, y e M
suchthat
cod.omainof ø
belongsto
the domainof y is
definedthe
cornpositionyofr,
ãrLdy"x e Il[.
From
tLis
d.efinitionit
followsthat
each morphismin M is
equivalentto
a derivationin (>, P)
fromits
domainto its
codomain. Then,for
two ,,bjects o(, P= Xx, Ifom (a,
p)is the
setof all
derivationsfrom e to
p,or the set of
rnorphismsfrom a to
p,Following norz fl],nnNsoN[3], cnmrrrns [2], onthe set of
mor- phismsfrom a to p
canbe
defineda
congruencerelation -
andfor
stu-dying the syntactical structure defined by (), P) in )* the
categoryFl-: (>*,Ml-) can be
considered.The, category F/- is
aÍL X-cate-gory
asit
was d,efined.by norz ll]. From this
reason and becauseX*
categories
will be
usedin the
sequel weshall
redefineit.
1.2,
The notioil of
X-cal;egorxthe
systernX:
(O, 14, Q,Z, ., *) is
a X-catcgoryif the
following propertieshold:
(i).
O andM
are sets,Q
and.Z
are functions, Q,Z: M
->O; Q will be
called.domain function
andZ will be
called codomain function.B
soMEoBsERVArtoNS
181(ii). . is a partial
operationon M,
o:
Mz ->M,
called composition, andis
definedin the
followingway: if (x, y) = Mz
theny
ox is
definecliff 8U) : Z(x) and the following
equalitiestake
place:QU
. ,) :
Q@),Z(y
" x):
Z(y)(iiÐ. . is
associative whereit is
defined.(iv). For
eachobject
d:e
Othere
exists a-uniquely determinedloe
e
/14 calledidentity on d,
sothat for
everyy,* = M
f.orwhich
ø o 1oand
1oo! are defined
alndZ(1,):Q(x),
0(1"): Z(y) t}ren x"ln- i
and looy:y.
(v). The
algebraic systems (O,*, Ìt),
(JW,*, 1¡) are
monoids,Âe )* is
empty stringin X*
and Q,Z: (M, 'r,
1i,) -+ (O,*, z\) aÍe
monoid homomorphisms.(vi). For every *y
x2,lr lz e M so that
Q(yr): Z(*,), i :
l,1Zthe following identity takes
place:(yr*
yr) "(xrx
xr): (!ro
xr)* (!r.
xr)(vii), For
eachln,
7ue M,
lu xlu:
lu*uNow, given
a
rewriting saystem(>,
P)the
corresponding X-categoryis
denoted 7>yD: (>*, M,
Q,2,", *)
where()*,
*,Â) is the
free monoid generatedby
>the notation Hom, (a, p) for the
setof all
morphismsfrom a to p in the
categoryD we
have:1.
ø3> p is
equivalentto
Hom1r(a,þ) + ø
2.V* c X*,
Vyc 2, G: (2*,V*,Vr, P) then the
language generated.by"C is L(G):{ueV$llxeM, Q@)=V*, Z(x):p¡
3, rf
pe x* then the
syntactical structuresof g
arev*Homoþ,
þ)4. the set of all
syntactical structuresof the
language iss(:*,
r/N,vr, P) : u Q.
Homoþ,u)v\- o'v*
For the study of
somerelations
between languagesthe notion
ofX-functor is
wanted.In
ord.erto
definelhat, let X¡ :
(O¡,M¡, Z¡, ",
*)j :
1,2be two
X-categories.A pair of functions
11: (hr, h*) will
becalled.
X-functor if the following
propertiestake
place:(i). ho:
(Or,x, ¡) +
(Or,*, A)
and(iù. h*: (Mr,'r, l¡) n (Mr, x,
1¡)are
monoid homomorphisrns.iÈéoon iiúé 2
SOME OBSERVÄTIONs 183
TEODoR RUS 4
(iii). ã'.(Or,
M,,, Q,Z, ") -
(Or,Mr,
Qr,Zr, ") is a functor, that
is(iii1).
If a e
Orthen h*(1"):
1¿o(o)(iiir), For
eachy, xeM sothat )toxis
definedh*(y"x):h*(y)"h*(x) (iiir). The following
diagrams commutecatcgory associated
to a rewriting
sys-tem(>' P)'Thcn an
interpretatiou;î" ð'ï, -ï"t i. r
""X-"åiottctor"1-:
D -' àet so that for
everyo ' ?, T\rí*'ä ^;i it"¡ + rf -*fr"t"
^ is the identity set
accordingto
theoueration
X."u"'îåiäuâ D is freely
generatedby-(ì, p) a particular
interpretation¡
is-a"t"tmined by the
fãllorving conditions :(i). For
eachøe>, I
(ø)*Ø, I(ø) eV'
(ii).Foreachø*p€ P, I(a'*P) :1(P) 4I(a)'f eF
The
above considerations $¡erela *
ß).That is
because theìir... it-r"
svntactical structurby G: (>*, VN, Vr, P)
isuÁe
D tò define the
languaof the
language.I,et now
7!)1,Isz c L(G) be given' \\/hat kind of relations
can r ¡ed.efine between
u,
and ø,? Of
coursmorohisms
'Th" ittt"tttal from
IvI.structure of
theG: (Ð*, V*, Vr, P) can be
studrole bf
symbols-ftonr V,
d:uring,will
lead.us to an
overlaPPing ofa
1eve1will be the set of
generatomust fol1ow tfre
naiurái way'of
lauguagedefi'ition,
whichis
pointed' outü;;;;t;atural oiãititi"iáf
languãge."The ptinciplesin this
overlappingare the following:
(i).
Thereis a first level of I dictionary' ll !þ"
"r."'ãi "ãã"irl-f""g"ãg"r-ih" ai"t dictionarv of
.thelansuase and
in tü8-""'sà of progra it is its
basic data strtictu"re,primitive
operations and'tiil. Let the
leveis0,1,.. ., i - I be built'
Thelevel , (if it
exists)*i11
f,; ¡irlt Ìiom the
elementsof
levels0,1,..., i - l iu a
recursrvcty way,by the rules
specifiedby the
gtammat'782 5
zt
-0
i'
11t
t"
(;,
luo
t4,
I
0, c.
Ii
0
Qe.
Fig. I
The
pair ¡7:
(h,rr, /zo)is a
cofunctorif
insteadof (iiir) and (iiir)
we consider'(äi|).
tono(1t"x): h*(x)"lrr(1,), for ever¡' x, y
eM fot which yox
isdefined.
(iiii). The follorving
diagrams comute/L
I'ig. B
1.3.
Thc notion of
interpretationof a
lang¡uagoFor
semanticdefinition of a
language vve sha1l considerthe
notionTEODOR RUS SOME OBSERVATTONS 185
184 6 7
From these
observationsfollows that in the set
,44of
syntactical structuresof the
ele_mentsof the
languagemust be
defineclan
ord.eringrelation which will
decomposethe
setM in
classes followingthe
princi"-ples (i) and
(ii).The
overlappingof the
languagewill
showus that
\Me are able to associateto a
languagean internal
algebricalstructure
richerthan that of x-category. This
structurervill
be defined usingthe notion of free )-
algebra defined
by nrccrns l5l.
2. THD OVERI,APPING OIi A FORMAI/
I.ANGUAGB 2.1. T'he gcneral eonsitlerationson the
decornpositionof P
For
'the definition of the
overlapping discussecl above we sha1l startwith
generaldefinition of the
languzg" by
meansof a rewriting
system(P, fl.
S_9,f9r
Vto= 4*, .Vr c ) we
considerthe gramm"t G: (l*, Yr, Vr, P). Our
hypothesiswill be that V* c X and the
grarnmàr Gis a
context-free grammar.From $ 1,2
rveliâve:
3(>l*, zN, v,, P): u u Hom, (o, ,)
QevT aevN
L(G)
: {u e Vflfx e X[,
Q@)= V*, Z(x) :
ø]The classification of. t_he prod.uction set P which
will
supply an overlappirrgof the
languggewill be-relating only to the set s(>*; V*, Vr, eiin{t
is, only to that part of M "of
morphismswhich
canbe
considered. as svirtactical'struc-n
ordering relain a finite
set1 y in the
earFor that
we considerthe
grarnntarG: (>*, V*, Vr, P) not
havingjust
one1{om. Each
symbolfrom V*
canbe
considere¿ai
axiorn likõin RUS t6]. That
doesnot
changethe fact that
Gis
context-free in a classicalway,
because there existsa
context-free grammarG' with just
one axiom sothat L(G): L(G').This
idea isvery na¡¡¡al havingi1
viewthe
prograrnming language. So,not
every expressionin a
programming languageis a
program,but
belongsto the
language. For instãnce, the ide,ntifiers are-no programsbut
belongto the
languagein
whichthey
aredefined.
In_this
way the ideaof
overláppingof
thé language can beieali-
zed.
in
the following r /ay :(i).
Thefirst
level of the language is Zo(G) andis
defined.bythe
strin- gsu e
L(G) for which we have : iLu =
Lo(G)that
meansthat there
existsA -w e P
andA e
Vw,u e Vï.
I.et Ms be the set of
firorphisms{rom M(L) which
are syntactical 1 bebuilt,
denotedbv Io(G),
L'.(G)'built by that
that
meanscan
be
repre- orphisms fromMo, "' Thã Mr,
effectivå i"ãS¡Latiot,..', M¡-1,
M¡.of (i) and (ii)
above will_be made by
anord."ring relation
¿"fì""ã o"
the pòrîersetdi'p. This
lead.to a
decomposi-tion
of "Pin
classesof
subsets. Such classes were considered'by
,SAI,OMAAlTlfarestrictiononthesetofd.erivationswith
a c in
Salorcrit is
PaPera rnatrix
grammaÍor an
ordered- accordingtã the
ordering d.efinition.tions.
2,2. Tlne
all¡orithm for
dceompositionof
Fin classes we shal1
nVr' þ:("'þ)
the
emPtY string.I wherc l¡ = Vi
or2, ..., n. By
Cat(þ)is a
subsetof P
thenVr, P)
and,L(G) + Ø tloen
tkeYetkat
þrr(þ) =
V¡t' þY,(þ)= Vi' that-there
existsat least
oÍre u)e
syntactical structureol a
derivationThat means that
thereis P e
P,number
of
steps as above we sha1l find- the.production p'---ihtootooi.
ll
L(G)+Ø
then there ex'istsqn uryiqu^e-- 9?
oÍthe iet P in
the"tuùtttt'
Po,Pt, .. ', P,
so that tkefol'l'
'itionstake þl,ace :
(i). ry þ' P
ønd'þ e
Po tken CøtQfl:g¡'
186
(1ù.
If þ = P; fot' i: l, 2, ..,, n
th,eng soME oBSERVA'rIoNS 787
P¿*, (at
i.he That
meansto
perform,, I Þ,*, U wili
be cleanedfrom
C'î trr" åilgoii
DECS'rf the
conditione
next stlep
DECT'DEC7.
Verily if all the
elementsof P1
are classifiecl.For that
setI to
1+ l, I
:: I I
1, ancl verifYif
tions from P1 rvhich can be classified' ar
can be eliminated from P
becauselanguage.
In this
caseset I to I -
tlre- algorithm is DEC9. If Pt *
r
been
built.
Thenperformthe
operationC::
PL\U^ 4
j:oand
algorithmcontinue vgith
the
step DEC8.DECS.
\/erify
the conclitiotc :
Ø?Irft
is true the[ext
s-t9r is. DEcg becauseall
elementsof Pl
are classified.If the
conditionis
false the next stepof the algorithm is
DEC6.DECT.
set a
nervvariabile N to 1, N:: I andbeginthe
classification of
P2.DEC\T. \¡erify
1.he cond.ition P2:Ø? Il it is true the algoritltry l:
comoletecl an,L
subslii ^rl" Po, Pt,
.", Pn
r"'here n'is the
va'lueof N
If
Pz: Ø is
falseit follol's the
step DËCl1'DECI1.
Choosc anarbitrary
ele nentþ = P'and build the
correspon-cling-"1eme'111
p" br;;;.iitg
rromþrr(þ) ail
symbols equalwith
þrL(þ)' DEC12. Set -Ito
zeto,I'.:0
DEC13. VerifY
if Cù (þ*) : Ø or iÎ
Cat(þ*)c. U n'l"i
þr,(q)j:o
If at
lecst oneof
thcsc tr,r-o conclition hoid, tlLerrP¡+t" :
Port-U/
r1h-erei is the
valueof 1,
ancl 7) rvi11bc
crascclfrom
P2.Next
step _of algorithmis Dlici0. If ro
oneof thc
aborre condition ho1d,the algorithm will
lookup {o, a
nc\\¡ su.bsetÍor
classì1i1'1"g-þsetilg I to I +
1,!:: I )-
1' and choosingthe ncxt
stcpto
bef,,flCtã.'If theie
afe no setsfor
classifying/,
tlren is Tu1fi11ec1
I
==Ñ
utdþ
canbe
erasedfrom
P2 becausethere
are noå1.-""t0
ut= L(G)
r.r,hich óanbe
obtaine-dby
using/. In this
case thealgorithm contìuue
l'ith
DEC10.The
operatìons uscclto DEC
clescr-iption can be .easlly pr_ogrammedi" ."..,
asöemb11, languagcr¡r I,ISP-likè
language.The flow
diagrarn ofDEC is
presenteclin figure
1.Cat(b\
c
TEODOR RT'S
t,
þv,(q)u þr'(þ)
B
quUPj j:0
(iii). Q
tlPn. e, P, n
P¡: Ø,
i, +j
i:o
(ir'.).
Th,e decontt>osition. Po,Pr, ...,
Pn í,s th,efinest
one zaitk tlte bigest cørclinølityof
tloe classes Po,Pr,
. ..,
Pnuhich
has the þroþerties(i)
-
(iii) .,,(r,),
If ue
considcr the grømmat' G': (2*, V*, Vr, P')
uh,ereP' : : U
P¿ thenit
fottows L(G):
L(G').Proof
.
The demonstration ofthis
theoremwill
be madeby
describingthe algorithm
¡¡'hich rvi11 dccomposeP
sothat (i) - (") hold. For that
1et
DEC be the
nameof the algorithn. The
stepsof this algorithm will
be denotedby
DEC followedby
digits.DECI
.
Set indexI to
zero,I
:: 0. It
rvi11 count the number of classes.DEC2. Decompose
the set P in two subscts
PLand P2
sothat P :
PL\)
P2,Pr î
Pz: Ø
accordtngto the
following definition:P' : {þ =P lþr'(þ)
æ cøt(þ)}P' : {þ =
PI þr,(þ) =
cat(þ)}DEC3. The
first
classof P is
Po, Po-
P1, andis built by the
rela-tion
Po: U, = P'lþ/r(þ) = Vi\.
Observation:
From
lemrnaI it
follorn'sthat
Po*Ø,
DEC4.
I.ct
Pu,Pr, ..., Pi,
be alreadybuilt.
Considerthe set C
de-finerÌ b1' C :
:
P1'..[J Pi
r'vhcre b1...
u,e have denotedthe
operation ofsubtlaction nn r.ta.':n
DECí. \¡erify the conclition
C:
Ø? If this
conditiotiis true,
thealgorithm continuc rvith
DlìC7; if the condition is
false,the next
stepis
DEC6.DEC6 Cat(p)
=qG l) Pj
i=o
Choose
an
ar1¡itrar)' e1elxeütþ - C
andverifl' the
conditionV lrrr(q). If tliis
conditiorris true then we
have obtainect.l: -0
é
Ì.,t1
€. ca/
€ (
P, =l
P2--ø L =y
¡
Q) =É s roP
DEC
U
i,.o
C:=C
c.p
U
C:--P/\ Pj
lr€-c
(, l'
1e¡t
Y{5
yE5
s Y{,t
1t SOMB OBSBRVATIONS iB0
Let
nowp' :ÜP¡
wheren isthevalue
of .ðy', andG':(2*,
V¡¡,Vr, P')' From the algoriihm
d:0 described aboveit results that
L(G): f(G')¡
The other properties followsfrom the
algorithrn description too.Examplel X: {Xo, Xr., a, b, c}, V¡¡: {Xo, X},Vr: {ø,
b, c},P :
{Xo -+X¡X1,
Xo-
øXob, XL -+ cXy, Xo-
øb,Xt'+
c)Pt : {Xo
-> øb,X,
-> c}P' :
{Xo -+ XoX1, Xo-
øXob,Xr +
cXy}In this
casewe have Po: Pr an . If
G0: (Z*,
Vw,Vr,
Po)a :_{qb,
c},- L_(G)7
: {ø"bic^l ¿(GJ: {a"b}
anð'Lot
n:0
From
Lemrna
2. If u e L(G)
and' xe
Homp(A,u) is a
syntkacticøl' d'escriþ_-ion of a,
so tkøtfor
ø þiueni', A = {þrr(þ)lþ = P¡)
thenfor
each sub-string u' of u,
Is:
IsLT!)'uo,so that u' =
L(G)there-
is ø
syntacticøl' d'escriþt'ion y e Honor(B,w')
uhereBe
þr,(þ)V =[JP,
j:0This
result makesit
posibleto
d.efinethe
overlapingof the
languageZ(G)
as follows:1. The first level of the
languageis
Zo(G) and. it,is
generated byGo: (2*,
VN,Vr,
Po).2. the
sécond leve1of the
languageis Zt(G)
and,it is
generated byGr: (2*,
V¡¡,Vr, Po U Pr)
ìi. The i-th level of the
languageis Z;(G)
andit is
generatedby
G¡: (2*, V*, Vr, Po U Pl U ... u
P¿)n.
Then-th
(the last) leve1 of the language isI(G,)
andit is
generatedby G,: (X*,
VN,Vr, Po
UP, U ... U
Pr)The-sets Po,
Pr, ...,
P¿,.,., P,
arethe
subsetsof the set P
defi- ned.by the
algorithm DEC, Nowit is
clearthat
r,,r'e have(i)
¿d(c)c
L¿+{G),i:0, I, ..., n - | (ii)
¿,(G):
L(G)According
to the
above relations betweenthe
levelsof the
languageZ(G) we can
d.efinethe
relations betweenthe
syntactical d.escriptions ofthe
stringsof the
language.I-,et us
denotebV M(L) all
morphisms of Ftg. 1. Thø flout di,agrønt' o.f DEÇieo TEODOR RUS
72
3,
'S-AI,GEBRA OF A
T'ORMAI,I,ANGUAGË
3,1. ìS-algebrasset
ancla family eL(I) of
relationson I, r = e(4 with the
properties(it, ir, ..., i,, j) =,
follõrvJi:/
ì1" "l'","3i'îli "åf îå*
"":,"î:t tï: Í
) can
be indexeclby the n-arity
ofthcir
cornponents,aQ) : l) O"(l),
e.(1): [J a,(¡)
rvtrere O(1)is the
setof all
operationson 1, "
'tS lrgil'(I,
,!Ð,!t F e(I) will be
called a retational algebraon 1
anda lrair U, A), q .
O(1)s'ill
be callec1a partial
algebra orr- 1.I,et
us consider now a noncnrtl'
setf), Q n
1: Ø sothat
Q:
UC¿".Art'
{l-structure
on1 is
definccby a function
a :o -- ll(-I) y,hich
upþti"u{l,in8Ln¡r(I), n:0, 1, .... Inthis Yayasymbol.acts
underthe
mappi- ng ,t as an'(ít.¡ l)-ary
relation on1. If
each symbqlg =
Q,n,n :0, l, aõts
und.erd as an n-ary
operation,theri (1, a) is
calledan
C)-partial algebra.In this
caseô e {I,,,
rou"=
O(1)(it, ir,
. .., i,,, i) = .(o)
and u'e denotethis
operatiouby iri, ... i,,a or i:tttz ...in6.
For a
givennon emty 1 and a
nonemty
set {ù,and an
application ø : C) ->St(I) the pair ) : (1,
,.)is
ca1ledan
C)-schemeor
operator sclte-me
[5].Lét
nowA
be afamily
of sets,¿ :
{A¡}æ¡ indexedby I.
We supposcthat for
eacho e
e)n,n:0, 1,
eincleach (ir, ir, ..., in, i) =
o,'ois
given a function-
Tlrefamily A: (ti,i,,,.i,,:A¡,X {A¡)¡.¡ together
A¡,X rvith .. . X all
A¡,,'--+functions
A.¡. givenby a )-
scireme
will
be callecl an Q-algebrawith
the oper-ator schemeX or
shortlr', )-algebraIn this
waythe notion of
algebrais
definedby
using heterogeneous operations defiuedby a given
operator scheme). For that two
thingsmust be
precisecl :(i)
, A
functionI"
->I u'ith the
roleof
domain selectorof
operations definedby the
scheme.(ii). A
composition 1awfor the
elementsof the
selectedsetsby
(i).For
algebrical porposes(i) and (ii)
arequite
enoughto
charracterizethe structure
definecLby operator scliene 2:
(1,
ø),on a family
of sets -4: {A;\¡=¡. That
becausethe problen
is not toseehor¡'the
opera-tions
defined-by
operator scherne areconputed, but it is
enoughto
saythat for
eacho e
C), cocrrvill
selecttlie
domaitt and coclomainof
operation, sothat
(l). (r,, i2,
. ..,
,i,,'i) e
aa(2).
(or, &2,.,,,
&n)ra,i,¿,..,ini: atØz,',
an6i,i,i...i,¡for
each øoe
Aihh:1,2, ..., n
and.øra, ... aori,i,...t¡ e
A¿For the
algorithmicpoint of I'iew this
clefinition must hasa
compie-tion in the
senseof indicating
howthe
operatiolls (ò¿,1:,...i*i
àr? computed.That
means,that from the algorithmic point of view it is not
enoughto say tlrat
n-tupl.
(ør, ø2,...,
a,,) belongsto the
domainof
cl¡,.¡,...;n¡.It is
necessaryãlso to indicate the way of
dependingof the
building processof atør, , ,
Øn6í,i,...iuiby the values of
ã1, a2,,..,
&rt:lhat
õan be
better
seerr consideringthis
process asan algorithm
described' bya
sequencesof
steps.The order of the
execution stepsis given by
the valuesof ør, ar,
. ..,
&n rvhichare data of the
algorithm,In
the usual cases of operationin
the numerical structures,this
aspectis not very
clear beacusethe
numbers havetwo
different determinations, On one side as syrnbolic names ancl onthe other
siclc as valucsof
thesenames. The value of a nurnber
is
predicatedby its
synrbolicform, or
in.otherwords, the value of a
nttmberis irnplicitely
givenby its
symbolic representation.If
rve considerthat
speaking about sets we usethe
nanlesf their
elements, consielered. as t¡ariableon
these sets,then this
double irspect ofthe
nanre and of tire value arise immecliately.13 SoMr ous¡nvattoNs 1e1
x-category D which are syntactical
descriptionsof the
language. Then we have :l'. The first
class ?f_ !!.(L)._d.enotedbv MoØ) is the
samewith
po2'. I1 the
classesMr(L), Mr(L), ..., MnØ) have
beenbuilt,
then M,*t^(L,)will be built by all
morphismsfrom
E(2,1,,Vn, Vr, p) wtth
the following
properties :(i).-If x e M¡+t(Z) th91
thereexistsa
decomposition ofø
accordingto " and x
sothat x_- y{?}r, y
?_Pn.-r,z e Mo u M, ... lJ
M¿11o1,.l:.tr,_y
=X[.oU,Mr,t)
... u M¡tr
whcrcy{i\z nr.a"s yoz or y*2.
(ii). If
l.(x)is the length of x, that is, t"hd'íiumber of rules
íror,, Po,!1, .:.,-P¡_\r
applliedto build r, then l(x) > i + l.
The study of the morphism classes
Mo,
ll,[r,'...,
JII,, r,r'i11 1eac1to
somemethocls
of
s¡'n13-q1ical arralysisusing riormal
algorithmthc
classesMo, Mþ .,.,
ilI,,
shou,us a kiucl õf
struc be clefined onthe
stringsof the
language.This
structure bcclby Mo, Mr, ..., M,, in
anindireci
u'ay, canbe
clireaical structrll'e on Z(G), definecl
b¡'
¿,
o.":nå,,Yîì'il'iîff ;i "ü*,å?
o, u -:
o(zar,ur, ..., uu) =
L(G)i1t
byusirg a
free algebra scheme such a structurcu,ill
be clclinedinthe next
secticin usingx-
algebrasdelined by urcc;rNS t5l, for characterizing
heterogeneo-us algJbricalstructure, For this
reason rve shal1 begin thé next seciionwith
tËe defi-nition of
)S-algebras rvhich are suitable structuresfor
characterizirg the inf.ernalstructure of a
iarguage.1,ô2 TEODOR RUS 14
;'
Ë,The
above observations lead usto a
generaTizationof the notion
of operator scheme,that
arisesby
determining an operation underthe
follo- wing conditions :(i). A
functionI"
--+I
whichwill
selectthe
domain and codomain of operations.- (ii).4
compositionlaw for the
elementsof the
selected setsby
(i).(iii).
A state word of the operation which u'i1l indicate the wayin
which the proôcss of buildingthc
resùltis dependingbythe value ofthe
operands.on (iii)
1et usBisasetof
fl;,";r;,?ä'
A by
7,types of the type of the
above constructionby
3.
Tleen oneele
1,2, 2, 3) is not
enoughfor
showingwhat this
element of _operatorscherir.e shõu1d
be 3) or in other fornr
((1,2, 2),
(i1,then, el
examplein
programming langirages. But wetry
to indicate a general scheme for this kind. of operations, using on one side the context-free grammars andon the
other side )-alge- bras defiuedby nrccrxs
[5].By an operator scheme XS we mean a pair (I
,
ø) where øis a
functionø:O + O(I) x SI,
where57'is a
given setof
rvotcls,'charracterizing the selected operationby
o., and called semantics selectors or state words.In this
rvayto
eacho € O, will
correspond.by a a triple (ir, ir,
. ..,
i*)in the
domainof
toø,(i) in the
coclomainof
<,¡q ands c ST of
oø.I,et
rrorvA : {A¿\;-¡ be a family of sets
indexed.by 1 and a )
Sscheme
as
consiclerìed.' above,Then for
coe
C), we havethe
follo-wingsIf. (i\, iz, ..., i,,) e D(oø), (i) =
R(<oa),(tr, tr, ...,. s,+r)-<
S?(ora), whereAf D, R,
S?-'we have denoted respectively domain, codomain and.state worcls
of the
operation coa,then for each
ctn= A¿t (sra1, s2ct2,.'.,
strarr, sto+t) crla
:
sLøLszttz , ,.
srrarrsa4-1 ' belongs to'-' A¿.In this
definition <¡ isnot
explici ;ely represented.in the
result trecause sometimesit
is represented by one ofthe
senantic selectorsor state
words.But
sometinresit
is necessaryto explicit
thernin the form of the
,,llameof operation" or,rname of
resu1t".In this
caseô will be a
1abe1of
the result ancl we sha1l be ableto
define operations on these namestoo,
being ablein this
manerto
havean
algebrãical clescriptionof the
algorithmic processes.'Ihe form of
representingof
these labels, when used,will
beo): s{L\szq.z...sra*snt1 or_
avoiding any
ambiguityin_the lotm airir...-i"i.^
sLøLszaz. . .sra.*s,¡¡1.
In this way the
1abels becom thenselves operands ofthettype
ø.Afamilyof
sets¿: {Aa}r,=¡indexedbyl
togetherwith all
op_erations clcfinedby a
X5-operator-siheme,)S: (1,
"),where u.:ç,
->9(1) x
S7-will
be called.a
)S-algebra.When
ST:
Øthen
ZS-algebrais just a
X-algebla,15 SoME obSERVATÍÔÑs 193
3.2.
ES-Algel;ra
assoeiatctito a
grammaÍ. Let I
= (2", Vu, l'.x, lt)
be a given context-frce gràrltrriíì1', suppliedby a
semi-Thue systernlX,
P-) a:ndD: (t*,
X4,q, Z, ",
r,¡bc
X'-õate-E9?
geueratedby (>, P), The
language generatedby
Gis
defined by L(G):
{we v.i:llx e
ù!,.Q@)= v*: zú) : *}.
As rvé have shown therêis an
uniclue_clccompos;itio'ofP in thc
stibsetÁpo, pr, ,..., p,
sothat
theorem
t
ho1d.rlsing tliis.
dcc_omposition rveshall
dèfirieno*'in l1c¡
a structure
of
xs-algebra. tr'orthat, let
L1s use the following notions :B¡, the index of G
weshall
unclerstandthe set zr-indexecl by
its elements.For
avoiciirrgany
misunclersta:rding rve d.enote"the index
-ofG
ÞV-!o
supposingthat
In isa set of ilatural
numbers sothat the
followinghold:
(i). If i e Ic then there
exists(ij) If i, j = 1", i -#_j, then A¡ = V*, A¡ #
Ai.Given zr
prockction þ e P, /, : ("
"i jtrr(ü -
A,g:
7
srArsrAr.,,suA,rs,,-¡1, s¡€
Z.lTors¿ : i,
2::,,,,à, rì+t
Ry þrvr(1)
rve sha1l denotethe se ., s,, s,+r) and
byþyr*(þ) we sliall
clenotethe
secluence(t!r, Ar,
. . .,A*). By I(irrr*(þ)) we
denot-etLc
sí-rlrlcnce(ir, ir, ..., .i,,) u'hcre
iuis the
inclex o1 Ào in1", lor
k -.- 1,2,
, ..,
11,.For the
decompositionof P in the
subsetspn, pr, ..,,
pnlet
usconsider the Tollolving sets:
S,: l)
þt,nr(þ), O,: U-r(þrr"
(1,)),T, : l) r(þr,(þ)).
þ=Pi þ-Pi "
þ.Pi
It is
clearthat to
eachþ € P¡
we can associatea tr
ereo¡=.
O¡ sr= S,, t¡= T¿.The triple
(o,(l>), s¡(þ),t¡(þ))
pe-lqtion
scherne suppliedlry þ
.oo(fl
1Å catteciaoäá
oD,ta(þ) is called codomain of
thè opetãîion and
s;(p)is
orsemantics selector
of the
operation.I,et
nowÐ' :
{(on(þ), t¡(þ),t,(Ð)l
on(Ð= o¡,
s¡(þ)=
S¡, to(þ)-
7-i}for a
given subsetP;, and
wecall it
opelator schemeof the
subsetFor the
grammar G we can consideron:
i:0Ú o¡, so:
i:oú t,, T":
i:oü 7,, ,o: ü
- i:0,,
called respectively domains
of
operations suppliedby
G, state words or semantics selectorsof
operations suppliedby
G, codomainof
operations suppliedby
G and operator schemeof
operations suppliedby
G.-be Pi.
6 - MathÈluatica
- Revue d'analyse uumórique et de lhéorie de l'approximatiotÌ
- Torue 4, No. 2/1g?5
1g4
ftóDoRRùs
16E x e m p 1e
: I,et
G bethe
gÏal11marfrom the
exampl.ein
2,2, where,,r"
"ã*id"r ior X, the
inclex 1 ãnclfor X, the index 2. 'Ihen
rve have :IG: {1, 2},
So:
{øb,c},
S,: {(^,
^, ^,), (o' b)' þ, ^)}
oo
: {( ), ( )}, o, :
{(1,2), (r), (2)}' r0: {(1),
(2)}?1
: {(1),
(1),(2)}, )o : {( ( )' (ot)'
(1)),(( ), (')'
(z))}>, :
{((1,2), (^,^,^,),
(1)),((1),
(ø,a), (t)), ((z),
(c,Â)'
(2))}Using the notiou of
XS-sdefine
thé
operationsin the
lathe
languagewill be
describedassociatãd.
io the
languagewil both,
syntacticresult of the pro
in
the form offr (or
realisations) sets.An operatiori described by
al
element o.= )p will
be clefined. as follows :I"t X :-ilrir=r"t" -o iu^ny of sets,
inclexedby the index In of
the, i\, i e I. will be
calleda set of the type i' If
l),'then
ol- (ir, iz, .. ', i,), t:
(sr, sz,''',
s¿,S,r-rrí, ..., n, i' å r",
ro= s; ii:1,2, ..,, n, *+1,
necl
by
oin X :
{Xr}r=¡}is
definecl asa
-composl-:
:"#
;î ffi '"j'""":ili ii*if'ïå
that is, the
corresPond'ing algo-ï1'äff:ä"Xïu,iåI ffläti*
Given a gfammaÍ
G
anð,)n the
ES-scheme associatedto G, a family
oi."tr itá"*.? ¡y io, X: {Xi,.r" together with all
operations supplied associateclto G and will be
denoted:T
t i, 3¡ f, 1"''$,?
XTïI",
ut(11
set
of
a1l stringsof the
language.Then we
have :17 SOME OBSERVATIONS 195
(i).
So=
L(G) being considered as individual constantsof
XS(G, L(GÐ.(ii). r,et now be
u)1,ru2, .., u, = L(G) of the types it, ir, ...,
inand
o e 2i,,i > l. fi o: (o,s, t)
andiÎ o: (ir, ir, ..., i")
then we can write o(zør,Uu ...,wu):
sP)Lszl!)z...Snlunsn¡1or usingthe
operation name a¡,¿,...iriis.u)Lszlpz,,.s;t*s,rlr. Of
coursero(ar, wr,...,rnr)
bclongsto
the language and hasthe type r', where t: (i). Norv,
because ¿u(C):
S0and becatrse L¡(G)
-
L¿.r(G),i:0, 1, .,., n, L,,(G):
L(C), '"r'e can for-mulate the following
theorem:THEoREM
2. For
eacl¿,i, 0 < i < n
the language Ln(G) 'is øfree ),S'
al,gebrø
of uords,
generated.by
Lo(G) U¿r(G) u .., u L,,r(G), uitk
theoþerator scheme
)r" : Ü t¡
j:0 ancluil,t
be clenoted byL,(G)
:
'S(¿,(C),
>dJ.
Iu this
waythe free )
-algebraof
words suppliedbyGin
Z(G)canbervritten
asthe
pair>s(G,
¿(G)): >s(¿(G),
)n)This result
lvas obtainedby
consid.eringonly operations ofthen-aily 0, 1,
and2, that is by
reducingthe
grammarto
a Chomsky not'mal formin
the papernus
[6].From the above theorem
it
followst hat we have on one side the overlap-ping of the
language andon the othei
sidethe )S-structure
definedon eachlevel of the
language.Also,
theorem2
show usthe relation
between levels fromthe
generation and structurepoint
of view.We can define now
the
sernantic dornainof a
given languagein
thefollowing rvay: let 1:
{X¿}rcr"be a given family of
sets indexed. bythe index
,Inof the
grammar. XS-algebra (whenis defined) >S(X,
G):- : (X: {X,},-tn,
Xo)is
calledan
elementof the semantic
clomain otI(G).
Becausethe
XS-algebraof the
languageZ(G) is
>S(¿(G). G):
:
(¿(G),)"), it
issimilar to )S(X,
G),we can
definean
homomorphismH:
L(G)--t :S1X, G), called
semantic homomorphismin the
lollowingway:
(i). First
we defineIl on the
structure associated, to.ä-o(G),I'hich
isgenerally a finite set (or
denurrerable set).For that let w e
Zo(G) þe án element ofthe
typei-€
1c.'lhen H(w) wlll
be the injection oIa in
the setX,
which has the sametype
as ø.(ii). r-,"t us stlppose that
H
was defined on the leve1s Lr(G), L'(G),...,Lr(G),Fol
extenisonof H to L¡¡t(G)
we proceedas follows: If u =
Ln+t(G),because Zo(G)
u
Lt(G)u ... a
Li(G) isthe set of
generatorsfor
l¡11(G)there exist the, strings
'te,, u)2,...,
wnforro [J L¡(G) arñ' o e
X1,+r)c j :t)\
I
()
196
so
that o(ur, u,
we
haveTEODOR RUS 18
, Ur)
:
w,or
11):
(ni,i,..,iti:
s\IÙLszI|)z , ''
SrP)nSn*1. Then19 SolvfE OBSERVATIONS 797
(iv). There exists an operation o €
O,(1",),o: I[,
--> 16, denoted by o(00, 0,), rvlrere n.-
p(nr,nr, ..., nu) and 1[,
belongsto the
codornai¡of
0d.(v). Thefollowing diagram of operation composition
ino(Iç,)
commtltesH(*) :
(ùi,i,...i,¡i: srlf(ør)s, II (wr).'
. u,,H(un)s,,¡t
In this
waythe
semantic homomorphism defined onthe first
level of the languag"will
be homomorphic extend.to all the
language. !h_e homo- morphilm i¿is itr fact
an interpretatio_n ofthe
language irrthe
XS-al.gebra defiåed.by
Gin the family of
setsy: {x¿}¡-r". This interpretation
is givenby
a constructive method and describealso the role which state rvords have,The set
of all
)S-algebras definedby
a given grammar Gwill
be called semantic domainof the
langtlage genelated.by
G.It is
cluite clearthat
a
languagehas a family of
semantics,but
each eleme.ntof this
famil1' has a-str-ucturesimilar to that of
language, becanseit is
definedby
the samegrammaï. It should be interesting to .*t.4y
the, classesof
lan- guagesäefined. by some iclentity relations definedin
XS-algebras,We
shoulclo¡tain in this
way the varieties ofthe
languages.I,etnow@bea set so that @n N:Ø
and.a function ã:@-'
--)
O(N) lvhere g(N)
denotesthe
operation schemeas
above.In
this\4/ay we have defined
on the set
O(Iç,) o1 operatiorison
16,a
X-algebr.a Because)6, is a
subset o1. O(Iç,)the restriction of this structure to
the setof
operations definedby 2", will be
calleda
X-structureon
X6, andwill be
d.enoted.by 2",:
(.0,Nc,). The effect of
some operations Se )6, is
describedin the following rvay: let A : {A,lr-r",,
beaf.amil.y of sets indexed
by
15,,and 0 e
@. ø0is an
operationin
g(N).Let this
operation be ø 0 : NÉ- N. Then the opetatioir supplied bl)
Oin A : {Ar}¡-¡", is
describedby the
diagram(tlil^Al^
*,41,) ^ (/\,l,Ar:"
.r,4,i,) x -..x(,t;..t¡ :.,,1,¡..ør,l 't .,c,)zi "t ø.,,. '',t
IA¡ x A¿iz x'.\
,4ô"I¡ig. 7)
I;,
O,l
[,t X
t^," -
;"',' --- lÌl-,*- ¡ ;
I
a(.9.i,ۓr)
-4--. t!J Ftg. C
3.3, Relal.ions between languages
In the last part of the
papef weshall
definethe relation of
transla-tiirn
bet.r,r,eentri,o
languagei. -Ftorthat let two
grammarsG
andG'
begiven a L(G')
generatecl respectivelyby
Gãnd G'.
are context-freeand that
operatorschemes
weshall
def
Forthat
.lwe '
aslN COHN
: (o', s', t'),o' e
I'å,,s' e
Sc,,t' € Ic. I,et N
bethe
setof all
-n-arytiesof
òperatioásfrom
O(1",)), As rve li¿ivõ obser'ed. O(^16,) can be indexedby the set N,
O(Ic,):
{O,1t",)},¡=n, ândif Ic, is not empty then N is
notempty
too.A function
p : liÀ+ N rviil
be calledan
operation scheme on O(16')if the following
conditions holcl:(i). For
each (nr, Ø2,...,
7¿É)e Il which
beloilgsto the
domainof p'ihere
existsiî-O(I;') the
oþeratiars o1, o2,.. ',
ohof the
n-aryties71L,'lL2' .,,' iln.
(ii). there
exists afunction
0o:I'|ixI';:x ... x Iþ
->I[, whete
?i: : þ(nt, nr, ...,
no).(iii). Thcre exists
an operation0, e
OoU",)so that the
composition 0,(or,or,
. ..,
or)is
definedin
0(16').tc
:
,r ,l¿,!, ) ,JA ,Ak æu)/l .
llL
The process which