14 citations · 35 across the 12 of their papers we have counts for
22 papers
Monus semantics in vector addition systems with states
Pascal Baumann, Khushraj Madnani, Filip Mazowiecki +1
Vector addition systems with states (VASS) are a popular model for concurrent systems. However, many decision problems have prohibitively high complexity. Therefore, it is sometime…
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality
Marvin Künnemann, Filip Mazowiecki, Lia Schütze +2
Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodi…
Coverability in 2-VASS with One Unary Counter is in NP
Filip Mazowiecki, Henry Sinclair-Banks, Karol Węgrzycki
Coverability in Petri nets finds applications in verification of safety properties of reactive systems. We study coverability in the equivalent model: Vector Addition Systems with…
On Rational Recursive Sequences
Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki +1
We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of…
Verifying generalised and structural soundness of workflow nets via relaxations
Michael Blondin, Filip Mazowiecki, Philip Offtermatt
Workflow nets are a well-established mathematical formalism for the analysis of business processes arising from either modeling tools or process mining. The central decision proble…
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki +2
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of…
The complexity of soundness in workflow nets
Michael Blondin, Filip Mazowiecki, Philip Offtermatt
Workflow nets are a popular variant of Petri nets that allow for algorithmic formal analysis of business processes. The central decision problems concerning workflow nets deal with…
Continuous One-Counter Automata
Michael Blondin, Tim Leys, Filip Mazowiecki +2
We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper and lower bound tests against the counter…
Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
Floris Geerts, Filip Mazowiecki, Guillermo A. Pérez
In this paper we cast neural networks defined on graphs as message-passing neural networks (MPNNs) in order to study the distinguishing power of different classes of such models. W…
On polynomial recursive sequences
Michaël Cadilhac, Filip Mazowiecki, Charles Paperman +2
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
Pumping lemmas for weighted automata
Agnishom Chattopadhyay, Filip Mazowiecki, Anca Muscholl +1
We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural nu…
Reachability in fixed dimension vector addition systems with states
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić +2
The reachability problem is a central decision problem for formal verification based on vector addition systems with states (VASS), which are equivalent to Petri nets and form one…
Affine Extensions of Integer Vector Addition Systems with States
Michael Blondin, Christoph Haase, Filip Mazowiecki +1
We study the reachability problem for affine -VASS, which are integer vector addition systems with states in which transitions perform affine transformations on the cou…
A Robust Class of Linear Recurrence Sequences
Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote +1
We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show…
Reachability for Bounded Branching VASS
Filip Mazowiecki, Michał Pilipczuk
In this paper we consider the reachability problem for bounded branching VASS. Bounded VASS are a variant of the classic VASS model where all values in all configurations are upper…
The Reachability Problem for Petri Nets is Not Elementary
Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic +2
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and datab…
Weak Cost Register Automata are Still Powerful
Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki +1
We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over with updates using and i…
When is Containment Decidable for Probabilistic Automata?
Laure Daviaud, Marcin Jurdziński, Ranko Lazić +3
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean au…
Eliminating Recursion from Monadic Datalog Programs on Trees
Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski
We study the problem of eliminating recursion from monadic datalog programs on trees with an infinite set of labels. We show that the boundedness problem, i.e., determining whether…
Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
Filip Mazowiecki, Cristian Riveros
Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural pro…
Satisfiability of the Two-Variable Fragment of First-Order Logic over Trees
Witold Charatonik, Emanuel Kieroński, Filip Mazowiecki
We consider the satisfiability problem for the two-variable fragment of first-order logic over finite unranked trees. We work with signatures consisting of some unary predicates an…