Awali
Another Weighted Automata library
Namespaces | Data Structures | Typedefs | Enumerations | Functions | Variables
awali::dyn Namespace Reference

Namespace for the dynamical layer of Awali. More...

Namespaces

 context
 Namespace containing functions to build arbitrary automata context (advanced and mostly undocumented).
 
 deprecated
 
 factory
 Namespace containing what we call factories, that is, functions that generates a member in a family of automata, rational expression or transducer.
 
 internal
 Implementation details of dyn layer (not stable).
 
 lift
 Namespace containing the functions allowing to execute the state elimination algorithm (aut_to_exp) step-by-step; probably will be moved elsewhere in the future.
 
 loading
 Namespace containtaing facilities for on-the-fly compilation.
 

Data Structures

struct  abstract_automaton_t
 Abstract interface listing the services provided by automata at the dynamical layer. More...
 
struct  abstract_context_t
 Abstract interface representing the weightset and labelset of an automaton, a rational expression or a transducer. More...
 
class  abstract_ratexp_t
 Abstract interface for rational expression at the dynamical layer; lists the services provided by automata. More...
 
struct  any_cast_exception
 
struct  any_t
 Structure used to erase the type of labels/weights at the dyn layer. More...
 
class  automaton_t
 An automaton_t is essentially a shared pointer to an abstract_automaton_t, but also contains static functions serving as constructors. More...
 
class  context_t
 Dynamical wrapper for a context, that is a weightset and a labelset. More...
 
class  options_t
 An options_t is a set of optional parameters that is passed on to called functions. More...
 
class  ratexp_t
 Main class for representing rational expresson at the dynamical layer. More...
 
struct  scc_return_t
 
struct  transducer_t
 

Typedefs

using label_t = any_t
 Type for (transition) labels; it is an alias to any_t since its precise type depends on the weightset of manipulated automaton_t or ratexp_t. More...
 
using state_t = unsigned
 Type representing automata states; currently simply identifiers of type unsigned, but this might change in the future. More...
 
using transition_t = unsigned
 Type representing automata transitions; currently simply identifiers of type unsigned, but this might change in the future. More...
 
using weight_t = any_t
 Type for (transition) weights; it is an alias to any_t since the its precise type depends on the weightset of manipulated automaton_t or ratexp_t. More...
 
using word_t = any_t
 Type for words; it is an alias to any_t since the precise type depends on the context (most of the time, it is a std::string). More...
 

Enumerations

enum class  ExpKind {
  ZERO , ONE , ATOM , SUM ,
  PROD , STAR
}
 

Functions

automaton_t accessible (automaton_t aut, options_t opt={})
 Makes aut accessible or returns a copy of the accessible part of aut. More...
 
std::set< state_taccessible_states (automaton_t aut)
 Computes the list of accessible states in aut. More...
 
void add_path (automaton_t aut, state_t p, state_t q, const std::string &s, bool strict_alphabet=true)
 add a subautomaton realizing the series s between states p and q of aut. More...
 
void add_path (automaton_t aut, state_t p, state_t q, ratexp_t exp)
 add a subautomaton realizing the series exp between states p and q of aut. More...
 
automaton_t allow_eps_transition (automaton_t aut, options_t opts={})
 Returns a copy of aut in which epsilon-transitions are allowed. More...
 
automaton_t allow_words (automaton_t aut)
 Returns a copy of aut in which transitions may bear words. More...
 
bool are_equivalent (automaton_t aut1, automaton_t aut2)
 Tests if aut1 and au2 are equivalent. More...
 
bool are_isomorphic (automaton_t aut1, automaton_t aut2)
 Determines if two automata are isomorphic. More...
 
ratexp_t aut_to_exp (automaton_t aut, options_t opts={})
 Computes a rational expression equivalent to aut. More...
 
void change_alphabet (automaton_t aut, const std::string &alphabet)
 Change the alphabet of the automaton. More...
 
void change_int_alphabet (automaton_t aut, int a, int b)
 Change the alphabet of the automaton. More...
 
automaton_t characteristic (automaton_t aut, std::string weightset, options_t opts={})
 Computes the characteristic of aut over weightset. More...
 
automaton_t coaccessible (automaton_t aut, options_t opt={})
 Makes aut coaccessible or returns a copy of the coaccessible part of aut. More...
 
std::set< state_tcoaccessible_states (automaton_t aut)
 Computes the list of coaccessible states in aut. More...
 
automaton_t compact (automaton_t aut)
 In a copy of an automaton aut which allows words as label, compacts each non-branching path into one transition. More...
 
automaton_t complement (automaton_t aut, options_t opts={})
 Complements aut or returns a complemented copy of aut. More...
 
automaton_t complete (automaton_t aut, options_t opts={})
 Completes aut or returns a completed copy of given automaton. More...
 
transducer_t compose (transducer_t tdc1, transducer_t tdc2)
 
automaton_t concatenate (automaton_t aut1, automaton_t aut2, options_t opts={})
 Concatenates aut2 to aut1 or computes a new standard automaton. More...
 
automaton_t condensation (automaton_t aut)
 Computes the condensation of an automaton; it results from reducing each strongly connected component of the original automaton to a single state. More...
 
weight_t constant_term (ratexp_t exp)
 Returns the constant term of exp, that is the weight of epsilon. More...
 
context_t context_words (automaton_t aut)
 
automaton_t copy (automaton_t aut, options_t opts={})
 Makes a deep copy of aut. More...
 
automaton_t coquotient (automaton_t aut, std::vector< std::vector< state_t >> &equiv, options_t opts={})
 Computes the coquotient of an automaton with respect to a given equivalence. More...
 
automaton_t determinize (automaton_t aut, options_t opts={})
 Determinizes an automaton. More...
 
automaton_t domain (transducer_t tdc)
 Returns the automaton corresponding to the second tape of the transducer. More...
 
automaton_t draw_exp (ratexp_t exp)
 Computes a tree-like automaton representing expression exp. More...
 
std::map< any_t, weight_tenumerate (automaton_t aut, unsigned max)
 Gives the weight associated with each word shorter than max by aut. More...
 
weight_t eval (automaton_t aut, any_t word)
 Computes the weight associated with word by aut. More...
 
automaton_t eval_tdc (automaton_t aut, transducer_t tdc)
 
ratexp_t eval_word (transducer_t tdc, const std::string &word)
 
automaton_t exp_to_aut (ratexp_t ratexp, options_t opts={})
 Computes an automaton equivalent to ratexp. More...
 
ratexp_t expand (ratexp_t exp)
 Expands a rational expression. More...
 
automaton_t factor (automaton_t aut, options_t opts={})
 Computes an automaton accepting all factors of words accepted by aut; function will modify aut or not depending on given opts. More...
 
automaton_t image (transducer_t tdc)
 Returns the automaton corresponding to the second tape of the transducer. More...
 
transducer_t images (transducer_t tdc)
 Projects out the very first tape of the transducer. More...
 
automaton_t infiltration (automaton_t aut1, automaton_t aut2, options_t opts={})
 Computes the infiltration product of aut1 and aut2. More...
 
transducer_t inverse (transducer_t tdc)
 
bool is_accessible (automaton_t aut)
 Tests whether every state of the automaton is accessible. More...
 
bool is_ambiguous (automaton_t aut)
 Tests whether an automaton is ambiguous. More...
 
bool is_coaccessible (automaton_t aut)
 Tests whether every state of aut is coaccessible. More...
 
bool is_complete (automaton_t aut)
 Tests whether an automaton is complete. More...
 
bool is_congruence (automaton_t aut, std::vector< std::vector< state_t >> &equiv)
 Check whether an equivalence is a congruence. More...
 
bool is_deterministic (automaton_t aut)
 Tests whether an automaton is deterministic. More...
 
bool is_empty (automaton_t aut)
 Tests whether the automaton has no state. More...
 
bool is_functional (transducer_t tdc)
 Tests whether tdc is functional. More...
 
bool is_of_finite_image (automaton_t tdc, unsigned i=0)
 
bool is_promotable (const std::string &src_ws, const std::string &dest_ws)
 Tests whether a promotion is possible from one weightset to the other one. More...
 
bool is_proper (automaton_t aut)
 Tests whether an automaton has epsilon-transitions. More...
 
bool is_realtime (transducer_t tdc)
 
bool is_sequential (automaton_t aut)
 Tests whether an automaton is sequential. More...
 
bool is_standard (automaton_t aut)
 Tests whether aut is standard. More...
 
bool is_synchronizable (transducer_t tdc)
 
bool is_trim (automaton_t aut)
 Tests whether aut is trim. More...
 
bool is_useless (automaton_t aut)
 Tests whether the automaton has useful states. More...
 
bool is_valid (automaton_t aut)
 Tests whether epsilon removal is possible in aut. More...
 
bool is_valid (ratexp_t exp)
 Tests whether exp is valid that is, if every monomial in the series it represents is properly weighted. More...
 
automaton_t left_mult (automaton_t aut, weight_t w, options_t opts={})
 Produces an automaton that associates with every word the weight (w * x), where x is the weight associated with this word in aut. More...
 
automaton_t left_reduce (automaton_t aut)
 
automaton_t letterize (automaton_t aut)
 
automaton_t letterize_tape (automaton_t tdc, unsigned i=1)
 
automaton_t load (const std::string &path, options_t opts={})
 Loads an automaton from file pointed by path. More...
 
ratexp_t load_exp (const std::string &filepath)
 Loads a ratexp_t from file filepath More...
 
context_t make_context_with_another_semiring (context_t ctx, const std::string &ws)
 Computes a context with the same labelset as ctx and the weightset ws. More...
 
automaton_t min_coquotient (automaton_t aut, options_t opts={})
 Computes the minimal coquotient of aut. More...
 
automaton_t min_quotient (automaton_t aut, options_t opts={})
 Computes the minimal quotient of aut. More...
 
automaton_t minimal_automaton (automaton_t aut, options_t opts={})
 Computes the minimal complete deterministic automaton of the language accepted by aut. More...
 
automaton_t minimal_automaton (ratexp_t exp, options_t opts={})
 Computes the minimal complete deterministic automaton of the language of exp. More...
 
size_t num_accessible_states (automaton_t aut)
 Computes the number of accessible states in aut. More...
 
size_t num_coaccessible_states (automaton_t aut)
 Computes the number of coaccessible states in aut. More...
 
std::ostream & operator<< (std::ostream &o, automaton_t aut)
 
std::ostream & operator<< (std::ostream &o, const dyn::any_t &a)
 
internal::formatted_ostream operator<< (std::ostream &o, io_format_t const fmt)
 
std::ostream & operator<< (std::ostream &o, ratexp_t e)
 
std::ostream & operator<< (std::ostream &o, transducer_t aut)
 
std::istream & operator>> (std::istream &i, automaton_t &aut)
 
internal::formatted_istream operator>> (std::istream &i, io_format_t const fmt)
 
automaton_t parse_automaton (json_ast_t ast)
 
automaton_t parse_automaton (std::istream &in, options_t opts={})
 Parse an automaton from. More...
 
ratexp_t parse_ratexp (json_ast_t ast)
 
ratexp_t parse_ratexp (std::istream &i)
 
transducer_t partial_identity (automaton_t aut)
 
void pdfdisplay (automaton_t aut, options_t opts={})
 Computes geometry of aut with program dot and displays with a pdf-viewer. More...
 
automaton_t power (automaton_t aut, unsigned int n)
 Build the n -th power of aut. More...
 
automaton_t prefix (automaton_t aut, options_t opts={})
 Computes an automaton accepting all prefixes of words accepted by aut; function will modify aut or not depending on given opts. More...
 
automaton_t product (automaton_t aut1, automaton_t aut2, options_t opts={})
 Computes the classical product of aut1 and aut2. More...
 
automaton_t projection (transducer_t tdc, unsigned i)
 Projects tdc on the tape i. More...
 
automaton_t promote_automaton (automaton_t aut, const std::string &ws, options_t opts={})
 Computes a new automaton with the specified weightset. More...
 
automaton_t proper (automaton_t aut, options_t opts={})
 Removes epsilon-transitions in aut or returns a new automaton equivalent to aut that has no epsilon-transition. More...
 
std::ostream & put (automaton_t aut, std::ostream &o, options_t opts={})
 Write aut to output stream o. More...
 
std::ostream & put (ratexp_t aut, std::ostream &o, options_t opts={})
 
automaton_t quotient (automaton_t aut, std::vector< std::vector< state_t >> &equiv, options_t opts={})
 Computes the quotient of an automaton with respect to a given equivalence. More...
 
transducer_t realtime (transducer_t tdc)
 
automaton_t reduce (automaton_t aut)
 Reduces an automaton. More...
 
automaton_t right_mult (automaton_t aut, weight_t w, options_t opts={})
 Produces an automaton that associates with every word the weight (x * w), where x is the weight associated with this word in aut. More...
 
automaton_t right_reduce (automaton_t aut)
 Simpy calls transpose, left_reduce, transpose. More...
 
void save (const automaton_t aut, const std::string &path, options_t opts={})
 Writes aut to file pointed by path. More...
 
std::vector< state_tscc_of (automaton_t aut, state_t s)
 Returns the strongly connected component of a state. More...
 
void set_error_stream (std::ostream &o)
 Setter for the error_stream of the dynamical layer. More...
 
void set_warning_stream (std::ostream &o)
 Setter for the warning_stream of the dynamical layer. More...
 
std::map< any_t, weight_tshortest (automaton_t aut, unsigned max)
 Gives the shortest , returns an empty map if no such word is shorter than max. More...
 
automaton_t shuffle (automaton_t aut1, automaton_t aut2, options_t opts={})
 Computes the shuffle product of aut1 and aut2. More...
 
automaton_t standard (automaton_t aut, options_t opts={})
 Makes aut standard or return a new standard automaton equivalent to aut. More...
 
automaton_t star (automaton_t aut, options_t opts={})
 Builds a standard automaton that recognizes the star of the language of aut. More...
 
unsigned star_height (ratexp_t exp)
 Return the star height of exp. More...
 
ratexp_t star_normal_form (ratexp_t exp)
 Builds an expression equivalent to exp that is in star normal form. More...
 
scc_return_t strongly_connected_components (automaton_t aut)
 Computes the strongly connected components of an automaton. More...
 
automaton_t suffix (automaton_t aut, options_t opts={})
 Computes an automaton accepting all suffixes of words accepted by aut; function will modify aut or not depending on given opts. More...
 
automaton_t sum (automaton_t aut1, automaton_t aut2, options_t opts={})
 Computes the parallele union of aut1 and aut2. More...
 
automaton_t sum_of_standard (automaton_t aut1, automaton_t aut2, options_t opts={})
 Sums standard automaton aut2 into standard automaton au1 or computes a new standard automaton that is equivalent to the sum of aut1 and aut2. More...
 
automaton_t support (automaton_t aut, options_t opts={})
 Computes the support of aut, that is the boolean automaton resulting from replacing any non-zero weight by True. More...
 
transducer_t synchronize (transducer_t tdc)
 
void tdc_circulation_here (transducer_t tdc)
 
json_ast_t to_json_ast (automaton_t aut, json_ast_t extra_medata=json_ast::empty())
 
json_ast_t to_json_ast (ratexp_t exp, json_ast_t extra_medata=json_ast::empty())
 
automaton_t transpose (automaton_t aut, options_t opts={})
 Transposes aut or returns a transposed copy of aut. More...
 
automaton_t trim (automaton_t aut, options_t opts={})
 Trims aut or returns a trimmed copy of aut. More...
 
std::set< state_tuseful_states (automaton_t aut)
 Computes the list of useful states in aut. More...
 

Variables

internal::option_t< bool > 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_tDIRECTION
 Option used when there are "forward" or "backward" strategies. More...
 
std::ostream * error_stream
 A pointer to the error_stream used at dynamical layer. More...
 
internal::option_t< exp_to_aut_algo_tEXP_TO_AUT_ALGO
 Option used when a rational expression is computed from an automaton. More...
 
internal::option_t< bool > IN_PLACE
 Option used when an algorithm may be done in place. More...
 
internal::option_t< io_format_tIO_FORMAT
 Option used to specify an input or output format. More...
 
internal::option_t< bool > KEEP_HISTORY
 Option used to specify whether to keep the history of states. More...
 
internal::option_t< layout_tLAYOUT
 Option used when displaying an automaton with dot. More...
 
internal::option_t< minim_algo_tMINIM_ALGO
 Option used to specify the algorithm to use for computing minimization. More...
 
internal::option_t< bool > PREPOST_PARADIGM
 Option used to specify whether to consider initial/final status of states as normal transitions. More...
 
internal::option_t< bool > PRUNE
 Option used when in the process of the algorithm, some elements (e.g. More...
 
internal::option_t< quotient_algo_tQUOTIENT_ALGO
 Option used to specify the algorithm to use for computing quotients. More...
 
internal::option_t< bool > SAFE
 Option used when performing some test is costly or impossible. More...
 
internal::option_t< state_elim_order_tSTATE_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...
 
std::ostream * warning_stream
 A pointer to the error_stream used at dynamical layer. More...
 

Detailed Description

Namespace for the dynamical layer of Awali.

Templates types annotatin automa (among others) have been erased. Each algorithm call an in a given module, possibly compiling it on the fly.

See also:


Data Structure Documentation

◆ awali::dyn::scc_return_t

struct awali::dyn::scc_return_t
Data Fields
vector< vector< state_t > > partition Partition of the states into strongly connected components.
unordered_map< state_t, unsigned int > scc_of Map of states to their strongly connected component.

Typedef Documentation

◆ label_t

using awali::dyn::label_t = typedef any_t

Type for (transition) labels; it is an alias to any_t since its precise type depends on the weightset of manipulated automaton_t or ratexp_t.

Example (Getting back a label knowing its type)
automaton_t aut = load("a1");
// In a1, labels are chars so we may cast it directly:
char label = (char) aut->label_of(aut->transitions()[0]) ;
// NB: the previous line takes the label of the first transition in an
// arbitrary order; its meaning is dubious.
automaton_t load(const std::string &path, options_t opts={})
Loads an automaton from file pointed by path.

◆ state_t

using awali::dyn::state_t = typedef unsigned

Type representing automata states; currently simply identifiers of type unsigned, but this might change in the future.

◆ transition_t

using awali::dyn::transition_t = typedef unsigned

Type representing automata transitions; currently simply identifiers of type unsigned, but this might change in the future.

◆ weight_t

using awali::dyn::weight_t = typedef any_t

Type for (transition) weights; it is an alias to any_t since the its precise type depends on the weightset of manipulated automaton_t or ratexp_t.

Example (Getting back a weight knowing its type)
automaton_t aut = load("binary");
// In `binary`, weights are integers so we may cast it as such:
int weight = (int) eval(aut, "101010");
weight_t eval(automaton_t aut, any_t word)
Computes the weight associated with word by aut.

◆ word_t

using awali::dyn::word_t = typedef any_t

Type for words; it is an alias to any_t since the precise type depends on the context (most of the time, it is a std::string).

Enumeration Type Documentation

◆ ExpKind

enum awali::dyn::ExpKind
strong
Enumerator
ZERO 

Only the "empty" rational expression is of this kind (that is, with an empty language).

This expression is the neutral element for the sum of rational expressions.

Beware
The empty rational expression is not the same thing as the rational expression consisting of a single epsilon.
ONE 

Only the "epsilon" rational expression is of this kind (that is, with a language reduced to the empty word).

This expression is the neutral element for the concatenation of rational expressions.

ATOM 

Rational expressions of this kind are simply a label.

See also
abstract_ratexp_t::value
SUM 

Rational expression which is a sum (or union) of rational expressions.

See also
PROD 

Rational expression which is a product (or concatenation) of rational expressions.


See also
STAR 

Rational expressions of this kind are the star of another rational expression.

The subexpressions is given by abstract_ratexp_t::children().

Function Documentation

◆ accessible()

automaton_t awali::dyn::accessible ( automaton_t  aut,
options_t  opt = {} 
)

Makes aut accessible or returns a copy of the accessible part of aut.

The following options may be given: KEEP_HISTORY, IN_PLACE. (Other options are ignored.)

Parameters
autA dynamic Awali automaton
optsome options
Returns
A dynamic Awali automaton

Example:

automaton_t aut;
// definition of aut
automaton_t b = trim (aut); // b is a copy of the accessible part of aut
accessible (aut, {IN_PLACE=true}); // aut is now accessible
internal::option_t< bool > IN_PLACE
Option used when an algorithm may be done in place.
automaton_t trim(automaton_t aut, options_t opts={})
Trims aut or returns a trimmed copy of aut.
automaton_t accessible(automaton_t aut, options_t opt={})
Makes aut accessible or returns a copy of the accessible part of aut.

◆ accessible_states()

std::set<state_t> awali::dyn::accessible_states ( automaton_t  aut)

Computes the list of accessible states in aut.

Parameters
autA dynamic Awali automaton
Returns
the set of accessible states.

◆ add_path() [1/2]

void awali::dyn::add_path ( automaton_t  aut,
state_t  p,
state_t  q,
const std::string &  s,
bool  strict_alphabet = true 
)

add a subautomaton realizing the series s between states p and q of aut.

The string s is parsed to obtain a rational expression; the function add_path is then called

Parameters
autthe automaton in which the subautomaton is inserted
pthe source state
qthe destination state
sthe inserted series
strict_alphabetif true the letters in the expression must belong to the alphabet of the automaton; otherwise, they can be added to the alphabet
Exceptions
std::runtime_errorif aut does not allow epsilon-transitions and s is not proper

◆ add_path() [2/2]

void awali::dyn::add_path ( automaton_t  aut,
state_t  p,
state_t  q,
ratexp_t  exp 
)

add a subautomaton realizing the series exp between states p and q of aut.

The behaviour of the function depends whether the automaton aut allows epsilon-transitions.

– If it does, a COMPACT_THOMPSON automaton is built from exp and copied between states p and q.

– If it does not, a STANDARD automaton is built from exp and copied between states p and q. In this case, the series exp must be proper.

Parameters
autthe automaton in which the subautomaton is inserted
pthe source state
qthe destination state
expthe inserted series
Exceptions
std::runtime_errorif aut does not allow epsilon-transitions and exp is not proper

◆ allow_eps_transition()

automaton_t awali::dyn::allow_eps_transition ( automaton_t  aut,
options_t  opts = {} 
)

Returns a copy of aut in which epsilon-transitions are allowed.

Parameters
aut
opts

◆ allow_words()

automaton_t awali::dyn::allow_words ( automaton_t  aut)

Returns a copy of aut in which transitions may bear words.

Parameters
aut
Returns
a new automaton, copy of aut in which transitions may bear words.

◆ are_equivalent()

bool awali::dyn::are_equivalent ( automaton_t  aut1,
automaton_t  aut2 
)

Tests if aut1 and au2 are equivalent.

Parameters
aut1
aut2
Returns
true if aut1 and aut2 associates every word with the same weight.
Precondition
The algorithm only work if either:
  • both aut1 and aut2 are over weightset B;
  • automaton aut2 is over a weightset that is a field, or over Z, and the context of aut1 is compatible with the context of aut2.

◆ are_isomorphic()

bool awali::dyn::are_isomorphic ( automaton_t  aut1,
automaton_t  aut2 
)

Determines if two automata are isomorphic.

Parameters
aut1
aut2
Precondition
aut1 and aut2 must have the same context

◆ aut_to_exp()

ratexp_t awali::dyn::aut_to_exp ( automaton_t  aut,
options_t  opts = {} 
)

Computes a rational expression equivalent to aut.

Parameters
aut
optsA set of options; only STATE_ELIM_ORDER is meaningful.
Returns
a new rational expression, equivalent to aut

◆ change_alphabet()

void awali::dyn::change_alphabet ( automaton_t  aut,
const std::string &  alphabet 
)

Change the alphabet of the automaton.

This function replaces the alphabet of the automaton by the given alphabet on char. Transitions which are labeled with letters that do not belong to the new alphabet are deleted.

Parameters
autthe automaton
alphabetthe new alphabet

◆ change_int_alphabet()

void awali::dyn::change_int_alphabet ( automaton_t  aut,
int  a,
int  b 
)

Change the alphabet of the automaton.

This function replaces the alphabet of the automaton by the given alphabet on int. Transitions which are labeled with letters that do not belong to the new alphabet are deleted.

Parameters
autthe automaton
athe first letter of the new alphabet
bthe last letter of the new alphabet

◆ characteristic()

automaton_t awali::dyn::characteristic ( automaton_t  aut,
std::string  weightset,
options_t  opts = {} 
)

Computes the characteristic of aut over weightset.

Consists in copying aut, and setting the weight of every transition to one (i.e. the multiplicative neutral element of the weightset).

Parameters
aut
weightsetstring representation of a weightset
optsa set of options Only option KEEP_HISTORY is meaningful.
Returns
an automaton
  • whose weightset is the one represented by string weightset,
  • whose labelset is the same as the one of aut.
Precondition
aut must be a boolean automaton

◆ coaccessible()

automaton_t awali::dyn::coaccessible ( automaton_t  aut,
options_t  opt = {} 
)

Makes aut coaccessible or returns a copy of the coaccessible part of aut.

The following options may be given: KEEP_HISTORY, IN_PLACE. (Other options are ignored.)

Parameters
autA dynamic Awali automaton
optsome options
Returns
A dynamic Awali automaton

Example:

automaton_t aut;
// definition of aut
automaton_t b = trim (aut); // b is a copy of the coaccessible part of aut
coaccessible (aut, {IN_PLACE=true}); // aut is now coaccessible
automaton_t coaccessible(automaton_t aut, options_t opt={})
Makes aut coaccessible or returns a copy of the coaccessible part of aut.

◆ coaccessible_states()

std::set<state_t> awali::dyn::coaccessible_states ( automaton_t  aut)

Computes the list of coaccessible states in aut.

Parameters
autA dynamic Awali automaton
Returns
a standard set

◆ compact()

automaton_t awali::dyn::compact ( automaton_t  aut)

In a copy of an automaton aut which allows words as label, compacts each non-branching path into one transition.

Parameters
aut

◆ complement()

automaton_t awali::dyn::complement ( automaton_t  aut,
options_t  opts = {} 
)

Complements aut or returns a complemented copy of aut.

Parameters
autautomaton to be complemented
optsA set of option. Only IN_PLACE is meaningful.
Returns
Precondition
aut should be deterministic and over weightset B

◆ complete()

automaton_t awali::dyn::complete ( automaton_t  aut,
options_t  opts = {} 
)

Completes aut or returns a completed copy of given automaton.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningfull.
Returns
a complete automaton

◆ condensation()

automaton_t awali::dyn::condensation ( automaton_t  aut)

Computes the condensation of an automaton; it results from reducing each strongly connected component of the original automaton to a single state.

Parameters
aut
Returns
The condensation of aut

◆ constant_term()

weight_t awali::dyn::constant_term ( ratexp_t  exp)

Returns the constant term of exp, that is the weight of epsilon.

Parameters
exp
Returns
a weight

◆ context_words()

context_t awali::dyn::context_words ( automaton_t  aut)

◆ copy()

automaton_t awali::dyn::copy ( automaton_t  aut,
options_t  opts = {} 
)

Makes a deep copy of aut.

Parameters
autAutomaton to copy
optsa set of options. Only option KEEP_HISTORY is meaningful.
Returns
a copy of aut

◆ determinize()

automaton_t awali::dyn::determinize ( automaton_t  aut,
options_t  opts = {} 
)

Determinizes an automaton.

The determinization is computed by the subset construction. In case of weighted automata, every state of the result corresponds to a weighted subset; hence, if the semiring is not locally finite, the termination is not guarantee.

Therefore, the function can not be called if the semiring of weights is not locally finite, except if the option SAFE is set to false.

The option KEEP_HISTORY is meaningful only for the Boolean determinization. If true, every state of the determinization is linked to a subset of states of aut.

Parameters
optsA set of option. Only KEEP_HISTORY and SAFE are meaningful.
Precondition
aut should be over a locally finite weighset, except if SAFE is false.
Returns
The derminization of aut

◆ draw_exp()

automaton_t awali::dyn::draw_exp ( ratexp_t  exp)

Computes a tree-like automaton representing expression exp.

Use with pdfdisplay

Parameters
exp

◆ enumerate()

std::map<any_t, weight_t> awali::dyn::enumerate ( automaton_t  aut,
unsigned  max 
)

Gives the weight associated with each word shorter than max by aut.

Parameters
aut
max
Precondition
aut should not be a transducer or allow epsilon transitions.

◆ eval()

weight_t awali::dyn::eval ( automaton_t  aut,
any_t  word 
)

Computes the weight associated with word by aut.

Parameters
aut
word
Precondition
aut should not be a transducer or allow epsilon transitions.

◆ eval_word()

ratexp_t awali::dyn::eval_word ( transducer_t  tdc,
const std::string &  word 
)

◆ exp_to_aut()

automaton_t awali::dyn::exp_to_aut ( ratexp_t  ratexp,
options_t  opts = {} 
)

Computes an automaton equivalent to ratexp.

Parameters
ratexp
optsA set of options; EXP_TO_AUT_ALGO is meaningful.
Returns
A new automaton whose behaviour is the same as the one of ratexp.

◆ expand()

ratexp_t awali::dyn::expand ( ratexp_t  exp)

Expands a rational expression.

Parameters
exp

◆ factor()

automaton_t awali::dyn::factor ( automaton_t  aut,
options_t  opts = {} 
)

Computes an automaton accepting all factors of words accepted by aut; function will modify aut or not depending on given opts.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningful.
Returns
A new automaton if IN_PLACE is set, or aut otherwise.

◆ is_accessible()

bool awali::dyn::is_accessible ( automaton_t  aut)

Tests whether every state of the automaton is accessible.

Parameters
autA dynamic Awali automaton
Returns
true if every state is accessible; false otherwise.

◆ is_ambiguous()

bool awali::dyn::is_ambiguous ( automaton_t  aut)

Tests whether an automaton is ambiguous.

That is, whether aut features two accepting runs for the same word.

◆ is_coaccessible()

bool awali::dyn::is_coaccessible ( automaton_t  aut)

Tests whether every state of aut is coaccessible.

Parameters
autA dynamic Awali automaton
Returns
true if every state is coaccessible; false otherwise.

◆ is_complete()

bool awali::dyn::is_complete ( automaton_t  aut)

Tests whether an automaton is complete.

Precondition
the labels of aut should be letters.

◆ is_congruence()

bool awali::dyn::is_congruence ( automaton_t  aut,
std::vector< std::vector< state_t >> &  equiv 
)

Check whether an equivalence is a congruence.

This function tests whether the equivalence is a congruence with respect to the transitions of the automaton; that is, if p~q then p and q have the same final weight and, for every letter a and every part P of the equivalence, Sum(k, p–a|k -> s with s in p) = Sum(k, q–a|k -> s with s in P). equiv is described as the list of its parts, each part being a list of states; equiv can be partially described: if a state does not appear in any part, it is considered as a singleton part.

  • aut The automaton onwhich the equivalence is tested
  • equiv The equivalence to test
    Returns
    true if equiv is a congruence, false otherwise

◆ is_deterministic()

bool awali::dyn::is_deterministic ( automaton_t  aut)

Tests whether an automaton is deterministic.

A deterministic automaton is a sequential automatoon (is_sequential) where the weigth of every transition is equal to one, as well as every initial weight. Notice that the final weight can take any value.

Parameters
autthe automaton
Precondition
the labels of aut should be letters.

◆ is_empty()

bool awali::dyn::is_empty ( automaton_t  aut)

Tests whether the automaton has no state.

Parameters
autA dynamic Awali automaton
Returns
true if the automaton has no state; false otherwise.

◆ is_functional()

bool awali::dyn::is_functional ( transducer_t  tdc)

Tests whether tdc is functional.

Parameters
tdc
Returns
true if tdc is functional.

◆ is_promotable()

bool awali::dyn::is_promotable ( const std::string &  src_ws,
const std::string &  dest_ws 
)

Tests whether a promotion is possible from one weightset to the other one.

src_ws and dest_ws are the public names of weightsets like "B", "Z/5Z", etc.

Parameters
src_wsthe weightset to promote
dest_wsthe target of the promotion
Returns
true if the promotion is possible.

◆ is_proper()

bool awali::dyn::is_proper ( automaton_t  aut)

Tests whether an automaton has epsilon-transitions.

This is a dynamical test: the function will check for the existence of a transition labelled by epsilon. If the automaton does not allow epsilon transitions, this functions return true without computation.

Parameters
aut
Returns
true if aut has no transition labelled by epsilon.

◆ is_sequential()

bool awali::dyn::is_sequential ( automaton_t  aut)

Tests whether an automaton is sequential.

An automaton is sequential if it has at most one initial state, and, for every state, all the outgoing transitions carry different labels.

Parameters
autthe automaton
Precondition
the labels of aut should be letters.

◆ is_standard()

bool awali::dyn::is_standard ( automaton_t  aut)

Tests whether aut is standard.

An automaton is standard if

  • it has a single initial state with an initial function equal to 1;
  • the initial state has no incoming transition.
Parameters
aut
Returns
true if aut is a standard automaton.

◆ is_trim()

bool awali::dyn::is_trim ( automaton_t  aut)

Tests whether aut is trim.

Parameters
autA dynamic Awali automaton
Returns
true if the automaton is trim; false otherwise.

◆ is_useless()

bool awali::dyn::is_useless ( automaton_t  aut)

Tests whether the automaton has useful states.

Parameters
autA dynamic Awali automaton
Returns
true if the automaton has no useful state; false otherwise.

◆ is_valid() [1/2]

bool awali::dyn::is_valid ( automaton_t  aut)

Tests whether epsilon removal is possible in aut.

Parameters
aut
Returns
true if proper would work on aut.

◆ is_valid() [2/2]

bool awali::dyn::is_valid ( ratexp_t  exp)

Tests whether exp is valid that is, if every monomial in the series it represents is properly weighted.

This is always true for rational expression weighted by booleans.

Parameters
exp
Returns
true if exp is valid

◆ left_reduce()

automaton_t awali::dyn::left_reduce ( automaton_t  aut)

◆ letterize()

automaton_t awali::dyn::letterize ( automaton_t  aut)

◆ load()

automaton_t awali::dyn::load ( const std::string &  path,
options_t  opts = {} 
)

Loads an automaton from file pointed by path.

Parameters
path
optsA set of options; IO_FORMAT is meaningful.
Returns
A new automaton

◆ load_exp()

ratexp_t awali::dyn::load_exp ( const std::string &  filepath)

Loads a ratexp_t from file filepath

◆ make_context_with_another_semiring()

context_t awali::dyn::make_context_with_another_semiring ( context_t  ctx,
const std::string &  ws 
)

Computes a context with the same labelset as ctx and the weightset ws.

ws is the public name of a weightset like "B", "Z/5Z", etc.

Parameters
ctxA dynamic context
wsthe public name of a weightset
Returns
a new dynamic context

◆ min_quotient()

automaton_t awali::dyn::min_quotient ( automaton_t  aut,
options_t  opts = {} 
)

Computes the minimal quotient of aut.

Parameters
aut
optsA set of option; only QUOTIENT_ALGO and KEEP_HISTORY are meaninglful.

Note that algorithm BRZOZOWSKI is not valid.

Precondition
The function works for all automata but gives the classical minimal automaton only if aut is a deterministic boolean.

◆ minimal_automaton() [1/2]

automaton_t awali::dyn::minimal_automaton ( automaton_t  aut,
options_t  opts = {} 
)

Computes the minimal complete deterministic automaton of the language accepted by aut.

This may result in a call to proper, to quotient, and to determinize if needed.

Parameters
aut
optsA set of options; MINIM_ALGO is meaningful, and so is QUOTIENT_ALGO in the case where MINIM_ALGO is set to DETERMINIZE_QUOTIENT.
Returns
a new automaton.
Precondition
Automaton aut needs to be over weightset B (and not a transducer).

◆ minimal_automaton() [2/2]

automaton_t awali::dyn::minimal_automaton ( ratexp_t  exp,
options_t  opts = {} 
)

Computes the minimal complete deterministic automaton of the language of exp.

Simply calls exp_to_aut and then minimal_automaton(automaton_t,options_t).

Parameters
exp
optsA set of options; MINIM_ALGO, EXP_TO_AUT_ALGO, and KEEP_HISTORY are meaningful; if MINIM_ALGO is set to DETERMINIZE_QUOTIENT (default), QUOTIENT_ALGO is meaningful.
Returns
a new automaton.
Precondition
Automaton aut needs to be over weightset B (and not a transducer).

◆ num_accessible_states()

size_t awali::dyn::num_accessible_states ( automaton_t  aut)

Computes the number of accessible states in aut.

Computes the number of accessible states.

Parameters
autA dynamic Awali automaton
Returns
a size_t number

◆ num_coaccessible_states()

size_t awali::dyn::num_coaccessible_states ( automaton_t  aut)

Computes the number of coaccessible states in aut.

Parameters
autA dynamic Awali automaton
Returns
a size_t number

◆ operator<<() [1/5]

std::ostream& awali::dyn::operator<< ( std::ostream &  o,
automaton_t  aut 
)

◆ operator<<() [2/5]

std::ostream & awali::dyn::operator<< ( std::ostream &  o,
const dyn::any_t a 
)

◆ operator<<() [3/5]

internal::formatted_ostream awali::dyn::operator<< ( std::ostream &  o,
io_format_t const  fmt 
)

◆ operator<<() [4/5]

std::ostream& awali::dyn::operator<< ( std::ostream &  o,
ratexp_t  e 
)

◆ operator<<() [5/5]

std::ostream& awali::dyn::operator<< ( std::ostream &  o,
transducer_t  aut 
)

◆ operator>>() [1/2]

std::istream& awali::dyn::operator>> ( std::istream &  i,
automaton_t aut 
)

◆ operator>>() [2/2]

internal::formatted_istream awali::dyn::operator>> ( std::istream &  i,
io_format_t const  fmt 
)

◆ parse_automaton() [1/2]

automaton_t awali::dyn::parse_automaton ( json_ast_t  ast)

◆ parse_automaton() [2/2]

automaton_t awali::dyn::parse_automaton ( std::istream &  in,
options_t  opts = {} 
)

Parse an automaton from.

Parameters
inInput stream.
optsA set of options; IO_FORMAT is meaningful.
Returns
The parsed automaton.

◆ parse_ratexp() [1/2]

ratexp_t awali::dyn::parse_ratexp ( json_ast_t  ast)

◆ parse_ratexp() [2/2]

ratexp_t awali::dyn::parse_ratexp ( std::istream &  i)

◆ partial_identity()

transducer_t awali::dyn::partial_identity ( automaton_t  aut)

◆ pdfdisplay()

void awali::dyn::pdfdisplay ( automaton_t  aut,
options_t  opts = {} 
)

Computes geometry of aut with program dot and displays with a pdf-viewer.

Parameters
autAutomaton to display
optsA set of options; KEEP_HISTORY, LAYOUT are meaningful.

◆ prefix()

automaton_t awali::dyn::prefix ( automaton_t  aut,
options_t  opts = {} 
)

Computes an automaton accepting all prefixes of words accepted by aut; function will modify aut or not depending on given opts.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningful.
Returns
A new automaton if IN_PLACE is set, or aut otherwise.

◆ projection()

automaton_t awali::dyn::projection ( transducer_t  tdc,
unsigned  i 
)

Projects tdc on the tape i.

Parameters
tdcTransducer to project
itape on which to project
Returns
Return a new automaton

◆ promote_automaton()

automaton_t awali::dyn::promote_automaton ( automaton_t  aut,
const std::string &  ws,
options_t  opts = {} 
)

Computes a new automaton with the specified weightset.

If aut is a Boolean automaton this function is equivalent to characteristic. If ws is the weightset of aut, the function returns a copy of the automaton.

ws is the public name of a weightset like "B", "Z/5Z", etc.

The following option may be given: KEEP_HISTORY. (Other options are ignored.)

Parameters
auta dynamic automaton
wsthe public name of a weightset
optssome options
Returns
a new dynamic automaton

◆ proper()

automaton_t awali::dyn::proper ( automaton_t  aut,
options_t  opts = {} 
)

Removes epsilon-transitions in aut or returns a new automaton equivalent to aut that has no epsilon-transition.

NB: the type of automaton returned depends on whether IN_PLACE is true or not.

  • If IN_PLACE is true, the epsilon-transitions are removed from aut in place. Hence, aut still allows epsilon-transitions, and functions that require automata that do not allow epsilon-transitions will not work.
  • If IN_PLACE is false, the resulting automaton will not allow epsilon-transition.
Parameters
aut
optsA set of options. Meaningful options are IN_PLACE, DIRECTION, PRUNE and KEEP_HISTORY.
  • If PRUNE is true (default), the algorithm removes the states that become useless during the process of removing epsilon-transitions.
  • If DIRECTION is BACKWARD (default) the closure of the transitions (or final states) is computed w.r.t. the preceding transitions; if it is FORWARD the closure of transitions (or initial states) is computed w.r.t. the following transitions.
  • The option KEEP_HISTORY is meaningful only if IN_PLACE is false.
Returns
Argument aut if IN_PLACE is true, a new automaton otherwise.
Precondition
aut must be valid (it is always true for Boolean automata).

◆ put() [1/2]

std::ostream& awali::dyn::put ( automaton_t  aut,
std::ostream &  o,
options_t  opts = {} 
)

Write aut to output stream o.

Parameters
aut
o
optsA set of options; IO_FORMAT is meaningful; KEEP_HISTORY and LAYOUT are meaningful if given IO_FORMAT uses dot to compute geometry.
Returns
The stream o

◆ put() [2/2]

std::ostream& awali::dyn::put ( ratexp_t  aut,
std::ostream &  o,
options_t  opts = {} 
)

◆ reduce()

automaton_t awali::dyn::reduce ( automaton_t  aut)

Reduces an automaton.

Precondition
the weightset of aut should be a field or Z.

◆ right_reduce()

automaton_t awali::dyn::right_reduce ( automaton_t  aut)

◆ save()

void awali::dyn::save ( const automaton_t  aut,
const std::string &  path,
options_t  opts = {} 
)

Writes aut to file pointed by path.

Parameters
aut
path
optsA set of options; IO_FORMAT is meaningful; KEEP_HISTORY and LAYOUT are meaningful if given IO_FORMAT uses dot to compute geometry.

◆ scc_of()

std::vector<state_t> awali::dyn::scc_of ( automaton_t  aut,
state_t  s 
)

Returns the strongly connected component of a state.

@ param aut @ param state The strongly connected component of which is computed @ return The list of the states in the strongly connected component of aut

◆ set_error_stream()

void awali::dyn::set_error_stream ( std::ostream &  o)

Setter for the error_stream of the dynamical layer.

◆ set_warning_stream()

void awali::dyn::set_warning_stream ( std::ostream &  o)

Setter for the warning_stream of the dynamical layer.

◆ shortest()

std::map<any_t, weight_t> awali::dyn::shortest ( automaton_t  aut,
unsigned  max 
)

Gives the shortest , returns an empty map if no such word is shorter than max.

Parameters
aut
max
Precondition
aut should not be a transducer or allow epsilon transitions.

◆ standard()

automaton_t awali::dyn::standard ( automaton_t  aut,
options_t  opts = {} 
)

Makes aut standard or return a new standard automaton equivalent to aut.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningful.
Returns
a new automaton, or aut if IN_PLACE was set to true.
Precondition
Automata aut1 and aut2 must have the same weightset and labelset, and both be standard.

◆ star()

automaton_t awali::dyn::star ( automaton_t  aut,
options_t  opts = {} 
)

Builds a standard automaton that recognizes the star of the language of aut.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningful.
Returns
a new automaton, or aut1 if IN_PLACE was set to true.
Precondition
aut must be a standard automaton.

◆ star_height()

unsigned awali::dyn::star_height ( ratexp_t  exp)

Return the star height of exp.

Parameters
exp

◆ star_normal_form()

ratexp_t awali::dyn::star_normal_form ( ratexp_t  exp)

Builds an expression equivalent to exp that is in star normal form.

Returns
A new rational expression with same context as exp.

◆ strongly_connected_components()

scc_return_t awali::dyn::strongly_connected_components ( automaton_t  aut)

Computes the strongly connected components of an automaton.

Parameters
aut
Returns
A double map: states to scc and scc to states

◆ suffix()

automaton_t awali::dyn::suffix ( automaton_t  aut,
options_t  opts = {} 
)

Computes an automaton accepting all suffixes of words accepted by aut; function will modify aut or not depending on given opts.

Parameters
aut
optsA set of options. Only IN_PLACE is meaningful.
Returns
A new automaton if IN_PLACE is set, or aut otherwise.

◆ sum_of_standard()

automaton_t awali::dyn::sum_of_standard ( automaton_t  aut1,
automaton_t  aut2,
options_t  opts = {} 
)

Sums standard automaton aut2 into standard automaton au1 or computes a new standard automaton that is equivalent to the sum of aut1 and aut2.

Parameters
aut1
aut2
optsA set of options. Only IN_PLACE is meaningful.
Returns
a new automaton, or aut1 if IN_PLACE was set to true.
Precondition
Automata aut1 and aut2 must have the same context, and both be standard.
See also
sum For the general function working on any automaton.

◆ support()

automaton_t awali::dyn::support ( automaton_t  aut,
options_t  opts = {} 
)

Computes the support of aut, that is the boolean automaton resulting from replacing any non-zero weight by True.

Parameters
autautomaton the support of which is computed
optsa set of options Only option KEEP_HISTORY is meaningful.
Returns
automaton over B

◆ tdc_circulation_here()

void awali::dyn::tdc_circulation_here ( transducer_t  tdc)

◆ to_json_ast() [1/2]

json_ast_t awali::dyn::to_json_ast ( automaton_t  aut,
json_ast_t  extra_medata = json_ast::empty() 
)

◆ to_json_ast() [2/2]

json_ast_t awali::dyn::to_json_ast ( ratexp_t  exp,
json_ast_t  extra_medata = json_ast::empty() 
)

◆ transpose()

automaton_t awali::dyn::transpose ( automaton_t  aut,
options_t  opts = {} 
)

Transposes aut or returns a transposed copy of aut.

The following options may be given: KEEP_HISTORY, IN_PLACE. (Other options are ignored.)
KEEP_HISTORY is meaningful only if IN_PLACE is false.

Parameters
autAutomaton to transpose
optsA set of options
Returns
a new automaton, or the input if IN_PLACE is true.

◆ trim()

automaton_t awali::dyn::trim ( automaton_t  aut,
options_t  opts = {} 
)

Trims aut or returns a trimmed copy of aut.

The following options may be given: KEEP_HISTORY, IN_PLACE. (Other options are ignored.)

Parameters
autA dynamic Awali automaton
optssome options
Returns
A dynamic Awali automaton

Example:

automaton_t aut;
// definition of aut
automaton_t b = trim (aut); // b is a trimmed copy of aut
trim (aut, {IN_PLACE=true}); // aut is now trim

◆ useful_states()

std::set<state_t> awali::dyn::useful_states ( automaton_t  aut)

Computes the list of useful states in aut.

Parameters
autA dynamic Awali automaton
Returns
a standard set

Variable Documentation

◆ error_stream

std::ostream* awali::dyn::error_stream
extern

A pointer to the error_stream used at dynamical layer.

◆ warning_stream

std::ostream* awali::dyn::warning_stream
extern

A pointer to the error_stream used at dynamical layer.