Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
From MaRDI portal
Publication:2641226
DOI10.1016/0166-218X(90)90144-2zbMath0721.90075MaRDI QIDQ2641226
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
polynomial algorithmslogic programmingdeadlocksminimal trapPetri net analysispreconservative components
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Pattern recognition, speech recognition (68T10)
Related Items
On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ On liveness in Extended Non Self-Controlling Nets ⋮ Trapping mutual exclusion in the box calculus
Uses Software
Cites Work
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- A switching algorithm for the solution of quadratic Boolean equations
- Deterministic buffer synchronization of sequential processes
- Complete problems for deterministic polynomial time
- The equality problem for vector addition systems is undecidable
- Complexity of some problems in Petri nets
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Marked directed graphs
- Composantes préconservatives minimales d'un réseau de Petri : étude structurelle
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- HORNLOG: A graph-based interpreter for general Horn clauses
- Unit Refutations and Horn Sets
- On the Complexity of Timetable and Multicommodity Flow Problems
- The complexity of theorem-proving procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems