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 Labels¶

Operators - a correspondance between Python operators and method names
ldivide - Left quotient of labels
multiply - product of labels, i.e., concatenation
rdivide - Right quotient of labels

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

Operations on Weights¶

Operators - a correspondance between Python operators and method names
add - addition of weights
ldivide - left quotient of two weights
multiply - product of weights
rdivide - right quotient of two weights

Operations on Automata¶

Generic Operations on Automata¶

Operations on Transducers¶

Operations on Contexts¶

Operations on Expansions¶

Operations on Expressions¶

Operations on Labels¶

Operations on Polynomials¶

Operations on Weights¶

Operations on Automata ¶

Operations on Transducers ¶

Operations on Contexts ¶

Operations on Expressions ¶