UNIVERSITATEA DIN PITESTI

FACULTATEA DE MATEMATICA-INFORMATICA

REFERAT

SCHEME SEMANTICE

Cuprins

Scheme semantice 6

Concepte de baza 8

Aspecte sintactice 10

Introducere 10

Aplicatia generata de S 10

Proprietati algebrice ale F_comp(S) 14

Elemente ordonate 15

Clase de obiecte 17

Bibliografie 19

Scheme semantice

Conceptul de schema semantica a fost introdus in (Tandareanu (2004d)) si aceasta structura extinde conceptul de retea semantica. O schema semantica este o structura abstracta care poate reprezenta cunostintele folosind o interpretare.

O astfel de structura S este un tuplu format din patru entitati,
S=(X, A₀, A, R), fiecare dintre ele specificand anumite caracterstici ale procesului de reprezentare. Pentru o anumita schema semantica S, o interpretare I₁ reprezinta o piesa de cunostinte KP₁. Daca vom inlocui I₁ printr-o alta interpretare I₂, S va reprezenta alta piesa de cunostinte KP₂.

In legatura cu o schema semantica S vom distinge doua aspecte

Un aspect formal prin care sunt obtinute calcule formale intr-o s-algebra Peano. Calculele sunt bazate pe conceptul de derivare (Tandareanu and Ghindeanu (2006a)) iar multimea de rezultate este notata prin F_comp(S) (Figura 2). vom introduce conceptul de tip al unei entitati formale a F_comp(S). Un tip este un element din multimea A, care este o submultime a s-algebrei Peano generata de A₀. Bazandu-ne pe acest concept putem imparti F_comp(S) in clase de echivalenta. O clasa de echivalenta va cuprinde toate elementele care au acelasi tip.

Un aspect de evaluare, tinand cont de o anumita interpretare. Entitatile obtinute la pasul anterior vor avea valori din spatiul semantic Y. Fiecare entitate din clasa de echivalenta [u]_F, unde u este un tip, este transformat in scopul obtinerii semanticii. Prin aceasta transformare obtinem o submultime Y_u a lui Y, fiecare Y_u avand clasa u. Spatiul Y devine astfel o uniune de clase de obiecte.

In Figura 2 vom vedea primul nivel al multimii R, care este o componenta a unei schemei semantice S. Un element din R este de forma (x, u, y) , unde uIA.

Calculele formale, bazate pe derivare, ne dau clasele de echivalenta [u]_F, fiecare element are tipul u si este transformat cu ajutorul unui obiect din clasa u. In acest fel, un element al lui A este un tip al unei entitati formale si o clasa a unui obiect din spatiul semantic.

Figura 2.

Concepte de baza

Sa consideram un simbol q de aritate 2 si o multime A₀ finita si nevida. Notam prin q-algebra Peano (Rudeanu (1991)) generata de A₀, deci , unde A_n este definit recursiv dupa cum urmeaza:

A_n+1 = A_n È n ³

Pentru fiecare aIvom defini trace(a astfel:

daca aIA₀ atunci trace(a)=<a>;

daca a q(u,v) atunci trace(a)=<p, q>, unde trace(u)=<p> si trace(v)=<q>

Definitie (Tandareanu (2004d))

O q schema semantica (pe scurt schema semantica) este un sistem

S=(X, A₀, A, R) unde:

X este o multime de simboluri finita si nevida iar obiectele sale se numesc simboluri de obiecte

A₀ este o multime de elemente finita si nevida numite simboluri de etichete si

A₀ A , unde este q-algebra Peano generata de A₀ (Rudeanu (1991))

R X A X este o multime nevida ce indeplineste urmatoarele conditii

x, q (u, v), y) I R Þ z I X: (x, u, z) I R, (z, v, y) I R

q (u, v) I A, (x, u, z) I R, (z, v, y) I R Þ (x, q (u, v), y) I R

u I A Û (x, u, y) I R

Vom nota:

R₀ = R X A₀ X)

Aspecte sintactice

Introducere

Mai jos vom prezenta conceptul de derivare intr-o schema semantica S, vom defini aplicatia generata de S, vom defini multimea F_comp(S) ce contine rezultatul final al procesului de derivare, vom stabili cateva proprietati algebrice pentru multimea F_comp(S) si vom pregati notiunile necesare pentru conceptul de interpretare (tipul unui element din multimea F_comp(S) si clasa unui obiect

Aplicatia generata de S

Fie S=(X, A₀, A, R) o schema semantica. Sa consideram un simbol h de aritate 1, un simbol s de aritate 2 si multimea:

M =

Vom nota cu H s-algebra Peano generata de M.

Vom nota cu Z alfabetul care include simbolul s, elementele lui X si elementele lui A, parantezele rotunde inchisa si deschisa, simbolu h si , (virgula). Vom nota cu Z^* multimea tuturor cuvintelor ce se pot forma cu simboluri din Z. La fel ca in cazul unui sistem de rescriere, vom da doua reguli de rescriere in definitia urmatoare.

Definitie

Fie w₁, w₂IZ^*. vom defini relatia binara Þ dupa cum urmeaza:

daca (x, a, y) I R₀, atunci w₁ (x, a, y) w₂Þ w₁ h(x, a, y) w₂

fie (x, q(u, v), y) I R. Daca (x, u, z) I R si (z, v, y) I R atunci

w₁ (x, q(u, v), y) w₂Þ w₁ s((x, u, y),(z, v, y)) w₂

Relatia Þ se numeste derivare directa peste Z^*. Vom nota prin Þ si Þ inchidera refleziva si tranzitiva a relatiei Þ, respectiv inchiderea tranzitiva. Relatia Þ va fi numita simplu derivare peste Z^*.

Definitie

Pentru fiecare wI Z^* unde w=w₁w₂w_n cu w_iIZ, iI, n³1, vom nota first(w)=w₁ si last(w)=w_n.

Definitie

Aplicatia generata de S este

G_S:R 2^H

definita dupa cum urmeaza

G_S(x, a, y)= pentru aIA₀

G_S(x, q(u, v), y)= pentru aIA₀

Multimea H este o multime infinita. Vom extrage din H acele elemente care pot fi derivate din R si vom nota aceasta multime cu F_comp(S).

Cu alte cuvinte

F_comp(S)=

Evident, vom avea:

F_comp(S)= G_S(x, u, y)

Mai jos sunt prezentate cateva proprietati fara demonstratie.

Propozitia 1

Presupunem ca (x, q(u, v), y)IR. Daca (x, q(u, v), y) Þ w atunci:

i)          Exista zIX pentru care

(x, q(u, v), y) Þ s (x, u, z), (z, u, y)) Þ w

ii)        Exista a si b astfel incat

w=s a b

(x, u, z) Þ a (z, u, y) Þ b

Propozitia 2

Daca (x, u, z) Þ a si aI ÈM)^* atunci aIH.

Propozitia 3

Sa presupunem ca wIG_S(x, q(u, v), y) si fie a si b acele elemente ale lui H, unic determinate, astfel incat w=s a b Atunci, exista zIX, astfel incat

(x, q(u, v), y)Þs((x, u, z), (z, v, y))

aIG_S(x, u, z) si bIG_S(z,    v, y)

Propozitia 4

Daca (x, u, z) Þ a si (z, v, y) Þ b atunci

s((x, u, z), (z, v, y)) Þ s a b

Corolar

G_S(x, q(u, v), y)= G_S(x, u, z) A G_S(z, v, y)

unde P A Q =

Definitie

Definim:

H(h(x, a, y))=<h(x, a, y)>, pentru h(x, a, y)IM

H(s a b))=<p, q>, unde H(a)=<p> si H(b)=<q>,

s a b IH, aIH, bIH

Propozitia 5

Fie uIA astfel incat trace(u)=<a₁, , a_n>. Pentru fiecare

aI G_S(x₁, u, z₁) exista y₁, , y_n-1IX pentru care H(a)=<h(x₁, a₁, y₁), h(y₁, a₂, y₂), , h(y_n-1, a_n, z₁)> pentru n³2 si H(a)=<h(x₁, u, z₁)> pentru n=1.

Corolar

Daca G_S(x₁, u, z₁) G_S(x₂, v, z₂)¹Æ atunci x₁=x₂, trace(u)=trace(v) si z₁=z₂.

Corolar

Elementul zIX din propozitia 3 este unic determinat.

Proprietati algebrice ale F_comp(S)

Mai jos, vom da cateva proprietati noi ale multimii F_comp(S). Deoarece vom lucra cu doua scheme semantice S si P, vom nota cu H_S si H_P s-algebrele Peano generate de S, respectiv P.

Propozitia 6

F_comp(S) I Initial(H_S)

Propozitia 7

Propozitia 8

Daca F_comp(S) H_S si F_comp(P) H_P atunci

F_comp(S) F_comp(P) I Initial(H_S H_P)

Pentru simplificarea demonstratilor anumitor proprietati vom da urmatoarea definitie

Definitie

O derivare la stanga este o derivare de forma w₁ Þ w₂ Þ astfel incat pentru fiecare i³1 derivarea directa w_i Þ w_i+1 are proprietatea ca w_i+1 este obtinut inlocuind primele trei simboluri din partea stanga ale lui w_i.

Astfel, proprietatea urmatoare este evidenta.

Propozitia 9

Daca w este derivat din (x, u, y), atunci exista o derivare la stanga a lui w din (x. u, y).

Propozitia 10

Fie doua scheme semantice S si P. Daca wI F_comp(S) F_comp(P) atunci (x, u, y) Þ w este o derivare la stanga in S dac si numai daca este o derivare la stanga in P.

Propozitia 11

Daca S P atunci F_comp(S) F_comp(P).

Elemente ordonate

Pentru introducerea notiunii de element ordonat avem nevoie de cateva rezultate preliminare. O proprietate folositoare este data de propozitia urmatoare.

Propozitia 12

Daca w I G_S(x, u₁, z) G_S(x, u₂, z) atunci u₁ = u₂.

Mai jos vom da o proprietate de baza care ne ajuta sa introducem conceptul de element ordonat.

Propozitia 13

Pentru fiecare wI F_comp(S) exista un singur element (x, u, y) I R care satisface proprietatea (x, u, y)Þ w.

Definitie

Daca wI F_comp(S) atunci elementul u I A pentru care (x, u, y) I R si (x, u, y)Þ w este numit tipul lui w si vom nota sort(w) = u.

Propozitia 14

Fiecare element wI F_comp(S) are un tip care este unic determinat.

Propozitia 15

Presupunem ca s a b I F_comp(S), aI F_comp(S) si bI F_comp(S). Daca sort(s a b s(u, v) atunci sort(a)=u si sort(b =v.

Definitie

Fie w₁, w₂I F_comp(S). Vom scrie w₁ ~ w₂ daca sort(w₁) sort(w₂). Pentru fiecare uIA vom nota

[u]_F=

O proprietate importanta in studiul acestor multimi este data de urmatoarea propozitie:

Propozitia 16

Pentru fiecare (x, u, y) I R vom avea G_S(x, u, y) ¹ Æ

Propozitia 17

Pentru fiecare uIA vom avea [u]_F ¹ Æ

Observam ca relatia ~ definita mai sus este reflexiva, simetrica si tranzitiva, deci este o relatie de echivalenta. Astfel, multimea F_comp(S) este impartita in clase de echivalenta iar toate elementele unei clase de echivalenta vor avea acelati tip. Cu alte cuvinte

Multimea F_comp(S) este rezultatul calculelor formale definite de schema S.

Clase de obiecte

Sa consideram:

O schema semantica S = (X, A₀, A, R)

O aplicatie bijectiva ob:X→Ob, unde Ob este o multime de obiecte (numite obiecte simple)

Pentru fiecare uIA vom considera un algoritm Alg_u pentru care din doua obioecte o₁ si o₂ obtinem alt obiect Alg_u(o₁, o₂). In plus, presupunem ca pentru aIA₀, elementul Alg_a(o₁, o₂) este definit numai de obiectele o₁, o₂ IOb (obiecte simple). Obiectele Alg_u(o₁, o₂) sunt numite obiecte complexe.

Definitie

Vom defini recursiv:

Obiectul o=Alg_a(ob(x), ob(y)) pentru aIA₀ si x, yIX este un obiect complex de clasa a si vom nota aceasta afirmatie prin cls(o)=a.

Daca cls(o₁)=u, cls(o₂)=v si q(u, v)IA atunci o=Alg_{q(u, v)}(o₁, o₂) este un obiect complex si cls(o)=q(u, v).

Observam ca pentru un obiect de clasa q(u, v) este un obiect ce constituie iesirea algoritmului Alg_{q(u, v)} pentru doua obiecte de intrare de clasa u, respectiv v.

De asemenea remarcam ca elementele lui A sunt vazute ca tipuri pentru elementele lui F_comp(S) si clase pentru obiecte.

Bibliografie

[1] Tandareanu, N. (2004d): Semantic Schemas and Applications in Logical representation of Knowledge, Proceedings of the 10th International Conference on Cybernetics and Information Technologies, Systems and Applications (CITSA2004), July 21-25, Orlando, Florida, Vol. III p.82-87

[2] Tandareanu N., Ghindeanu M. (2006a): Properties of derivations in a Semantic Schema, Annals of University of Craiova, Math. Comp. Sci. Ser.

[3] Tandareanu N. (2005a): Transfer of knowledge via semantic schemas, July 10-13, Vol. IV, p.70-75, 2005

[4] Tandareanu N., Ghindeanu, M. (2005b): A three-level distributed knowledge system based on semantic schemas, 16th Int. Workshop on Database and Expert Systems Applications, Proceedings of DEXA'05, Copenhagen, p.423-427, 2005

[5] Tandareanu, N. (2000a): Proving the Existence of labeled Stratifed Graphs, Annals of the University of Craiova, Vol. XXVII, 81{92; on line version at https://inf.ucv.ro/~ntand/en/publications.html

[6] Tandareanu, N., (2000b): Knowledge Bases with Output, Knowledge and Information Systems 2(2000) 4, 438-460.

[7] Tandareanu, N. (2001): Intuitive Aspects of the Semantic Computations in KBO, Research Notes in Artificial Intelligence and Digital Communications 101, 1th     National Conference on Artificial Intelligence and Digital Communications, Craiova,June 2001, 1-8.