Zobrazeno 1 - 10
of 81
pro vyhledávání: '"Mazowiecki, Filip"'
We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recen
Externí odkaz:
http://arxiv.org/abs/2310.02204
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
Vector addition systems with states (VASS) are a popular model for concurrent systems. However, many decision problems have prohibitively high complexity. Therefore, it is sometimes useful to consider overapproximating semantics in which these proble
Externí odkaz:
http://arxiv.org/abs/2308.14926
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 encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackof
Externí odkaz:
http://arxiv.org/abs/2305.01581
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 States (VASS). A k-VASS can be seen as k counters and a finite automat
Externí odkaz:
http://arxiv.org/abs/2301.13543
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 depth 1, where the next values are computed as rational functions of t
Externí odkaz:
http://arxiv.org/abs/2210.01635
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 problems for workflow nets are $k$-soundness, generalised soundness and stru
Externí odkaz:
http://arxiv.org/abs/2206.02606
Autor:
Czerwiński, Wojciech, Lefaucheux, Engel, Mazowiecki, Filip, Purser, David, Whiteland, Markus A.
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of boundedness and zero isolation ask whether there is a sequence of wor
Externí odkaz:
http://arxiv.org/abs/2205.13516
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 soundness, where the initial and final configurations are specified.
Externí odkaz:
http://arxiv.org/abs/2201.05588
Autor:
Cadilhac, Michaël1 (AUTHOR), Mazowiecki, Filip2 (AUTHOR) filipm@mpi-sws.org, Paperman, Charles3 (AUTHOR), Pilipczuk, Michał4 (AUTHOR), Sénizergues, Géraud5 (AUTHOR)
Publikováno v:
Theory of Computing Systems. Aug2024, Vol. 68 Issue 4, p593-614. 22p.
