Graph extended with Input-Output and Labels

Graphs will often be used as visual representtions of automata (see section about automata). In connection with automata it is very common to extend the automata definitions by input and output words connected to transitions as well as properties connected to states. To include this in the definition of a graph one has to extend the basic definition of a graph as follows:

A graph G can be extended (i) with properties (:= atomic propositions) AP with a labelling function l with $l : V \longrightarrow 2^{AP}$ associating each vertex $v \in V$ with some finite set $P$ of atomic propositions with $P \in 2^{AP}$ or (ii) with input and output words connected to the edge relation E with $E \subseteq V \times \Sigma^{*} \times \Xi^{*} \times V$ with $\Sigma$ as a finite input alphabet and $\Xi$ as a finite output alphabet.

The structure of a labelled transition graph has then to be given as

$$\langle V,E,\Sigma,\Xi, l,AP \rangle$$

with

1. $E \subseteq V \times \Sigma^{*} \times \Xi^{*} \times V$
2. $l : V \longrightarrow 2^{AP}$

Remark: We are using here $\Sigma^{*}$ as well as $\Xi^{*}$ for convinience instead of $\Sigma$ and $\Xi$; $\Sigma^{*}$ as well as $\Xi^{*}$ allows either individual elements but also strings, i.e. words w with $\mid w\mid \geq 1$.