The epistemology of nondeterminism

DOI10.1007/S10849-022-09389-4MaRDI QIDQ6097774zbMATH OpenOpenAlexFDO

Authors Adam Bjorndahl

Publication date 7 June 2023

Published in Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.08193

zbMATH Keywords

topologyepistemic logicmodal logicnondeterminismpropositional dynamic logic

Mathematics Subject Classification ID

Logics of knowledge and belief (including belief change) (03B42) Modal logic (including the logic of norms) (03B45)

Abstract: This paper proposes new semantics for nondeterministic program execution, replacing the standard relational semantics for propositional dynamic logic (PDL). Under these new semantics, program execution is represented as fundamentally deterministic (i.e., functional), while nondeterminism emerges as an epistemic relationship between the agent and the system: intuitively, the nondeterministic outcomes of a given process are precisely those that cannot be ruled out in advance. We formalize these notions using topology and the framework of dynamic topological logic (DTL). We show that DTL can be used to interpret the language of PDL in a manner that captures the intuition above, and moreover that continuous functions in this setting correspond exactly to deterministic processes. We also prove that certain axiomatizations of PDL remain sound and complete with respect to the corresponding classes of dynamic topological models. Finally, we extend the framework to incorporate knowledge using the machinery of subset space logic, and show that the topological interpretation of public announcements coincides exactly with a natural interpretation of test programs.

Recommendations

• The epistemology of nondeterminism
• Determinism and non-determinism in PDL
• A stochastic interpretation of propositional dynamic logic: expressivity
• A nondeterministic program logic
• Logical analysis of demonic nondeterministic programs

Cites work

• scientific article; zbMATH DE number 3574936 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• Dynamic epistemic logic
• Dynamic topological logic
• Logics of public communications
• Modal logic
• Reasoning About Space: The Modal Way
• Semantics of nondeterminism, concurrency, and communication
• Topo-logic as a dynamic-epistemic logic
• Topological reasoning and the logic of knowledge
• Topological subset space models for public announcements

Cited in

(6)

• Interplays of knowledge and non-contingency
• scientific article; zbMATH DE number 5917702 (Why is no real title available?)
• Nondeterminism through well-founded choice
• Note on Rescher's formalization of Aristotelian indeterminism
• Epistemology versus non-causal realism
• The epistemology of nondeterminism

This page was built for publication: The epistemology of nondeterminism

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