Zobrazeno 1 - 10
of 81
pro vyhledávání: '"Jancar, Petr"'
Autor:
Jancar, Petr
The textbook proofs of Commoner's theorem characterizing liveness in free-choice Petri nets are given in contexts of technical notions and claims that make the proofs look a bit long. The aim of this note is to give a concise self-contained proof.
Externí odkaz:
http://arxiv.org/abs/2401.12067
Autor:
Jančar, Petr, Leroux, Jérôme
A set of configurations $H$ is a home-space for a set of configurations $X$ of aPetri net if every configuration reachable from (any configuration in) $X$ can reach (some configuration in) $H$. The semilinear home-space problem for Petri nets asks, g
Externí odkaz:
http://arxiv.org/abs/2207.02697
Autor:
Jancar, Petr, Valusek, Jiri
Publikováno v:
Fundamenta Informaticae, Volume 188, Issue 3 (April 18, 2023) fi:10281
We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently intro
Externí odkaz:
http://arxiv.org/abs/2112.15524
Autor:
Jancar, Petr, Sima, Jiri
We introduce a new notion of C-simple problems for a class C of decision problems (i.e. languages), w.r.t. a particular reduction. A problem is C-simple if it can be reduced to each problem in C. This can be viewed as a conceptual counterpart to C-ha
Externí odkaz:
http://arxiv.org/abs/2102.10416
Publikováno v:
Fundamenta Informaticae, Volume 186, Issues 1-4: Trakhtenbrot's centenary (October 21, 2022) fi:8781
Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of
Externí odkaz:
http://arxiv.org/abs/2101.07711
Publikováno v:
Logical Methods in Computer Science, Volume 19, Issue 1 (February 9, 2023) lmcs:6739
We answer an open complexity question by Hofman, Lasota, Mayr, Totzke (LMCS 2016) for simulation preorder on the class of succinct one-counter nets (i.e., one-counter automata with no zero tests where counter increments and decrements are integers wr
Externí odkaz:
http://arxiv.org/abs/2008.11753
Autor:
Jančar, Petr, Schmitz, Sylvain
Publikováno v:
34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019)
Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by S\'enizergues (1998, 2005). We provide the first known complexity upper bound for this famous problem, in the equivalent setting of firs
Externí odkaz:
http://arxiv.org/abs/1901.07170
Autor:
Jancar, Petr
A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by S\'enizergues (1998, 2005) that subsumes his affirmative solution of the famous decidability question for deterministic pus
Externí odkaz:
http://arxiv.org/abs/1812.03518
We note that the remarkable EXPSPACE-hardness result in [G\"oller, Haase, Ouaknine, Worrell, ICALP 2010] ([GHOW10] for short) allows us to answer an open complexity question for simulation preorder of succinct one counter nets (i.e., one counter auto
Externí odkaz:
http://arxiv.org/abs/1801.01073
Publikováno v:
Logical Methods in Computer Science, Volume 14, Issue 4 (November 15, 2018) lmcs:4077
We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without eps
Externí odkaz:
http://arxiv.org/abs/1711.06120