Efficient Temporal Satisfiability

DOI10.1093/LOGCOM/2.2.173MaRDI QIDQ4013255zbMATH OpenOpenAlexFDO

Authors Tom Sadler, Jai Srinivasan, E. Allen Emerson

Publication date 27 September 1992

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/2.2.173

zbMATH Keywords

temporal logicpolynomial time complexityprogram synthesisexponential time complexity\(P=NP\)complexity of testing satisfiabilityHorn propositional logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70)

Recommendations

• The complexity of temporal constraint satisfaction problems
• Temporal constraint satisfaction problems in fixed-point logic
• scientific article; zbMATH DE number 2202277
• Efficient solving of time-dependent answer set programs
• Publication:5750422
• Tractable combinations of temporal CSPs
• Efficient solution techniques for disjunctive temporal reasoning problems
• Efficient algorithms for qualitative reasoning about time
• Discrete temporal constraint satisfaction problems

Cited in

(6)

• ITSAT: An Efficient SAT-Based Temporal Planner
• Robust Approximation of Temporal CSP
• Temporal induction by incremental SAT solving
• A temporal logic-based approach for the description of object behavior evolution
• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• Model Theoretic Syntax and Parsing

This page was built for publication: Efficient Temporal Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4013255)