Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems

DOI10.1016/0166-218X(90)90144-2zbMath0721.90075MaRDI QIDQ2641226

Kamel Barkaoui, Michel Minoux

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmslogic programmingdeadlocksminimal trapPetri net analysispreconservative components

Mathematics Subject Classification ID

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

• Ltur
• Hornlog

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