1 citations · 3 across the 7 of their papers we have counts for
11 papers · 1 filter
Parameterized Reachability for Register Machines with Data
Parosh Aziz Abdulla, Mohammed Faouzi Atig, Abhijith R Nair +2
We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set…
Bounded treewidth, multiple context-free grammars, and downward closures
C. Aiswarya, Pascal Baumann, Prakash Saivasan +2
The reachability problem in multi-pushdown automata (MPDA) has many applications in static analysis of recursive programs. An example is safety verification of multi-threaded recur…
Equivalence of Deterministic Weighted Real-time One-Counter Automata
Prince Mathew, Vincent Penelle, Prakash Saivasan +1
This paper introduces deterministic weighted real-time one-counter automaton (DWROCA). A DWROCA is a deterministic real-time one-counter automaton whose transitions are assigned a…
Satisfiability of Context-free String Constraints with Subword-ordering and Transducers
C Aiswarya, Soumodev Mal, Prakash Saivasan
We study the satisfiability of string constraints where context-free membership constraints may be imposed on variables. Additionally a variable may be constrained to be a subword…
Weighted One-Deterministic-Counter Automata
Prince Mathew, Vincent Penelle, Prakash Saivasan +1
We introduce weighted one-deterministic-counter automata (ODCA). These are weighted one-counter automata (OCA) with the property of counter-determinacy, meaning that all paths labe…
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…
On the Upward/Downward Closures of Petri Nets
Mohamed Faouzi Atig, Roland Meyer, Sebastian Muskalla +1
We study the size and the complexity of computing finite state automata (FSA) representing and approximating the downward and the upward closure of Petri net languages with coverab…
Nested Words for Order-2 Pushdown Systems
C. Aiswarya, Paul Gastin, Prakash Saivasan
We study linear time model checking of collapsible higher-order pushdown systems (CPDS) of order 2 (manipulating stack of stacks) against MSO and PDL (propositional dynamic logic w…
On the Complexity of Bounded Context Switching
Peter Chini, Jonathan Kolberg, Andreas Krebs +2
Bounded context switching (BCS) is an under-approximate method for finding violations to safety properties in shared memory concurrent programs. Technically, BCS is a reachability…
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)…