Temporal logics over linear time domains are in PSPACE

DOI10.1016/j.ic.2011.11.002zbMath1280.68112OpenAlexW2046306944MaRDI QIDQ418122

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 logicsatisfiabilityPSPACEtemporal logics

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of temporal logic over the reals
• The decision problem for linear temporal logic
• The monadic second order theory of all countable ordinals
• The monadic theory of order
• The complexity of the temporal logic with ``until over general linear time
• The first order properties of products of algebraic systems
• The Complexity of Temporal Logic with Until and Since over Ordinals
• Logic and Rational Languages of Words Indexed by Linear Orderings
• Temporal Logics over Linear Time Domains Are in PSPACE
• The complexity of propositional linear temporal logics
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• On the elementary theory of linear order
• $ℵ_0$-categoricity of linear orderings
• Decidability of Second-Order Theories and Automata on Infinite Trees

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