6 papers
A Framework for Consistency Algorithms
Peter Chini, Prakash Saivasan
We present a framework that provides deterministic consistency algorithms for given memory models. Such an algorithm checks whether the executions of a shared-memory concurrent pro…
Complexity of Liveness in Parameterized Systems
Peter Chini, Roland Meyer, Prakash Saivasan
We investigate the fine-grained complexity of liveness verification for leader contributor systems. These consist of a designated leader thread and an arbitrary number of identical…
Liveness in Broadcast Networks
Peter Chini, Roland Meyer, Prakash Saivasan
We study liveness and model checking problems for broadcast networks, a system model of identical clients communicating via message passing. The first problem that we consider is L…
Fast Witness Counting
Peter Chini, Rehab Massoud, Roland Meyer +1
We study the witness-counting problem: given a set of vectors in the -dimensional vector space over , a target vector , and an integer , count all ways t…
Fine-Grained Complexity of Safety Verification
Peter Chini, Roland Meyer, Prakash Saivasan
We study the fine-grained complexity of Leader Contributor Reachability (LCR) and Bounded-Stage Reachability (BSR), two variants of the safety verification problem for shared memor…
Complexity of regular abstractions of one-counter languages
Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman +3
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA)…