Igor Walukiewicz
YOU?
Author Swipe
View article: Distributed controller synthesis for deadlock avoidance
Distributed controller synthesis for deadlock avoidance Open
We consider the distributed control synthesis problem for systems with locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction this problem is undecidable even for three processes each …
View article: Infinite lexicographic products of positional objectives
Infinite lexicographic products of positional objectives Open
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs. Recently, [Ohlmann, TheoretiCS 2023] established that positionality of prefix-independent objectives is preserv…
View article: Minimal History-Deterministic Co-Buchi Automata: Congruences and Passive Learning
Minimal History-Deterministic Co-Buchi Automata: Congruences and Passive Learning Open
Abu Radi and Kupferman (2019) demonstrated the efficient minimization of history-deterministic (transition-based) co-Büchi automata, building on the results of Kuperberg and Skrzypczak (2015). We give a congruence-based description of thes…
View article: Revisiting Stateful Partial-Order Reduction
Revisiting Stateful Partial-Order Reduction Open
The goal of partial-order methods is to accelerate the exploration of concurrent systems by examining only a representative subset of all possible runs. The stateful approach builds a transition system with representative runs, while the s…
View article: Krivine machines and higher-order schemes
Krivine machines and higher-order schemes Open
We propose a new approach to analysing higher-order recursive schemes. Many results in the literature use automata models generalising pushdown automata, most notably higher-order pushdown automata with collapse (CPDA). Instead, we propose…
View article: Model-checking parametric lock-sharing systems against regular constraints
Model-checking parametric lock-sharing systems against regular constraints Open
In parametric lock-sharing systems processes can spawn new processes to run in parallel, and can create new locks. The behavior of every process is given by a pushdown automaton. We consider infinite behaviors of such systems under strong …
View article: Model-Checking Parametric Lock-Sharing Systems Against Regular Constraints
Model-Checking Parametric Lock-Sharing Systems Against Regular Constraints Open
In parametric lock-sharing systems processes can spawn new processes to run in parallel, and can create new locks. The behavior of every process is given by a pushdown automaton. We consider infinite behaviors of such systems under strong …
View article: Distributed controller synthesis for deadlock avoidance
Distributed controller synthesis for deadlock avoidance Open
We consider the distributed control synthesis problem for systems with locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction this problem is undecidable even for three processes each …
View article: Distributed Controller Synthesis for Deadlock Avoidance
Distributed Controller Synthesis for Deadlock Avoidance Open
We consider the distributed control synthesis problem for systems with locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction this problem is undecidable even for three processes each …
View article: Checking Timed Büchi Automata Emptiness Using the Local-Time Semantics
Checking Timed Büchi Automata Emptiness Using the Local-Time Semantics Open
We study the Büchi non-emptiness problem for networks of timed automata. Standard solutions consider the network as a monolithic timed automaton obtained as a synchronized product and build its zone graph on-the-fly under the classical glo…
View article: Active Learning for Sound Negotiations
Active Learning for Sound Negotiations Open
We present two active learning algorithms for sound deterministic negotiations. Sound deterministic negotiations are models of distributed systems, a kind of Petri nets or Zielonka automata with additional structure. We show that this addi…
View article: Verifying higher-order concurrency with data automata
Verifying higher-order concurrency with data automata Open
Using a combination of automata-theoretic and game-semantic techniques, we propose a method for analysing higher-order concurrent programs. Our language of choice is Finitary Idealised Concurrent Algol (FICA) due to its relatively simple f…
View article: Leafy Automata for Higher-Order Concurrency
Leafy Automata for Higher-Order Concurrency Open
Finitary Idealized Concurrent Algol (FICA) is a prototypical programming language combining functional, imperative, and concurrent computation. There exists a fully abstract game model of FICA, which in principle can be used to prove equiv…
View article: Leafy automata for higher-order concurrency
Leafy automata for higher-order concurrency Open
Finitary Idealized Concurrent Algol ( $$\mathsf {FICA}$$ ) is a prototypical programming language combining functional, imperative, and concurrent computation. There exists a fully abstract game model of $$\mathsf {FICA}$$ , which in p…
View article: Why Liveness for Timed Automata Is Hard, and What We Can Do About It
Why Liveness for Timed Automata Is Hard, and What We Can Do About It Open
The reachability problem for timed automata asks if a given automaton has a run leading to an accepting state, and the liveness problem asks if the automaton has an infinite run that visits accepting states infinitely often. Both of these …
View article: Characterizing Consensus in the Heard-Of Model
Characterizing Consensus in the Heard-Of Model Open
The Heard-Of model is a simple and relatively expressive model of distributed computation. Because of this, it has gained a considerable attention of the verification community. We give a characterization of all algorithms solving consensu…
View article: Revisiting local time semantics for networks of timed automata
Revisiting local time semantics for networks of timed automata Open
International audience
View article: Revisiting Local Time Semantics for Networks of Timed Automata
Revisiting Local Time Semantics for Networks of Timed Automata Open
We investigate a zone based approach for the reachability problem in timed automata. The challenge is to alleviate the size explosion of the search space when considering networks of timed automata working in parallel. In the timed setting…
View article: Soundness in negotiations
Soundness in negotiations Open
Negotiations are a formalism for describing multiparty distributed cooperation. Alternatively, they can be seen as a model of concurrency with synchronized choice as communication primitive. Well-designed negotiations must be sound, meanin…
View article: Static analysis of deterministic negotiations
Static analysis of deterministic negotiations Open
Negotiation diagrams are a model of concurrent computation akin to workflow Petri nets. Deterministic negotiation diagrams, equivalent to the much studied and used free-choice workflow Petri nets, are surprisingly amenable to verification.…
View article: Typing weak MSOL properties
Typing weak MSOL properties Open
We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations. Weak monadic second-order logic (…
View article: Automata theory and higher-order model-checking
Automata theory and higher-order model-checking Open
In verification, an automata theoretic approach is by now a standard. In order to extend this approach to higher-order programs we need a good understanding of higher-order control flow, and for this semantics has the right tools. We prese…
View article: Reachability for dynamic parametric processes
Reachability for dynamic parametric processes Open
In a dynamic parametric process every subprocess may spawn arbitrarily many, identical child processes, that may communicate either over global variables, or over local variables that are shared with their parent. We show that reachability…
View article: Idealized Algol with ground recursion, and PDA equivalence
Idealized Algol with ground recursion, and PDA equivalence Open
HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or…
View article: Typing weak MSOL properties
Typing weak MSOL properties Open
We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations. Weak monadic second-order logic (…