Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 45856
Kernel: Python 3

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

Operations on Contexts

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