Temporal logics over linear time domains are in PSPACE

DOI10.1016/J.IC.2011.11.002MaRDI QIDQ418122zbMATH OpenOpenAlexFDO

Authors Alexander Rabinovich

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.11.002

zbMATH Keywords

complexitymonadic second-order logicPSPACEsatisfiabilitytemporal logics

Mathematics Subject Classification ID

Temporal logic (03B44) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Temporal logics over linear time domains are in PSPACE
• The complexity of propositional linear temporal logics
• The complexity of the temporal logic with ``until over general linear time
• The complexity of linear-time temporal logic over the class of ordinals
• The complexity of temporal logic over the reals

Cites work

• ℵ_0-categoricity of linear orderings
• Automata and temporal logic over arbitrary linear time
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Decidability of Second-Order Theories and Automata on Infinite Trees
• scientific article; zbMATH DE number 747023 (Why is no real title available?)
• scientific article; zbMATH DE number 1086492 (Why is no real title available?)
• scientific article; zbMATH DE number 1834651 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Logic and Rational Languages of Words Indexed by Linear Orderings
• On the elementary theory of linear order
• Temporal logics over linear time domains are in PSPACE
• The complexity of propositional linear temporal logics
• The complexity of temporal logic over the reals
• The Complexity of Temporal Logic with Until and Since over Ordinals
• The complexity of the temporal logic with ``until over general linear time
• The decision problem for linear temporal logic
• The first order properties of products of algebraic systems
• The monadic second order theory of all countable ordinals
• The monadic theory of order

Cited in

(21)

• The complexity of the temporal logic with ``until over general linear time
• Complexity of monodic guarded fragments over linear and real time
• Temporal logics on strings with prefix relation
• The complexity of linear-time temporal logic over the class of ordinals
• About the temporal logic of the lexicographic products of unbounded dense linear orders: a new study of its computability
• The Complexity of Temporal Logic with Until and Since over Ordinals
• Temporal logics over linear time domains are in PSPACE
• The complexity of propositional linear temporal logics
• scientific article; zbMATH DE number 2086598 (Why is no real title available?)
• scientific article; zbMATH DE number 757645 (Why is no real title available?)
• scientific article; zbMATH DE number 7561320 (Why is no real title available?)
• Automated Deduction – CADE-20
• Pspace-Completeness of the Temporal Logic of Sub-Intervals and Suffixes
• Time and Gödel: fuzzy temporal reasoning in PSPACE
• Decidability of Difference Logic over the Reals with Uninterpreted Unary Predicates
• Non-emptiness test for automata over words indexed by the reals and rationals
• Epsilon automata on linear orderings
• On the theory of order over real numbers
• Deciding reachability in automata on words indexed by the reals and rationals
• Quantitative temporal logics over the reals: PSpace and below
• Simple interpretations among complicated theories

This page was built for publication: Temporal logics over linear time domains are in PSPACE

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