31 citations · 56 across the 19 of their papers we have counts for
21 papers
Structural Liveness of Immediate Observation Petri Nets
Petr Jancar, Jiri Valusek
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…
Simplest Non-Regular Deterministic Context-Free Language
Petr Jancar, Jiri Sima
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 eac…
Resource Bisimilarity in Petri Nets is Decidable
Irina Lomazova, Vladimir Bashkin, Petr Jančar
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…
Countdown games, and simulation on (succinct) one-counter nets
Petr Jancar, Petr Osicka, Zdenek Sawa
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…
Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete
Petr Jančar, Sylvain Schmitz
Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity up…
Equivalence of pushdown automata via first-order grammars
Petr Jancar
A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by Sénizergues (1998, 2005) that subsumes his affirmativ…