Search

• < Previous
• 1
• Next >

---

Model Checking Vector Addition Systems with one zero-test

Rémi Bonnet ; Alain FInkel ; Jérôme Leroux ; Marc Zeitoun.

We design a variation of the Karp-Miller algorithm to compute, in a forward manner, a finite representation of the cover (i.e., the downward closure of the reachability set) of a vector addition system with one zero-test. This algorithm yields decision procedures for several problems for these&nbsp;[&hellip;]

---

Forward Analysis for WSTS, Part II: Complete WSTS

Alain Finkel ; Jean Goubault-Larrecq.

We describe a simple, conceptual forward analysis procedure for infinity-complete WSTS S. This computes the so-called clover of a state. When S is the completion of a WSTS X, the clover in S is a finite description of the downward closure of the reachability set. We show that such completions are&nbsp;[&hellip;]

---

Well Behaved Transition Systems

Michael Blondin ; Alain Finkel ; Pierre McKenzie.

The well-quasi-ordering (i.e., a well-founded quasi-ordering such that all antichains are finite) that defines well-structured transition systems (WSTS) is shown not to be the weakest hypothesis that implies decidability of the coverability problem. We show coverability decidable for monotone&nbsp;[&hellip;]

---

Verification of Flat FIFO Systems

Alain Finkel ; M. Praveen.

The decidability and complexity of reachability problems and model-checking for flat counter machines have been explored in detail. However, only few results are known for flat (lossy) FIFO machines, only in some particular cases (a single loop or a single bounded expression). We prove, by&nbsp;[&hellip;]

---

Forward Analysis for WSTS, Part III: Karp-Miller Trees

Michael Blondin ; Alain Finkel ; Jean Goubault-Larrecq.

This paper is a sequel of "Forward Analysis for WSTS, Part I: Completions" [STACS 2009, LZI Intl. Proc. in Informatics 3, 433-444] and "Forward Analysis for WSTS, Part II: Complete WSTS" [Logical Methods in Computer Science 8(3), 2012]. In these two papers, we provided a framework to conduct forward&nbsp;[&hellip;]

---

Bounded Reachability Problems are Decidable in FIFO Machines

Benedikt Bollig ; Alain Finkel ; Amrita Suresh.

The undecidability of basic decision problems for general FIFO machines such as reachability and unboundedness is well-known. In this paper, we provide an underapproximation for the general model by considering only runs that are input-bounded (i.e. the sequence of messages sent through a particular&nbsp;[&hellip;]

---

Synchronizability of Communicating Finite State Machines is not Decidable

Alain Finkel ; Etienne Lozes.

A system of communicating finite state machines is synchronizable if its send trace semantics, i.e.the set of sequences of sendings it can perform, is the same when its communications are FIFO asynchronous and when they are just rendez-vous synchronizations. This property was claimed to be decidable&nbsp;[&hellip;]

---

Branch-Well-Structured Transition Systems and Extensions

Benedikt Bollig ; Alain Finkel ; Amrita Suresh.

We propose a relaxation to the definition of well-structured transition systems (\WSTS) while retaining the decidability of boundedness and non-termination. In this class, the well-quasi-ordered (wqo) condition is relaxed such that it is applicable only between states that are reachable one from&nbsp;[&hellip;]

---