Co-Finiteness and Co-Emptiness of Reachability Sets in Vector Addition Systems with States | Zendy

Petr Jančar | Zendy; Jérôme Leroux | Zendy; Grégoire Sutre | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Co-Finiteness and Co-Emptiness of Reachability Sets in Vector Addition Systems with States

Author(s) -

Petr Jančar,

Jérôme Leroux,

Grégoire Sutre

Publication year - 2019

Publication title -

fundamenta informaticae

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.311

H-Index - 67

eISSN - 1875-8681

pISSN - 0169-2968

DOI - 10.3233/fi-2019-1841

Subject(s) - decidability , reachability problem , reachability , mathematics , liveness , bounded function , emptiness , petri net , upper and lower bounds , discrete mathematics , combinatorics , conjecture , computer science , algorithm , theoretical computer science , mathematical analysis , philosophy , theology

The coverability and boundedness problems are well-known exponential-space complete problems for vector addition systems with states (or Petri nets). The boundedness problem asks if the reachability set (for a given initial configuration) is finite. Here we consider a dual problem, the co-finiteness problem that asks if the complement of the reachability set is finite; by restricting the question we get the co-emptiness (or universality) problem that asks if all configurations are reachable.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research