TaPAS  0.2
Typedefs | Functions
Shared Automata

Typedefs

typedef struct sataf_sa_st sataf_sa
 Type for the data structure encoding Shared Automata.
 

Functions

sataf_sasataf_sa_create_one (uint32_t alphabet_size)
 Create the unique SA recognizing all words on an alphabet of size alphabet_size. More...
 
sataf_sasataf_sa_create_zero (uint32_t alphabet_size)
 Create the unique SA recognizing no words on an alphabet of size alphabet_size. More...
 
static sataf_sasataf_sa_add_reference (sataf_sa *sa)
 Add one the counter of references to sa. More...
 
static void sataf_sa_del_reference (sataf_sa *sa)
 Decrement the number of references to sa. More...
 
sataf_sasataf_sa_find_or_add (sataf_ea *ea, sataf_sa **bind_sa, uint32_t *bind_init)
 Look-up in the SA-unicity-table for a shared automaton defined by ea and the binding function (bind_sa, bind_init). More...
 
void sataf_sa_display_as_dot (sataf_sa *sa, ccl_log_type log, int marked_state, const char **alphabet, int with_info)
 Display the shared automaton sa in DOT file format. More...
 
void sataf_sa_display_scc_as_dot (sataf_sa *sa, ccl_log_type log)
 Display the graph of SCCs composing the shared automaton sa. More...
 
static int sataf_sa_is_zero (sataf_sa *sa)
 Return if sa is the shared automaton accepting no word. More...
 
static uint32_t sataf_sa_get_alphabet_size (sataf_sa *sa)
 Return the size of the alphabet. More...
 
static int sataf_sa_is_one (sataf_sa *sa)
 Return if sa is the shared automaton accepting any word. More...
 
static int sataf_sa_is_zero_or_one (sataf_sa *sa)
 Check if sa accepts nothing or accepts nothing. More...
 
void sataf_sa_table_statistics (ccl_log_type log)
 Display internal statistics about the use of SAs. In particular informations related to the unicity table. More...
 

Detailed Description

Function Documentation

static sataf_sa* sataf_sa_add_reference ( sataf_sa sa)
inlinestatic

Add one the counter of references to sa.

Parameters
sathe shared automaton
Precondition
sa != NULL
Returns
sa
sataf_sa* sataf_sa_create_one ( uint32_t  alphabet_size)

Create the unique SA recognizing all words on an alphabet of size alphabet_size.

Parameters
alphabet_sizethe size of the alphabet.
Precondition
alphabet_size > 0
sataf_sa* sataf_sa_create_zero ( uint32_t  alphabet_size)

Create the unique SA recognizing no words on an alphabet of size alphabet_size.

Parameters
alphabet_sizethe size of the alphabet.
Precondition
alphabet_size > 0
static void sataf_sa_del_reference ( sataf_sa sa)
inlinestatic

Decrement the number of references to sa.

When this counter falls to zero the resources allocated to sa are freed.

Parameters
sathe shared automaton
Precondition
sa != NULL
void sataf_sa_display_as_dot ( sataf_sa sa,
ccl_log_type  log,
int  marked_state,
const char **  alphabet,
int  with_info 
)

Display the shared automaton sa in DOT file format.

Each node represents a state of the represented automaton sa i.e. without exit states. Each node is labelled with:

  • a string L@d-s where d is the depth of the SA and s the state in this SA.
  • the address of the SA the node belong to.
  • the address of the EA underlying the SA the node belong to.

A state (typically an initial state) marked_state of the top-level shared automaton sa can be distinguished using different color. If marked_state is negative then all states are displayed in white.

Parameters
sathe displayed SA
logthe CCL output stream
marked_statea differenciated state
alphabetan array of strings used as letters.
Precondition
sa != NULL
See Also
http://www.graphviz.org/
void sataf_sa_display_scc_as_dot ( sataf_sa sa,
ccl_log_type  log 
)

Display the graph of SCCs composing the shared automaton sa.

Each node displayed in the graph represents a SA. Edge between nodes are labelled by integers. An edge $N_1 \stackrel{i}{\longrightarrow} N_2$ indicates there exists an entry in the binding function of $N_1$ yielding into the state i of $N_2$.

Parameters
sathe displayed SA
logthe CCL output stream
Precondition
sa != NULL
sataf_sa* sataf_sa_find_or_add ( sataf_ea ea,
sataf_sa **  bind_sa,
uint32_t *  bind_init 
)

Look-up in the SA-unicity-table for a shared automaton defined by ea and the binding function (bind_sa, bind_init).

The library maintains a unicity table for shared automata. This function looks up in this table for a shared automaton binding each couple of (bind_sa[i], bind_init[i]) to the exit state i of ea.

Parameters
eathe exit automaton of the SA
bind_sathe SAs associated to exit states of ea
bind_initthe initial states associated to exit states of ea
Precondition
ea != NULL && bind_sa != NULL && bind_init != NULL
bind_sa and bind_init must have sataf_ea_get_nb_exits (ea).
Returns
a pointer to the unique SA (ea,bind_sa,bind_init).
static uint32_t sataf_sa_get_alphabet_size ( sataf_sa sa)
inlinestatic

Return the size of the alphabet.

Parameters
sathe considered shared automaton
Precondition
sa != NULL
Returns
the size of the underlying alphabet
static int sataf_sa_is_one ( sataf_sa sa)
inlinestatic

Return if sa is the shared automaton accepting any word.

Parameters
sathe shared automaton
Precondition
sa != NULL
Returns
a non-null value if sa recognize all words.
static int sataf_sa_is_zero ( sataf_sa sa)
inlinestatic

Return if sa is the shared automaton accepting no word.

Parameters
sathe shared automaton
Precondition
sa != NULL
Returns
a non-null value if sa recognize no word.
static int sataf_sa_is_zero_or_one ( sataf_sa sa)
inlinestatic

Check if sa accepts nothing or accepts nothing.

Parameters
sathe shared automaton
Precondition
sa != NULL
Returns
sataf_sa_is_one (sa) || sataf_sa_is_zero (sa)
void sataf_sa_table_statistics ( ccl_log_type  log)

Display internal statistics about the use of SAs. In particular informations related to the unicity table.

Parameters
logthe CCL ouptut stream