Decidability Problems for Micro-Stipula

G. Delzanno, C. Laneve, A. Sangnier, G. Zavattaro · 2025

Read Decidability Problems for Micro-Stipula by G. Delzanno, C. Laneve, A. Sangnier, G. Zavattaro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16703.txt.

Introduction

Delzanno, Laneve, Sangnier, and Zavattaro study what can and cannot be decided about programs written in a small contract language. In that language, clauses wake up either when the outside world calls them or when a time condition fires. Their 2025 paper asks whether a program can tell, in general, if a given clause will never run.

The answer is no: they prove that question has no general algorithm, even for two trimmed-down versions of the language. One version forces all time values to be strictly positive, and the other forces them all to zero. A narrow corner does allow an answer, when the starting states of functions and events do not overlap in the zero-time version. The results map the limits of automatic checks for such timed programs.

Catalog record

CREATORG. Delzanno, C. Laneve, A. Sangnier, G. Zavattaro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE118 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16703

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decidability Problems for Micro-Stipula G. Delzanno, C. Laneve, A. Sangnier, G. Zavattaro Abstract Micro- Stipula is a stateful calculus in which clauses can be activated either through interactions with the external environment or by the evaluation of time expressions. Despite the apparent simplicity of its syntax and operational model, the combination of state evolution, time reasoning, and nondeterminism gives rise to significant analytical challenges. In particular, we show that determining whether a clause is never executed is undecidable. We formally prove that this undecidability result holds even for syntactically restricted fragments: namely, the time-ahead fragment, where all time expressions are strictly positive, and the instantaneous fragment, where all time expressions evaluate to zero. On the other hand, we identify a decidable subfragment: within the instantaneous fragment, reachability becomes decidable when the initial states of functions and events are disjoint. 1 Introduction Micro- Stipula , noted \mu Stipula , is a basic calculus defining contracts , namely sets of clauses that are either ( a ) parameterless functions , to be invoked by the external environment, or ( b ) events that are triggered at given times. The calculus has been devised to study the presence of clauses in legal contracts written in Stipula [ 11 , 12 ] that can never be applied because of unreachable circumstances or of wrong time constraints – so-called unreachable clauses . In the legal contract domain, removing such clauses when the contract is drawn up is substantial because they might be considered too oppressive by parties and make the legal relationship fail. While dropping unreachable code is a very common optimization in compiler construction of programming languages [ 6 , 9 ] , the presence of time expressions in \mu Stipula events makes the optimization complex. In particular, when the time expressions are logically inconsistent with the contract behaviour, the corresponding event (and its continuation) becomes unreachable. In [ 24 ] we have defined an analyzer that uses symbolic expressions to approximate time expressions at static-time and that computes the set of reachable clauses by means of a closure operation based on a fixpoint technique. The analyzer, whose prototype is at [ 17 ] , is sound (every clause it spots is unreachable) but not complete (there may be unreachable clauses that are not recognized). The definition of a complete algorithm for unreachable clauses was left as an open problem. In this paper we study the foregoing problem for three fragments of \mu Stipula that are used to model distinctive elements of legal contracts: \mbox{{\sf\emph{$\mu$Stipula}}${}^{\tt TA}$}: time expressions are always positive – the corresponding events allow one to define future obligations such as the power to exercise an option may only last until a deadline is met. For example, a standard clause in a legal contract for renting a device is – The Borrower shall return the device k hours after the rental and will pay Euro cost in advance where half of the amount is of surcharge for late return. This clause is transposed in \mu Stipula with an event like now + k >> @Using { cost \multimap Lender } => @End which is affirming that the money cost is sent to the Lender (the operation \multimap ) if the Borrower is Using the device when the deadline expires. \mbox{{\sf\emph{$\mu$Stipula}}${}^{\tt I}$}: time expressions are always now – the corresponding events permit to define judicial enforcements such as the immediate activation of a dispute resolution mechanism by an authority when a party challenges the content or the execution of the contract. For example, a contract for renting a device might also contain a clause for resolution of problems: – If the Lender detects a problem, he may trigger a resolution process that is managed by the Authority. The Authority will immediately enforce resolution to either the Lender or the Borrower. In this case, the \mu Stipula clause is the event now >> @Problem { // immediately enforce resolution to Lender or Borrower } => @Solved where the immediate resolution is implemented by a time expression now . In this case, if the Lender and the Borrower have not yet resolved the issue – the contract is in a state Problem – then the Authority enforces a resolution by, for example, sending a part of cost to Lender and the remaining part to Borrower. \mbox{{\sf\emph{$\mu$Stipula}}${}^{\tt D}$}: functions and events do not have initial states in common; events in this fragment allow one to model exceptional behaviours that must be performed before any party may invoke a function. This type of restriction is quite common in legal contracts, particularly when formalizing a clause that outlines the consequences of a party breaching a condition. Section 0.A contains a legal contract written in \mu Stipula D . We demonstrate that, even for the aforesaid fragments of \mu Stipula , there is no complete algorithm for determining unreachable clauses. The proof technique is based on reducing the unreachability problem to the halting problem for Minsky machines (finite state machines with two registers) [ 27 ] . The \mu Stipula encodings of Minsky machines model registers’ values with multiplicities of events and extensively use the features that ( a ) events preempt both the invocation of functions and the progression of time and ( b ) events that are not executed in the current time slot are garbage-collected when the time progresses. The encoding of \mu Stipula TA is particularly complex because we need to decouple in two different time slots the events corresponding to the two registers and recreate them when the time progresses. We then restrict to \mu Stipula DI , a fragment of \mu Stipula that is the intersection of \mu Stipula I and \mu Stipula D , and demonstrate that the corresponding contracts are an instance of well-structured transition systems [ 18 ] , whereby the reachability problem is decidable. To achieve this result, we had to modify the semantics of \mu Stipula by restricting the application of the time progression to states in which functions can be invoked (thus it is disabled in the states where events are executed). Hereafter, the correspondence between the models using the two different progression rules has been analyzed to demonstrate reachability results for \mu Stipula DI . The rest of this paper is structured as follows. Section 2 presents the calculus \mu Stipula with examples and the semantics. Section 3 contains the undecidability results for \mu Stipula TA , \mu Stipula I and \mu Stipula D . Section 4 contains the decidability results about \mu Stipula DI . Section 5 reports and discusses related work and Section 6 presents general conclusions and future work. The proofs of our propositions, lemmas and theorems are reported in Section 0.B . 2 The calculus \mu Stipula \mu Stipula is a calculus of contracts. A contract is declared by the term stipula C { init {\tt Q} F } where {\tt C} is the name of the contract, {\tt Q} is the initial state and a F is a sequence of functions . We use a set of states , ranged over {\tt Q} , {\tt Q}^{\prime} , \cdots ; and a set of function names {\tt f} , {\tt g} ,

Read the complete text