Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

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;]
Published on January 20, 2022
Volume 18, Issue 1

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;]
Published on June 12, 2024
Volume 20, Issue 2
  • < Previous
  • 1
  • Next >