transCSSR: Causal State Splitting Reconstruction for epsilon-transducers

A Python implementation of the Causal State Splitting Reconstruction (CSSR) algorithm for inferring epsilon-transducers from data generated by discrete-valued, discrete-time input/output systems. This library learns the underlying causal structure of a system from observed sequences, and uses it to filter causal states and predict future outputs.

As of version 1.1, the primary interface is the token-first transcssr package: sequences of arbitrary hashable tokens (integer ids from an NLP tokenizer, strings, tuples, ...) are first-class inputs. Single-character strings are just one token type among many. The original flat transCSSR.py module remains importable and unchanged as a legacy interface; see MIGRATION.md if you are upgrading existing code.

This implementation has been tested on macOS but should work on any Unix-based OS.

Key Features

• Token-first inputs: Work directly with list[int] token streams, strings, tuples, or 1-d NumPy arrays. No more "one character = one symbol" restriction.
• Causal State Inference: Learns the minimal set of causal states that explains the observed input/output sequences, including memoryful transducers whose state depends on past history.
• Predictive Modeling: Filters causal states and predicts future outputs from past observations, returning the full per-step output distribution.
• Statistical Hypothesis Testing: Chi-squared and G-tests compare predictive distributions to decide state equivalence.
• Serialization & Visualization: Round-trip models to versioned JSON, and export Graphviz .dot files for visualization.
• Lightweight dependencies: The transcssr package needs only numpy and scipy.

Installation

The canonical workflow uses uv. From a clone of the repository, uv sync creates a virtual environment, pins the interpreter (see .python-version), and installs the project from the locked uv.lock:

uv sync                 # runtime deps (numpy, scipy) + the transcssr package
uv sync --group dev     # add the full test/dev toolchain (see Testing)

Run anything inside the managed environment with uv run, e.g. uv run python examples/demo_CSSR.py (from the repo root).

Prefer uv pip or plain pip? Editable installs work too:

uv pip install -e .          # or: pip install -e .
uv pip install -e ".[legacy]"  # add the legacy/demo extras

Or install directly from GitHub:

pip install git+https://github.com/ddarmon/transCSSR

Dependencies: The token-first transcssr package requires only numpy and scipy. The legacy interface and the demo scripts need additional packages (python-igraph, pandas, matplotlib, joblib, tqdm), installable as the optional [legacy] extra shown above.

Python 3.10 or newer is required.

Graphviz

Rendering the exported .dot files requires Graphviz or similar software for reading dot files. To render inside a Jupyter notebook, install the graphviz Python package:

pip install graphviz

Quickstart 1: an epsilon-machine from the even process

The even process emits blocks of 1s of even length separated by 0s. It is a classic two-state process for an output-only source. Here we infer its epsilon-machine, inspect it, filter causal states, and export a .dot visualization.

from transcssr import infer_machine

# Load the output-only sequence (each character is one token).
ys = open("data/even.dat").readline().strip()

# Infer the epsilon-machine.
machine = infer_machine(ys, L_max=3, alpha=0.001)
print(machine.n_states)                # -> 2

# Filter the causal-state path and the per-step output distribution.
result = machine.filter(ys)
print(result.states[:12])              # -1 while unsynchronized, then 0/1
print(result.prediction_probs.shape)   # (len(ys), 2)

# Export a Graphviz .dot for visualization.
machine.to_dot("even.dot")

infer_machine returns an EpsilonMachine (the output-only special case of an EpsilonTransducer, whose input is a single dummy token). Its filter method takes just the output sequence. result.states holds one causal-state label per time step (-1 before the filter synchronizes), and result.prediction_probs is a dense (T, n_y) array of the predicted next-symbol distribution at every step.

Quickstart 2: an epsilon-transducer over integer tokens

Tokenizers turn words into integer ids. infer_transducer consumes those list[int] streams directly. Here a toy vocabulary drives a next-token prediction problem: the input at each step is the current word id and the output is the next word id. Because the word "the" is followed by two different words depending on context, predicting the next token requires memory --- exactly what causal states provide.

from transcssr import infer_transducer, EpsilonTransducer

# A toy tokenizer: words <-> integer ids, like an NLP vocabulary.
vocab = {"the": 0, "cat": 1, "sat": 2, "dog": 3, "barked": 4}
inv_vocab = {i: w for w, i in vocab.items()}

# A tiny deterministic "grammar": two sentences, repeated.
sentence = ["the", "cat", "sat", "the", "dog", "barked"]
corpus = [vocab[w] for w in sentence] * 200      # a list[int] token stream

# Next-token prediction: input is the current token, output is the next.
xs = corpus[:-1]
ys = corpus[1:]

model = infer_transducer(
    xs, ys, L_max=2, alpha=0.001,
    input_alphabet=list(vocab.values()),
    output_alphabet=list(vocab.values()),
)
print(model.n_states)      # -> 3 (to disambiguate the two uses of "the")

# Predict the next token at each step; None marks unsynchronized steps.
result = model.filter(xs, ys)
predicted_words = [inv_vocab[t] if t is not None else None
                   for t in result.predictions]
print(predicted_words[1:7])   # ['sat', 'the', 'dog', 'barked', 'the', 'cat']

# JSON round-trip: serialize and restore the model.
model.to_json("transducer.json")
restored = EpsilonTransducer.from_json("transducer.json")
print(restored.n_states)      # -> 3

result.predictions is a list of predicted output tokens (integers here), which decode straight back to words through inv_vocab; None marks steps where the filter has not yet synchronized. to_json / from_json serialize the full model --- alphabets, partition, and morph counts --- to a versioned JSON document.

These two quickstarts are executed verbatim as tests in tests/test_readme_examples.py, so the code above is guaranteed to run.

Command-line interface

Installing the package (via uv sync or pip install -e .) also installs a transcssr command. It wraps the same engine as the Python API in four subcommands: infer, filter, show, and export-dot. Run any of them inside the managed environment with uv run.

Infer the even-process epsilon-machine and inspect it:

uv run transcssr infer -y data/even.dat -L 3 -o even.json
# stderr: infer: machine, 2 state(s), n_y=2, L_max=3.

uv run transcssr show -m even.json
# kind: machine
# n_states: 2
# L_max: 3
# output_alphabet (2): '0', '1'
# ...per-state emission-probability table...

Infer an epsilon-transducer from a delay channel (pass -x for the input stream) and export a Graphviz .dot:

uv run transcssr infer -y data/Yt_delay-channel.dat -x data/Xt_delay-channel.dat \
    -L 2 -o delay.json
uv run transcssr export-dot -m delay.json -o delay.dot

Filter a data file through a trained model, writing a CSV of the filtered state, MAP prediction, and per-output-token probabilities to stdout (or to -o FILE):

uv run transcssr filter -m even.json -y data/even.dat -o even_filtered.csv
# columns: t,state,prediction,p_0,p_1

Data-reading options are shared by infer and filter: --format chars (default; each character a token, the legacy .dat convention) or --format tokens (whitespace-separated tokens, with --token-type auto|int|str); --multiline treats each nonempty line as one realization (an ensemble). User errors (missing file, bad format, machine/transducer mismatch) exit with code 2 and a one-line message. uv run transcssr --version prints the version.

API overview

from transcssr import (
    Alphabet,           # token <-> index bijection
    EpsilonMachine,     # output-only causal-state model
    EpsilonTransducer,  # input/output causal-state model
    infer_machine,      # epsilon-machine from an output-only process
    infer_transducer,   # epsilon-transducer from an input/output process
)

Sequence input. Every public entry point accepts a str (each character a token), a list/tuple of tokens, or a 1-d numpy.ndarray. An ensemble of realizations (the legacy is_multiline=True) is a list whose elements are themselves sequences; a list of scalar tokens (e.g. list[int]) is a single realization. Ensembles are detected by type, not by a flag. Two traps follow: a single sequence of tuple tokens [(0,0), (0,1), ...] or of multi-character word tokens ['the', 'cat', ...] auto-detects as an ensemble. Pass ensemble=False to force single-sequence handling (ensemble=True forces ensemble handling; None, the default, auto-detects).

Inference. infer_transducer(xs, ys, L_max, alpha=0.001, test="chi2", input_alphabet=None, output_alphabet=None, stats_mode="correct", ensemble=None) learns P(Y_t | X_t, X_past, Y_past). infer_machine(ys, L_max, ..., ensemble=None) is the output-only case. Alphabets may be passed explicitly (an Alphabet or a token list) or inferred from data (None).

Filtering / prediction. model.filter(xs, ys) (or machine.filter(ys) for an epsilon-machine) returns a FilterResult with .states (one causal-state label per step; -1 = unsynchronized), .predictions (the MAP next-output token per step; None where unsynchronized), and .prediction_probs (a dense (T, n_y) array of per-step output distributions).

Serialization / export. model.to_json(path) / EpsilonTransducer.from_json(path) round-trip the model as versioned JSON. model.to_dot(path) writes a Graphviz visualization. DOT is export-only and is never re-parsed.

stats_mode. The morph-comparison statistic defaults to stats_mode="correct" (the mathematically correct per-input-symbol stride). Pass stats_mode="legacy" only to reproduce the legacy engine's stride bug exactly; the two agree unless the number of input symbols is neither 1 nor equal to the number of output symbols. See MIGRATION.md for details.

Legacy interface

The original flat module remains importable and unchanged:

from transCSSR import (
    estimate_predictive_distributions,
    run_transCSSR,
    filter_and_predict,
)

It operates on single-character strings and returns the classic (epsilon, invepsilon, morph_by_state) structures. It serves as the parity oracle for the new engine and still backs the demo scripts. If you have existing code on this API, it keeps working; see MIGRATION.md for the old-function -> new-API mapping, the behavioral differences, and what remains legacy-only for now.

Demo scripts (legacy engine)

The demo scripts in examples/ exercise the legacy engine and require the [legacy] extra. Run them from the repo root (the legacy engine writes into transCSSR_results/ relative to the working directory):

• examples/demo_transCSSR.py: end-to-end inference of an epsilon-transducer and prediction, including plots.
• examples/demo_CSSR.py: epsilon-machine inference and prediction.
• examples/demo_computational_mechanics_bootstrap.py: bootstrapping to assess the statistical reliability of inferred models.

See examples/README.md for the experimental scripts and the data-generation code behind the datasets in data/.

Data formats (legacy engine)

The legacy engine accepts data in two formats:

Single sequence. stringX and stringY are strings whose characters are the input and output symbols at each time step.

Ensemble (multiple sequences). With is_multiline=True, stringX and stringY are lists of strings, one independent realization each:

stringX_list = ['abacabac', 'babacaba', 'cabacabc']
stringY_list = ['01000100', '10100101', '00100010']

word_lookup_marg, word_lookup_fut = estimate_predictive_distributions(
    stringX_list, stringY_list, L_max,
    axs=axs, ays=ays, is_multiline=True
)

All sequences in an ensemble must share the same alphabets, and corresponding input/output sequences must have equal length. (In the token-first transcssr package, the same data would be passed as stringX_list / stringY_list directly --- an ensemble is detected by type, with no is_multiline flag.)

Project structure

• transcssr/: the token-first package (primary interface). Modules: alphabet, counting, stats, cssr, machine, predict, api.
• transCSSR.py, filter_data_methods.py: the legacy flat modules (parity oracle + demo backend). Importable from a repo checkout only; they are deliberately not part of the installed distribution (see MIGRATION.md).
• docs/DESIGN.md, docs/SPEC-core.md: the architectural and behavioral contracts for the rewrite.
• tests/: unit and parity tests, with captured legacy outputs in tests/golden/.
• examples/: legacy-engine demos and notebooks, experimental research scripts, and the data-generation code for data/.
• data/: datasets used by the demos and quickstarts.

Testing

Install the dev toolchain and run the full suite with uv:

uv sync --group dev
uv run python -m pytest -q     # 144 passed

The dev dependency group installs pytest plus the [legacy] extras, so the legacy-parity tests (which import the legacy engine) run too. The two README quickstarts above are executed verbatim by tests/test_readme_examples.py, so passing the suite confirms they work.

Contributing

Contributions, bug reports, and feature requests are welcome. Please open an issue or submit a pull request on the GitHub repository.

License

This project is licensed under the GNU Public License.

---

A legacy version of transCSSR for Python 2.7 is hosted here.