INFORMATICA, 2015, Vol. 26, No. 3, 407417 407 [628002]

INFORMATICA, 2015, Vol. 26, No. 3, 407–417 407
2015 Vilnius University
DOI: http://dx.doi.org/10.15388/Informatica.2015.55
Formal Languages Generation in Systems
of Knowledge Representation Based
on Stratified Graphs
Daniela DĂNCIULESCU
University of Craiova, Department of Computer Science, Rom ania
e-mail: [anonimizat]
Received: November 2014; accepted: May 2015
Abstract. The concept of stratified graph introduces some method of rep resentation which can be
embedded with an interpretation mechanism in order to obtai n objects from some knowledge domain
based on the considered symbolic graph-based representati ons. As it was defined in the literature,
the inference process uses the paths of the stratified graphs , an order between the elementary arcs of
a path and some results of universal algebras. The order is de fined by considering a structured path
instead of a regular path. In a previous paper the concept of s ystem of knowledge representation
was defined. It includes a stratified graph G, a partial algebra Yof objects, an injective mapping
that embeds the nodes of Ginto objects of Yand a set of algorithms that takes pairs of objects
fromYto get some other object of Y. In this paper the inference process defined for such a system
of knowledge considers the interpretation of the symbolic e lements of a stratified graph as formal
language constructions. The concepts introduced in this pa per can initiate a possible research line
concerning the automatic generation mechanism for formal l anguages.
Key words: graph-based representation and reasoning, formal languag e generation, accepted
structured paths.
1. Introduction
We can distinguish the following two research directions co ncerning the implications
of graph-based theory into knowledge representation: conc eptual graphs (Sowa, 1976),
Sowa (1984) involve the usage of first-order logic into graph theory; labeled stratified
graphs (Țăndăreanu, 2000) and semantic schema (Țăndăreanu , 2004a). The last two con-
cepts were obtained by applying the methods of universal alg ebras to graph theory. For
other details regarding graph theory and some of their appli cations, the reader is referred,
for example, to Aho and Ullman (1955) Bang-Jensen and Gutin ( 2000), Berge (1967),
Biggs (1993), Flaut and Ghionea (2008), Godsil and Royle (20 01), Grossman (2002), Ore
(1962), Pop and Negru (2002).
The conceptual graphs are formal knowledge representation s provided with reasoning
operations which are sound and complete with respect to dedu ction in first order logics
(Sowa, 1984). The formalism takes the visual properties of t he semantic nets and also the
semantic aspects of these networks. Basically, a conceptua l graph is a bipartite labeled

408 D. Dănciulescu
oriented graph such that: each node is either a concept or a re lation between two concepts;
the arcs are not labeled; concepts have only arcs to relation s and vice versa.
Same as conceptual graphs, the labeled stratified graphs are based on labeled graphs.
Still, there are some important differences between these st ructures. The concept of the
labeled stratified graph is entirely an algebraic one, and no t logic as in the case of con-
ceptual graph (conceptual graphs are usually considered as visual concepts for logic). The
mathematical apparatus of labeled stratified graphs uses co ncepts from universal algebra:
Peano algebra, partial algebras, morphism of partial algeb ras.
Up to this point various mechanisms were developed in order t o define and generate
formal languages such as: finite automata (Hopcroft et al., 2000; Xavier, 2005), regular
expressions (Hopcroft et al. , 2000), formal grammars (Hopcroft et al. , 2000), Linden-
mayer systems (Prusinkiewicz and Lindenmayer, 1990), etc. A formal language consists
of a non-empty set of words which are finite strings of letters , symbols, or tokens. The set
from which these letters are taken is named the alphabet of th e language, over which the
language elements are constructed.
The method of knowledge representation based on stratified g raphs was successfully
applied in various domains such as: semantics of communicat ions and image synthesis
(Țăndăreanu, 2004b), reconstruction of a graphical image b y extracting the semantics
of a linguistic spatial description given in a natural langu age (Țăndăreanu and Ghin-
deanu, 2003, 2004), knowledge bases with output and their us e to the scheduling problems
(Țăndăreanu, 2000).
In this paper we continue the research line initiated in Tudo r (2011) concerning the
use of the accepted structured paths to generate formal lang uages. In our approach we
endowed the concept of System of Knowledge Representation b ased on Stratified Graphs
(Dănciulescu, 2013) with formal language interpretation c onstructions. In this manner, we
obtain a new system for Formal Language Generation as it will be detailed in what follows.
Because the developed system is based on stratified graphs re presentations, we begin our
study by presenting several definitions and properties from the Labeled Stratified Graphs
theory.
2. Labeled Stratified Graphs: Definitions and Basic Concepts
The concept of Labeled Stratified Graph was firstly introduce d in Țăndăreanu (2000).
A labeled stratified graph (shortly, LSG) is constructed over a labeled graph and an alge-
braic structure defined by means of a Peano algebra, a finite se t of binary relations and a
morphism of partial algebras (Țăndăreanu, 2004c).
By abinary partial operation on a non-empty set Awe understand a partial mapping f
fromA×AtoA. This implies that fis defined for the elements of some set noted with
dom(f )(Țăndăreanu, 2000):
f:dom(f )→A
where dom(f) ⊂A×A.

Formal Languages Generation in Systems of Knowledge Repres entation Based on SG 409
The pair (A,σ A), where Ais the support set and σAis a partial binary operation on
A, is called a partial σ-algebra (Țăndăreanu, 2000). If dom(σA)=A×Athen the pair
(A,σ A)is called σ-algebra (Țăndăreanu, 2000).
For a non-empty set Sthe collection of all subsets of S×Swill be denoted with 2S×S.
Ifρ1∈2S×Sandρ2∈2S×Sare two binary relations on Sthen by ρ1◦ρ2we understand the
set of all pairs (x,y) ∈S×Sfor which there is z∈Ssuch that (x,z)∈ρ1and(z,y)∈ρ2.
For the mapping prodS:dom(prodS)→2S×Ssuch that prodS(ρ1,ρ2)=ρ1◦ρ2and
(ρ1,ρ2)∈dom(prodS)if and only if ρ1◦ρ2/ne}ationslash= ∅, the set R(prodS)denotes the set of all
restrictions of the mapping prodS(Țăndăreanu, 2000):
R(prodS)= {u|u≪prodS}
where u≪prodSmeans that dom(u)⊆dom(prodS)andu(ρ 1,ρ2)=prodS(ρ1,ρ2)for
(ρ1,ρ2)∈dom(u). Moreover, if uis an element of R(prodS)then the pair (2S×S,u)is a
partial algebra (Țăndăreanu, 2000). This is the structure used to define the c oncept of the
labeled stratified graph .
In what follows, we take u∈R(prodS)and consider the closure T=Clu(T0)ofT0
in the algebra (2S×S,u), where T0notes the set of binary relations in a labeled graph
(Țăndăreanu, 2004d).
A labeled graph is considered represented by the following t uple (Țăndăreanu, 2000):
G0=(S0,L0,T0,f0)
where S0is a finite set of nodes, L0is a set of elements called labels, T0is a set of binary
relations on S0andf0:L0→T0is a surjective function.
For each nonempty set Mthere is a Peano σ-algebra over M. Indeed, for B=/uniontext
n>=0Bn, where:
B0=M,
Bn+1=Bn∪/braceleftbig
σL(x1,x2)/vextendsingle/vextendsinglex1,x2∈Bn/bracerightbig
the pair (B,σ L)is the Peano σ-algebra over M(Țăndăreanu, 2004d).
We consider a collection of subsets of B, noted in what follows with Initial(M). We
haveL∈Initial(M)if:
–M⊆L⊆B;
– ifσL(u,v) ∈L, thenu∈L,v∈L.
Alabeled stratified graph overG0is a tuple (G0,L,T,u,f ) where (Țăndăreanu, 2000):
–L∈Initial(L0);
–(u∈R(prodS)andT=Clu(T0);
–f:(L,σ L)→(2S×S,u)is a morphism of partial algebras such that f0≪f,f(L)=
Tand if (f (x),f(y)) ∈dom(u)then(x,y) ∈dom(σL).

410 D. Dănciulescu
3. Accepted Structured Paths
Let us consider a labeled graph G0=(S0,L0,T0,f0). BySTR(G0)we will note the set
of structured paths of the labeled graph G0, this concept being defined in Dănciulescu
(2013) as the smallest set satisfying the following conditi ons:
– for every a∈L0and(x,y) ∈f0(a)we have ([x,y],a)∈STR(G0);
– if([x1,…,x k],u),([xk,…,x n],v)∈STR(G0)then([x1,…,x k,…,x n],[u,v])∈
STR(G0).
We consider:
STR 2(G0)=/braceleftbigw| ∃(α,w) ∈STR(G0)/bracerightbig.
In fact, STR 2(G0)represents the projection of the set STR(G0)on the second axis, more
precisely, STR 2(G0)=pr2(STR(G0)). We consider the mapping h:STR 2(G0)→Bsuch
that (Dănciulescu, 2013):
h(a)=a,fora∈L0,
h/parenleftbig
[u,v]/parenrightbig
=σL/parenleftbig
h(u),h(v)/parenrightbig
where Bis defined as above. If we take G=(G0,L,T,u,f ) a labeled stratified graph
over the label graph G0, then by ASP(G)we note the set of all accepted structured paths
overG(Dănciulescu, 2013):
/parenleftbig[x1,…,x n],c/parenrightbig∈ASP(G)if and only if/parenleftbig[x1,…,x n],c/parenrightbig∈STR(G)andh(c)∈L.
Moreover, ∀d=([x1,…,x n],σL(u,v)) ∈ASP(G), there is one and only one k∈
{1,…,n }such that: ([x1,…,x k],u),([xk,…,x n],v)∈ASP(G).
In other words, this property states that every accepted str uctured path can be broken
in other two accepted structured paths.
4. System of Knowledge Representation Based on Labeled Stra tified Graph
for Formal Language Generation
As it is considered in literature, a formal language is a set o f words which are represented
by finite strings of letters, symbols or tokens. The set of all the letters or symbols upon
which the words are made of is called the alphabet of the formal language. Usually, a for-
mal language is defined by means of some formation rules or a formal grammar .
An interpretation for a labeled stratified graph provides a r epresentation in a domain
of knowledge (Pop and Negru, 2003). In the presented approac h, we take the domain of
knowledge to be a particular formal language. In what follow s we will note by Vthe
alphabet of the generated formal language.

Formal Languages Generation in Systems of Knowledge Repres entation Based on SG 411
Therefore, let us consider the labeled stratified graph G=(G0,L,T,u,f ) over a la-
beled graph G0=(S0,L0,T0,f0). We defined the interpretation of Gas a tuple:
I=/parenleftbig
V∗,ob,D,Y/parenrightbig
such that:
–V∗is the set of all strings constructed over the characters of V; in this formalism V∗
represents the knowledge domain of I;
–ob:S→V∗a bijective function that maps the symbols of Sinto the strings of V∗;
–D=(V∗,•)is a partial algebra over V∗. In what follows we will consider the oper-
ationoas a partial operation defined in the following manner:
for every natural number mwe take wm+1=wm•w;
– the set of algorithms Y= {Algu}u∈Lgenerate the elements of the interpretation do-
mainV∗,Algu:V∗×V∗→V∗,u∈L.
According to this interpretation system, the valuation map ping generated by Iis de-
fined as valI:ASP(G)→Ysuch that:
valI/parenleftbig[x,y],u/parenrightbig=Algu/parenleftbigob(x),ob(y)/parenrightbig, u∈L0,
valI/parenleftbig[x1,…,x n],σL(u,v)/parenrightbig
=valI/parenleftbig
[x1,…,x k],u/parenrightbig
•valI/parenleftbig
[xk,…,x n],v/parenrightbig
,forσL(u,v) ∈L.
R/e.sc/m.sc/a.sc/r.sc/k.sc 1. Because D=(V∗,•)is a partial algebra, results that valI([x1,…,x k],u)•
valI([xk,…,x n],v)∈V∗if and only if ([x1,…,x k],u),valI([xk,…,x n],v∈V∗and
(([x1,…,x k],u),valI([xk,…,xn ],v))∈dom(•).
R/e.sc/m.sc/a.sc/r.sc/k.sc 2. For each (ob1,ob2)∈Y×Y, the string Algu(ob1,ob2)foru∈L, is an ele-
ment of V∗, therefore/uniontext
u∈LAlgu(ob1,ob2)represents the formal language over Vcon-
structed by means of the abstract notations of G.
D/e.sc/f.sc/i.sc/n.sc/i.sc/t.sc/i.sc/o.sc/n.sc 1. We define a system of knowledge representation based on str atified graphs
for formal language generation as follows:
SKR=/parenleftbigG,/parenleftbigV∗,•/parenrightbig,ob,Y/parenrightbig.
The inference process IPSKRgenerated by the system of knowledge representation SKR
is:
IPSKR:ASP(G)→Y.
We obtain that the set Yincludes all the words constructed over the alphabet Vby
means of the algorithms defined in the interpretation system Iof the labeled stratified
graph G.

412 D. Dănciulescu
Therefore ∀d∈ASP(G)– an accepted structured path of the structure G, we have:
IPSKR(d)=valI(d).
Following the inference process given above the output elem ents of Yas defined follows:
takeC(x,y)=/braceleftbig
d∈ASP(G)/vextendsingle/vextendsinglefirst(d)=x,last(d)=y/bracerightbig
,
IPSKR=/uniondisplay
(x,y)∈S×SIPSKR(C(x,y));
IPSKR=/uniontext
(x,y)∈S×S{w∈Y| ∃d∈C(x,y):IPSKR(d)=w}where, for d∈ASP(G),d=
([x1,…,x n],u):first(d)=x1andlast(d)=xn.
5. A Study Case
In order to exemplify our mechanism of formal language gener ation we will consider the
following system of knowledge based on stratified graphs:
SKR=/parenleftbigG,/parenleftbigV∗,•/parenrightbig,ob,{Algu}u∈L/parenrightbig
where the language alphabet is represented by the set V= {0,1}and the labeled stratified
graph is given by the tuple G=(G0,L,T,u,f ) forG0=(S,L 0,T0,f0):
–S= {X1,X2,X3},
–L0= {a,b,c},
–T0= {ρ1,ρ2,ρ3}where ρ1= {(X1,X2)},ρ2= {(X2,X1)}andρ3= {(X2,X3)},
–f0:L0→T0,f0(a)=ρ1,f0(b)=ρ2,f0(c)=ρ3.
If we take the following binary relations: ρ4= {(X1,X1)},ρ5= {(X2,X2)}and
ρ6= {(X1,X3)}then the mapping u=prodSis defined as follows:
ρ1◦ρ2=ρ4, ρ 2◦ρ1=ρ5, ρ 1◦ρ3=ρ6,
ρ1◦ρ5=ρ1, ρ 2◦ρ4=ρ2, ρ 2◦ρ6=ρ3,
ρ4◦φ=φ,∀φ∈ {ρ1,ρ6},
ρ5◦φ=φ,∀φ∈ {ρ2,ρ3}.
The structure of the considered labeled stratified graphs im plies the following results:
– the set of labels Lis infinite, L=L0∪{σL(a,b),σ L(b,a),σ L(a,c),σ L(a,σ L(b,a)),
σL(b,σ L(a,b)),σ L(b,σ L(a,c)),σ L(σL(a,b),a),σ L(σL(b,a),b),σ L(σL(b,a),c),
σL(σL(a,b),σ L(a,c)),… }
f (a)=ρ1, f (b) =ρ2, f (c) =ρ3,

Formal Languages Generation in Systems of Knowledge Repres entation Based on SG 413
Fig. 1. The labeled graph G0.
f/parenleftbigσL(a,b)/parenrightbig=ρ4; ρ1◦ρ2=ρ4,
f/parenleftbigσL(b,a)/parenrightbig=ρ5; ρ2◦ρ1=ρ5,
f/parenleftbig
σL(a,c)/parenrightbig
=ρ6;ρ1◦ρ3=ρ6,
f/parenleftbig
σL/parenleftbig
a,σL(b,a)/parenrightbig/parenrightbig
=ρ1;ρ1◦ρ5=ρ1,
f/parenleftbig
σL/parenleftbig
b,σL(a,b)/parenrightbig/parenrightbig
=ρ2; ρ2◦ρ4=ρ2,
f/parenleftbig
σL/parenleftbig
b,σL(a,c)/parenrightbig/parenrightbig
=ρ3;ρ2◦ρ6=ρ3,
f/parenleftbig
σL/parenleftbig
σL(a,b),a/parenrightbig/parenrightbig
=ρ1;ρ4◦ρ1=ρ1,
f/parenleftbig
σL/parenleftbig
σL(a,b),σ L(a,c)/parenrightbig/parenrightbig
=ρ6;ρ4◦ρ6=ρ6,
f/parenleftbig
σL(σL(b,a),b)/parenrightbig
=ρ2; ρ5◦ρ2=ρ2,
f/parenleftbig
σL/parenleftbig
σL(b,a),c/parenrightbig/parenrightbig
=ρ3;ρ5◦ρ3=ρ3,
…
f/parenleftbig
σL(u,v)/parenrightbig
=ρ1,foru∈f−1(ρ1)andv∈f−1(ρ5),
f/parenleftbig
σL(u,v)/parenrightbig
=ρ2,foru∈f−1(ρ2)andv∈f−1(ρ4),
f/parenleftbigσL(u,v)/parenrightbig=ρ3,foru∈f−1(ρ2)andv∈f−1(ρ6),
f/parenleftbigσL(u,v)/parenrightbig=ρi,foru∈f−1(ρ4)andv∈f−1(ρi)withi∈ {1,6},
f/parenleftbigσL(u,v)/parenrightbig=ρi,foru∈f−1(ρ5)andv∈f−1(ρi)withi∈ {2,3}
–T=Clu(T0)= {ρ1,ρ2,ρ3,ρ4,ρ5,ρ6}.
Taking into account the set Tof binary relations, we will consider in what follows
the set N= {(X1,X2),(X 2,X1),(X 2,X3),(X 1,X1),(X 2,X2),(X 1,X3)}. We define the
function ob:→V∗in the following manner: ob(X1)=0,ob(X2)=1andob(X3)=10.
We consider the set of algorithms {Alga}a∈L0as follows:
–Alga(ob(Xi),ob(Xj))=ob(Xj)ob(Xi)– inversion of the two sequences ob(Xj)
andob(Xi);
–Algb(ob(Xi),ob(Xj))=ob(Xi)ob(Xj)– simple concatenation of the two se-
quences ob(Xj)andob(Xi);
–Algc(ob(Xi),ob(Xj))=ob(Xj)ob(Xj)– concatenation and replacement of the first
sequence with the second

414 D. Dănciulescu
R/e.sc/m.sc/a.sc/r.sc/k.sc 3. Because the set Lis infinite, also the generated formal language by means of
the considered interpretation Iis infinite.
In what follows we will prove that the language generated by m eans of the labeled
stratified graph Gand the interpretation Iis{(10)m|m >=1}. We have:
valI([X1,X2],a)=Alga(ob(X1),ob(X2))=10,
valI([X2,X1],b)=Algb(ob(X2),ob(X1))=10,
valI([X2,X3],c)=Algc(ob(X2),ob(X3))=10•10=(10)2,
valI([X1,X2,X1],σL(a,b)) =valI([X1,X2],a)•valI([X2,X1],b)
=10•10=(10)2,
valI([X2,X1,X2],σL(b,a)) =valI([X2,X1],b)•valI([X1,X2],a)
=10•10=(10)2,
valI([X1,X2,X3],σL(a,c)) =valI([X1,X2],a)•valI([X2,X3],c)
=10•(10)2=(10)3,
valI([X1,X2,X1,X2],σL(σL(a,b),a))
=valI([X1,X2,X1],σL(a,b)) •valI([X1,X2],a)=(10)2•10=(10)3,
valI([X2,X1,X2,X1],σL(σL(b,a),b))
=valI([X2,X1,X2],σL(b,a)) •valI([X2,X1],b)=(10)2•10=(10)3,
valI([X2,X1,X2,X3],σL(σL(b,a),c))
=valI([X2,X1,X2],σL(b,a)) •valI([X2,X3],c)=(10)2•(10)2=(10)4,
valI([X1,X2,X1,X2,X3],σL(σL(a,b),σ L(a,c)))
=valI([X1,X2,X1],σL(a,b)) •valI([X1,X2,X3],σL(a,c))
=(10)2•(10)3=(10)5,
…
Using this interpretation, the generated language is made o f(10)msequences, m > 0
as it will be proved in the next proposition.
Proposition 1. The language generated by the considered system of knowledg e represen-
tation SKR is:
IPSKR=/uniondisplay
d∈ASP(G)IPSKR(d)=/uniondisplay
d∈ASP(G)valI(d),
IPSKR=/braceleftbig(10)m/bracerightbig
m>0.

Formal Languages Generation in Systems of Knowledge Repres entation Based on SG 415
Proof. We have: IPSKP=/uniontext
(x,y)∈NC(x,y) . But N= {(X1,X2),(X 2,X1),(X 2,X3),
(X1,X1),(X 2,X2),(X 1,X3)}, which implies: IPSKP= {valI(d)|d∈ASP(G),first(d)=
X1,last(d)=X2}∪{valI(d)|d∈ASP(G),first(d)=X2,last(d)=X1}∪{valI(d)|d∈
ASP(G),first(d)=X2,last(d)=X3} ∪ {valI(d)|d∈ASP(G),first(d)=X1,last(d)=
X1} ∪ {valI(d)|d∈ASP(G),first(d)=X2,last(d)=X2} ∪ {valI(d)|d∈ASP(G),
first(d)=X1,last(d)=X3}.
Results IPSKR= {(10)2k+1}k>0∪ {(10)2k+1}k>0∪ {(10)2k}k>0∪ {(10)2k}k>0∪
{(10)2k}k>0∪ {(10)2k}k>0= {(10)2k+1}k>0∪ {(10)2k}k>0= {(10)m}m>0. /square
6. Conclusions
In this paper we propose a new system for formal language gene ration by means of a sys-
tem of knowledge based on labeled stratified graphs (LSGs). W e exemplified that, using
an interpretation system specially defined for stratified gr aphs representations, a particu-
lar formal language can be obtained by means of the resulted a ccepted structured paths.
Based on labeled stratified graphs representations a new mec hanism for natural language
generations was developed (see Dănciulescu and Colhon, 201 4). This generation mecha-
nism pays attention to the syntactic agreements involvedin natural language constructions.
In a future study we intend to investigate the manner in which , by imposing a set of re-
strictions Ron the computations in the inference process of such systems the generated
formal language sequences would be affected. Also, we intend to study the formal lan-
guages families that can be obtained in this type of knowledg e system: regular languages,
context-sensitive languages, etc.
Acknowledgements. This work was supported by the strategic grant POSDRU/159/1 .5/S/
133255, Project ID 133255 (2014), co-financed by the Europea n Social Fund within the
Sectorial Operational Program Human Resources Developmen t 2007–2013.
References
Aho, A.V., Ullman, J.D. (1995). Foundations of Computer Science . Computer Science Press, New York.
Bang-Jensen, J., Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications . Springer, London.
Berge, C. (1967). Théorie des graphes et ses applications . Dunod, Paris.
Biggs, N. L. (1993). Algebraic Graph Theory , 2nd ed. Cambridge University Press, London.
Dănciulescu, D. (2013). Systems of knowledge representati on based on stratified graphs and their inference
process. In: 9th International Conference of Applied Mathematics, Abst racts and Pre-Proceedings, Baia
Mare .
Dănciulescu, D., Colhon, M. (2014). Splitting the structur ed paths in stratified graphs. Application in natural
language generation. Annals of Ovidius University of Constanța, Mathematics Ser ies, 22(2), 59–69.
Flaut, C., Ghionea, F. (2008). Some properties of the line gr aph associated to a graph G.Italian Journal of Pure
and Applied Mathematics , 25, 165–174.
Hopcroft, J.E., Motwani, R., Ullman, J.D. (2000). Introduction to Automata Theory, Languages, and Computa-
tion. Addison-Wesley, Boston.
Godsil, C., Royle, G. (2001). Algebraic Graph Theory . Springer, Berlin.
Grossman, P. (2002). Discrete Mathematics for Computing . Palgrave MacMillan, New York.

416 D. Dănciulescu
Ore, O. (1962). Theory of Graphs . AMS, Rhode Island.
Pop, D. Negru, V. (2002). Knowledge Management in Expert System Creator, Artificial I ntelligence: Methodol-
ogy, Systems and Applications . In:Lecture Notes in Computer Science , Vol. 2443, pp. 233–242.
Pop, D., Negru, V. (2003). An Extensible Environment for Expert System Development, K nowledge-Based Intel-
ligent Information and Engineering Systems . In:Lecture Notes in Computer Science , Vol. 2773, pp. 1016–
1022.
Prusinkiewicz, P., Lindenmayer, A. (1990). The Algorithmic Beauty of Plants . Springer, New York.
Sowa, J. F. (1976). Conceptual graphs for a data base interface .IBM Journal of Research and Development ,
20(4), 336–357.
Sowa, J. F. (1984). Conceptual Structures: Information Processing in Mind and Machine . Addison-Wesley,
Boston, 481 pp.
Tudor (Preda), I.-V. (2011). Considerations regarding for mal languages generation using labelled stratified
graphs. International Journal of Applied Mathematics and Informat ics, 2(5), pp. 101–108.
Țăndăreanu, N. (2000). Knowledge bases with output. Knowledge and Information Systems , 2(4), 438–460.
Țăndăreanu, N. (2004a). Semantic schemas and applications in logical representation of knowledge. In: Pro-
ceedings of the 10th International Conference on Cyberneti cs and Information Technologies, Systems and
Applications , July 21–25, USA, III, pp. 82–87.
Țăndăreanu, N. (2004b). Knowledge representation by label ed stratified graphs. In: Proceedings of the 8th World
Multi-Conference on Systemics, Cybernetics and Informati cs, Orlando, Florida, USA, V, pp. 345–350.
Țăndăreanu, N. (2004c). Distinguished representatives fo r equivalent labelled stratified graphs and applications.
Discrete Applied Mathematics , 144(1–2), 183–208.
Țăndăreanu, N. (2004d). Knowledge representation by label ed stratified graphs. Proceedings of the 8th World
Multi-Conference on Systemics, Cybernetics and Informati cs, 5, 345–350.
Țăndăreanu, N., Ghindeanu, M. (2003). Image synthesis from natural language description. Research Notes in
Artificial Intelligence and Digital Communications , 103, 82–96.
Țăndăreanu, N., Ghindeanu, M. (2004). Hierarchical reason ing based on stratified graphs. Application in image
synthesis. In: Proceedings of 15th International Workshop on Database and Expert Systems Applications
DEXA2004, Zaragoza . IEEE Computer Society, Los Alamitos, pp. 498–502.
Xavier, S.P.E. (2005). Theory of Automata, Formal Languages and Computation , New Age International Limites
Publisher.

Formal Languages Generation in Systems of Knowledge Repres entation Based on SG 417
D. Dănciulescu (born Daniela Udrea): Since 2006: Associate Profesor at Dep artment
of Computer Science, University of Craiova, Romania; since 2004: PhD in Cybernetics
and Economic Statistics, University of Craiova, Romania, a nd since 2012: PhD Student
at Faculty of Mathematics and Computer Science, The West Uni versity of Timișoara,
Romania with the PhD thesis title “New Results in Graph-base d Knowledge Representa-
tion”; Competence domains: Analysis, Design and Implement ation of Information Sys-
tems, Computers Programming, Expert System, Knowledge Rep resentation and Reason-
ing; Teaches: Databases, Computers Programming, Operatio n Systems at Department
of Computer Science, University of Craiova; Representativ e articles: (1) Daniela Dănci-
ulescu, Mihaela Colhon, Systems of knowledge representati on based on stratified graphs:
Application to natural language generation, Carpathian Journal of Mathematics , vol. 2
(2016 – to appear), (2) Andrei Horvat Marc, Levente Fuksz, Pe trică C. Pop, Daniela Dăn-
ciulescu, A novel hybrid algorithm for solving the clustere d vehicle routing problem, in:
Proceedings of International Conference HAIS 2015 , Springer International Publishing
Switzerland (2015), (3) Daniela Dănciulescu, Mihaela Colh on, Splitting the structured
paths in stratified graphs: Application in natural language generation, Annals of Univeristy
Ovidius of Constanța, Mathematics Series , vol. 22, no. 2, pp. 59–69, ISSN: 1224-1784
(2014).
Formalios kalbos generavimas žinių vaizdavimo sistemose,
grįstose sluoksniniais grafais
Daniela D ˘ANCIULESCU
Pateikiant sluoksninius grafus, supažindinama su žinių vai zdavimo metodu, kuriam gali būti pridė-
tas interpretavimo mechanizmas, skirtas objektų išgavimu i iš tam tikros žinių srities, atsižvelgiant
į simbolinius grafais pagrįstus atvaizdavimus. Remiantis literatūra, išvedimo procese yra naudo-
jami sluoksninių grafų keliai, tvarka tarp elementariųjų k elio lankų ir keli universaliųjų algebrų
rezultatai. Tvarka yra apibrėžiama, pasirenkant struktūr izuotus kelius vietoj įprastų. Ankstesniame
straipnyje buvo pristatyta žinių vaizdavimo sistema. Ją su daro sluoksninis grafas G, dalinė objektų
algebra Y, injekcinis surišimas, kuris susieja grafo Gviršūnes su algebros Yobjektais, ir algorit-
mų aibė, kurie naudoja objektų iš Yporas, kad išgautų kitus Yobjektus. Šiame straipsnyje žinių
sistemos išvedimo procese sluoksninių grafų simboliniai e lementai interpretuojami kaip formalios
kalbos konstrukcijos. Darbe pateikiamos idėjos, kurios ga li būti panaudotos, vystant formalių kalbų
automatinius generavimo mechanizmus.