stackdump

Things I learned while programming as a Petri-net maximalist.

The early web was meant to be a decentralized, user-owned hypertext system — a living web of information. Today, we've ended up with centralized silos where link previews, discovery, and even metadata are controlled by corporate platforms.

Gno.land gives us a chance to course-correct.

On Gno.land:

  • Metadata can be user-generated and stored directly in realms, without needing external servers or private APIs.
  • Previews can be computed deterministically from shared, verifiable code.
  • Users can own and fork content, making information remixable and participatory again — not just locked inside engagement farms.
  • Discovery can be peer-to-peer, with realms linking to each other openly, not filtered through black-box algorithms.

The goal isn’t just better previews. It’s restoring the editable, decentralized, user-sovereign spirit that the Web was supposed to have.

It starts simple: make the link structure public, verifiable, and open for everyone to extend.

Gno.land can be that foundation.

🚀 I’m working to build a Gno.land package: /p/pflow/metamodel ! (WIP on github)

  • Using Pflow means Gno developers can embed Petri nets directly inside their contracts without requiring external servers.
  • Petri net models are encoded in JSON or SVG, base64-encoded, and rendered inline using data URLs.

How This Works: Petri Nets in Gno

The p/pflow/metamodel package now includes a set of functions that allow Petri nets to be declared and then serialized as:

  1. JSON Data URLs (for programmatic consumption)

  2. SVG Data URLs (for direct visualization in Gno Markdown)

  3. Markdown Image Embeds (to display Petri nets inside contract descriptions)

  4. Markdown Hyperlinks (to share and interact with Petri nets on external viewers)

See an example of how to use this on my home realm: /r/stackdump/home

Declarative Differential Models (DDM) refer to a modeling approach where the entire system's behavior—states, transitions, constraints, and objectives—is described declaratively and encoded directly within a set of differential equations or differential-algebraic equations (DAEs).

Key Features of DDM:

  1. Declarative Nature:

    • The system is described by its rules and relationships, not step-by-step instructions.
    • These rules are translated into continuous or discrete dynamics that govern the system's evolution.

  2. Constraint Embedding:

    • Logical and physical constraints (e.g., conservation laws, capacity limits) are directly included in the model equations.
    • This ensures the system operates within valid bounds without requiring external enforcement.

  3. Dynamic and Adaptive Behavior:

    • DDMs can handle both deterministic and probabilistic transitions, making them suitable for hybrid systems (e.g., mixing continuous flows and discrete events).

  4. Optimization-Friendly:

    • DDMs naturally integrate with optimization techniques, allowing parameters (e.g., transition rates) to be learned or fine-tuned directly within the model.

Examples and Applications:

  • Petri Nets: Encoding resource flows, transitions, and state changes as ODEs.
  • Hybrid Systems: Combining discrete decision-making with continuous dynamics.
  • Physics-Inspired Machine Learning: Embedding physical constraints within Neural ODEs.
  • Optimal Control: Modeling decision problems directly in the dynamics for optimization.

Why Declarative?

The term “declarative” emphasizes that the model focuses on what the system does (rules and behaviors) rather than how it does it (procedural steps).

Use Case Example:

In a knapsack optimization problem:

  • States represent item availability, weight, and value.
  • Transitions represent decisions to include/exclude items.
  • Constraints (e.g., weight capacity) are encoded directly into the model dynamics, making the system solvable and interpretable.

See the python notebook

Continuous relaxation is a bridge between discrete and continuous domains, offering a powerful way to analyze complex problems by leveraging continuous mathematics. It is widely used across fields like optimization, physics, and systems modeling.

Using Continuous Relaxation with Petri Nets

Petri nets provide a robust framework for modeling the dynamics of Tic-Tac-Toe, extending beyond traditional game-tree analysis. By incorporating continuous relaxation, this approach transforms discrete moves and outcomes into a probabilistic system, making it possible to analyze strategic nuances using differential equations.

Modeling Tic-Tac-Toe as a Petri Net

In this model:

  • Places represent the grid's state, such as unclaimed cells (P00) and markers for Players X and O (e.g., X00 for Player X's mark in the top-left cell).
  • Transitions represent possible moves (e.g., Player X marking X00) and win conditions (e.g., X00_X01_X02 for a row win).
  • Tokens track the system's state, where a token in P00 indicates the top-left cell is unclaimed, while a token in X00 or O00 indicates it is marked by X or O.

Relaxing the System

Discrete moves are relaxed into continuous transitions, allowing the use of ODE solvers. For example:

  • A transition's firing rate represents the probability of a specific move, creating a probabilistic view of gameplay.
  • The win states (win_x, win_o) are modeled as accumulative probabilities derived from successful transition sequences.

Analyzing Strategies

By solving the ODEs, we can:

  1. Predict Win Probabilities: The probabilities of win_x and win_o over time show the likelihood of each player achieving victory.

  2. Evaluate Moves: The model ranks potential moves by their impact on the win probabilities, guiding optimal strategies.

  3. Visualize Dynamics: Plots of win probabilities provide insights into how the game evolves based on current states and potential player decisions.

Conclusion

This Petri-net-based continuous relaxation approach brings a novel lens to Tic-Tac-Toe analysis. By transitioning from discrete moves to probabilistic trajectories, we uncover richer strategic insights and establish a framework applicable to more complex games and systems.

Review the code from previous post where we apply this approach using Juila and Petri.jl

Optimization problems, like the knapsack problem, often invite varied approaches. At first glance, advanced methods might seem complex compared to classic algorithms. Surprisingly, this isn’t always true. In this post, we compare two methods:

  1. A continuous-time Petri net model using Ordinary Differential Equations (ODEs).

  2. A branch-and-bound algorithm, a traditional combinatorial optimization technique.

While the Petri net approach appears advanced, it’s often simpler to implement and interpret, especially for dynamic systems.

Approach 1: Petri Net with ODEs

The Petri net model uses Petri.jl to represent the knapsack problem as a dynamic system:

  • States (places): Represent the items, weight, value, and capacity.
  • Transitions: Define how items are added based on resource constraints.
  • ODEs: Govern the rate of change, allowing for continuous simulation of token flows.
Why It Works:
  • Simplicity in Design: Defining states and transitions requires fewer lines of code compared to implementing a full algorithm.
  • Ease of Visualization: ODE solvers and plotting libraries make it easy to track how the knapsack evolves over time.
  • Dynamic Exploration: Exclusions (removing certain items) can be simulated by setting specific transition rates to zero, requiring only minor code changes.

Approach 2: Branch-and-Bound Algorithm

Review the algorithm in the ipython notebook on github.

Branch-and-bound is a powerful yet more traditional approach that systematically explores all possible solutions:

  1. Tree Structure: Each node represents a decision (to include or exclude an item).

  2. Bounds: Calculates upper and lower bounds to prune branches.

  3. Iterative Exploration: Examines feasible solutions to maximize the knapsack's value.

Why It Works:
  • Proven Optimization: Guarantees an optimal solution by exhaustively exploring all branches.
  • Deterministic Results: No approximations or reliance on differential solvers.

Output from the branch-and-bound algorithm:

  • Maximal Value = 38

Which one to use?

  • For dynamic and exploratory analysis: The Petri net with ODEs is ideal. It offers a clear and flexible way to visualize how systems behave under various constraints.
  • For exact and guaranteed solutions: Branch-and-bound ensures optimality but comes with a higher implementation cost and less adaptability to dynamic changes.

Conclusion

While branch-and-bound excels in classic optimization, the Petri net approach proves that even advanced methods can be simpler and more intuitive in certain contexts. By leveraging tools like Petri.jl, we can tackle dynamic problems with ease, gaining insights without the overhead of intricate algorithms.

If you're diving into optimization or exploring Petri nets, try both methods and see which suits your needs. Continuous modeling might just surprise you with its simplicity and power.

Review the ipython notebook using Petri.jl w/ ODE solvers.

In our previous post, we demonstrated how Petri.jl can model Tic-Tac-Toe by translating its states and transitions into a dynamic Petri net framework. By embedding win conditions into Ordinary Differential Equations (ODEs), we quantified move heuristics to evaluate the value of each opening move.

Heuristics: Quantifying Strategy

We calculated heuristic scores for all possible opening moves by Player X. The results highlight the strategic significance of each position:

 -------- Scores -------
| 1.146 | 1.082 | 1.146 |
| 1.082 | 1.228 | 1.082 |
| 1.146 | 1.082 | 1.146 |

The center (P11) scores highest (1.228), confirming its importance. Corners follow, while edges lag behind.

Visualizing Probabilities

Simulations show how win probabilities evolve over time:

  • Center moves dominate quickly.
  • Corners remain competitive.
  • Edges grow slower, reflecting weaker strategic potential.

Broader Implications

This analysis validates Petri.jl as a robust tool for quantifying decision-making processes. Beyond games, it can model and optimize strategies in diverse domains.

Next Steps: Exploring Gossip Protocols

Having shown this technique works, we will now apply it to broader problems. Our next focus is modeling a simple gossip protocol to understand message propagation and consensus dynamics.

Stay tuned as we extend Petri.jl's capabilities to new frontiers of computational modeling!

Link to Notebook:

Some time ago, we explored modeling the classic game of Tic-Tac-Toe as a Petri net, demonstrating how this formalism could elegantly represent the interplay between game states and transitions. Today, we revisit this idea with fresh insights and a more advanced approach using Petri.jl, a Julia library that offers powerful tools for constructing and analyzing Petri nets.

From Concept to Visualization

Petri.jl allows us to model Tic-Tac-Toe in a way that's both expressive and computationally robust. Below is a visualization of the Petri net we constructed for Tic-Tac-Toe:

This graph showcases the game states as places and the player moves as transitions. Each directed arc represents the flow of tokens—analogous to moves advancing the game toward its conclusion.

Revisiting the Formalism

At its core, the Tic-Tac-Toe model encapsulates the following:

  1. Places: Represent the current state of the game (e.g., empty squares, player moves).

  2. Transitions: Represent the legal moves available to each player.

  3. Tokens: Indicate the state of play (e.g., which squares are occupied by X or O).

This approach highlights the game's structure, showing how states evolve as moves are made.

Analyzing Dynamics with ODEs

One of the most exciting possibilities opened up by Petri.jl is the ability to translate our Petri net into a system of Ordinary Differential Equations (ODEs). This enables a quantitative analysis of the game dynamics.

For

  • Each place corresponds to a variable representing the state of the board.
  • Transitions influence these variables based on player actions.
  • Solving the ODE system reveals trajectories of game progression.

Ensuring the Plot Matches the Game with Internal Win Conditions

The plots above appear to converge quickly to stable values, aligning with the game rules: the Next turn transition activates at t=1, and all moves settle to 0 starting at t=2. However, to confirm that this behavior accurately represents the game, we extended the Petri net model to include win conditions directly within the ODE system.

By embedding these conditions, we create a new ODEProblem that integrates both state dynamics and game logic. This approach ensures that the model can verify win outcomes internally, providing a stronger connection between the ODE-generated results and the expected behavior of Tic-Tac-Toe.

Model Checking X/O Win ratio

The extended model the Petri net to include places representing win conditions for each player. Each time a win condition was met, a token was deposited in the corresponding winx_ or wino_ place. After we solved and plotted the result, we measured this ratio at t=9.

Remarkably, the results showed only a 0.85% error compared to the expected statistical win ratios for Tic-Tac-Toe. This seems to demonst the model's accuracy in reflecting real-game dynamics.

Why This Matters

Revisiting our Tic-Tac-Toe model with modern tools like Petri.jl underscores how mathematical frameworks evolve alongside computational advancements. It also highlights the versatility of Petri nets in capturing not just static systems but also dynamic, strategy-driven games like Tic-Tac-Toe.

Next Steps

This approach is just the beginning. Future explorations could include:

  • Extending the model to other games with more complex rules.
  • Investigate how adding other Petri-net structures affect the dynamics of the ODE plots.

Python notebook with source code used in this post is available here

Pflow’s workflow implementation simplifies and extends WF-net ideas for practical, real-world systems by:

  1. Adding retry and reentry mechanisms (allow_reentry).

  2. Restricting state behaviors to enforce runtime constraints.

  3. Focusing on execution rather than pre-runtime verification.

WF-nets remain a formal and abstract framework for analyzing workflows, often requiring specialized tooling and theoretical grounding. Pflow’s workflow model aligns more with runtime task automation and system engineering.

I recently attended an Austin hackathon oriented around the latest open source models from Meta. https://lu.ma/atx-llama-hackathon.

As the main sponsor, representatives from Meta are spreading the word about their impact grant program. https://www.llama.com/llama-impact-grants/

I got to work with some great tools from these additional sponsors:

Pflow-prompt

During this hackathon, I decided to try to test the ability for for Llama to generate petri-nets using the pflow.xyz notation.

I’ve been interested in trying to use LLMs to convert code into equivalent petri-net models. So, I started with a program written in a state-machine style in BASH.

I then provided it as user input, alongside a system prompt:

Output models:

Remarks

I’m pretty impressed with how well OpenAI 4o performed. The LLM correctly intuited that we’d like to use the state and action names as labels.

It also seemed to do a good job laying out the objects, and using the playground feature, I was even able to prompt another time to ask it to “add more space between the elements” – with consistent results.

Most of the other submissions made use of natural language translation and auto-classification.

Upon reflection: I could have applied the RAG approach using tools provided by Datastax, or built a tool using lang-graph, or even tried model refinement to get the results I wanted from Llama.

In the end, because OpenAI 4o worked with a single prompt I didn’t see any benefit to try to use Llama.

While developing this experiment I used the API https://platform.openai.com/ and only spent $.06 !!

Conclusion:

For now, I’ll be using 4o as I add LLM support to pflow.xyz.

Going forward, my sense is that various refinement approaches will become less relevant as better LLMs are developed, and for now the cost seems to be right for this application.

1. PetriNet

  • General Behavior: Petri nets allow the most general and flexible state transitions, supporting multiple states being active at once and various roles or conditions for enabling transitions.
  • Fire Method: petri_net_fire
    • Transitions update states based on their delta values.
    • Guards are applied to inhibit transitions if conditions are not met.
    • The result includes flags for overflow, underflow, and whether the transition was inhibited.
    • Supports full vector addition for state changes, with capacity checks.
  • Key Features:
    • Most complex and capable model.
    • Can handle arbitrary guard conditions and multiple active states.

2. Elementary

  • General Behavior: Simplifies the Petri net model, restricting the number of active states post-transition to one. This ensures clear, single-state progression.
  • Fire Method: elementary_fire
    • Works similarly to petri_net_fire, but includes an additional check to ensure only one state is active (output_state_count == 1).
    • Transitions are inhibited if multiple states are active after firing.
  • Key Features:
    • Simplifies state behavior by enforcing single-state transitions.
    • Suitable for workflows where transitions must always result in a single active state.

3. Workflow

  • General Behavior: A further simplification of the Elementary model, explicitly designed for workflows with retry and reentry behavior. Allows more leniency in retrying failed transitions while enforcing constraints on state updates.
  • Fire Method: workflow_fire
    • States are constrained to values 0, 1, or 2:
    • 0 or -1: Inactive states or retryable errors.
    • 1: Active state.
    • 2: Overflow; mapped to 1 for retry or inhibited transitions.
    • Enforces single active state but introduces retry behavior.
    • Allows transitions with specific conditions (e.g., allow_reentry).
  • Key Features:
    • Designed for task flows or processes with explicit reentry behavior.
    • Introduces stricter constraints but enables retry loops for overflow states.

Comparison

Practical Applications:

  1. PetriNet: Use for complex, concurrent systems where multiple states must interact or coexist.

  2. Elementary: Apply to simpler decision trees or systems that require deterministic, single-state outputs.

  3. Workflow: Ideal for workflows or task management systems where retry and fail-safe mechanisms are essential.

This framework allows flexible modeling based on system requirements, enabling efficient and accurate representation of different operational paradigms.

Review the Rust code on used to compare these algorithms on github.