morphata 2.1.0

Representation theory for automata, made practical.

morphata

morphata does representation theory for automata, and makes it practical.

An automaton -- its states, transitions, and acceptance condition -- is a structural object. Operators turn that structure into a quantitative interpretation: a matrix-valued morphism over a semiring, a multilinear polynomial over a bounded distributive lattice, or a BDD-canonicalised symbolic representation. morphata packages both halves -- the structures and the morphisms that interpret them -- in one library.

It builds on algebraic for backend-agnostic semiring algebra (NumPy, JAX, PyTorch).

Quick Start

Installation

pip install morphata

Basic Usage

import algebraic
import jax.numpy as jnp
from morphata.builder import AutomatonBuilder
from morphata.alphabet import weighted_alphabet
from morphata.operators.matrix import MatrixOperator
import logic_asts as logic

builder: AutomatonBuilder[int, str] = AutomatonBuilder()
builder.add_state(0, initial=True)
builder.add_state(1, accepting=True)
builder.add_transition(0, guard=logic.Variable("a"), succ=1)
aut = builder.build()

def xi(x, guard):
    return float(x[0])

alphabet = weighted_alphabet(xi=xi)
maxplus = algebraic.semirings.tropical_semiring(minplus=False)
op = MatrixOperator.from_nfa(aut, semiring=maxplus, alphabet=alphabet)

x = jnp.array([2.0])
transitions = op.cost_transitions(x)

For more, see the documentation.

Citation

If you use the matrix operator or this package, please cite one of:

• For differentiable weighted automata in general:

@inproceedings{balakrishnan2024differentiable,
  title = {Differentiable {{Weighted Automata}}},
  booktitle = {{{ICML}} 2024 {{Workshop}} on {{Differentiable Almost Everything}}: {{Differentiable Relaxations}}, {{Algorithms}}, {{Operators}}, and {{Simulators}}},
  author = {Balakrishnan, Anand and Deshmukh, Jyotirmoy V.},
  year = 2024,
  month = jun,
  url = {https://openreview.net/forum?id=k2hIQYqHTh},
  copyright = {All rights reserved},
  langid = {english}
}

• For weighted automata in motion planning:

@inproceedings{balakrishnan2024motion,
  title = {Motion {{Planning}} for {{Automata-based Objectives}} Using {{Efficient Gradient-based Methods}}},
  booktitle = {2024 {{IEEE}}/{{RSJ International Conference}} on {{Intelligent Robots}} and {{Systems}} ({{IROS}})},
  author = {Balakrishnan, Anand and Atasever, Merve and Deshmukh, Jyotirmoy V.},
  year = 2024,
  month = oct,
  pages = {13734--13740},
  issn = {2153-0866},
  doi = {10.1109/IROS58592.2024.10802177}
}

• For alternating weighted automata in multi-agent systems:

@inproceedings{balakrishnan2025monitoring,
  title = {Monitoring {{Spatially Distributed Cyber-Physical Systems}} with {{Alternating Finite Automata}}},
  booktitle = {Proceedings of the 28th {{ACM International Conference}} on {{Hybrid Systems}}: {{Computation}} and {{Control}}},
  author = {Balakrishnan, Anand and Paul, Sheryl and Silvetti, Simone and Nenzi, Laura and Deshmukh, Jyotirmoy V.},
  year = 2025,
  month = may,
  pages = {1--11},
  publisher = {ACM},
  address = {Irvine CA USA},
  doi = {10.1145/3716863.3718033},
  isbn = {979-8-4007-1504-4},
  langid = {english}
}

License

See LICENSE file for details.