20 citations · 59 across the 20 of their papers we have counts for
25 papers
Integer reachability in VASS with transfers: a refined complexity analysis
Tymoteusz Kucharek, Piotr Hofman
Integer reachability is NP-complete for vector addition systems with states (VASS), but becomes PSPACE-complete in the presence of transfer operations. We refine this complexity ga…
Orbit-finite linear programming
Arka Ghosh, Piotr Hofman, Sławomir Lasota
An infinite set is orbit-finite if, up to permutations of the underlying structure of atoms, it has only finitely many elements. We study a generalisation of linear programming whe…
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
Wojciech Czerwiński, Piotr Hofman
We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASS) with the acceptance condition defined by the set of accepting…
Solvability of orbit-finite systems of linear equations
Arka Ghosh, Piotr Hofman, Sławomir Lasota
We study orbit-finite systems of linear equations, in the setting of sets with atoms. Our principal contribution is a decision procedure for solvability of such systems. The proced…
Linear equations for unordered data vectors in
Piotr Hofman, Jakub Różycki
Following a recently considered generalisation of linear equations to unordered-data vectors and to ordered-data vectors, we perform a further generalisation to data vectors that a…
Parikh's theorem for infinite alphabets
Piotr Hofman, Marta Juzepczuk, Sławomir Lasota +1
We investigate commutative images of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for…
Universality Problem for Unambiguous VASS
Wojciech Czerwiński, Diego Figueira, Piotr Hofman
We study languages of unambiguous VASS, that is, Vector Addition Systems with States, whose transitions read letters from a finite alphabet, and whose acceptance condition is defin…
Parametrized Universality Problems for One-Counter Nets
Shaull Almagor, Udi Boker, Piotr Hofman +1
We study the language universality problem for One-Counter Nets, also known as 1-dimensional Vector Addition Systems with States (1-VASS), parameterized either with an initial coun…
Timed Basic Parallel Processes
Lorenzo Clemente, Piotr Hofman, Patrick Totzke
Timed basic parallel processes (TBPP) extend communication-free Petri nets (aka. BPP or commutative context-free grammars) by a global notion of time. TBPP can be seen as an extens…
Continuous Reachability for Unordered Data Petri nets is in PTime
Utkarsh Gupta, Preey Shah, S. Akshay +1
Unordered data Petri nets (UDPN) are an extension of classical Petri nets with tokens that carry data from an infinite domain and where transitions may check equality and disequali…
Unboundedness problems for languages of vector addition systems
Wojciech Czerwiński, Piotr Hofman, Georg Zetzsche
A vector addition system (VAS) with an initial and a final marking and transition labels induces a language. In part because the reachability problem in VAS remains far from being…
Linear Equations with Ordered Data
Piotr Hofman, Sławomir Lasota
Following a recently considered generalization of linear equations to unordered data vectors, we perform a further generalization to ordered data vectors. These generalized equatio…
Linear Combinations of Unordered Data Vectors
Piotr Hofman, Jérôme Leroux, Patrick Totzke
Data vectors generalise finite multisets: they are finitely supported functions into a commutative monoid. We study the question if a given data vector can be expressed as a finite…
Bounding Average-energy Games
Patricia Bouyer, Piotr Hofman, Nicolas Markey +2
We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, de…
Simulation Problems Over One-Counter Nets
Piotr Hofman, Slawomir Lasota, Richard Mayr +1
One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1…
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)…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…
Tightening the Complexity of Equivalence Problems for Commutative Grammars
Christoph Haase, Piotr Hofman
We show that the language equivalence problem for regular and context-free commutative grammars is coNEXP-complete. In addition, our lower bound immediately yields further coNEXP-c…
Infinite-State Energy Games
Parosh Aziz Abdulla, Mohamed Faouzi Atig, Piotr Hofman +3
Energy games are a well-studied class of 2-player turn-based games on a finite graph where transitions are labeled with integer vectors which represent changes in a multidimensiona…
Trace Inclusion for One-Counter Nets Revisited
Piotr Hofman, Patrick Totzke
One-Counter nets (OCN) consist of a nondeterministic finite control and a single integer counter that cannot be fully tested for zero. They form a natural subclass of both One-Coun…
Simulation Over One-counter Nets is PSPACE-Complete
Piotr Hofman, Slawomir Lasota, Richard Mayr +1
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other…
Reachability Problem for Weak Multi-Pushdown Automata
Wojciech Czerwiński, Piotr Hofman, SŁawomir Lasota
This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all tran…
Decidability of Weak Simulation on One-counter Nets
Piotr Hofman, Richard Mayr, Patrick Totzke
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with only a weak test for zero. We show that weak…
Approximating Weak Bisimilarity of Basic Parallel Processes
Piotr Hofman, Patrick Totzke
This paper explores the well known approximation approach to decide weak bisimilarity of Basic Parallel Processes. We look into how different refinement functions can be used to pr…