posetta-stone 0.1.0

Exploratory tools for finite posets and related combinatorial analyses.

Posetta Stone

A lightweight exploratory framework for studying finite partially ordered sets (posets), dependency structures, and their combinatorial behavior.

Dependencies naturally occur in many contexts: tasks that must wait for others to finish before they begin or pre-requisites that must be satisfied before work can continue. These constraints can create bottlenecks by limiting what is available when.

These dependencies can be represented mathematically using partially ordered sets, shortened to posets. Posets are collections where individual items can be ordered relative to each other, but not enough to reduce the entire system to a single clean ordering. Posets can be represented as directed acyclic graphs, which lets us study these dependencies using combinatorial and graph-theoretical methods.

This library focuses on exploring finite posets through dependency analysis, linear-extension enumeration, order-ideal traversal, and related combinatorial methods. From there, related structures such as incidence algebras and residual graphs emerge naturally, exposing new perspectives on the underlying posets. Incidence algebras allow us to compactly define propagation structures which in turn allows us to model domain-specific dependency structures. In fact, many domain models reuse the same propagation rules differing primarily in interpretation.

This project is currently an exploratory research-oriented implementation under active development.

Current Capabilities

• Poset construction and validation
  Hasse diagram representation with cycle detection and parent/child adjacency maps.

• Poset factories for known families
  Built-in constructors for well-known benchmark poset families

• Exact linear-extension enumeration
  Memoized recursion over dual order ideals $\mathcal{O}(2^n)$ worst-case).

• Order-ideal traversal and lattice-layer analysis
  Groups ideals by rank to visualize the structure of the distributive lattice $J(P)$.

• Zeta and Mobius incidence utilities
  Computes zeta and Mobius matrices, supports zeta transforms with Mobius inversion, and reports transitive-closure comparability summaries.

• Compact interval, zeta, and Mobius summaries
  Reports aggregate interval and incidence statistics without returning full matrices by default.

• Dependency Models
  Attaches values to intervals, elements, and edges according to the incidence algebra of a particular domain-specific model. Examples include max-plus, probability, and numeric algebras.

Example Summary

The following creates a Boolean Lattice $B_2$ and runs the main analyzer summary.

from posetta_stone.analysis import PosetAnalyzer
from posetta_stone.families import boolean_lattice


poset = boolean_lattice(2)
analyzer = PosetAnalyzer(poset)

summary = analyzer.summary()

For the Boolean lattice $B_2$, PosetAnalyzer.summary() returns:

{
    "num_elements": 4,
    "num_relations": 4,
    "num_minimals": 1,
    "num_maximals": 1,
    "height": 3,
    "width": 2,
    "num_linear_extensions": 2,
    "num_ideals": 6,
    "lattice_layer_sizes": [1, 1, 2, 1, 1],
}

See test_example_usage.py for the full suite.

Model Examples

Incidence algebras let the same poset carry domain-specific values. A probability model can treat cover relations as transition probabilities and ask for the total probability of all finite paths between two comparable states.

from posetta_stone.algebras import IncidenceAlgebra
from posetta_stone.families import boolean_lattice


states = boolean_lattice(2)
probability = IncidenceAlgebra.probability()
transitions = probability.model(
    states,
    {
        ("{}", "{1}"): 0.8,
        ("{}", "{2}"): 0.6,
        ("{1}", "{1, 2}"): 0.7,
        ("{2}", "{1, 2}"): 0.5,
    },
)

analyzer = transitions.analyzer()
probability_of_completion = analyzer.total_path_probability("{}", "{1, 2}")

Here probability_of_completion is 0.86: the sum of the two possible two-step paths through {1} and {2}.

For workflow analysis, a max-plus model can treat edge values as task or handoff durations and ask for the critical path through an arbitrary dependency poset.

from posetta_stone.algebras import IncidenceAlgebra
from posetta_stone.poset import Poset


workflow = Poset(
    {"spec", "api", "ui", "data", "review", "ship"},
    [
        ("spec", "api"),
        ("spec", "ui"),
        ("spec", "data"),
        ("api", "review"),
        ("ui", "review"),
        ("data", "review"),
        ("review", "ship"),
    ],
)

max_plus = IncidenceAlgebra.max_plus()
durations = max_plus.model(
    workflow,
    {
        ("spec", "api"): 3,
        ("spec", "ui"): 5,
        ("spec", "data"): 2,
        ("api", "review"): 4,
        ("ui", "review"): 2,
        ("data", "review"): 6,
        ("review", "ship"): 1,
    },
)

critical_path_length = durations.analyzer().best_path_value("spec", "ship")

Here critical_path_length is 9, coming from the longest weighted dependency path spec -> data -> review -> ship.

Research Focus

Current work centers on:

• exact linear-extension counting,
• traversal of order ideals,
• lattice-layer analysis,
• Mobius inversion and incidence-style poset invariants,
• structural memoization strategies for repeated subproblems,
• exploring canonical workflow families,
• convolution over defined incidence algebras,
• modeling domain-specific dependency structures,
• and eventually providing ML-usable feature vectors.

Development Philosophy

This project doubles as a self-apprenticeship in algorithmic thinking, software architecture, and best practices. This project is also being used to test how well I can leverage AI's strengths without losing cognitive agency.

All algorithms are reconstructed through first principles, then sent to AI to speed up cross-checking against known and verified algorithms, and help provide both formal vocabulary and relevant literature. Mathematical reasoning originates from my own understanding, and final architectural decisions are done by me.

Repo Setup

Create and activate a virtual environment:

python -m venv .venv
source .venv/bin/activate

Install Python dependencies:

python -m pip install -r requirements.txt

This project includes a Rust-backed transitive-closure backend built through Maturin/PyO3. To use it, install Rust/Cargo if needed, then build the extension into the active virtual environment:

python -m maturin develop

If the Rust extension is not built, the Python closure backend is used as a fallback.

To verify which backend is active:

from posetta_stone.backend import backend_status


backend_status().as_dict()

When the Rust extension is active, incidence_backend reports "rust" for the accelerated incidence kernels. Some Rust functions may still be disabled by default when the Python path is faster; disabled_rust_functions reports those policy-disabled operations.

Running Tests

Activate the virtual environment and run:

pytest

Documentation

See docs/workflow_families.md for canonical structural benchmark families and motivating examples.

See docs/logs for session summaries and docs/transcripts for raw curated transcripts of sessions.

License

This project is licensed under the MIT License - see the LICENSE file for details.