Introduction

Constraint-based temporal reasoning has been widely used in many applications across many domains. Over the years, different formalisms have been presented to address specific requirements that frequently arise in real-world applications. The most commonly used formalism is probably the Simple Temporal Network (STN), in which a set of real-valued variables, called timepoints, are subject to binary difference constraints [1]. Timepoints represent the occurrence of events: when a timepoint is assigned a value t, the event occurs at instant t, or the timepoint is executed at time t. The binary difference constraints represent the temporal constraint between a pair of timepoints (X-Y ≤ 10 means that X can occur 10-time units after Y at most).

The two main problems for STNs are consistency and dispatchability.

The consistency problem asks whether an STN admits one or more timepoint assignments that satisfy all temporal constraints. In a consistent STN, each timepoint has a range of possible execution instants, called its time-window.

The dispatchability problem asks for a dynamic schedule of the timepoints, i.e., a schedule that, after a timepoint is executed at an allowed instant, updates the time-windows of the remaining unexecuted timepoints while guaranteeing that all timepoints can be executed in order as time flows.

Recently, a significant amount of research has focused on temporal reasoning in the presence of uncertainty.
Temporal uncertainty arises, for example, when the durations of some activities (i.e., some temporal intervals) are not controlled by the executor of the network, but are only observed in real time as the activities complete. In such settings, the executor seeks a dynamic strategy for executing the controllable timepoints so that all relevant constraints are necessarily satisfied, no matter how the uncertain durations turn out. To accommodate this kind of uncertainty, STNs have been augmented to include contingent links, where each contingent link represents an interval whose duration is bounded but uncontrollable; the resulting network is called a Simple Temporal Network with Uncertainty (STNU) [2].
The most important property of an STNU is whether it is dynamically controllable (DC)—that is, whether there exists a strategy for executing the controllable timepoints such that all relevant constraints are guaranteed to be satisfied no matter how the durations of the contingent links turn out.

Although STNUs have been successful in some domains, many domains require a richer set of constraints.
For example, in the healthcare domain, where workflow management systems are being developed to automate medical-treatment processes, medical tests for a given patient frequently generate information in real time that can affect which pathway the patient will follow [3].
The system must guarantee that any possible execution of the workflow strictly satisfies all specified temporal constraints no matter which test outcomes are observed. A set of test outcomes is called a scenario. The Conditional Simple Temporal Network (CSTN) model represents temporal constraints in conjunction with scenarios. In this way, it is possible to specify, for each possible scenario, a proper set of constraints that must be satisfied if the scenario occurs in an execution of the network. For CSTNs, several studies have established results and algorithms for handling CSTNs properly [8], [9], [11], [12], [13], [15] [16].

The Conditional Simple Temporal Network with Uncertainty (CSTNU) model extends the CSTN model by allowing the representation of contingent links. Several works have established properties and possible applications of CSTNUs [5], [6], [7], [10], [14].

The Conditional Simple Temporal Network with Partially Shrinkable Uncertainty (CSTNPSU) model extends the CSTNU model by allowing each contingent link to have a wider range that can be slightly shrunk at design or execution time to obtain a successful execution. The same model was later presented under the name Flexible Temporal Network with Uncertainty (FTNU), together with a DC-checking algorithm that determines the guarded bounds correctly; in this library the two names denote the same networks, FTNU being a wrapper of CSTNPSU. [19].

The Parameterized Conditional Simple Temporal Network with Uncertainty (PCSTNU) model extends the CSTNU model with parameter nodes, whose execution instants are decided at design time rather than during execution, so that a single network can describe a family of admissible configurations. [23].

The STNU with Oracles, also called STNUO in the literature and OSTNU in this tool, extends the STNU model with oracles. Each contingent link may be associated with at most one timepoint, called its oracle, which, when executed, reveals the duration that the contingent link will take. An oracle therefore provides information earlier than the completion of the activity itself, and an executor can exploit it: the property of interest is agile controllability, introduced for temporal business processes and then defined formally together with its propagation rules [21], [28], [32], [35].

Besides consistency and controllability, this tool addresses dispatchability for networks with uncertainty. A dispatchable network can be executed by a simple real-time algorithm that only propagates the constraints incident to the timepoint just executed; the size of the network is therefore the dominant cost of execution, which is what makes a minimal dispatchable form — one with as few edges as possible — worth computing. This line of work went from the foundations, where a real-time execution algorithm was shown to be equivalent to dispatchability [29], to converting an STNU into dispatchable form [24], and then into minimal equivalent dispatchable form [31], [30]. A canonical form for the nested diamond structures of an STNU [36] later revealed an incompleteness in the fastest of those algorithms and led to the one currently implemented here [37]; the whole progression, together with the faster search for negative cycles that supports it, is surveyed in [34].

This open-source project provides:

• a Java library for representing and checking temporal constraint networks of the types described above: STN, STNU, OSTNU, CSTN, CSTNU, PCSTNU, and CSTNPSU/FTNU;
• algorithms for transforming a dynamically controllable STNU into a minimal dispatchable network;
• a graphical Java editor for designing and checking all of the above from scratch;
• an experimental, still incomplete implementation of Probabilistic Simple Temporal Networks (PSTN), in which each contingent link carries a log-normal duration distribution.

If you use this tool in your research, please cite this project by including this website and the SoftwareX paper [17].

Recent developments

The models and algorithms above are the outcome of a few distinct lines of work, and the tool follows them as they progress. Dynamic controllability itself keeps being made faster: an order-of-magnitude practical improvement for STNUs [18], a sound-and-complete algorithm for the guarded ranges of FTNUs after a limit of a previous one was shown [19], and the extension to networks with parameters [23]. A second line studies dispatchability and the minimal dispatchable form, from its foundations to the algorithm currently implemented [29], [24], [31], [30], [36], [37], with a survey in [34]. A third one makes negative cycles a practical diagnostic tool rather than a mere proof of non-controllability: finding them faster [33] supports both the robust execution of probabilistic networks [26] and, in a multi-agent setting, the repair of interdependent networks whose weak controllability has been lost [38]. A fourth one introduces agile controllability for networks whose contingent durations may be revealed early by oracles [21], [28], [32], [35]. Applications, mostly to business processes and healthcare, motivate the models and provide the instances they are tested on [22], [27], [28], [20].

Benchmarks

Some algorithm implementations in the tool have been tested on benchmark instances. In general, each benchmark consists of temporal networks randomly generated according to specific criteria. For each benchmark, we describe the generation criteria, the characteristics of each random instance, and the DC/NOT-DC property.

An analysis of the benchmarks and the algorithm performance obtained on them is available at Benchmarks.

The directory containing benchmarks is https://profs.scienze.univr.it/~posenato/software/benchmarks/

Each benchmark belongs to a line of work, and the correspondence is the following.

• CSTNBenchmark2016 and CSTNBenchmark2018 — the algorithms for checking the dynamic consistency of CSTNs: [8], [9], [11], [13], [15], [16].
• CSTNUBenchmark2018 — the algorithms for checking the dynamic controllability of CSTNUs: [14].
• STNUBenchmark2020 — the algorithms for checking the dynamic controllability of STNUs, among them [18]; the benchmark page cites further works, including technical reports not listed here.
• CSTNPSUBenchmarks2023 — the dynamic-controllability checking and the prototypal-link algorithm for CSTNPSUs, also called FTNUs: [14], [19].
• OSTNUBenchmarks2024 — agile controllability of STNUs with oracles: [28], and the later [32], [35].
• STNUw4DiamondsBenchmark2025 and STNUw6DiamondsBenchmark2025 — converting a dispatchable STNU into an equivalent one with a minimal number of edges: [30], [31], [36], [37].

The two benchmarks of 2025 exist because of a negative finding: no instance of STNUBenchmark2020 contains a nested diamond structure, so on that benchmark the two minimization algorithms do the same work and their difference cannot be measured.

Bibliography

[1] R. Dechter, I. Meiri, and J. Pearl, “Temporal constraint networks,” Artificial Intelligence, vol. 49, pp. 61–95, 1991.

[2] P. Morris, N. Muscettola, and T. Vidal, “Dynamic control of plans with temporal uncertainty,” in 17th International Joint Conference on Artificial Intelligence (IJCAI-01), Morgan Kaufmann, 2001, pp. 494–499.

[3] C. Combi, M. Gambini, S. Migliorini, and R. Posenato, “Representing business processes through a temporal data-centric workflow modeling language: An application to the management of clinical pathways,” Systems, Man, and Cybernetics: Systems, IEEE Transactions on,  2014. Available online: https://ieeexplore.ieee.org/xpl/abstractReferences.jsp?arnumber=6733362

[4] L. Hunsberger, R. Posenato, and C. Combi, “The Dynamic Controllability of Conditional STNs with Uncertainty,” in Workshop on Planning and Plan Execution for Real-World Systems: Principles and Practices (PlanEx) @ ICAPS-2012, Atibaia, Jun. 2012, pp. 1–8. Available online: https://arxiv.org/abs/1212.2005

[5] C. Combi, L. Hunsberger, and R. Posenato, “An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty,” in Proc. of the 5th Int. Conf. on Agents and Art. Int. (ICAART-2013), vol. 2, pp. 144–156, SCITEPRESS, Feb. 2013

[6] C. Combi, L. Hunsberger, and R. Posenato, “An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty-revisited,” in Agents and Artificial Intelligence, vol. 449 of Communications in Computer and Information Science, pp. 314–331, Springer-Verlag, 2014. Available online: https://doi.org/10.1007/978-3-662-44440-5_19

[7] A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri, “Sound and complete algorithms for checking the dynamic controllability of temporal networks with uncertainty, disjunction and observation,” in 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), pp. 27–36, IEEE Computer Society, Sept. 2014. Available online: https://doi.org/10.1109/TIME.2014.21

[8] L. Hunsberger, R. Posenato, and C. Combi, “A Sound-and-Complete Propagation-based Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks,” in 22nd International Symposium on Temporal Representation and Reasoning (TIME 2015), pp. 4–18, IEEE Computer Society, Sept. 2015. Available online: https://doi.org/10.1109/TIME.2015.26

[9] L. Hunsberger and R. Posenato, “Checking the Dynamic Consistency of Conditional Simple Temporal Networks with Bounded Reaction Times”, in ICAPS 2016: International Conference on Automated Planning and Scheduling (ICAPS 2016), pp. 175–183, 2016. Available online: https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13108

[10] A. Cimatti, L. Hunsberger, A. Micheli, R. Posenato, and M. Roveri, ‘Dynamic controllability via Timed Game Automata’, Acta Inform., vol. 53, no. 6–8, pp. 681–722, Oct. 2016. Available online: https://dx.doi.org/10.1007/s00236-016-0257-2

[11] M. Cairo, L. Hunsberger, R. Posenato, and R. Rizzi, ‘A Streamlined Model of Conditional Simple Temporal Networks – Semantics and Equivalence Results’, in 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), 2017, vol. 90, no. 10, pp. 1–10. Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2017.10

[12] M. Cairo, C. Combi, C. Comin, L. Hunsberger, R. Posenato, R. Rizzi, M. Zavatteri, ‘Incorporating Decision Nodes into Conditional Simple Temporal Networks’, in 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), 2017, vol. 90, p. 9:1–9:18.
Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2017.9

[13] L. Hunsberger and R. Posenato, ‘Simpler and Faster Algorithm for Checking the Dynamic Consistency of Conditional Simple Temporal Networks’, in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018, pp. 1324–1330. Available online: https://dx.doi.org/10.24963/ijcai.2018/184

[14] L. Hunsberger, R. Posenato, ‘Sound-and-Complete Algorithms for Checking the Dynamic Controllability of Conditional Simple Temporal Networks with Uncertainty, in 25th International Symposium on Temporal Representation and Reasoning (TIME 2018), 2018, vol. 120, no. 14, p. 1–17.
Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2018.14

[15] L. Hunsberger, R. Posenato, ‘Reducing ε-DC Checking for Conditional Simple Temporal Networks to DC Checking’, in 25th International Symposium on Temporal Representation and Reasoning (TIME 2018), 2018, vol. 120, no. 15, pp. 1–15. Available online: https://dx.doi.org/10.4230/LIPIcs.TIME.2018.15

[16] L. Hunsberger and R. Posenato, ‘Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks’, in ICAPS 2020: International Conference on Automated Planning and Scheduling (ICAPS 2020), 2020.

[17] R. Posenato, ‘CSTNU Tool: A Java library for checking temporal networks’, SoftwareX 17, 100905. 2022. https://doi.org/10.1016/j.softx.2021.100905

[18] L. Hunsberger and R. Posenato, “Speeding up the RUL− Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty,” in Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI Press, 2022, pp. 9776–9785. Available online: https://doi.org/10.1609/aaai.v36i9.21213

[19] R. Posenato and C. Combi, “Adding flexibility to uncertainty: Flexible Simple Temporal Networks with Uncertainty (FTNU),” Information Sciences, vol. 584C, pp. 784–807, Jan. 2022. Available online: https://doi.org/10.1016/j.ins.2021.10.008

[20] M. Ocampo-Pineda, R. Posenato, and F. Zerbato, “TimeAwareBPMN-js: An editor and temporal verification tool for Time-Aware BPMN processes,” SoftwareX, vol. 17, p. 100939, Jan. 2022. Available online: https://doi.org/10.1016/j.softx.2021.100939

[21] R. Posenato, M. Franceschetti, C. Combi, and J. Eder, “Some results and challenges Extending Dynamic Controllability to Agile Controllability in Simple Temporal Networks with Uncertainties,” Dipartimento di Informatica – Università degli Studi di Verona, Technical Report 1/2023, 2023. Available online: https://iris.univr.it/handle/11562/1116013

[22] R. Posenato and C. Combi, “Flexible temporal constraint management in modularized processes,” Information Systems, vol. 118, p. 102257, 2023. Available online: https://doi.org/10.1016/j.is.2023.102257

[23] M. Franceschetti, R. Posenato, C. Combi, and J. Eder, “Dynamic Controllability of Parameterized CSTNUs,” in 37th ACM/SIGAPP Symposium on Applied Computing (SAC ’23), Tallin, Estonia: ACM, 2023, pp. 965–973. Available online: https://doi.org/10.1145/3555776.3577618

[24] L. Hunsberger and R. Posenato, “A Faster Algorithm for Converting Simple Temporal Networks with Uncertainty into Dispatchable Form,” Information and Computation, vol. 293, p. 105063, Jun. 2023. Available online: https://doi.org/10.1016/j.ic.2023.105063

[25] A. Artikis, R. Posenato, and S. Tonetta, “Temporal representation and reasoning in data-intensive systems,” Information Systems, vol. 122, p. 102350, May 2024. Available online: https://doi.org/10.1016/j.is.2024.102350

[26] L. Hunsberger and R. Posenato, “Robust Execution of Probabilistic STNs,” in 31st International Symposium on Temporal Representation and Reasoning (TIME 2024), Montpellier: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 12:1–12:19. Available online: https://doi.org/10.4230/LIPICS.TIME.2024.12

[27] G. A. Beltrame, C. Combi, A. Farinelli, R. Posenato, and G. Pozzi, “Ride-Sharing in Medical Transportations: Dealing with Temporal Requirements,” in Workshop Proceedings of the EDBT/ICDT 2024 Joint Conference, CEUR-WS, 2024. Available online: https://ceur-ws.org/Vol-3651/HeDAI-1.pdf

[28] R. Posenato, M. Franceschetti, C. Combi, and J. Eder, “Introducing Agile Controllability in Temporal Business Processes,” in Enterprise, Business-Process and Information Systems Modeling, vol. 511 of Lecture Notes in Business Information Processing, Springer, 2024, pp. 87–99. Available online: https://doi.org/10.1007/978-3-031-61007-3_8

[29] L. Hunsberger and R. Posenato, “Foundations of Dispatchability for Simple Temporal Networks with Uncertainty,” in 16th International Conference on Agents and Artificial Intelligence (ICAART 2024), Roma, Italy: SCITEPRESS, Feb. 2024, pp. 253–263. Available online: https://doi.org/10.5220/0012360000003636

[30] L. Hunsberger and R. Posenato, “Faster Algorithm for Converting an STNU into Minimal Dispatchable Form,” in 31st International Symposium on Temporal Representation and Reasoning (TIME 2024), vol. 318 of LIPIcs, 2024, p. 11:1–11:14. Available online: https://doi.org/10.4230/LIPICS.TIME.2024.11

[31] L. Hunsberger and R. Posenato, “Converting Simple Temporal Networks with Uncertainty into Minimal Equivalent Dispatchable Form,” in Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024), May 2024, pp. 290–300. Available online: https://doi.org/10.1609/icaps.v34i1.31487

[32] J. Eder, R. Posenato, C. Combi, M. Franceschetti, and F. S. Hollauf, “Agile Controllability of Simple Temporal Networks with Uncertainty and Oracles,” in 31st International Symposium on Temporal Representation and Reasoning (TIME 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 4:1–4:16. Available online: https://doi.org/10.4230/LIPICS.TIME.2024.4

[33] L. Hunsberger and R. Posenato, “A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty,” in 31st International Symposium on Temporal Representation and Reasoning (TIME 2024), vol. 318 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 9:1–9:15. Available online: https://doi.org/10.4230/LIPICS.TIME.2024.9

[34] L. Hunsberger and R. Posenato, “Recent Algorithmic Advances in Simple Temporal Networks with Uncertainty: from Faster Controllability Checking to Faster Execution,” Information and Computation, vol. 307, p. 105356, Nov. 2025. Available online: https://doi.org/10.1016/j.ic.2025.105356

[35] F. S. Hollauf, R. Posenato, C. Combi, and J. Eder, “Modeling Oracles in Simple Temporal Networks with Uncertainty,” Information and Computation, vol. 307, p. 105382, Nov. 2025. Available online: https://doi.org/10.1016/j.ic.2025.105382

[36] L. Hunsberger and R. Posenato, “Canonical Form of Nested Diamond Structures,” Dipartimento di Informatica – Università degli Studi di Verona, Technical Report 111/2025, May 2025. Available online: https://iris.univr.it/handle/11562/1163111

[37] L. Hunsberger and R. Posenato, “A Better Algorithm for Converting an STNU into Minimal Dispatchable Form,” in Proceedings of the 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025), vol. 355 of LIPIcs, London: Dagstuhl Publishing, 2025, pp. 1–15. Available online: https://doi.org/10.4230/LIPIcs.TIME.2025.11

[38] A. Sumic, T. Vidal, G. Picard, F. Maris, R. Posenato, and C. Combi, “Centralized and Distributed approaches for restoring the Weak Controllability of Multi-Agent Interdependent STNUs,” in Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), Paphos, Cyprus: International Foundation for Autonomous Agents and Multiagent Systems, May 2026. Available online: https://doi.org/10.65109/FQWT7513

[39] R. Posenato and I. Vanderfeesten, Eds., Advanced Information Systems Engineering Workshops: CAiSE 2026 Workshops, Verona, Italy, June 8–12, 2026, Proceedings, vol. 586 of Lecture Notes in Business Information Processing, Cham: Springer Nature Switzerland, 2026. Available online: https://doi.org/10.1007/978-3-032-28160-9