20 citations · 59 across the 20 of their papers we have counts for
15 papers · 1 filter
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…
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…
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…
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…
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…
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…
Relating timed and register automata
Diego Figueira, Piotr Hofman, Sławomir Lasota
Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between…