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

DOI10.1016/0020-0190(93)90014-ZzbMATH Open0796.68116OpenAlexW2041433942MaRDI QIDQ1209339FDOQ1209339

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

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

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)

Cites Work

• The complexity of propositional linear temporal logics
• Title not available (Why is that?)
• MOLOG: A system that extends PROLOG with modal logic
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Clausal intuitionistic logic I. fixed-point semantics
• Title not available (Why is that?)
• A note on the complexity of the satisfiability of modal Horn clauses

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)