automaton module

This module contains the Automaton class

class automaton.Automaton(nbL=0, nbS=0, initial=[], final=[], transitions=[])[source]

Bases: object

Define an automaton with parameters

  • Input:
Parameters:
  • nbL (int) – the number of letters
  • nbS (int) – the number of states
  • initial (list) – the initial vector
  • final (list) – the final vector
  • transition (list) – the transitions tables
BuildHankels(lrows=[], lcolumns=[])[source]

Return all Hankel (denses) matrices built on lrows and lcolumns

  • Input:
Parameters:
  • Output:
Returns:list of all Hankel matrices built on lrows and lcolumns
Return type:list
HouseholderReductionFw(tau)[source]

algorithm (Fig. 3) from the paper Stability and complexity of Minimising Probabilistic Automata by Kiefer and Wachter

  • Input:
Parameters:
  • self (Automaton) – an object of the automaton class
  • tau (float) – error tolerance parameter >=0
  • Output:
Returns:The canonical forward reduction computed to the tolerance tau
Return type:Automaton
static HouseholderReflector(x)[source]

the vector which defines the Householder for x

  • Input:
Parameters:x (vector) – a vector in R^k different from 0
  • Output:
Returns:v = u/||u|| where u_1 = x_1 + sign(x_1)||x|| and u_i = x_i for i \geq 2
Return type:vector
static SimpleExample()[source]

A Probabilistic Automaton with two states and two letters.

  • Output:
Returns:An automaton instance example with simple values
Return type:Automaton
calc_prefix_completion_weights(prefix)[source]

a sufficient condition to be absolutely convergent

  • Input:
Parameters:
  • self (Automaton) – Be careful that A should be a prefix transformation of an Automata. (see transformation())
  • prefix (List) – list of integers representing a prefix
  • Output:
Returns:a dictionary with all alphabet letters as keys. The associated values are the weights of being the next letter.
Return type:dict
final

The vector containing the final weight of each state

initial

The vector containing the initial weight of each state

isAbsConv

Does the automaton meet the sufficient condition to be absolutely convergent

static load_Spice_Automaton(adr)[source]

Load an automaton from a SPiCe file and returns an object of the class Automaton; works for PFA and PDFA - not for HMM.

minimisation(tau)[source]

compute an equivalent minimal automaton, to the precision tau

  • Input:
Parameters:self (Automaton) –
  • Output:
Returns:B, equivalent to A with a minimal number of states
Return type:Automaton
mirror()[source]

Compute the mirror automaton

  • Input:
Parameters:self (Automaton) – Automaton(nbL, nbS, initial, final, transitions)
  • Output:
Returns:mA = Automaton(nbL, nbS, final, initial, Newtransitions) where Newtransitions[x] = transpose(transitions[x])
Return type:Automaton
static mulHouseholderReflector(u, v)[source]

the product of u by the HouseholderReflector nxn matrix based on v

  • Input:
Parameters:
  • u (vector) – row vector of R^n
  • v (vector) – vector of R^k (k<=n)
  • Output:
Returns:w, row vector of R^n, w = uP(v) where P(v)=[I_{n-k} 0; 0 R]\in R^{n \times n} and R=I_k-2v^T.v
Return type:vector
nbL

The number of letters

nbS

The number of states

sum()[source]

the sum of a rational series

transformation(source='classic', target='prefix')[source]

Takes an automaton as input and transforms it.

  • Input:
Parameters:
  • source (str) – “prefix”, “factor” or “classic” (default)
  • target (str) – “prefix” (default), “factor” or “classic”
  • Output:
Returns:The result automaton instance
Return type:Automaton

The transformation is done according to the source and target parameters. .. warning:: it does not check the convergence
transitions

The list of arrays defining the transitions

val(word)[source]

Compute the value computed by the automaton on word

  • Input:
Parameters:
  • self (Automaton) – weighted automaton
  • word (str) – a string
  • Output:
Returns:probability r_A(w)
Return type:float