Awali
Another Weighted Automata library
|
Contains all functions that allows to construct automata and expressions. More...
Data Structures | |
struct | awali::dyn::ratexp_t::with_int_labels |
Helper class that contains convenience factories to build expressions whose labels are integers. More... | |
struct | awali::dyn::ratexp_t::with_tuple_labels |
Helper class that contains convenience factories to build expressions whose labels are tuples. More... | |
Functions | |
awali::dyn::automaton_t::automaton_t (context::labelset_description ld, context::weightset_description wd) | |
Builds a new empty automaton whose labelset is described by ld and weightset by wd . More... | |
awali::dyn::ratexp_t::ratexp_t (std::string str, context::labelset_description ld, context::weightset_description wd, bool fixed_alphabet=true) | |
Builds the expression represented by str and whose labelset is described by ld and weightset by wd . More... | |
automaton_t | awali::dyn::factory::cerny (unsigned n, const std::string &alphabet, const std::string &semiring="B") |
Returns an automaton with n states. More... | |
automaton_t | awali::dyn::factory::cerny (unsigned n, int a, int b, const std::string &semiring="B") |
Returns an automaton with n states. More... | |
automaton_t | awali::dyn::factory::divkbaseb (unsigned k, unsigned b, const std::string &alphabet="auto", const std::string &semiring="B") |
Returns an automaton which recognizes numbers in base b which are multiple of k . More... | |
automaton_t | awali::dyn::factory::double_ring (unsigned n, const std::vector< unsigned > &finals, const std::string &alphabet, const std::string &semiring="B") |
Returns a double ring automaton with n states. More... | |
automaton_t | awali::dyn::factory::double_ring (unsigned n, const std::vector< unsigned > &finals, int a, const std::string &semiring="B") |
Returns a double ring automaton with n states. More... | |
static automaton_t | awali::dyn::automaton_t::from (std::string alphabet, bool allow_eps_transitions, std::string="B") |
Builds a boolean automaton over given alphabet , that possibly allows eps_transitions. More... | |
static automaton_t | awali::dyn::automaton_t::from (std::string alphabet, std::string weightset="B", bool allow_eps_transitions=false) |
Builds an automaton with labels in given alphabet possibly allowing epsilon transitions, and with weights in given weightset . More... | |
static ratexp_t | awali::dyn::ratexp_t::with_int_labels::from (std::string str, std::string weightset="B") |
static ratexp_t | awali::dyn::ratexp_t::from (std::string str, std::string weightset="B", std::string alphabet="auto") |
Builds a rational expression from its string representation. More... | |
static ratexp_t | awali::dyn::ratexp_t::with_tuple_labels::from (std::string str, std::vector< std::string > alphabets, std::string weightset="B") |
static ratexp_t | awali::dyn::ratexp_t::with_tuple_labels::from (std::string str, unsigned n, std::string weightset="B") |
static automaton_t | awali::dyn::automaton_t::from_context (context_t ctx) |
Builds a new automaton whose labelset and weightset are given by ctx . More... | |
static ratexp_t | awali::dyn::ratexp_t::from_context (std::string str, context::labelset_description ld, context::weightset_description wd, bool fixed_alphabet=true) |
static ratexp_t | awali::dyn::ratexp_t::from_context (std::string str, context_t ctx, bool fixed_alphabet=true) |
Builds a rational expression from a string representation and a context. More... | |
static automaton_t | awali::dyn::automaton_t::with_int_labels::from_range (int l, int u, bool allow_eps_transitions) |
Builds an automaton with alphabet {l , l +1, ..., u }, possibly allowing epsilon transitions. More... | |
static automaton_t | awali::dyn::automaton_t::with_int_labels::from_range (int l, int u, std::string weightset="B", bool allow_eps_transitions=false) |
Builds an automaton with alphabet {l , l +1, ..., u } and weightset weightset More... | |
static ratexp_t | awali::dyn::ratexp_t::with_int_labels::from_range (std::string str, int l, int u, std::string weightset="B") |
static ratexp_t | awali::dyn::ratexp_t::with_int_labels::from_size (std::string str, unsigned n, std::string weightset="B") |
static automaton_t | awali::dyn::automaton_t::with_int_labels::from_size (unsigned n, bool allow_eps_transitions) |
Builds a Boolean automaton with alphabet {0, 1, ..., n -1}, possibly allowing epsilon transitions. More... | |
static automaton_t | awali::dyn::automaton_t::with_int_labels::from_size (unsigned n, std::string weightset="B", bool allow_eps_transitions=false) |
Builds an automaton with alphabet {0, 1, ..., n-1} and weightset weightset . More... | |
automaton_t | awali::dyn::factory::int_divkbaseb (unsigned k, unsigned b, const std::string &semiring="B") |
returns an automaton which recognizes numbers in base b which are multiple of k More... | |
automaton_t | awali::dyn::factory::ladybird (unsigned n, const std::string &alphabet, const std::string &semiring="B") |
Returns a "ladybird" automaton with n states. More... | |
automaton_t | awali::dyn::factory::ladybird (unsigned n, int a, const std::string &semiring="B") |
Returns an "ladybird" automaton with n states. More... | |
template<typename Context > | |
mutable_automaton< Context > | awali::sttc::n_ultimate (const Context &ctx, typename Context::labelset_t::value_t a, unsigned n) |
Returns an automaton which recognizes words with a specific n-ultimate letter. More... | |
automaton_t | awali::dyn::factory::n_ultimate (unsigned n, const std::string &alphabet, const std::string &semiring="B") |
Returns an automaton which recognizes words with a specific n-ultimate letter. More... | |
automaton_t | awali::dyn::factory::n_ultimate (unsigned n, int a, int b, const std::string &semiring="B") |
returns an automaton which recognizes words with a specific n-ultimate letter More... | |
automaton_t | awali::dyn::factory::randomDFA (unsigned size, std::string alph) |
<> Generates a random deterministic automaton over alphabet alph with size states. More... | |
automaton_t | awali::dyn::factory::witness (unsigned n, const std::string &alphabet, const std::string &semiring="B") |
Returns an automaton with n states. More... | |
automaton_t | awali::dyn::factory::witness (unsigned n, int a, const std::string &semiring="B") |
Returns an automaton with n states. More... | |
Contains all functions that allows to construct automata and expressions.
awali::dyn::automaton_t::automaton_t | ( | context::labelset_description | ld, |
context::weightset_description | wd | ||
) |
Builds a new empty automaton whose labelset is described by ld
and weightset by wd
.
Experts only.
This function is the most powerful constructor provided by the dyn layer of Awali. It allows to combine almost arbitrarily all implemented weightset and labelsets.
ld | A dynamical description of a labelset |
wd | A dynamical description of a weightset |
ld
(as in example above.) If you know that this will produce a transducer, just store it in a variable of type transducer_t: awali::dyn::ratexp_t::ratexp_t | ( | std::string | str, |
context::labelset_description | ld, | ||
context::weightset_description | wd, | ||
bool | fixed_alphabet = true |
||
) |
Builds the expression represented by str
and whose labelset is described by ld
and weightset by wd
.
This function is the most powerful constructor provided by the dyn layer of Awali. It allows to combine almost arbitrarily all implemented weightset and labelsets.
Experts only.
str | String representation of |
ld | A description of the labelset |
wd | A description of the weightset of the ratexp to build |
fixed_alphabet | If false , the alphabet of returned ratexp_t will potentially be augmented with letters encountered while parsing str |
automaton_t awali::dyn::factory::cerny | ( | unsigned | n, |
const std::string & | alphabet, | ||
const std::string & | semiring = "B" |
||
) |
Returns an automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z.
For every state p,
alphabet
labels transitions from p to p+1; n-1
,n
-1 otherwise;State 0 is both initial and final.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
The shortest synchronization word for this automaton has (n
-1)^2 letters
n | a positive integer |
alphabet | a list of letters |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive |
automaton_t awali::dyn::factory::cerny | ( | unsigned | n, |
int | a, | ||
int | b, | ||
const std::string & | semiring = "B" |
||
) |
Returns an automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z, over the alphabet [a
, b
].
For every state p,
n
-1 otherwise;State 0 is both initial and final.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
The shortest synchronization word for this automaton has (n
-1)^2 letters
n | a positive integer |
a | an integer |
b | an integer larger than a |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive |
automaton_t awali::dyn::factory::divkbaseb | ( | unsigned | k, |
unsigned | b, | ||
const std::string & | alphabet = "auto" , |
||
const std::string & | semiring = "B" |
||
) |
Returns an automaton which recognizes numbers in base b
which are multiple of k
.
The factory builds a deterministic automaton with k
states over an alphabet
of char. The letters of alphabet
are sorted, and the letter with index i represents the digit i. alphabet
must contain at least b
letters. If the alphabet has more than b
letters, the larger letters do not label any transition.
If alphabet
is set as "auto", an alphabet of digits is automatically built, capital letters are used for digits larger than 9; the base must be at most 36.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
k | a positive integer |
b | a positive integer |
alphabet | an unordered list of letters |
semiring | the description of a weightsed |
k
states runtime_error | if k is not positive, or if b is smaller than 2, or if alphabet has less than b letters, or if alphabet is "auto" and b is larger than 36 |
automaton_t awali::dyn::factory::double_ring | ( | unsigned | n, |
const std::vector< unsigned > & | finals, | ||
const std::string & | alphabet, | ||
const std::string & | semiring = "B" |
||
) |
Returns a double ring automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z.
For every state p,
alphabet
labels transitions from p to p+1; alphabet
has more than 2 letters, the other letters do not label any transition.State 0 is initial; finals
is the list of the final states.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
n | a positive integer |
finals | a vector of states |
alphabet | a list of letters |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive or if alphabet has less than 2 letters |
automaton_t awali::dyn::factory::double_ring | ( | unsigned | n, |
const std::vector< unsigned > & | finals, | ||
int | a, | ||
const std::string & | semiring = "B" |
||
) |
Returns a double ring automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z, over the alphabet {a
,a+1}
.
The first letter of the alphabet labels transitions from p to p+1 for every state p, the second one labels transitions from p to p-1. State 0 is initial; finals
is the list of the final states.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
n | a positive integer |
finals | a vector of states |
a | an integer |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive |
|
static |
Builds a boolean automaton over given alphabet
, that possibly allows eps_transitions.
alphabet | String representation of the alphabet of the returned automaton: each char is a letter of the automaton. |
allow_eps_transitions | Whether returned automaton should allow epsilon-transitions. Beware of the fact that automata with epsilon-transitions and automata without epsilon-transitions have different static types. Post construction, allowing/disallowing epsilon-transitions always requires a complete copy of the automaton. |
|
static |
Builds an automaton with labels in given alphabet
possibly allowing epsilon transitions, and with weights in given weightset
.
alphabet | String representation of the alphabet of the returned automaton: each char is a letter of the automaton. |
weightset | String representation of the weightset of the built automaton. |
allow_eps_transitions | Whether returned automaton should allow epsilon-transitions. Be aware of the fact that automata with epsilon-transitions and automata without epsilon-transitions have different static types. Post construction, allowing/disallowing epsilon-transitions always requires a complete copy of the automaton. |
|
static |
|
static |
Builds a rational expression from its string representation.
str | String representation of the rational expression to build |
weightset | String representation of a weightset. |
alphabet | If set to "auto" (default), the alphabet is inferred as part of the construction. Otherwise each caracter is a letter in the alphabet. If you need alphabet {a,u,t,o}, use string "otua". |
|
static |
|
static |
|
static |
Builds a new automaton whose labelset and weightset are given by ctx
.
This function is mostly useful for copying context, as in example below.
ctx | Context of automaton given |
ctx
. If you know that this will produce a transducer, just store it in a variable of type transducer_t:
|
static |
|
static |
Builds a rational expression from a string representation and a context.
str | String representation of the rational expresion to build |
ctx | Context (that is, weightset and labelset) of the rational expression to build |
fixed_alphabet | If set to true the function will raise an exception when encountering characters that are not in the labelset; otherwise, it will silently add them to the alphabet. |
|
static |
Builds an automaton with alphabet {l
, l
+1, ..., u
}, possibly allowing epsilon transitions.
l | Lower bound of the range |
u | Upper bound of the range |
allow_eps_transitions | If true , built automaton allows epsilon-transitions. |
|
static |
Builds an automaton with alphabet {l
, l
+1, ..., u
} and weightset weightset
l | Lower bound of the range. |
u | Upper bound of the range. |
weightset | |
allow_eps_transitions | If set to true , built automaton allows epsilon-transitions. |
|
static |
|
static |
|
static |
Builds a Boolean automaton with alphabet {0, 1, ..., n
-1}, possibly allowing epsilon transitions.
n | size of the alphabet |
allow_eps_transitions | If set to true , built automaton allows epsilon-transitions. |
|
static |
Builds an automaton with alphabet {0, 1, ..., n-1}
and weightset weightset
.
n | size of the alphabet |
weightset | String representation of the weightset of the built automaton |
allow_eps_transitions | If set to true , built automaton allows epsilon-transitions. |
automaton_t awali::dyn::factory::int_divkbaseb | ( | unsigned | k, |
unsigned | b, | ||
const std::string & | semiring = "B" |
||
) |
returns an automaton which recognizes numbers in base b
which are multiple of k
The factory builds a deterministic automaton with k
states over the alphabet [0; b
]. Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
k | a positive integer |
b | a positive integer |
semiring | the description of a weightsed |
k
states runtime_error | if k is not positive, or if b is smaller than 2 |
automaton_t awali::dyn::factory::ladybird | ( | unsigned | n, |
const std::string & | alphabet, | ||
const std::string & | semiring = "B" |
||
) |
Returns a "ladybird" automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z.
For every state p,
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
The minimal automaton of the language accepted by ladybird n
has 2^n
states.
The name ladybird comes from the shape of the 6-state automaton.
n | a positive integer |
alphabet | an unordered list of letters |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive or if alphabet has less than 3 letters |
automaton_t awali::dyn::factory::ladybird | ( | unsigned | n, |
int | a, | ||
const std::string & | semiring = "B" |
||
) |
Returns an "ladybird" automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z, over the alphabet {a
, a
+1, a
+2}. For every state p,
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
The minimal automaton of the language accepted by ladybird n
has 2^n
states.
The name ladybird comes from the shape of the 6-state automaton.
n | a positive integer |
a | an integer |
semiring | the description of a weightsed |
n
states runtime_error | if n is not positive |
mutable_automaton<Context> awali::sttc::n_ultimate | ( | const Context & | ctx, |
typename Context::labelset_t::value_t | a, | ||
unsigned | n | ||
) |
Returns an automaton which recognizes words with a specific n-ultimate letter.
The factory builds an automaton with n
+1 states.
The alphabet must contain at least two letters. The automaton accepts every word where the n-ultimate letter is a
.
The automaton is co-deterministic hence unambiguous; if weighted, the automaton realizes the characteristic series of the language described above.
Context | the type of the context |
ctx | the context of the automaton |
a | a label |
n | a positive integer: the position to last of the specified letter |
n
+1 states runtime_error | if n is not positive or if the alphabet has less than 2 letters |
automaton_t awali::dyn::factory::n_ultimate | ( | unsigned | n, |
const std::string & | alphabet, | ||
const std::string & | semiring = "B" |
||
) |
Returns an automaton which recognizes words with a specific n-ultimate letter.
The factory builds an automaton with n
+1 states that recognizes a language over the alphabet
of char.
The alphabet must contain at least two letters. The order of letters in alphabet
is significant: the automaton accepts every word where the n-ultimate letter is the first letter of alphabet
.
The automaton is co-deterministic hence unambiguous; a semiring
for weights can be specified every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
n | a positive integer: the position to last of the specified letter |
alphabet | a list of letters |
semiring | the description of a weightsed |
n
+1 states runtime_error | if n is not positive or if alphabet has less than 2 letters |
automaton_t awali::dyn::factory::n_ultimate | ( | unsigned | n, |
int | a, | ||
int | b, | ||
const std::string & | semiring = "B" |
||
) |
returns an automaton which recognizes words with a specific n-ultimate letter
The factory builds an automaton with n
+1 states that recognizes a language over the alphabet of integers [a
, b
].
The alphabet must contain at least two letters. The automaton accepts every word where the n-ultimate letter is a
.
The automaton is co-deterministic hence unambiguous; a semiring
for weights can be specified every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
n | a positive integer: the position to last of the specified letter |
a | an integer |
b | an integer larger than a |
semiring | the description of a weightsed |
n+1
states runtime_error | if n is not positive or if b - a is smaller than 1. |
automaton_t awali::dyn::factory::randomDFA | ( | unsigned | size, |
std::string | alph | ||
) |
<> Generates a random deterministic automaton over alphabet alph
with size
states.
size | The number of states in the generates |
alph | Alphabet of the returned automaton |
automaton_t awali::dyn::factory::witness | ( | unsigned | n, |
const std::string & | alphabet, | ||
const std::string & | semiring = "B" |
||
) |
Returns an automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z.
For every state p,
alphabet
labels transitions from p to p+1; alphabet
labels transitions from p to alphabet
labels transitions from p to n
-1,State 0 is initial, state n-1 is final.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
This automaton is the "universal witness" described in
Janusz A. Brzozowski and David Liu, Universal Witnesses for State Complexity of Basic Operations Combined with Reversal,
CIAA 2013, Lecture Notes in Computer Science, vol. 7982, pp. 72-83.
doi : 10.1007/978-3-642-39274-0_8
n | an integer larger than 1 |
alphabet | a list of at least 3 letters |
semiring | the description of a weightsed |
n
states runtime_error | if n is lesser than 2 or if alphabet has less than 3 letters |
automaton_t awali::dyn::factory::witness | ( | unsigned | n, |
int | a, | ||
const std::string & | semiring = "B" |
||
) |
Returns an automaton with n
states.
The factory builds an automaton with n
states with indices in Z/n
Z, over the alphabet {a
, a
+1, a
+2}. For every state p,
n
-1,State 0 is initial, state n-1 is final.
Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.
This automaton is the "universal witness" described in
Janusz A. Brzozowski and David Liu, Universal Witnesses for State Complexity of Basic Operations Combined with Reversal,
CIAA 2013, Lecture Notes in Computer Science, vol. 7982, pp. 72-83.
doi : 10.1007/978-3-642-39274-0_8
n | an integer larger than 1 |
a | an integer |
semiring | the description of a weightsed |
n
states runtime_error | if n is lesser than 2 |