Distinguished representatives for equivalent labelled stratified graphs and applications (Q1885822)

The concept of labelled stratified graph (LSG) was introduced by \textit{N. Ţăndăreanu} [Knowledge Inform. Syst. 2, 438--460 (2000; Zbl 1002.68616)] in connection with knowledge bases with output. A labelled graph can be defined as a hypergraph \(G\) on a set \(S\) of nodes, together with a set \(L_0\) of labels assigned to the arcs. The set of all arcs with the same label is viewed as a binary relation on \(S\); let \(T_0\) be the set of all those relations. Then the labelled graph is is formally defined as \(G=(S,L_0,T_0,f_0)\), where \(f_0:S\rightarrow T_0\) is the labelling function. Let Rel\((S)\) be the set of binary relations on \(S\) and \(R(\text{prod}_S)\) the set of those partially defined functions \(u\) from Rel\((S)^2\) to Rel\((S)\) which have the property \[ (\rho_1,\rho_2)\in \text{dom}(u)\Rightarrow u(\rho_1,\rho_2)=\rho_1\circ\rho_2\neq 0. \] An LSG over a labelled graph \(G\) is a tuple \((G,L,T,u,f)\), where \(G\) is a labelled graph, \(u\in R(\text{prod}_S)\) and the sets \(L\supseteq L_0\), \(T\supseteq T_0\) and the extension \(f\) of \(f_0\) satisfy certain conditions. The present paper introduces the set Strat\((G)\) of all LGSs over \(G\), a partial order \(\leq\) and an equivalence relation \(\cong\) on Strat\((G)\) and a partial order \(\sqsubseteq\) on the factor set Strat\((G)/\cong\), which becomes a join semilattice with greatest element. For each equivalence class \(C\) in the factor set, the least element of \((C,\leq)\) is called the distinguished representative of \(C\). The distinguished representatives of the join of two classes and of the greatest equivalence class are calculated and applied to a conveyance problem and to attribute graphs, respectively. Several open problems are briefly exposed in the last section.