Operations on Automata

Generic automata operations

  • operators - a correspondance between Python operators and method names
  • accessible - the subautomaton of accesssible states
  • ambiguous_word - a witness of ambiguity
  • coaccessible - the subautomaton of coaccesssible states
  • codeterminize - the transposed of the subset construction
  • complement - an automaton accepting the complement language
  • complete - a complete superautomaton
  • 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
  • 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_twins_property - a condition for determinizability in tropical semirings
  • infiltration - infiltration product of two automata
  • info - a dictionary of facts about an automaton
  • 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_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_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
  • 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
  • minimize - minimizing an automaton
  • pair - the pair automaton, useful for computing synchronizing words
  • 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)
  • 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
  • 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
  • type - the implementation type of an automaton

Operations on Transducers

Operations on Contexts

  • 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
  • trie - trie automaton from a file of (weighted) words

Operations on Expressions

  • operators - a correspondance between Python operators and method names
  • automaton - build an automaton from an expression
  • conjunction - synchronized product of expressions
  • complement - complement 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
  • is_equivalent - whether two expressions denote the same series
  • is_valid - whether an expression is valid (denotes a series)
  • multiply - product of expressions, i.e., concatenation
  • shortest - the smallest denoted words
  • standard - the "Position automaton", or "Glushkov automaton"
  • star_normal_form - an equivalent expression where stars are only on proper expressions
  • sum - addition of expressions
  • thompson - the Thompson automaton of an expression
  • transpose - reverse all the concatenations
  • transposition - add a "transposition" operator to an expression
  • zpc - the ZPC automaton of an expression

Operations on Labels

  • operators - a correspondance between Python operators and method names

Operations on Polynomials

  • operators - a correspondance between Python operators and method names
  • cotrie - a reversed trie automaton from a polynomial (finite series)
  • multiply - product of polynomials
  • trie - trie automaton from a polynomial (finite series)

Operations on Weights

  • operators - a correspondance between Python operators and method names