Processes Documentation

This page contains the Processes Package documentation.

The period Module

Convenience functions for periodic processes.

cmpy.machines.processes.period.Period(P)

Constructs a periodic process with period P.

Parameters:

P : integer

The period of the process. The base word will be ‘0’*(P-1) + ‘1’.

Returns:

m : MealyHMM

The machine generating a period-P process.

cmpy.machines.processes.period.Period1(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period12(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period16(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period2(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period4(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period7(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Period8(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.period.Periodic(word, reduce=True)

Constructs a periodic process, cycling over the symbols of word.

Parameters:

word : array-like

The word which will be used to construct the periodic process. The period of the process will be equal to the length of word.

reduce : bool, True

When True, the periodicity of the word will be determined before create the states of the machine. If reduce is False, then the resulting machine might be non-minimal.

The noisyp2 Module

Noisy Period-2 Process

cmpy.machines.processes.noisyp2.NoisyPeriod2(noise=0.5)

Noisy Period-2 Process.

Alternate between 0 and 1. During the 1, output a 0 with noise.

Parameters:

noise : float

If a 1 is seen, we see 0 with p(0) = noise.

The coin Module

Coins

cmpy.machines.processes.coin.BiasedCoin(bias, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)
cmpy.machines.processes.coin.FairCoin(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)
cmpy.machines.processes.coin.IID(k, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Returns an IID process on k symbols.

If k is a list then it is used as the alphabet.

cmpy.machines.processes.coin.RandomBiasedCoin(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

The even Module

Even Process

cmpy.machines.processes.even.Even(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, bias=0.5)

Constructs a machine which generates the even process.

The bias specifies Pr(0|0).

cmpy.machines.processes.even.EvenRedundant(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, bias=0.5)

Returns the even process as a redundant, unifilar presentation.

cmpy.machines.processes.even.RandomEven(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

This function creates a random machine with the same template as the Even process. That is:

T^0 = [[x, 0], [0, 0]] T^1 = [[0, y], [1, 0]]

So instead of outputing a 0 or 1 with equal probability from node A, we uniformly select two numbers, which sum to one, as the probabilities.

cmpy.machines.processes.even.ThreEven(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Returns the three-symbol even process: any number of 0s, and only even numbers of 1s and 2s.

The odd Module

Odd Process

cmpy.machines.processes.odd.EvenOdd(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Returns a machine that produces an even number of 1s and an odd number of 0s.

cmpy.machines.processes.odd.Odd(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, bias1=0.5, bias2=0.5)

Constructs a machine which generates the odd process.

bias1 specifies Pr(0|0). bias2 specifies Pr(1|01).

cmpy.machines.processes.odd.OddGHMM(variant=1)
cmpy.machines.processes.odd.ThreEvenOdd(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Returns a machine that produces any number of 0s, an even number of 1s, and an odd number of 2s.

The rn1n Module

Rn1N - Random, Noisy 1 NOT

When synchronized to state A, the machine output is:
XYXYXYXY...

X is a random bit. When X=0, Y is the NOT of X. When X=1, Y is the noisy NOT of X.

Rn1N is a 2-block process that is strictly sofic, crytpic, irreversible, and has an infinite number of transient causal states.

cmpy.machines.processes.rn1n.Rn1N(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, bias=0.5, noise=0.1)

Constructs a machine which generates the Rn1N process.

Parameters:

machine_type : class

The type of machine used to create the process.

bias : float

Specification of Pr(0|A).

noise : float

Specification of Pr(1|C).

Returns:

machine : machine

A machine which generates the process.

The sns Module

Simple Non-Deterministic Source

cmpy.machines.processes.sns.SNS(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)

The irrev Module

Place for some helpful irreversible processes.

cmpy.machines.processes.irrev.IrreversibleTwoState(p=0.5, q=0.5, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

The rip Module

Random Insertion Process

cmpy.machines.processes.rip.RIP(p=0.5, q=0.5, reverse=False)

Random Insertion Process

This is 3-state machine #35 from topological eM enumeration.

The forward process has 3 recurrent causal states while the reverse process has 4 recurrent causal states.

Parameters:

reverse : bool, False

When True, return the reverse eM.

Returns:

m : RecurrentEpsilonMachine

The recurrent portion of the eM.

The alternatingbiasedcoins Module

Alternating Biased Coins

cmpy.machines.processes.alternatingbiasedcoins.ABC(p=0.75, q=0.25)

Alternating Biased Coins process.

The simplest non-exactly synchronizable machine.

Parameters:

p : float [0, 1], optional

The probability of 0 for the first coin.

q : float [0, 1], optional

The probability of 0 for the second coin.

The rrx Module

Random-Random-XOR Process

cmpy.machines.processes.rrx.RRX(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

The flower Module

Flower Process

cmpy.machines.processes.flower.Flower(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, N=4, M=3, forward_dist=None, reverse_dists=None)

Constructs a machine which generates the flower process.

N = number of states in forward eM M = number of states in reverse eM forward_dist = probability distribution for going from central state to each of the N-1 `petal’ states reverse_dists = N-1 probability distributions for going from each petal state back to the central state

each of these distributions is over the M return symbols.

The bandmerging Module

Band Merging Process

cmpy.machines.processes.bandmerging.BandMerging(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)

The cyclic Module

Cyclic Branching Processes

cmpy.machines.processes.cyclic.CyclicBranching(num_states, num_branchings, num_symbols=2)

Returns a noisy periodic process.

The first state transitions on a ‘0’ to the second state... The second state transitions on a ‘0’ to the third state...

The last num_branchings states transition on ‘0’ and ‘1’ with some probability. If uniform==True, then it is a 50/50 distribution.

The goldenmean Module

Golden Mean Process

cmpy.machines.processes.goldenmean.CoupledGMPs(epsilon=0.01, p=0.5, alt=True, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Two Coupled Golden Mean Processes.

Two components: (A,B) and (C,D) A and C are linked.

epsilon is the coupling strength.

p is the mixture probability of the (A,B) component as epsilon -> 0.

cmpy.machines.processes.goldenmean.GoldenMean(bias=0.5, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Constructs a machine which generates the Golden Mean process.

Parameters:

machine_type : machine class

Specifies the class of the presentation.

bias : float

Pr(B,0|A)

cmpy.machines.processes.goldenmean.GoldenMeanGHMM()
cmpy.machines.processes.goldenmean.NonunifilarGoldenMean(bias=0.5, free=0.6666666666666666)

2-state nonunifilar presentation of the Golden Mean process.

The function defines a parameterized family of 2-state presentations.

Parameters:

bias : float

The bias transition probabity Pr(B,0|A) of the Golden Mean eM. This can be between 0 < bias < 1.

free : float

A float satisfying bias <= float <= 1. The value specifies the probability of transitioning to B on a 0 from A: Pr(B,0|A), in the nonunifilar presentation. If p == .5, then we have the standard Golden Mean eM. If p == 1, then we have the time-reversed presentation of the Golden Mean eM. The default value is p=2/3, which is the parameter value that maximizes the state entropy.

Returns:

m : MealyHMM

The presentation generating the Golden Mean process.

cmpy.machines.processes.goldenmean.RandomGoldenMean(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

This function creates a random machine with the same template as the Golden Mean process. That is:

T^0 = [[0, x], [0, 0]] T^1 = [[y, 0], [1, 0]]

So instead of outputing a 0 or 1 with equal probability from node A, we uniformly select two numbers, which sum to one, as the probabilities.

cmpy.machines.processes.goldenmean.RestrictedGM(k)

Returns the Restricted Golden Mean Process, for the specified value of k.

For a given k value, create a machine that is k-cryptic. This machine should also be order-k Markov. Its name is derived from the fact that its support is a restriction of the support of the GM.

k=1 is the Golden Mean.

Parameters:

k : int

The desired cryptic order.

cmpy.machines.processes.goldenmean.RkGM(R, k)

Returns the R-k Golden Mean Process for the specified vlaues of R and k.

For the given R and k, create a machine that is order-max(R, k) Markov while being k-cryptic.

R=1, k=1 is the standard Golden Mean Process.

Parameters:

R : int

The desired Markov order.

k : int

The desired cryptic order.

Returns:

rkgm : MealyHMM

The R-k Golden Mean Process.

cmpy.machines.processes.goldenmean.StretchedGM(k)

Returns the Stretched Golden Mean Process, for the specified value of k.

For the given k value, create a machine that is 1-cryptic, but order-k Markov. While the GMP has all blocks of 0 of length 1, the Stretched Golden Mean process has all blocks of 0 of length k.

k=1 is the Golden Mean Process.

Also, for each value of k>1, H[k] != C_mu.

Parameters:

k : int

The desired cryptic order.

cmpy.machines.processes.goldenmean.UncoupledGMPs(p=0.5, machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Two Coupled Golden Mean Processes.

Two components: (A,B) and (C,D)

epsilon is the coupling strength.

p is the mixture probability of the (A,B)

The butterfly Module

Butterfly Process

cmpy.machines.processes.butterfly.Butterfly()

Butterfly Process.

Example machine for IAACP, original counterexample to results in IELBMOC.

Constructed such that:

C_mu - E neq H[S_0 | X_0, S_1].

The transducers Module

Example Transducers

cmpy.machines.processes.transducers.BinaryChannel(p=0.0, q=0.0, create_using=None)

Returns a general memoryless binary channel.

Parameters:

p : float

The probability of writing a 1 upon reading a 0.

q : float

The probability of writing a 0 upon reading a 1.

Interesting parameter values :

——- :

p = q : Binary symmetric channel (BSC)

q = 0 : Z-channel (noisy zero)

p = 0, q = 0 : Binary identity

p = 0, q = 1 : Always outputs period-1 zeros process

p = 1, q = 1 : Bit flip

p = .5, q = .5 : Always outputs fair coin

cmpy.machines.processes.transducers.BitFlip(create_using=None)
cmpy.machines.processes.transducers.Delay(length=2, symbols=2, create_using=None)

Returns a transducer which delays its input by an arbitrary amount. Currently, only the recurrent portion is constructed.

Parameters:

length : int

The delay length.

symbols : {int, list}

If a list, then symbols is the input and output alphabet of the transducer. If an integer, then the alphabet will be range(symbols).

cmpy.machines.processes.transducers.FlipEveryOther(parity='Even', create_using=None)
cmpy.machines.processes.transducers.GMtoEven(bias=0.5, create_using=None)
cmpy.machines.processes.transducers.Parity(create_using=None)

Returns the parity channel.

Y_t = 0 whenever an even number of ones has been input since the
last time an input was equal to zero.

Y_t = 1 otherwise

cmpy.machines.processes.transducers.RCT(bias=0.5, create_using=None)

Random, Copy Transducer

cmpy.machines.processes.transducers.SlidingNOR(create_using=None)

Returns the sliding NOR channel.

Y_t = NOT(X_{t-1} OR X_t)
cmpy.machines.processes.transducers.TwoPerm(symbols=2, create_using=None)

Returns a transducer which exchanges even and odd time indices of its input process. The transducer outputs this new process with a delay of one time step.

Parameters:

symbols : {int, list}

If a list, then symbols is the input and output alphabet of the transducer. If an integer, then the alphabet will be range(symbols).

The nrps Module

The Noisy Random Phase Slip process

cmpy.machines.processes.nrps.NRPS()

Returns the noisy random phase slip (NRPS) process.

States: 5 Alphabet: 2 ICDFA#: 38562

The analyticeven Module

Symbolic computations of the Even process.

cmpy.machines.processes.analyticeven.EvenAnalytic()

The cantor Module

Cantor Process

cmpy.machines.processes.cantor.Cantor(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)

The nemo Module

Nemo process

cmpy.machines.processes.nemo.Nemo(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, p=0.5, q=0.5)

Process which is not order-k cryptic for any finite k.

cmpy.machines.processes.nemo.NemoRedundant(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, p=0.5, q=0.5)

Process which is not order-k cryptic for any finite k.

The multiple Module

Generalized Even Processes

cmpy.machines.processes.multiple.Multiple3(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, bias=0.5)
cmpy.machines.processes.multiple.Multiple4(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, bias=0.5)
cmpy.machines.processes.multiple.MultipleN(n, machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, bias=0.5)

The misiurewicz Module

Misiurewicz

cmpy.machines.processes.misiurewicz.Misiurewicz(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.misiurewicz.MisiurewiczSimplified(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)
cmpy.machines.processes.misiurewicz.MisiurewiczUniform(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>)

The threehundred Module

A 6-state (recurrent states) eM with 300 causal states.

cmpy.machines.processes.threehundred.ThreeHundred(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>, biases=(0.5, 0.5, 0.5))

The beforeafter Module

Before-After Process

cmpy.machines.processes.beforeafter.BeforeAfter(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, style='simple')

The beadsonnecklace Module

Beads on Necklace Process

cmpy.machines.processes.beadsonnecklace.BeadsOnNecklace(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, beads=['a', 'b'], necklace=['0', '1', '3'], probs=0.5)

Constructs a machine which generates the Beads On Necklace process.

It is called this because the machine looks like a beaded necklace.

necklace - List specifying the symbols seen travelling around the necklace. beads - List of lists each specifying the symbols seen travelling around the bead.

If this is just a list, then repeat for each bead location.
probs - List of probabilities for moving from one bead attachment point to the next (vs cycling
through the bead again). If this is just a float, use this for each bead.
cmpy.machines.processes.beadsonnecklace.BeadsOnNecklace2(machine_type=<class 'cmpy.machines.mealyhmm.MealyHMM'>, beads=None, necklace=['a', 'b'], probs=0.5)

Constructs a machine which generates a generalized version of Beads On Necklace where the beads are machines.

necklace - List specifying the symbols seen travelling around the necklace. beads - List of machines at each bead location.

If this is just one machine, repeat for all locations.
probs - List of probabilities for moving from one bead attachment point to the next (vs cycling
through the bead again). If this is just a float, use this for each bead.

The rn1c Module

Random Noisy-1, Copy Process

cmpy.machines.processes.rn1c.Rn1C(noise=0.5, bias=0.5)

Random Noisy-1 Copy

Randomly choose 0 or 1. If 0, copy the result. If 1, copy the result with noise. Repeat ad infinitum.

Parameters:

noise : float

If a 1 is seen, we see 0 with p(0) = noise.

bias : float

Pr(0|A).

The rrxro Module

cmpy.machines.processes.rrxro.RRXRO(machine_type=<class 'cmpy.machines.epsilonmachine.RecurrentEpsilonMachine'>)

Returns the ‘Random-Random-XOR-Random-OR’ machine.

The rotation Module

A rotation GHMM.

Note: These won’t work until GHMMs are back in CMPy

cmpy.machines.processes.rotation.Oscillator()

Returns a rotation GHMM with rotation angle equal to 1 radian.

Anytime a ‘0’ is seen, we revert back to {‘A’: 0.75, ‘B’: 0, ‘C’: 0.25}. Also, p(1|1^k) oscillates like a sine wave as a function of k.

Source: Jaeger, H. Discrete-time, discrete-valued observable operator
models: a tutorial. Technical report, German National Research Center for Information Technology. GMD Report 42, 1998.
cmpy.machines.processes.rotation.Rotation(radians)

Returns a rotation GHMM.

Anytime a ‘0’ is seen, we revert back to {‘A’: 0.75, ‘B’: 0, ‘C’: 0.25}. Also, p(1|1^k) oscillates like a sine wave as a function of k.

Source: Jaeger, H. Discrete-time, discrete-valued observable operator
models: a tutorial. Technical report, German National Research Center for Information Technology. GMD Report 42, 1998.

The logic Module

Methods for computing machine which implement logical operations.

cmpy.machines.processes.logic.LogicMachine(logic, bias=0.5, noise=0.5, minimize=True)

Returns an MealyHMM which implements the specified logic operations.

The resulting machine will generate an r-block Markov chain where r is equal to the length of logic. For example, `logic`=’RRX’ specifies the random-random-xor process, which is a 3-block IID process.

Parameters:

logic : array-like

The string which specifies the logic of the machine. The language used to specify logic has the following symbols:

R - random bit with bias A - logical AND of the last 2 bits O - logical OR of the last 2 bits X - logical XOR of the last 2 bits N - logical NOT of the last bit C - logical COPY of the last bit

Modifiers are provided for N and C:

nN - noisy logical NOT of the last bit n0N - logical NOT of the last bit, noisy when last bit is 0 n1N - logical NOT of the last bit, noisy when last bit is 1

nC - noisy logical COPY of the last bit n0C - logical COPY of the last bit, noisy when last bit is 0 n1C - logical COPY of the last bit, noisy when last bit is 1

In the simplest case, logic can be any string in the following context-free grammar, where ‘a’,’b’,’c’, and ‘m’ are non-terminal variables and ‘a’ is the start variable:

a -> R | Rb b -> Rc | Nc | Cc | mNc | mCc c -> b | Ac | Oc | Xc m -> n | n0 | n1

Essentially, logic must start with an ‘R’ and you need at least two bits defined before you can specify a binary operator.

In the advanced case, any integer preceeding an operator (A,O,X,N,C) will specify the airty (or aryness) of the operator. For example, RRR3A specifies that the AND is over the last 3 bits, AND(R,R,R). Note that A,O,X require 2 or more bits while N and C require 1 or more. Thus, RR2A is equivalent to RRA, RN is equivalent to R1N, etc.

As an example of this advaned behavior, compare the following:

RRCC (suppose RR=01, then RRCC=0111) RR2C (suppose RR=01, then RR2C=0101)

In CC, the second C says to copy the first copied bit. In 2C, we copy the last two bits. Thus, CC != 2C.

bias : float

Whenever a random bit is drawn, Pr(1) = bias. If bias is a list of floats, then we will cycle through the elements each time a random bit is drawn. So logic`=’RRR’ and `bias`=[.3,.2] would draw the first and last random bit with Pr(1)=.3 and the second random bit with Pr(1)=.2. More generally, `bias can be anything with a next() method implemented. Then each time a random bit is needed, bias.next() is called to determine Pr(1).

noise : float

Whenever noise is needed, Pr(unintended event)=`noise`. If noise is a list of floats, then we will cycle through the elements each time a noisy bit is drawn. More generally, noise can be anything with a next() method implemented. Then each time a noisy bit is needed, noise.next() is called to determine Pr(unintended event).

minimize : bool

The resulting machine is guaranteed to be unifilar, but perhaps not the unique, minimal unifilar presentation. When minimize is True, we minimize the presentation before returning.

Returns:

m : MealyHMM

The machine generating the requested process.

Raises:

CMPyException :

Raised when logic is not a valid string.

The random Module

Module for functions/classes pertaining to building random HMMs.

cmpy.machines.processes.random.uniform_mealyhmm(topology, name=None, nodes=None, symbols=None, create_using=None, prng=None)

Returns a randomly constructed MealyHMM from a specified topology.

Parameters:

topology : {MealyHMM, dict, list}

A specification of the topology for the labeled transition matrices. If a machine is passed in, then constructed machine will have the same topology as the original machine. If a dict, then the keys specify the output symbols and the values should be NumPy arrays. The number of nodes in the machine is obtained from the shape of the NumPy arrays. If a list, then the entries should be NumPy arrays. The number of arrays determines the number of symbols.

name : {str, None}

The name to give the constructed machine.

nodes : {list, None}

The names to assign to the rows/cols of the topology. If None, then the nodes will be integers from 0.

symbols : {list, None}

The names to assign the matrices in topology (when it is a list). If unspecified, the symbols will be integers from 0.

create_using : {callable, None}

A callable which returns a machine instance to be populated. If None, then we use the MealyHMM class.

prng : random number generator

A random number generator which returns `k’ random numbers when `prng.rand(k)’ is called. If unspecified, then we use the random number generator at cmpy.math.prng.

Returns:

m : machine

The randomly constructed machine.

Examples

>>> m1 = cmpy.machines.Even()
>>> m2 = cmpy.machines.uniform_mealyhmm(m1)
cmpy.machines.processes.random.uniform_mealymc(order, symbols, name=None, create_using=None, prng=None)

Returns a random Markov chain of the specified order.

The Markov chain is drawn uniformly from the space of all Markov chains of the specified order and alphabet size.

Parameters:

order : int

The order of the Markov chain.

symbols : {int, list}

If a list, then symbols is the alphabet of the process. If an integer, then the alphabet will be range(symbols).

name : {str, None}

The name to give the constructed machine. If None, we use ‘Random Markov Chain’. In either case, we append ” (k=`order`)” to the name.

create_using : {callable, None}

A callable which returns a machine instance to be populated. If None, then we use the MealyHMM class.

prng : random number generator

A random number generator which returns `k’ random numbers when `prng.rand(k)’ is called. If unspecified, then we use the random number generator at cmpy.math.prng.

Returns:

m : machine

The random Markov chain.

See also

uniform_mealymc