Distinguished representatives for equivalent labelled stratified graphs and applications Original Research Article

The concept of labelled stratified graph (LSG) was introduced in Ţăndăreanu (Knowledge Inform. Syst. 2(4) (2000) 438) in connection with that of knowledge base with output (KBO). The aim of this paper is to present a distinct facet of this concept. We prove several algebraic properties for LSGs and we conclude that a LSG can be used independently of a KBO. In order to realize this aim we define a partial order image on the set image of all LSGs over a labelled graph G, an equivalence relation image on image and a partial order image on the factor set image. The set image endowed with image becomes a join semilattice with greatest element. Each equivalence class image contains an unique LSG, which is named distinguished representative of C. This is the least element of image. Particularly we obtain the distinguished representative for the supremum of two classes (DRS) and the greatest distinguished LSG (the least LSG of the greatest element of image, denoted GD). Two applications are presented, one for DRS and one for GD. Several opens problems are briefly exposed in the last section.