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_t >	accessible_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_t >	coaccessible_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_t >	enumerate (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...

ratexp_t	eval_exp (ratexp_t exp, transducer_t tdc)

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	explore_by_length (automaton_t aut, unsigned depth)
	Computes the exploration of `aut` by length. More...

automaton_t	explore_with_bound (automaton_t aut, weight_t bound)
	Computes the exploration of `aut` with respect to a bound. 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...

context_t	join_context (context_t c1, context_t c2)

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_mult_standard (automaton_t aut1, 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	promote_automaton (automaton_t aut, context_t ctx, options_t opts={})

ratexp_t	promote_ratexp (ratexp_t exp, const std::string &weightset)
	Computes a new expression 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...

ratexp_t	ratexp_characteristic (ratexp_t exp, std::string const &weightset)
	Computes the characteristic of `exp` over `weightset`. More...

ratexp_t	ratexp_copy (ratexp_t exp)
	Returns a copy of `exp`. More...

ratexp_t	ratexp_support (ratexp_t exp)
	Returns a Boolean rational expression where all weights of `exp` are removed. 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_t >	scc_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_t >	shortest (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...

transducer_t	subnormalize (transducer_t tdc)

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_metadata=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_t >	useful_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_t >	DIRECTION
	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_t >	EXP_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_t >	IO_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_t >	LAYOUT
	Option used when displaying an automaton with dot. More...

internal::option_t< minim_algo_t >	MINIM_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_t >	QUOTIENT_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_t >	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...

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.

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.

awali::dyn::load
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");

awali::dyn::eval
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 abstract_ratexp_t::children abstract_ratexp_t::arity
PROD	Rational expression which is a product (or concatenation) of rational expressions. See also abstract_ratexp_t::children abstract_ratexp_t::arity
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

aut	A dynamic Awali automaton
opt	some 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

◆ accessible_states()

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

Computes the list of accessible states in aut.

Parameters

aut	A 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

aut	the automaton in which the subautomaton is inserted
p	the source state
q	the destination state
s	the inserted series
strict_alphabet	if `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_error if 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

aut	the automaton in which the subautomaton is inserted
p	the source state
q	the destination state
exp	the inserted series

Exceptions

std::runtime_error if 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
opts	A 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

aut	the automaton
alphabet	the 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

aut	the automaton
a	the first letter of the new alphabet
b	the 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
weightset	string representation of a weightset
opts	a 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

aut	A dynamic Awali automaton
opt	some 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

◆ coaccessible_states()

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

Computes the list of coaccessible states in aut.

Parameters

aut	A 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

aut	automaton to be complemented
opts	A 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
opts	A 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

aut	Automaton to copy
opts	a 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

aut	Automaton to determinize (possibly weighted)
opts	A 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_exp()

ratexp_t awali::dyn::eval_exp	(	ratexp_t	exp,
		transducer_t	tdc
	)

◆ 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
opts	A 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

◆ explore_by_length()

automaton_t awali::dyn::explore_by_length	(	automaton_t	aut,
		unsigned	depth
	)

Computes the exploration of aut by length.

Parameters

aut	the automaton to explore
depth	the depth of the exploration

Returns: a weighted deterministic automaton

This function builds every state of the weighted determinization with distance at most depth from the initial state. The result is a deterministic automaton which
– has the same behaviour as aut on words of length at most depth;
– does not accept any word which is not accepted by aut;
– either rejects or accepts words of length larger than depth that are accepted by aut; in the latter case, the weight of the word is equal to the weight of the word in aut.

◆ explore_with_bound()

automaton_t awali::dyn::explore_with_bound	(	automaton_t	aut,
		weight_t	bound
	)

Computes the exploration of aut with respect to a bound.

Parameters

aut	the automaton to explore
bound	the bound of the exploration

Returns: a weighted deterministic automaton

This function builds every state of the weighted determinization such that the square of the bound is not smaller than the square of every component of the multiset corresponding to the state; The ordering is managed by the weightset.

Precondition: Weightset of aut needs to be N, Z, Noo or N<int> .

◆ 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
opts	A 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

aut	A 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

aut	A 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

aut	the 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

aut	A 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_ws	the weightset to promote
dest_ws	the 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

aut	the 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

aut	A 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

aut	A 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

◆ join_context()

context_t awali::dyn::join_context	(	context_t	c1,
		context_t	c2
	)

◆ left_mult()

automaton_t awali::dyn::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.

This function multiplies every initial weight by w on the left.

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

If IN_PLACE is true, this operation operation is done directly on aut. In this case, KEEP_HISTORY is ignored.

If IN_PLACE is `false, this operation is done on a copy of aut.

Parameters

aut	automaton (unchanged)
w	weight by which the initial weights are multiplied
opts	a set of options

Returns: a copy of aut in which the transition weights have been multiplied by w

◆ 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
opts	A 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

ctx	A dynamic context
ws	the 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
opts	A 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
opts	A 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
opts	A 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

aut	A 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

aut	A 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

in	Input stream.
opts	A 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

aut	Automaton to display
opts	A 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
opts	A 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

tdc	Transducer to project
i	tape on which to project

Returns: Return a new automaton

◆ promote_automaton() [1/2]

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

aut	a dynamic automaton
ws	the public name of a weightset
opts	some options

Returns: a new dynamic automaton

◆ promote_automaton() [2/2]

automaton_t awali::dyn::promote_automaton	(	automaton_t	aut,
		context_t	ctx,
		options_t	opts = `{}`
	)

◆ promote_ratexp()

ratexp_t awali::dyn::promote_ratexp	(	ratexp_t	exp,
		const std::string &	weightset
	)

Computes a new expression with the specified weightset.

If ws is the weightset of exp, the function returns a copy of the expression.

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

Parameters

exp	a rational expression
ws	the public name of a weightset

Returns: a new rational expression

◆ 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
opts	A 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
opts	A 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 = `{}`
	)

◆ ratexp_characteristic()

ratexp_t awali::dyn::ratexp_characteristic	(	ratexp_t	exp,
		std::string const &	weightset
	)

Computes the characteristic of exp over weightset.

Consists in copying exp in the context of weightset. The resulting tree is isomorphic to the tree of exp.

Parameters

exp
weightset	string representation of a weightset

Returns

a rational expression

whose weightset is the one represented by string weightset,
whose labelset is the same as the one of exp.

Precondition: exp must be a boolean rational expression

◆ ratexp_copy()

ratexp_t awali::dyn::ratexp_copy ( ratexp_t exp )

Returns a copy of exp.

Parameters

exp

Returns: a rational expression

◆ ratexp_support()

ratexp_t awali::dyn::ratexp_support ( ratexp_t exp )

Returns a Boolean rational expression where all weights of exp are removed.

Parameters

exp

Returns: a rational expression

◆ 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 )

Simpy calls transpose, left_reduce, transpose.

◆ 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
opts	A 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
opts	A 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
opts	A 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
opts	A 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
opts	A 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

aut	automaton the support of which is computed
opts	a 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_metadata = `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

aut	Automaton to transpose
opts	A 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

aut	A dynamic Awali automaton
opts	some 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

aut	A 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.

Namespaces

Data Structures

Typedefs

Enumerations

Functions

Variables

Detailed Description

Data Structure Documentation

◆ awali::dyn::scc_return_t

Typedef Documentation

◆ label_t

◆ state_t

◆ transition_t

◆ weight_t

◆ word_t

Enumeration Type Documentation

◆ ExpKind

Function Documentation

◆ accessible()

◆ accessible_states()

◆ add_path() [1/2]

◆ add_path() [2/2]

◆ allow_eps_transition()

◆ allow_words()

◆ are_equivalent()

◆ are_isomorphic()

◆ aut_to_exp()

◆ change_alphabet()

◆ change_int_alphabet()

◆ characteristic()

◆ coaccessible()

◆ coaccessible_states()

◆ compact()

◆ complement()

◆ complete()

◆ condensation()

◆ constant_term()

◆ context_words()

◆ copy()

◆ determinize()

◆ draw_exp()

◆ enumerate()

◆ eval()

◆ eval_exp()

◆ eval_word()

◆ exp_to_aut()

◆ expand()

◆ explore_by_length()

◆ explore_with_bound()

◆ factor()

◆ is_accessible()

◆ is_ambiguous()

◆ is_coaccessible()

◆ is_complete()

◆ is_congruence()

◆ is_deterministic()

◆ is_empty()

◆ is_functional()

◆ is_promotable()

◆ is_proper()

◆ is_sequential()

◆ is_standard()

◆ is_trim()

◆ is_useless()

◆ is_valid() [1/2]

◆ is_valid() [2/2]

◆ join_context()

◆ left_mult()

◆ left_reduce()

◆ letterize()

◆ load()

◆ load_exp()

◆ make_context_with_another_semiring()

◆ min_quotient()

◆ minimal_automaton() [1/2]

◆ minimal_automaton() [2/2]

◆ num_accessible_states()

◆ num_coaccessible_states()

◆ operator<<() [1/5]

◆ operator<<() [2/5]