Michael Blondin

Michael Blondin
Are you Michael Blondin?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Michael Blondin
Affiliation
Location

Pubs By Year

Pub Categories

 
Computer Science - Logic in Computer Science (4)
 
Computer Science - Computational Complexity (1)
 
Computer Science - Distributed; Parallel; and Cluster Computing (1)

Publications Authored By Michael Blondin

Population protocols are a well established model of computation by anonymous, identical finite state agents. A protocol is well-specified if from every initial configuration, all fair executions reach a common consensus. The central verification question for population protocols is the well-specification problem: deciding if a given protocol is well-specified. Read More

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. Read More

The coverability problem for Petri nets plays a central role in the verification of concurrent shared-memory programs. However, its high EXPSPACE-complete complexity poses a challenge when encountered in real-world instances. In this paper, we develop a new approach to this problem which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. Read More

Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidable, the problem to this day lacks any complexity upper bound whatsoever. In this paper, reachability for two-dimensional VASS is shown PSPACE-complete. Read More