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

\(P=NP\)complexity of testing satisfiabilityexponential time complexityHorn propositional logicpolynomial time complexityprogram synthesistemporal logic

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 4185056
• 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)

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

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)