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
  • eval - 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

Operations on Expansions

  • operators - a correspondance between Python operators and method names
  • add - addition of 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

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
  • 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)
  • lift - convert into a spontaneous expression
  • lweight - left scalar produt of an expression by a weight
  • multiply - product of expressions (i.e., concatenation)
  • project - select a single tape from a multitape expression
  • rweight - right scalar produt of an expression by a weight
  • shortest - the smallest denoted words
  • shuffle - shuffle product 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
  • multiply - product of labels, i.e., concatenation

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)
  • multiply - product of polynomials
  • 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
  • multiply - product of weights