Python library for manipulating probabilistic automata.

# Probabilistic Automata

Python library for manipulating Probabilistic Automata. This library builds upon the `dfa` package.

# Installation

If you just need to use `probabilistic_automata`, you can just run:

`\$ pip install probabilistic_automata`

For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:

`\$ poetry install`

# Usage

The `probabilistic_automata` library centers around the `PDFA` object which models a finite probabilistic transition system, e.g., a Markov Decision Process, as a `DFA` or Moore Machine over a product alphabet over the system's actions and the environment's stochastic action.

```import probabilistic_automata as PA

def transition(state, composite_action):
sys_action, env_action = composite_action
return (state + sys_action + env_action) % 2

def env_dist(state, sys_action):
"""Based on state and the system action, what are the probabilities
of the environment's action."""

return {0: 1/2, 1: 1/2}  # Always a coin flip.

noisy_parity = PA.pdfa(
start=0,
label=bool,
inputs={0, 1},
env_inputs={0, 1},
outputs={0, 1},
transition=transition,
env_dist=env_dist,   # Equivalently, PA.uniform({0, 1}).
)
```

The support and transition probabilities can easily calculated:

```assert noisy_parity.support(0, 0) == {0, 1}
assert noisy_parity.transition_probs(0, 0) == {0: 1/2, 1: 1/2}
assert noisy_parity.prob(start=0, action=0, end=0) == 1/2
```

## Dict <-> PDFA

Note that `pdfa` provides helper functions for going from a dictionary based representation of a probabilistic transition system to a `PDFA` object and back.

```import probabilistic_automata as PA

mapping = {
"s1": (True, {
'a': {'s1': 0.5, 's2': 0.5},
}),
"s2": (False, {
'a': {'s1': 1},
}),
}

start = "s1"
pdfa = PA.dict2pdfa(mapping=mapping, start=start)
assert pdfa.inputs == {'a'}

mapping2, start2 = PA.pdfa2dict(pdfa)
assert start == start2
assert mapping2 == mapping
```

## DFA to PDFA

The `probabilistic_automata` library has two convenience methods for transforming a Deterministic Finite Automaton (`dfa.DFA`) into a `PDFA`.

• The `lift` function simply creates a `PDFA` whose transitions are deterministic and match the original `dfa.DFA`.
```import probabilistic_automata as PA
from dfa import DFA

parity = DFA(
start=0,
inputs={0, 1},
label=bool,
transition=lambda s, c: (s + c) & 1,
)

parity_pdfa = lift(parity)

assert pdfa.inputs == parity.inputs
assert pdfa.env_inputs == {None}
```
• The `randomize` function takes a `DFA` and returns a `PDFA` modeling the actions of the `DFA` being selected uniformly at random.
``````noisy_parity = PA.randomize(parity)

assert noisy_parity.inputs == {None}
assert noisy_parity.env_inputs == noisy_parity.inputs
``````

## Composition

Like their deterministic variants `PDFA` objects can be combined in two ways:

1. (Synchronous) Cascading Composition: Feed outputs of one `PDFA` into another.
```machine = noisy_parity >> noisy_parity

assert machine.inputs == noisy_parity.inputs
assert machine.outputs == noisy_parity.outputs
assert machine.start == (0, 0)

assert machine.support((0, 0), 0) == {(0, 0), (0, 1), (1, 0), (1, 1)}
```
1. (Synchronous) Parallel Composition: Run two `PDFA`s in parallel.
```machine = noisy_parity | noisy_parity

assert machine.inputs.left == noisy_parity.inputs
assert machine.inputs.right == noisy_parity.inputs

assert machine.outputs.left == noisy_parity.outputs
assert machine.outputs.right == noisy_parity.outputs

assert machine.env_inputs.left == noisy_parity.env_inputs
assert machine.env_inputs.right == noisy_parity.env_inputs

assert machine.start == (0, 0)
assert machine.support((0, 0), (0, 0)) == {(0, 0), (0, 1), (1, 0), (1, 1)}
```

Note Parallel composition results in a `PDFA` with `dfa.ProductAlphabet` input and output alphabets.

## Project details

This version 0.4.2 0.4.1 0.4.0 0.3.0 0.2.0 0.1.1 0.1.0