Skip to main content

Python library for manipulating probabilistic automata.

Project description

Probabilistic Automata

Build Status Docs codecov PyPI version License: MIT

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

Table of Contents

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 PDFAs 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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for probabilistic-automata, version 0.4.0
Filename, size File type Python version Upload date Hashes
Filename, size probabilistic_automata-0.4.0-py3-none-any.whl (9.6 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size probabilistic_automata-0.4.0.tar.gz (10.2 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page