CoChat
Sign Up
Cited by 252Logic, Reasoning, and KnowledgeFormal Methods in VerificationMulti-Agent Systems and Negotiation

The DOI matches its Crossref record.

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

Open access
Halpern, Joseph Y., Vardi, Moshe Y.·1989·Journal of Computer and System Sciences
DOI 10.1016/0022-0000(89)90039-1
Open this paper in CoChat — free account

Overview

Integrity signals

Registry

Crossref · 10.1016/0022-0000(89)90039-1

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Knowledge action interchanges presuppose abilities of agents such as Perfect Recall.

    “Knowledge action interchanges presuppose abilities of agents such as Perfect Recall (Halpern & Vardi 1989, van Benthem 2001).”

    From THE STORIES OF LOGIC AND INFORMATION (2008) · cites this paper as Halpern & Vardi 1989

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 21

  1. Abrahamson, 1980, Decidability and Expressiveness of Logics of Processes, Ph.D. thesis, University of Washington Technical Report 80-08-01
  2. Chandy, 1986, How processes learn, Distrib. Comput., 1, 40, 10.1007/BF01843569 · DOI
  3. Chandra, 1981, Alternation, J. Assoc. Comput. Mach., 28, 114, 10.1145/322234.322243 · DOI
  4. Emerson, 1983, Alternative semantics for temporal logics, Theoret. Comput. Sci., 26, 121, 10.1016/0304-3975(83)90082-8 · DOI
  5. Emerson, 1982, Using branching time temporal logic to synthesize synchronization skeletons, Sci. Comput. Programming, 2, 241, 10.1016/0167-6423(83)90017-5 · DOI
  6. Emerson, 1985, Decision procedures and expressiveness in the temporal logic of branching time, J. Comput. System Sci., 30, 1, 10.1016/0022-0000(85)90001-7 · DOI
  7. Emerson, 1986, “Sometimes” and “not never” revisited: On branching vs. linear time, J. Assoc. Comput. Math., 33, 151, 10.1145/4904.4999 · DOI
  8. Fischer, 1987, Interpreting logics of knowledge in propositional dynamic logic with converse, Inform. Process. Lett., 25, 175, 10.1016/0020-0190(87)90129-3 · DOI
  9. Halpern, 1987, Using reasoning about knowledge to analyze distributed systems, Vol. 2
  10. Halpern, 1983, The propositional dynamic logic of deterministic well-structured programs, Theoret. Comput. Sci., 27, 127, 10.1016/0304-3975(83)90097-X · DOI
  11. Harel, 1983, Recurring dominoes: Making the highly undecidable highly understandable, Vol. 158, 177
  12. Harel, 1983, Propositional dynamic logic of nonregular programs, J. Comput. System Sci., 26, 222, 10.1016/0022-0000(83)90014-4 · DOI
  13. Manna, 1984, Synthesis of communicating processes from temporal logic specifications, ACM Trans. Programming Lang. Systems, 6, 68, 10.1145/357233.357237 · DOI
  14. Moses, 1986, Cheating husbands and other stories: A case study of knowledge, action, and communication, Distrib. Comput., 1, 167, 10.1007/BF01661170 · DOI
  15. Parikh, 1985, Distributed processing and the logic of knowledge, Vol. 193, 256
  16. Pease, 1980, Reaching agreement in the presence of faults, J. Assoc. Comput. Mach., 27, 228, 10.1145/322186.322188 · DOI
  17. Pnueli, 1985, Linear and branching structures in the semantics and logics of reactive systems, Vol. 194, 15
  18. Reif, 1985, A multiprocess network logic with temporal and spatial modalities, J. Comput. System Sci., 30, 41, 10.1016/0022-0000(85)90003-0 · DOI
  19. Rosenschein, 1985, Formal theories of knowledge in At and robotics, New Generation Comput., 3, 345, 10.1007/BF03037076 · DOI
  20. Sato, 1977, A study of Kripke-style methods of some modal logics by Gentzen's sequential method, Publ. Res. Inst. Math. Sci., 13, 10.2977/prims/1195189814 · DOI
  21. Sistla, 1985, The complexity of propositional linear temporal logics, J. Assoc. Comput. Mach., 32, 733, 10.1145/3828.3837 · DOI

Cited by

Sorted by citations

Metadata

Authors
Halpern, J. Y., & Vardi, M. Y.
Affiliations
IBM Research - Almaden (US)
ORCID
Venue
Journal of Computer and System Sciences
Publisher
Elsevier BV
Published
1989-02
Volume
38
Issue
1
Pages
195-237
ISSN
0022-0000 (ISSN-L)
DOI
10.1016/0022-0000(89)90039-1
OpenAlex
W2055092188
Cited by
252
References
0
Citations by year
2025: 1 · 2024: 1 · 2023: 7 · 2022: 5 · 2021: 9 · 2020: 6 · 2019: 4 · 2018: 2 · 2017: 10 · 2016: 7 · 2015: 7 · 2014: 12 · 2013: 6 · 2012: 7
FWCI
3.42
Type
journal article
Language
en
Open access
Licence
Locations
Journal of Computer and System Sciences (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
  • Physical Sciences › Computer Science › Artificial Intelligence › Multi-Agent Systems and Negotiation
Keywords
distributed systems, common knowledge, lower bounds, computational complexity, validity problem, PSPACE-completeness, branching time, linear time, forgetting, learning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review