specless.automaton.mps.SWDFA_MPS

specless.automaton.mps.SWDFA_MPS(states: ~typing.Set[~typing.Hashable], start_state: ~typing.Hashable, F: ~numpy.ndarray, empty_symbol: ~typing.Hashable, node_index_map: <module 'bidict' from '/home/runner/.cache/pypoetry/virtualenvs/specless-uI3xtS-v-py3.10/lib/python3.10/site-packages/bidict/__init__.py'>, trans_prob_fcn: ~typing.Callable, transition_map: ~typing.Callable) → Tuple[Iterable[Hashable], float, List[Tuple[float, Tuple[Iterable[Hashable], Iterable[float]]]]][source]

Computes the EXACT consensus string (the actual most probable string (MPS)) for a stochastically weighted DETERMINISTIC finite automaton (SWDFA).

:warning THIS MPS CALCULATION IS ONLY VALID FOR A DETERMINISTIC AUTOMATA,

as this is a very fast greedy algorithm where the optimal substructure assumption only holds for deterministic automata.

Parameters:

  • states – The states of the automaton

  • start_state – The start state of the SWDFA

  • F – a (|states| x 1) vector containing the final state probabilities

  • empty_symbol – The empty symbol

  • node_index_map – a mapping from node label to it’s index in the vectorized representation of the automaton

  • trans_prob_fcn – a function that extracts the transition probabilities and associated symbols at the current state.

  • transition_map – a map of start state label and symbol to destination state

Returns:

(most probable word in the SWDFA, it’s probability, ALL viable strings in a max heap container)