An Algorithm for the General Petri Net Reachability Problem
From MaRDI portal
Publication:3677184
DOI10.1137/0213029zbMath0563.68057OpenAlexW2164003033WikidataQ56638999 ScholiaQ56638999MaRDI QIDQ3677184
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213029
Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40)
Related Items
Coverability in 2-VASS with one unary counter is in NP, Infinite results, Coverability and Termination in Recursive Petri Nets, Computing with chemical reaction networks: a tutorial, Constrained properties, semilinear systems, and Petri nets, Unnamed Item, The undecidability theorem for the Horn-like fragment of linear logic (Revisited), A pumping lemma for random permitting context languages, Applying CEGAR to the Petri Net State Equation, Linear logic as a logic of computations, Reachability problems on reliable and lossy queue automata, Petri net algorithms in the theory of matrix grammars, Alternating two-way AC-tree automata, Bounded self-stabilizing Petri nets, On polynomial ideals, their complexity, and applications, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, An exercise in structural congruence, Incremental construction of coverability graphs, Context-free commutative grammars with integer counters and resets, Petri nets, Horn programs, linear logic and vector games, On the Relationship between π-Calculus and Finite Place/Transition Petri Nets, Weak Time Petri Nets Strike Back!, Finding a partial solution to a linear system of equations in positive integers, Deciding a class of path formulas for conflict-free Petri nets, On selective unboundedness of VASS, Problems concerning fairness and temporal logic for conflict-free Petri nets, Linear logic automata, On the verification of membrane systems with dynamic structure, Decidability of weak fairness in petri nets, Handles and reachability analysis of free choice nets, High undecidability of weak bisimilarity for Petri nets, A Note on Decidable Separability by Piecewise Testable Languages, Macro liveness graph and liveness of \(\omega\)-independent unbounded nets, Linear time analysis of properties of conflict-free and general Petri nets, The reachability problem for branching vector addition systems requires doubly-exponential space, Undecidable problems in unreliable computations., On detectability of labeled Petri nets and finite automata, Unnamed Item, Encoding the dynamics of deterministic systems, Unnamed Item, Deciding Structural Liveness of Petri Nets, Tableau methods for PA-processes, Honesty by Typing, Decidability of a temporal logic problem for Petri nets, Checking system boundedness using ordinary differential equations, Refining the hierarchy of blind multicounter languages and twist-closed trios., Unnamed Item, Reduction and covering of infinite reachability trees, Open Petri nets, Petri nets and regular processes, Deciding properties of integral relational automata, Deciding Fast Termination for Probabilistic VASS with Nondeterminism, Static analysis and stochastic search for reachability problem, On the decision problem for MELL, Reachability analysis of fragments of mobile ambients in AC term rewriting, The complexity of problems involving structurally bounded and conservative Petri nets, A unified approach for deciding the existence of certain petri net paths, Concurrent regular expressions and their relationship to Petri nets, Verification of membrane systems with delays via Petri nets with delays, Undecidability of bisimilarity for Petri nets and some related problems, Complexity results for 1-safe nets, Proving nonreachability by modulo-invariants, Strategic reasoning with a bounded number of resources: the quest for tractability, Finite automata on directed graphs, Finding a Witness Path for Non-liveness in Free-Choice Nets, The context-freeness of the languages associated with vector addition systems is decidable, Reachability in cyclic extended free-choice systems, Chip-firing games on directed graphs, Partially commutative inverse monoids., Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm, Unnamed Item, A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application, Normal and sinkless Petri nets, Collaborative planning with confidentiality, Communicating processes, scheduling, and the complexity of nontermination, Decidability of code properties, Reachability in Timed Counter Systems, When ambients cannot be opened, Unnamed Item, Unnamed Item, Unnamed Item, Any ground associative-commutative theory has a finite canonical system, On the Reachability Problem in P Systems with Mobile Membranes, On the Dynamics of PB Systems with Volatile Membranes, Minimal Cost Reachability/Coverability in Priced Timed Petri Nets, On decidability of LTL model checking for process rewrite systems, Distributed semantics for the \(\pi \)-calculus based on Petri nets with inhibitor ARCS, Unnamed Item, TOWARD UNDERSTANDING THE GENERATIVE CAPACITY OF ERASING RULES IN MATRIX GRAMMARS, Non axiomatisability of positive relation algebras with constants, via graph homomorphisms, Erasing in Petri Net Languages and Matrix Grammars, Fifo nets without order deadlock, Reachability in Petri Nets with Inhibitor Arcs, Projections of vector addition system reachability sets are semilinear, A shrinking lemma for random forbidding context languages, Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable, Reachability analysis of low-order discrete state reaction networks obeying conservation laws, On Petri Nets with Hierarchical Special Arcs, Unnamed Item, Process rewrite systems., Regular Graphs and the Spectra of Two-Variable Logic with Counting, Type-based information flow analysis for the \(\pi\)-calculus, Petri net models of flexible and automated manufacturing systems: a survey, A taxonomy of fairness and temporal logic problems for Petri nets, Analysis issues in Petri nets with inhibitor arcs, Coverability, Termination, and Finiteness in Recursive Petri Nets, Flat Petri nets (invited talk), A lazy query scheme for reachability analysis in Petri nets, Characterization and complexity results on jumping finite automata
