FAdo.prax

Polynomial Random Approximation Algorithms

class Dirichlet(t=2.000001, d=1)[source]

Dirichlet distribution function

Parameters:
Return type:

float

New in version 2.0.4.

max_length(e)[source]

Computes the maximal length that needs to be considered for a given error

Parameters:

e (float) – error

Return type:

int

sum_list2(L, F)[source]
Returns the Dirichlet D_{t,d} probability of the set of words

which is the union of (1/2**F[i]) of the words of length L[i], for i=0,…,len(L)-1

Parameters:

  • t (float) – parameter in (1,+∞) of the Dirichlet distribution

  • d (int) – minimum length of a word w for which D_{t,d}(w)>0

  • L (list) – list of word lengths (integers)

  • F (list) – list of lengths (integers)

Return type:

DFA

sum_minus2(L, F)[source]

Returns the probability of the complement of the set referred to in the function sum_dirichlet_list2(t,d,L,F)

class GenWordDis(f, alf, e, strict=False)[source]

Word generator according to a given distribution function (used for sizes), for prax test

Variables:

  • sigma (list) – alphabet

  • pd (PDistribution) – distribution

  • e (float) – acceptable error

  • n_tries (int) – size of the sample

  • max_length (int) – maximal size of the words sampled

  • dist (list) – cumulative probability for each size considered (up to max_length)

class Lambert(d=1, z=0.9)[source]

Laplace distribution function

Parameters:

  • d (int) – displacement

  • z (float) – a number 9<z<1

Return type:

float

Raises:

FAdoGeneralError – if z is null

class PDistribution[source]

Probability Distribution

block_maximality_index(eps, a, prop)[source]
Maximality index of a block automaton for a given transducer property prop

Using approx tolerance eps

Parameters:

  • eps (float) – approximation tolerance

  • a (FA) – block automaton (accepting words of fixed length)

  • prop (IPTProp) – transducer property

Returns:

block maximality index

Return type:

float

block_unive_index(eps, a)[source]
Universality index of a block automaton (accepting words of fixed length)

Using approx tolerance eps

Parameters:

  • eps (float) – approximation tolerance

  • a (FA) – block automaton (accepting words of fixed length)

Returns:

block universality index

Return type:

float

maximal_index_p(g, aut, prop)[source]

Maximality index of a automaton for a given distribution and code property (parallel version)

Parameters:
Returns:

maximality index

Return type:

float

maximality_index(g, aut, prop)[source]
Maximality index (approximate) of a automaton for a given

distribution and transducer property prop

Parameters:

  • g (GenWordDis) – distribution

  • aut (FA) – automaton

  • prop (IPTProp) – transducer property

Returns:

universality index

Return type:

float

minI(a, t, u=None)[source]

An operator that returns a t-independent language containing L(a)

Parameters:

  • a (FA) – the initial automaton

  • t (Transducer) – input-altering transducer

  • u (FA | None) – universe to consider

Return type:

NFA

prax_block_maximal_nfa(eps, a, prop, debug=False)[source]
Polynomial Randomized Approximation (PRAX) for block NFA maximality

wrt a code property

Parameters:

  • eps (float) – approximation tolerance

  • a (FA) – block automaton (accepting words of fixed length)

  • prop (IPTProp) – transducer property

  • debug (bool) –

Return type:

bool

prax_block_univ_nfa(eps, a, debug=False)[source]

Polynomial Randomized Approximation (PRAX) for block NFA universality

Parameters:

  • eps (float) – approximation tolerance

  • a (FA) – block automaton (accepting words of fixed length)

  • debug (bool) –

Return type:

bool

See also

S.Konstantinidis, M.Mastnak, N.Moreira, R.Reis. Approximate NFA Universality and Related Problems Motivated by Information Theory, arXiv, 2022.

prax_maximal_nfa(g, a, prop, debug=False)[source]
Polynomial Randomized Approximation (PRAX) for NFA maximality wrt a code

property

Parameters:
Return type:

bool

prax_univ_nfa(g, a, debug=False)[source]

Polynomial Randomized Approximation (PRAX) for NFA universality

Parameters:

  • a (FA) – the automaton being tested

  • g (GenWordDis) – word generator

  • debug (bool) –

Return type:

bool

See also

S.Konstantinidis, M.Mastnak, N.Moreira, R.Reis. Approximate NFA Universality and Related Problems Motivated by Information Theory, arXiv, 2022.

New in version 2.0.4.

random() → x in the interval [0, 1).
unive_index(g, aut)[source]

Universality index (approximate) of an automaton for a given distribution

Parameters:
Returns:

universality index

Return type:

float