The complexity of reasoning about knowledge and time. I: Lower bounds

DOI10.1016/0022-0000(89)90039-1zbMath0672.03015OpenAlexW2055092188MaRDI QIDQ1119565

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90039-1

zbMATH Keywords

synchronization parallel interacting processes propositional time logic specification of distributed computing systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Theory of operating systems (68N25)

Related Items (54)

Hierarchical information and the synthesis of distributed strategies ⋮ Logics of Rational Interaction ⋮ Computation as social agency: what, how and who ⋮ Undecidability of QLTL and QCTL with two variables and one monadic predicate letter ⋮ Discrete linear temporal logic with knowing-value operator ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ First-order temporal verification in practice ⋮ Building an Epistemic Logic for Argumentation ⋮ Diagnosability of fair transition systems ⋮ Common knowledge and update in finite environments ⋮ Synchronizing Automata with Extremal Properties ⋮ Modeling belief in dynamic systems. I: Foundations ⋮ Merging DEL and ETL ⋮ Preface to the special issue: Temporal logics of agency ⋮ Assumption-based runtime verification ⋮ Decidability of logics based on an indeterministic metric tense logic ⋮ IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING? ⋮ The Logic of Public Announcements, Common Knowledge, and Private Suspicions ⋮ A history based logic for dynamic preference updates ⋮ Book review of: Johan van Benthem, Logical dynamics of information and interaction ⋮ A resolution-based proof method for temporal logics of knowledge and belief ⋮ Exploring the tractability border in epistemic tasks ⋮ Knowledge and communication: A first-order theory ⋮ A GENERAL NOTION OF UNIFORM STRATEGIES ⋮ A guide to completeness and complexity for modal logics of knowledge and belief ⋮ Some comments on history based structures ⋮ Infinite games with finite knowledge gaps ⋮ Interactions between knowledge, action and commitment within agent dynamic logic ⋮ Modeling reasoning in a social setting ⋮ Using temporal logics of knowledge for specification and verification -- a case study ⋮ The logic of knowledge based obligation ⋮ Non-primitive recursive decidability of products of modal logics with expanding domains ⋮ Model-based safety assessment of a triple modular generator with xSAP ⋮ The Complexity of Decomposing Modal and First-Order Theories ⋮ Knowledge condition games ⋮ Intensional protocols for dynamic epistemic logic ⋮ Knowledge and Local Actions ⋮ Modelling knowledge and action in distributed systems ⋮ The price of universality ⋮ First-Order Linear-Time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment ⋮ Revisiting Satisfiability and Model-Checking for CTLK with Synchrony and Perfect Recall ⋮ Two Logical Faces of Belief Revision ⋮ Tableaux for logics of time and knowledge with interactions relating to synchrony ⋮ Merging frameworks for interaction ⋮ Temporal Aspects of the Dynamics of Knowledge ⋮ Logic and Game Theory ⋮ Modal logic, truth, and the master modality. ⋮ Toward a theory of play: a logical perspective on games and interaction ⋮ Temporal Logics of Knowledge and their Applications in Security ⋮ Uniform strategies, rational relations and jumping automata ⋮ A Tableau-Based Proof Method for Temporal Logics of Knowledge and Belief ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries ⋮ Clausal resolution in a logic of rational agency ⋮ \({\mathcal E}\)-connections of abstract description systems

Cites Work

This page was built for publication: The complexity of reasoning about knowledge and time. I: Lower bounds