The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic

DOI10.1016/0020-0190(93)90014-ZMaRDI QIDQ1209339zbMATH OpenOpenAlexFDO

Authors Cheng-Chia Chen, I-Peng Lin

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90014-z

zbMATH Keywords

first-order logicsatisfiabilitytemporal logicHorn formulastemporal logic programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Logic programming (68N17)

Recommendations

• The complexity of propositional linear temporal logics
• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• The complexity of propositional linear temporal logics in simple cases
• scientific article; zbMATH DE number 1136071
• Parametrised complexity of satisfiability in temporal logic
• scientific article; zbMATH DE number 2086598
• The computational complexity of hybrid temporal logics
• The complexity of the temporal logic with ``until over general linear time
• Linear-time algorithms for testing the satisfiability of propositional horn formulae

Cites work

• scientific article; zbMATH DE number 4119669 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A note on the complexity of the satisfiability of modal Horn clauses
• Clausal intuitionistic logic I. fixed-point semantics
• MOLOG: A system that extends PROLOG with modal logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of propositional linear temporal logics

Cited in

(8)

• Backdoors for linear temporal logic
• The complexity of propositional linear temporal logics in simple cases
• A Cookbook for Temporal Conceptual Data Modelling with Description Logics
• An artificial neural network satisfiability tester
• scientific article; zbMATH DE number 1950255 (Why is no real title available?)
• scientific article; zbMATH DE number 6917935 (Why is no real title available?)
• scientific article; zbMATH DE number 7439733 (Why is no real title available?)
• Sub-propositional fragments of the interval temporal logic of Allen's relations

This page was built for publication: The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic

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