next up previous
Next: The Deterministic Automaton Classes Up: Complexity values Previous: Complexity values

Notations

In the tables, if X is a set, we use X as a shortcut for |X| and c for $\vert c(q)\vert, q \in Q$. Space complexity is expressed in bytes and $\sigma$ (resp. q) stands for the number of bytes needed to designate an element of $\Sigma$ (resp. Q). p is the size of a pointer. Values between braces designate time complexity when reallocation is needed.
   
Figure 1: ASTL structure
Representations Space Complexities
Matrix $Q \Sigma q$
Map Adjacency List $ \Delta (\sigma + 4p) + 3pQ $
Compact $\Delta (\sigma + q)$
Hash Table $\Delta (\sigma + 2q)$
Arrays with Binary Search $\Delta (2p + \sigma)$
Arrays with Move-To-Front $\Delta (2p + \sigma)$
Arrays with Transpose $\Delta (2p + \sigma)$


Space complexities of automaton containers

 
  Matrix Adj. List Compact Hash Bin. Search Arrays [*]
Ins/del state 1 (Q) 1 No 1 1 1
Ins/del trans 1 log c No 1 ($\Delta$) c c
Access trans 1 log c 1 1 log c c


Time complexities of automaton containers

next up previous
Next: The Deterministic Automaton Classes Up: Complexity values Previous: Complexity values
Vincent Lemaout
12/9/1997