## 3 Graph Representation of the IoT Network
### Graph Generation Using a Formal Grammar  
Formally, the graph representing the IoT we will be defined as follows:  
**Definition 1**. : _A graph grammar \(\Omega\) is a tuple:_  
\[\Omega=(\Sigma_{\Omega},\Gamma_{\Omega},\Delta_{\Omega},\Phi_{\Omega},S_{ \Omega},\Pi_{\Omega})\]  
_where the following definitions apply:_  
* \(\Sigma_{\Omega}\) _is the set of node labels;_
* \(\Delta_{\Omega}\subset\Sigma_{\Omega}\) _is the set of terminal node labels (nonterminal nodes are working elements);_
* \(\Gamma_{\Omega}\) _is the set of edge labels;_
* \(\Phi_{\Omega}\) _is the set of transformation rules;_
* \(S_{\Omega}\) _is the starting graph;_
* \(\Pi_{\Omega}\) _is the graph grammar validation condition which verifies the current state of the graph._  
We use \(\Pi_{\Omega}\) as the validation condition of the graph grammar because sometimes it is necessary to execute a sequence of transformations, and some of the intermediate states may not form a correct graph. With \(L(\Omega)\), we denote the language defined by the graph grammar \(\Omega\) (i.e., \(S_{\Omega}\in L(\Omega)\)), and for any \(H\in L(\Omega)\) and any \(P\in\Phi_{\Omega}\), then \(P(H)\in L(\Omega)\). The first validation condition formalizes the informal assumption that the final graph may not have any nonterminal nodes (i.e., \(\forall H\in L(\Omega)\) and \(\forall\upsilon\in V_{H}:label(v)\in\Sigma_{\Omega}-\Delta_{\Omega}\)). Formally, using the sensors defined earlier, \(\Sigma_{\Omega}=\{TS,HS,LS,MS,CE,LC,TC\}\). The relation between the nodes is represented by the edges, such as in the following examples:  
* A node TC should be associated with a node labeled CE by an edge labeled _as_ (where the temperature sensor is associated with the calculation element);
* A node MS should be associated with a node labeled LC by an edge labeled _lc_ (where lighting control is associated with the movement sensor). Formally, \(\Gamma_{\Omega}=\{as,lc,in\dots\}\). Figure 2: Global capability of IoT network. **Definition 2**. : _A capability in a graph \(G\) is a triple \((a,H,\mathrm{Y})\) where the following apply:_  
* \(H\subseteq G\) _is a subgraph_ \(G\)_;_
* \(a\in H\) _is a node in graph_ \(H\)_;_
* \(\mathrm{Y}\) _is a predicate over graph_ \(H\)_'s structure and attribute values._  
In the context of maintaining graph isomorphism and computational problems, we attribute elementary capabilities to a specific node, denoted as \(a\), within the graph. Based on the aforementioned definition, an elementary capability is represented as a triple \((a,\{a\},\{A\},\mathrm{Y})\), where \"a\" signifies the node associated with the capability, [a] represents the ability to perform an action and \(\mathrm{Y}\) denotes the parameters required to execute or validate the action. The parameters of the action are linked to the graph's node, which is defined by an appropriate grammar. A global capability, on the other hand, encompasses a combination of elementary capabilities, predicates and additional parameters associated with the entire graph. The complete graph represents the global capability. A predicate is a logical formula that utilizes the graph's definition as its input parameter. It is defined externally to the graph but forms an integral part of the definition of the graph's global capabilities. The inclusion of a root element within the graph is essential to enhance the effectiveness of graph validation. The correctness of the proper graph generation is ensured by the graph transformation rules defined in a graph grammar. A single transformation rule that transforms one graph into another one is denoted as \(\pi\in\Phi_{\Omega}\) (a set of transformation rules). Each \(\pi\) is denoted as a set of two graphs: _lhs_ and _rls_.