stackdump

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

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.

Orthographic & Isometric Drawing - MR. ELSIE - TECHNOLOGICAL EDUCATION

In the realm of software design, visualizing complex systems is paramount. Drawing inspiration from isometric projection—a drafting technique that represents three-dimensional objects in two dimensions—we can adopt a similar approach using Petri nets. This method offers a comprehensive perspective on system workflows and resources.

Isometric Projection: A Brief Overview

Isometric projection allows for the depiction of 3D objects on a 2D plane without distortion, maintaining equal scale along three axes. This technique provides a clear and detailed view of intricate structures, facilitating better understanding and analysis.

Petri Nets: Modeling System Dynamics

Petri nets are mathematical representations used to model distributed systems. They consist of places (depicting states), transitions (representing events), and arcs (indicating the flow between places and transitions). This framework effectively captures the dynamic behavior of systems, including concurrency and resource sharing.

Integrating Isometric Principles with Petri Nets

By applying the concept of isometric projection to Petri nets, we can create layered models that offer multiple perspectives of a system:

  1. Primary Net: Illustrating the Overall Workflow

The primary Petri net serves as a high-level map of the system's main processes. It outlines the general flow, highlighting key transitions and states. This top-level view provides a clear understanding of the system's core functionality.

  1. Sub-Nets: Detailing Resources and Sub-Workflows

Sub-nets delve into specific components, such as resources or subsidiary workflows. Each sub-net focuses on a particular aspect, offering detailed insights into its operations and interactions. This modular approach simplifies complex systems by breaking them down into manageable sections.

  1. Composite View: Achieving a Comprehensive Projection

Combining the primary net with its associated sub-nets results in a holistic representation of the system. This integrated model mirrors the clarity of an isometric projection, allowing for simultaneous examination of the system's overall structure and its detailed components.

Advantages of This Approach

  • Enhanced Clarity: Layered modeling clarifies complex systems, making them easier to understand and analyze.
  • Modularity: Sub-nets enable focused examination of individual components, facilitating targeted development and troubleshooting.
  • Scalability: This method accommodates system growth, allowing for the addition of new sub-nets as the system evolves.

Conclusion

Embracing the principles of isometric projection through the use of Petri nets offers a structured and comprehensive approach to software design. This technique not only enhances visualization but also improves the management and scalability of complex systems.

To see how this this actually done start with: 3 Petri-Net Data Types

This blog post is NOT about LLMs!! The term Model is barely mentioned now-a-days without a prefix — as “Large Language Models” have reshaped the technical landscape.

A model is an abstract representation of a process that is composed of both behaviors (actions) and attributes (data). A good model allows for a system to be more predictable and easier to understand. A great model can also reduce the code complexity of a program.

Building Functional Models

Functional programming philosophy tells us that any problem can be solved via a reductionist approach: the developer decomposes a problem into functions, and then re-composes those functions into a solution.

This same paradigm is can be formally applied using petri-net models. First, we model the problem to be solved as a series of events. Then, by linking actions with input and output states, we compose these events into a full solution.

Net Analysis

Petri-nets are a formal analysis tool providing a formal foundation at design time, but we can also use them to make assertions about our program at runtime.

One useful attribute for analysis is reachability:

Given an input state, can the petri-net state machine be transformed into a target state?

Another testable property is boundedness:

Does this net model a closed system? Can a given place ever hold more than N tokens? Does the system ever create or destroy tokens?

The last property we hilight is liveness:

Can the network reach a state where no transformations are possible? under what conditions does the network reach this halting state?

Many of these properties can be analyzed through simulation. The petri-net itself is an executable schema. Pflow leverages this ability to interact with a model as a way to let users perform these checks simply by running model in a browser.

Conclusion

Building models into our code can improve design and the execution. Small models are comprehensible a user and developer alike. For a software developer, using a state machine for problem solving applies rigor at both design-time and program runtime. As a user, models can inform and educate about the state of a running process while interacting with a program. Check out the resources below how to use models in your code:

Visit https://pflow.xyz/docs-petri-net-101 to learn more about petri-nets, or try to compose one yourself using the editor https://pflow.xyz/editor.