Operations on Automata
Generic Operations on Automata
Operators - a correspondance between Python operators and method names
accessible - the subautomaton of accesssible states
add - add/union of automata
ambiguous_word - a witness of ambiguity
coaccessible - the subautomaton of coaccesssible states
codeterminize - the transposed of the subset construction
cominimize - the transposed of the minimization
complement - an automaton accepting the complement language
complete - a complete superautomaton
conjugate - conjugate of an automaton
conjunction - synchronized product of automata
context - the algebraic type of an automaton
costandard - whether the transposed automaton is standard
determinize - the subset construction
difference - restrict an automaton
eliminate_state - perform one step in the Brzozowski-McCluskey procedure
evaluate - evaluate a word
expression - compute an equivalent expression using the Brzozowski-McCluskey state-elimination procedure
factor - an automaton that accepts the factor language of another
filter - focus on a subset of the states
has_lightening_cycle - whether the automaton has lightening cycles
has_twins_property - a condition for determinizability in tropical semirings
infiltrate - infiltrate product of two automata
info - a dictionary of facts about an automaton
insplit - an equivalent automaton which has no states with both spontaneous and proper incoming transitions
is_accessible - whether all its states are reachable
is_ambiguous - whether some word may be accepted by different paths
is_coaccessible - whether all its states can reach a final state
is_codeterministic - whether the automaton is codeterministic
is_complete - whether the automaton is complete
is_costandard - whether the automaton is costandard
is_cycle_ambiguous - whether the automaton is exponentially ambiguous
is_deterministic - whether the automaton is deterministic
is_empty - whether the automaton has no states
is_equivalent - whether two automata have the same behavior
is_letterized - whether an automaton is letterized (transitions are letters)
is_partial_identity - whether a transducer implements a partial identity
is_proper - whether an automaton is proper
is_isomorphic - whether two automata are isomorphic ("equal")
is_realtime - whether an automaton is realtime
is_standard - whether the automaton is standard
is_trim - whether accessible and coaccessible
is_useless - whether the automaton accepts no words
is_valid - whether the automaton has a well defined behavior
ldivide - left quotient of two automata
lweight - left scalar product of an automaton by a weight
letterize - split the labels into letters
lift - convert into a spontaneous automaton weighted by expressions
lightest - the words with the smallest weights accepted by an automaton
lightest_automaton - the path with the smallest weight in an automaton
minimize - minimizing an automaton
multiply - product of automata, i.e., concatenation
pair - the pair automaton, useful for computing synchronizing words
partial_identity - from single-tape to double-tape automaton
prefix - an automaton that accepts the prefix language of another
proper - remove the spontaneous transitions
project - select a single tape from a multitape automaton (transducer)
push_weights - push weights towards the initial state(s)
rdivide - right quotient of two automata
rweight - right scalar product of an automaton by a weight
reduce - a matrix-based minimization
realtime - turn into a realtime automaton
scc - decomposition into strongly-connected components
shortest - the smallest accepted words of an automaton
shuffle - shuffle product of automata
standard - turn into a standard automaton
star - star of an automaton
strip - remove decorations
subword - an automaton that accepts the subword language of another
suffix - an automaton that accepts the suffix language of another
synchronizing_word - compute a word that sends all the states to a single state
transpose - reverse all the arrows
trim - the subautomaton with no useless states
tuple - Cartesian product of automata
type - the implementation type of an automaton
weight_series - the weighted distance between initial and final states
Operations on Transducers
compose - composition of transducers
delay_automaton - an equivalent transducer where each state has a single delay between tapes
has_bounded_lag - whether the transducer can be synchronized
is_functional - whether a transducer implements a function
is_synchronized - whether a transducer is synchronized
synchronize - an equivalent transducer where delays bewteen tapes are reduced
Operations on Contexts
Operators - a correspondance between Python operators and method names
cerny - Černý automata
cotrie - a reversed trie automaton from a file of (weighted) words
divkbaseb - an automaton that recognizes multiples of a number
de_bruijn - de Bruijn automata
ladybird - Ladybird automata
levenshtein - Levenshtein (or edit-distance) automaton
quotkbaseb - a transducer that divides by a number
random_automaton - generate a random automaton
random_expression - generate a random expression
random_weight - generate a random weight
trie - trie automaton from a file of (weighted) words
tuple - multitape context
weight_one - the weight one
weight_zero - the weight zero
word_context - context of the words of a context
Operations on Expansions
Operators - a correspondance between Python operators and method names
add - addition of expansions
complement - complement of an expansion
conjunction - synchronized product of expansions
ldivide - left quotient of two expansions
lweight - left scalar product of an expansion by a weight
project - select a single tape from a multitape expansion
rweight - right scalar product of an expansion by a weight
tuple - Cartesian product of expansions
Operations on Expressions
Operators - a correspondance between Python operators and method names
add - addition of expressions
automaton - build an automaton from an expression
complement - complement of an expression
conjunction - synchronized product of expressions
constant_term - the weight of the empty word
context - the algebraic type of an expression
derivation - differentiation with respect to labels
derived_term - the derived-term (or "Antimirov") automaton of an expression
difference - restrict an expression
expansion - a generalization of the differentiation process
inductive - build an automaton from an expression by inductive operations
infiltrate - infiltrate product of two expressions
info - a dictionary of facts about an expression
is_equivalent - whether two expressions denote the same series
is_valid - whether an expression is valid (denotes a series)
ldivide - left quotient of two expressions
lift - convert into a spontaneous expression
lweight - left scalar produt of an expression by a weight
multiply - product of expressions (i.e., concatenation)
partial_identity - from single-tape to double-tape expression
project - select a single tape from a multitape expression
rdivide - right quotient of two expressions
rweight - right scalar produt of an expression by a weight
shortest - the smallest denoted words
shuffle - shuffle product of expressions
split - break expressions that are sums into polynomials of expressions
standard - the "Position automaton", or "Glushkov automaton"
star_normal_form - an equivalent expression where stars are only on proper expressions
thompson - the Thompson automaton of an expression
transpose - reverse all the concatenations
transposition - add a "transposition" operator to an expression
tuple - Cartesian product of expressions
zpc - the ZPC automaton of an expression
Operations on Polynomials
Operators - a correspondance between Python operators and method names
add - addition of polynomials
conjunction - synchronized product of polynomials
cotrie - a reversed trie automaton from a polynomial (finite series)
ldivide - left quotient of two polynomials
lweight - left scalar product of a polynomial by a weight
multiply - product of polynomials
rweight - right scalar product of a polynomial by a weight
split - break expressions in polynomials of expressions
trie - trie automaton from a polynomial (finite series)
tuple - Cartesian product of polynomials