next up previous
Next: Structure of the Library Up: Generic programming on automata Previous: Introduction

Notations

We recall here our definition of an automaton :
We aim to design code with efficiency and genericity in mind, thus we add to the usual abstract type automaton two sets T and $\tau$ in order to associate any kind of information (tags) to the states.
Let $A(\Sigma, Q, I, F, \delta, T, \tau)$ be a 7-uple of finite sets defined as follow :
$\Sigma$ the alphabet
Q a set of states
$I \subset Q$ a set of initial states
$F \subset Q$ a set of final states
$\Delta \subset Q \times \Sigma \times Q$ a set of transitions
T a set of tags
$\tau \subset Q \times T$ a relation between states and tags
Let $c(q), q \in Q$ be the context of a state :
$c(q) = \{ a \in
\Sigma \:\vert\: \exists p \in Q \wedge (q, a, p) \in \Delta \}$, that is the set of the letters on the outgoing edges of a state q.
We define P(X) as the power-set of a set X and |X| as its number of elements.
Let's view $\Delta$ as two distinct transition functions $\delta_{1}$ and $\delta_{2}$according to the most frequent operations needed on an automaton:

$\delta_{1} \: : \: Q \times \Sigma \rightarrow P(Q) $
$\delta_{2} \: : \: Q \rightarrow P(\Sigma \times Q)$



These two functions are the corner stone of the library. To put it formally, everything comes down to manipulate a set of triples in $Q \times \Sigma \times Q$ and two subsets of Q.

Besides these definitions, we introduce the notion of occupation ratio defined as follow:

\begin{displaymath}
\alpha(q) = \frac{\vert c(q)\vert}{\vert\Sigma\vert},\:q \in Q\end{displaymath}

and the average value, $\overline{\alpha}$ as :

\begin{displaymath}
\overline{\alpha} = \frac{1}{\vert Q\vert} \sum_{q \in Q} \alpha(q)\end{displaymath}

This value is crucial in estimating which container fits better when memory space is limited. Intuitively, the closer $\overline{\alpha}$ gets to 0, the emptier the transition matrix will be.


next up previous
Next: Structure of the Library Up: Generic programming on automata Previous: Introduction
Vincent Lemaout
12/9/1997