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 algorithms; logic programming; deadlocks; minimal trap; Petri net analysis; preconservative components

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B35: Deterministic scheduling theory in operations research

68T10: Pattern recognition, speech recognition

Related Items

On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity, 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