A definition for complexity in the context of semantification of workflows is not easy to find or create. "Complexity" is a broad term used in different contexts and needs disambiguation.

Let's start with a simple naive example: a simple versus a complex relationship. We would assume that simplicity correlates with small size and complexity with large size. The more people (nodes) involved in a relation the more effort it is to keep the state of the network in order. In a knowledgegraph G=(V,E) it might therefore make sense to count the nodes and edges and the depth and breadth of the structure the graph might build (e.g. if it is a tree).

The cost of traversing the network and the benefit of doing so will most likely also influence the complexity.

So a first step in this train of source is: simple relations have few participants, low transaction costs and high transaction benefits. E.g. buying an ice cream in summer might lead to a good relation to the ice cream vendor if the price is low and the ice most tasty and the ice cream parlor was only a walk away on a hot summer day - you did not have to wait in line and the person selling was kind to you (and of course so have you been).

Formally ... Let's test whether an AI can derive a proper complexity formalization for us ... give me a formulazation and explanation a) in mediawiki markup b) in latex

Prompt

For my PhD thesis i would like to test ... (above text) ...

Complexity Formalization for Semantification of Workflows

Let G = (V, E) be a knowledge graph where V is the set of nodes (vertices) and E is the set of edges.

Complexity Measure

We define the complexity C of a workflow as: [math]C = \alpha \cdot |V| + \beta \cdot |E| + \gamma \cdot d + \delta \cdot b + \frac{\epsilon \cdot T_c}{T_b}[/math] Where:

|V| is the number of nodes |E| is the number of edges d is the depth of the graph structure b is the breadth of the graph structure T_c is the transaction cost T_b is the transaction benefit α, β, γ, δ, and ε are weighting factors

\section{Complexity Formalization for Semantification of Workflows}

Let $G = (V, E)$ be a knowledge graph where $V$ is the set of nodes (vertices) and $E$ is the set of edges.

\subsection{Complexity Measure}

We define the complexity $C$ of a workflow as:

\begin{equation}
C = \alpha \cdot |V| + \beta \cdot |E| + \gamma \cdot d + \delta \cdot b + \frac{\epsilon \cdot T_c}{T_b}
\end{equation}

Where:
\begin{itemize}
    \item $|V|$ is the number of nodes
    \item $|E|$ is the number of edges
    \item $d$ is the depth of the graph structure
    \item $b$ is the breadth of the graph structure
    \item $T_c$ is the transaction cost
    \item $T_b$ is the transaction benefit
    \item $\alpha, \beta, \gamma, \delta,$ and $\epsilon$ are weighting factors
\end{itemize}

\subsection{Interpretation}

\begin{itemize}
    \item The first four terms ($|V|, |E|, d, b$) represent the structural complexity of the workflow.
    \item The last term ($T_c / T_b$) represents the efficiency of the workflow.
    \item Lower values of $C$ indicate simpler, more efficient workflows.
    \item Higher values of $C$ indicate more complex, potentially less efficient workflows.
\end{itemize}

\subsection{Example: Ice Cream Purchase}

Consider a simple ice cream purchase scenario:

\begin{itemize}
    \item $|V| = 2$ (customer, vendor)
    \item $|E| = 1$ (transaction)
    \item $d = 1$ (single-level interaction)
    \item $b = 2$ (two parties involved)
    \item $T_c$ is low (short distance, no waiting, kind interaction)
    \item $T_b$ is high (tasty ice cream on a hot day)
\end{itemize}

This scenario would result in a low complexity value $C$, indicating a simple and efficient workflow.

⚠️ LLM-generated content notice: Parts of this page may have been created or edited with the assistance of a large language model (LLM). The prompts that have been used might be on the page itself, the discussion page or in straight forward cases the prompt was just "Write a mediawiki page on X" with X being the page name. While the content has been reviewed it might still not be accurate or error-free.

Interpretation

The first four terms (|V|, |E|, d, b) represent the structural complexity of the workflow. The last term (T_c / T_b) represents the efficiency of the workflow. Lower values of C indicate simpler, more efficient workflows. Higher values of C indicate more complex, potentially less efficient workflows.

Example: Ice Cream Purchase

Consider a simple ice cream purchase scenario:

|V| = 2 (customer, vendor) |E| = 1 (transaction) d = 1 (single-level interaction) b = 2 (two parties involved) T_c is low (short distance, no waiting, kind interaction) T_b is high (tasty ice cream on a hot day)

This scenario would result in a low complexity value C, indicating a simple and efficient workflow.

Literature

Complexity

Contents