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 associating each vertex with some finite set of atomic propositions with or (ii) with input and output words connected to the edge relation E with with as a finite input alphabet and as a finite output alphabet.

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

with

Remark: We are using here as well as for convinience instead of and ; as well as allows either individual elements but also strings, i.e. words w with .

Gerd Doeben-Henisch 2010-03-03