OctoPAs for Python

A Python interface to OctoPAs, a library for parametric automata and transducers. OctoPAs runs on the JVM, and this package drives it in-process through JPype.

Install

pip install octopas             # or "octopas[plot]" for drawing automata

You need Python 3.9 or newer and Java 17 or newer. The OctoPAs library is bundled with the package, so nothing else has to be built. If Java is not found, set JAVA_HOME to your JDK. Plotting also needs the Graphviz dot executable.

Parametric automata

A guard constrains the current symbol x. A parameter has one value for the whole accepting run:

import octopas as oc
from octopas import x

pa = oc.interval()
y = pa.parameter("y")

# Words whose last letter is strictly larger than all earlier ones.
a2 = pa.automaton(0, [1], [(0, x < y, 0), (0, x == y, 1)])
a2.accepts("abz")            # True
a2.witness("abz")            # {y: 122}

lower = pa.star_of(oc.between("a", "z"))
(a2 & lower).accepted_run()  # ([97], {y: 97})

To write guards, use x < y, x == y + 1, (x >= "a") & (x <= y), oc.between(lo, hi) or oc.any_symbol(). A bound can be an integer, a one-character string, a parameter plus an offset, or None for infinity.

These are the operators and methods on automata:

Linear guards

oc.linear() builds automata whose guards are Boolean combinations of comparisons between x, parameters plus offsets, and constants. Unlike an interval guard, a linear guard can constrain parameters on their own:

from octopas.linear import cmp

la = oc.linear()
p, q = la.parameter("p"), la.parameter("q")
a = la.automaton(0, [1], [(0, (x == p) & cmp(p, "<", q), 1)])
a.accepts_under([3], {p: 3, q: 4})   # True
a.accepts_under([3], {p: 3, q: 3})   # False

Interval guards such as x < p also work here. Combine guards with &, | and ~. The automata support &, |, ~ (pointwise complement), equivalent, accepted_run, accepts and accepts_under.

Active learning (PL*)

octopas.learning learns a parametrized automaton from membership queries under fixed parameter values and pointwise equivalence queries.

from octopas.learning import learn

target = la.automaton(0, [1], [(0, x < p, 0), (0, x == p, 1)])
result = learn(target)
result.hypothesis.equivalent(target)   # True
result.stats                            # queries, slices, time

By default the vocabulary is the set of terms in the target's guards. Pass Vocabulary.from_terms(...) to use another one.

Transducers

upper = pa.transducer(0, [0], [(0, oc.between("a", "z"), [x - 32], 0)])
upper.output_on("abc")       # [65, 66, 67]
image = upper(a2 & lower)    # exact image; guards become offsets of y
upper.preimage(image)
upper.then(other)            # composition: upper first, then other

An output is a sum of x, parameters, and constants. An exact operation that OctoPAs cannot represent raises oc.Unsupported. That is different from an empty result.

UTF-16 automata

These are parameter-free automata over code units 0..65535. They support exact complement and minimisation.

s = oc.utf16()
ident = s.range("a", "z") + s.range("a", "z").star()
(~ident).example()           # a word outside the language
(ident - s.word("abc")).accepts("abc")   # False
ident.minimize()

Plotting

a.plot("a.svg") writes a drawing. Without a file name, it returns a graphviz.Source, and automata also display inline in Jupyter. Highlighting follows Mata's Python binding:

a2.plot("a2.svg",
        node_highlight=[(lambda aut, q: q in aut.finals, {"fillcolor": "red"})],
        edge_highlight=[(lambda aut, e: e.guard == "{y}", {"style": "dashed"})])

Development

To work on the binding itself, build the JAR from source. You need a JDK (17 or newer) and sbt:

sbt pythonJar                # in the repository root: builds python/octopas/_jars/octopas-all.jar
python3 -m venv .venv        # a Python 3 environment; plain `pip` may be Python 2
source .venv/bin/activate
pip install -e "python[plot,test]"
python -m pytest python/tests

To use a JAR from somewhere else, set OCTOPAS_JAR=/path/to/octopas-all.jar.

License

MIT. See LICENSE.