The epistemology of nondeterminism

DOI10.1007/S10849-022-09389-4zbMATH Open1516.03008arXiv1803.08193OpenAlexW2790092091MaRDI QIDQ6097774FDOQ6097774

Authors: Adam Bjorndahl 

Publication date: 7 June 2023

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

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.

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

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

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)

Cites Work

• Modal logic
• Title not available (Why is that?)
• Dynamic epistemic logic
• Reasoning About Space: The Modal Way
• Logics of public communications
• Dynamic topological logic
• Title not available (Why is that?)
• Semantics of nondeterminism, concurrency, and communication
• Topological reasoning and the logic of knowledge
• Topo-logic as a dynamic-epistemic logic
• Topological subset space models for public announcements

Cited In (6)

• Interplays of knowledge and non-contingency
• Title not available (Why is that?)
• 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)