Zobrazeno 1 - 10
of 79
pro vyhledávání: '"Hofman, Piotr"'
Autor:
Chistikov, Dmitry, Czerwiński, Wojciech, Hofman, Piotr, Mazowiecki, Filip, Sinclair-Banks, Henry
In this paper we propose two new subclasses of Petri nets with resets, for which the reachability and coverability problems become tractable. Namely, we add an acyclicity condition that only applies to the consumptions and productions, not the resets
Externí odkaz:
http://arxiv.org/abs/2310.01992
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 where constraints are expressed by an orbit-finite system of linear inequ
Externí odkaz:
http://arxiv.org/abs/2302.00802
Autor:
Czerwiński, Wojciech, Hofman, Piotr
Publikováno v:
LIPIcs, 2022, 243, 16:1--16:22, Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASSes) with the acceptance condition defined by the set of accepting states (and more generally by some upward-closed conditions). In ge
Externí odkaz:
http://arxiv.org/abs/2202.08033
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 procedure works for every field (and even commutative ring) under mild effec
Externí odkaz:
http://arxiv.org/abs/2201.09060
Autor:
Hofman, Piotr, Różycki, Jakub
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 4 (December 12, 2022) lmcs:8459
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 are functions from k-element subsets of the unordered-data set to vecto
Externí odkaz:
http://arxiv.org/abs/2109.03025
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 orbit-finite unions instead of only finite ones. We prove that commut
Externí odkaz:
http://arxiv.org/abs/2104.12018
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 defined by a set of final states (i.e., the coverability language). We show
Externí odkaz:
http://arxiv.org/abs/2007.10907
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 counter value, or with an upper bound on the allowed counter value during
Externí odkaz:
http://arxiv.org/abs/2005.03435
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 extension of timed automata (TA) with context-free branching rules, and as s
Externí odkaz:
http://arxiv.org/abs/1907.01240
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 disequality of tokens. UDPN are well-structured, so the coverability and termin
Externí odkaz:
http://arxiv.org/abs/1902.05604