Awali
Another Weighted Automata library
Enumerations | Functions | Variables
Options

Contains all enums describing the different algorithms to execute a transformation, and the option mechanism used at dyn layer. More...

Enumerations

enum  awali::direction_t { awali::FORWARD, awali::BACKWARD }
 Used in some algorithms in which one may considers transitions forward or backwards. More...
 
enum  awali::exp_to_aut_algo_t {
  awali::GLUSHKOV, awali::STANDARD =GLUSHKOV, awali::DERIVED_TERM, awali::BREAKING_DERIVED_TERM,
  awali::BREAKING = BREAKING_DERIVED_TERM, awali::THOMPSON, awali::COMPACT_THOMPSON, awali::WEIGHTED_THOMPSON,
  awali::STANDARD_AND_QUOTIENT
}
 The different algorithms for transforming an expression into an automaton. More...
 
enum  awali::history_kind_t {
  awali::history_kind_t::SINGLE, awali::history_kind_t::TUPLE, awali::history_kind_t::RATEXP, awali::history_kind_t::STRING,
  awali::history_kind_t::NO_HISTORY, awali::history_kind_t::PARTITION
}
 The different kinds of history. More...
 
enum  awali::io_format_t {
  awali::FSM_JSON_V1 = 0x101, awali::JSON = FSM_JSON_V1, awali::TEXT = 0, awali::FADO,
  awali::GRAIL, awali::DOT, awali::PDF, awali::SVG,
  awali::FSM_JSON_V0
}
 The different format for input/output of automata and expressions. More...
 
enum  awali::layout_t { awali::VERTICAL, awali::HORIZONTAL, awali::CIRCULAR }
 The different layout that we may pass to program dot to compute geometry of automata. More...
 
enum  awali::minim_algo_t { awali::DETERMINIZE_QUOTIENT, awali::BRZOZOWSKI }
 The different algorithms for computing the minimal automaton. More...
 
enum  awali::quotient_algo_t { awali::MOORE, awali::HOPCROFT }
 The diffĂ©rent algorithms for computing the minimal quotient. More...
 
enum  awali::star_status_t { awali::STARRABLE, awali::NON_STARRABLE, awali::TOPS, awali::ABSVAL }
 The different behaviours a weightset may have with respect to the star. More...
 
enum  awali::state_elim_order_t { awali::MIN_INOUT_DEGREE, awali::MIN_ID, awali::ID_ORDER =MIN_ID }
 The different strategies for choosing which state to eliminate first when transforming an automaton into an expression. More...
 

Functions

bool awali::is_json_like (io_format_t format)
 
bool awali::is_true_json (io_format_t format)
 

Variables

internal::option_t< bool > awali::dyn::AUTOPROMOTE
 Option used to specify whether to automatically promote an automaton (or automata) if its context does not allow to perform an operation, but a more general context allows it. More...
 
internal::option_t< direction_tawali::dyn::DIRECTION
 Option used when there are "forward" or "backward" strategies. More...
 
internal::option_t< exp_to_aut_algo_tawali::dyn::EXP_TO_AUT_ALGO
 Option used when a rational expression is computed from an automaton. More...
 
internal::option_t< bool > awali::dyn::IN_PLACE
 Option used when an algorithm may be done in place. More...
 
internal::option_t< io_format_tawali::dyn::IO_FORMAT
 Option used to specify an input or output format. More...
 
internal::option_t< bool > awali::dyn::KEEP_HISTORY
 Option used to specify whether to keep the history of states. More...
 
internal::option_t< layout_tawali::dyn::LAYOUT
 Option used when displaying an automaton with dot. More...
 
internal::option_t< minim_algo_tawali::dyn::MINIM_ALGO
 Option used to specify the algorithm to use for computing minimization. More...
 
internal::option_t< bool > awali::dyn::PREPOST_PARADIGM
 Option used to specify whether to consider initial/final status of states as normal transitions. More...
 
internal::option_t< bool > awali::dyn::PRUNE
 Option used when in the process of the algorithm, some elements (e.g. More...
 
internal::option_t< quotient_algo_tawali::dyn::QUOTIENT_ALGO
 Option used to specify the algorithm to use for computing quotients. More...
 
internal::option_t< bool > awali::dyn::SAFE
 Option used when performing some test is costly or impossible. More...
 
internal::option_t< state_elim_order_tawali::dyn::STATE_ELIM_ORDER
 Option used to specify the order in which states should be eliminated (typically in functions such as awali::dyn::exp_to_aut). More...
 

Detailed Description

Contains all enums describing the different algorithms to execute a transformation, and the option mechanism used at dyn layer.

The options mechanism

The options mechanism emulates the named arguments paradigm that is included in more recent languages.

Example
options_t opts = {IN_PLACE = true, QUOTIENT_ALGO = MOORE};
opts += {MINIM_ALGO = 42} // This fails at runtime: a type check is done
opts += {MINIM_ALGO = BRZOZOWSKI } // This succeeds and is the prefered way
opts += {MINIM_ALGO = "brzozowski"} // This succeeds but should only be used
// if a std::string is given from an
// external source.
opts += {MINIM_ALGO = "brzzwski"} // This fails with a std::domain_error

Enumeration Type Documentation

◆ direction_t

Used in some algorithms in which one may considers transitions forward or backwards.

Enumerator
FORWARD 
BACKWARD 

◆ exp_to_aut_algo_t

The different algorithms for transforming an expression into an automaton.

Enumerator
GLUSHKOV 

This automaton without epsilon-transitions is incrementally built from the expression.

It is isomorphic to the Position automaton. It has n+1 states, where n is the litteral length of the expression, i.e. the number of letters.

STANDARD 

Alias to GLUSHKOV.

DERIVED_TERM 

Also known as Partial derived terms.

Described by Antomirov for Boolean semrings; extension to weighted automata by Lombardy and Sakarovitch. It is a quotient of the Standard automaton.

BREAKING_DERIVED_TERM 

A variant of the Derived term automaton where left factors of expressions which are sums are "broken".

BREAKING 

Alias to BREAKING_DERIVED_TERM.

THOMPSON 

The classical Thompson automaton, with epsilon-transitions.

It has exactly 2n states, where n is the size of the expressions (letters + operators). The maximal out- and in-degree of every state is 2; if it is 2, the labels of transitions are epsilon. It has one and only one initial (resp. final) state with no incoming (resp. outgoing) transition.

COMPACT_THOMPSON 

A variant of the Thompson automaton, with fewer states.

WEIGHTED_THOMPSON 

A variant of the Thompson automaton, with no circuit of epsilon-transitions; in this variant, the initial state may be another final state.

STANDARD_AND_QUOTIENT 

Standard automaton followed by quotient.

◆ history_kind_t

enum awali::history_kind_t
strong

The different kinds of history.

This class represents the different kinds of history a state may have. For instance, if an automaton is the result of a determinisation, then the history of a state is of kind PARTITION.

Enumerator
SINGLE 

The states comes from a single state.

TUPLE 

The states comes from a tuple of state.

It is typically, the history kind of an automaton resulting from a product of automata.

RATEXP 

The state comes from a rational expression.

STRING 

The state history is expressed directy as a string.

It is typically the history kind typically used when no other kind is proper.

NO_HISTORY 

The state has no history.

PARTITION 

The state is a set of states of another automaton.

It is typically the history kind of an automaton resulting from a determinization process.

◆ io_format_t

The different format for input/output of automata and expressions.

Enumerator
FSM_JSON_V1 

The native Awali format.

JSON 

The current Awali format.

TEXT 

Used for pure-text representation.

Rational expression only.

FADO 

FADO format.

Boolean automata only.

GRAIL 

Grail format.

Boolean automata only.

DOT 

Format used by graphviz.

Output only.

PDF 

A pdf image is produced by graphviz.

Output only.

SVG 

Image produced by graphviz.

Output only.

FSM_JSON_V0 

Deprecated Awali and Vaucanson-R format.


Warning: this format does not follow Json syntax.
Input only.

◆ layout_t

The different layout that we may pass to program dot to compute geometry of automata.

Enumerator
VERTICAL 

Spring left to right layout.

HORIZONTAL 

Spring top down layout.

CIRCULAR 

Circular layout.

◆ minim_algo_t

The different algorithms for computing the minimal automaton.

Enumerator
DETERMINIZE_QUOTIENT 

Determinizes, then computes the minimal quotient (see quotient_algo_t).

BRZOZOWSKI 

Transposes, then determinizes, then transposes, then determinizes.

◆ quotient_algo_t

The différent algorithms for computing the minimal quotient.

Enumerator
MOORE 
HOPCROFT 

◆ star_status_t

The different behaviours a weightset may have with respect to the star.

Enumerator
STARRABLE 

The star of every element exists.

NON_STARRABLE 
TOPS 
ABSVAL 

◆ state_elim_order_t

The different strategies for choosing which state to eliminate first when transforming an automaton into an expression.

Enumerator
MIN_INOUT_DEGREE 

States are eliminated by increasing in-out degree.

The in-out degree of a state is the product of the number of incoming transition by the number of outgoing transitions.

MIN_ID 

States are eliminated by increasing id number (that is, in an arbitrary order).

ID_ORDER 

Alias to MIN_ID.

Function Documentation

◆ is_json_like()

bool awali::is_json_like ( io_format_t  format)

◆ is_true_json()

bool awali::is_true_json ( io_format_t  format)

Variable Documentation

◆ AUTOPROMOTE

internal::option_t< bool > awali::dyn::AUTOPROMOTE

Option used to specify whether to automatically promote an automaton (or automata) if its context does not allow to perform an operation, but a more general context allows it.

Used typically in functions such as awali::dyn::product. Defaults to false.

Beware
Promotion always requires a full copy of the automaton.

◆ DIRECTION

internal::option_t< direction_t > awali::dyn::DIRECTION

Option used when there are "forward" or "backward" strategies.

Defaults to BACKWARD.

◆ EXP_TO_AUT_ALGO

internal::option_t< exp_to_aut_algo_t > awali::dyn::EXP_TO_AUT_ALGO

Option used when a rational expression is computed from an automaton.

Defaults to STANDARD_AND_QUOTIENT.

◆ IN_PLACE

internal::option_t< bool > awali::dyn::IN_PLACE

Option used when an algorithm may be done in place.

If set, the automaton is modified (and returned), if unset, the function copies input automaton before executing the algorithm.

Defaults to false.

◆ IO_FORMAT

internal::option_t< io_format_t > awali::dyn::IO_FORMAT

Option used to specify an input or output format.

Defaults to JSON.

◆ KEEP_HISTORY

internal::option_t< bool > awali::dyn::KEEP_HISTORY

Option used to specify whether to keep the history of states.

  • In algorithms, if set to true, each state in the resulting automaton is endowed with its history (e.g., with a set of states for determinization).
  • In display functions, if set to true, the history will be shown in states (instead of names). Defaults to true.
See also
The enum history_kind_t that gives the different kinds of history a state may have.

◆ LAYOUT

internal::option_t< layout_t > awali::dyn::LAYOUT

Option used when displaying an automaton with dot.

Defaults to HORIZONTAL.

◆ MINIM_ALGO

internal::option_t< minim_algo_t > awali::dyn::MINIM_ALGO

Option used to specify the algorithm to use for computing minimization.

Defaults to DETERMINIZE_QUOTIENT; note that it makes QUOTIENT_ALGO meaningful.

◆ PREPOST_PARADIGM

internal::option_t< bool > awali::dyn::PREPOST_PARADIGM

Option used to specify whether to consider initial/final status of states as normal transitions.

In this paradigm:

  • There is one preinitial state (see abstract_automaton_t::pre); it has no incoming transition, and is the source of a transition coming in each initial state.
  • There is one postfinal state (see abstract_automaton_t::post); it has no outgoing transition, and is the destination of one transition going out of each final state.

If set to true, some functions will return these additionals states and transitions. Defaults to false.

See also
abstract_automaton_t::incoming, abstract_automaton_t::outgoing, abstract_automaton_t::states, abstract_automaton_t::transitions,

◆ PRUNE

internal::option_t< bool > awali::dyn::PRUNE

Option used when in the process of the algorithm, some elements (e.g.

states) may be found to be useless. If set to true, these elements are deleted. ( Setting this to false is mostly useful for pedagogical purpose.)

Defaults to true.

◆ QUOTIENT_ALGO

internal::option_t< quotient_algo_t > awali::dyn::QUOTIENT_ALGO

Option used to specify the algorithm to use for computing quotients.

Note that it is also used by default when making a minimization.

Defaults to MOORE.

◆ SAFE

internal::option_t< bool > awali::dyn::SAFE

Option used when performing some test is costly or impossible.

If set to false the program will assume the precondition is satisfied. This may result in inconsistent automata or infinite loops.

Defaults to true.

◆ STATE_ELIM_ORDER

internal::option_t< state_elim_order_t > awali::dyn::STATE_ELIM_ORDER

Option used to specify the order in which states should be eliminated (typically in functions such as awali::dyn::exp_to_aut).

Defaults to MIN_INOUT_DEGREE.

awali::MOORE
@ MOORE
Definition: enums.hh:65
awali::dyn::QUOTIENT_ALGO
internal::option_t< quotient_algo_t > QUOTIENT_ALGO
Option used to specify the algorithm to use for computing quotients.
awali::dyn::MINIM_ALGO
internal::option_t< minim_algo_t > MINIM_ALGO
Option used to specify the algorithm to use for computing minimization.
awali::dyn::IN_PLACE
internal::option_t< bool > IN_PLACE
Option used when an algorithm may be done in place.
awali::BRZOZOWSKI
@ BRZOZOWSKI
Transposes, then determinizes, then transposes, then determinizes.
Definition: enums.hh:59