David Pym

David Pym

Auto-generated profile, based on publicly available information

David Pym

University College London

Research Focus & Metrics

Academic Career Length

27Years (2000-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 January 2025 in Studia Logica
Verified
Journal Article
Open access
PDF file
AGAlexander V. Gheorghiu
Alexander V. Gheorghiu
DPDavid J. Pym
David J. Pym
Proof-theoretic semantics (P-tS) is the approach to meaning in logic based on proof (as opposed to truth). There are two major approaches to P-tS: proof-theoretic validity (P-tV) and base-extension semantics (B-eS). The former is a semantics of arguments, and the latter is a semantics of logical constants. This paper demonstrates that the B-eS for intuitionistic propositional logic (IPL) encapsulates the declarative content of a version of P-tV based on the elimination rules. This explicates how the B-eS for IPL works, and shows the completeness of this version of P-tV.

1 January 2003 in ACM Transactions on Computational Logic
Verified
Journal Article
Open access
JHJames Harland
James Harland
DPDavid Pym
David Pym
We consider the problem of searching for proofs in sequential presentations of logics with multiplicative (or intensional) connectives. Specifically, we start with the multiplicative fragment of linear logic and extend, on the one hand, to linear logic with its additives and, on the other, to the additives of the logic of bunched implications ( BI ). We give an algebraic method for calculating the distribution of the side-formulæ in multiplicative rules which allows the occurrence or non-occurrence of a formula on a branch of a proof to be determined once sufficient information is available. Each formula in the conclusion of such a rule is assigned a Boolean expression. As a search proceeds, a set of Boolean constraint equations is generated. We show that a solution to such a set of equations determines a proof corresponding to the given search. We explain a range of strategies, from the lazy to the eager, for solving sets of constraint equations. We indicate how to apply our methods systematically to large family of relevant systems.

31 January 2023 in Studia Logica
Verified
Journal Article
Open access
PDF file
AGAlexander V. Gheorghiu
Alexander V. Gheorghiu
DPDavid J. Pym
David J. Pym
We give a novel approach to proving soundness and completeness for a logic (henceforth: the object-logic) that bypasses truth-in-a-model to work directly with validity. Instead of working with specific worlds in specific models, we reason with eigenworlds (i.e., generic representatives of worlds) in an arbitrary model. This reasoning is captured by a sequent calculus for ameta-logic (in this case, first-order classical logic) expressive enough to capture the semantics of the object-logic. Essentially, one has a calculus of validity for the object-logic. The method proceeds through the perspective of reductive logic (as opposed to the more traditional paradigm of deductive logic), using the space of reductions as a medium for showing the behavioural equivalence of reduction in the sequent calculus for the object-logic and in the validity calculus. Rather than study the technique in general, we illustrate it for the logic of Bunched Implications (BI), thus IPL and MILL (without negation) are also treated. Intuitively, BI is the free combination of intuitionistic propositional logic and multiplicative intuitionistic linear logic, which renders its meta-theory is quite complex. The literature on BI contains many similar, but ultimately different, algebraic structures and satisfaction relations that either capture only fragments of the logic (albeit large ones) or have complex clauses for certain connectives (e.g., Beth’s clause for disjunction instead of Kripke’s). It is this complexity that motivates us to use BI as a case-study for this approach to semantics.

30 June 2023 in Bulletin of the Section of Logic
Verified
Journal Article
Open access
PDF file
AGAlexander V. Gheorghiu
Alexander V. Gheorghiu
DPDavid J. Pym
David J. Pym
Proof-theoretic semantics (P-tS) is the paradigm of semantics in which meaning in logic is based on proof (as opposed to truth). A particular instance of P-tS for intuitionistic propositional logic (IPL) is its base-extension semantics (B-eS). This semantics is given by a relation called support, explaining the meaning of the logical constants, which is parameterized by systems of rules called bases that provide the semantics of atomic propositions. In this paper, we interpret bases as collections of definite formulae and use the operational view of them as provided by uniform proof-search—the proof-theoretic foundation of logic programming (LP)—to establish the completeness of IPL for the B-eS. This perspective allows negation, a subtle issue in P-tS, to be understood in terms of the negation-as-failure protocol in LP. Specifically, while the denial of a proposition is traditionally understood as the assertion of its negation, in B-eS we may understand the denial of a proposition as the failure to find a proof of it. In this way, assertion and denial are both prime concepts in P-tS.

8 August 2025 in Studia Logica
Verified
Journal Article
Open access
PDF file
TGTao Gu
Tao Gu
AGAlexander V. Gheorghiu
Alexander V. Gheorghiu
DPDavid J. Pym
David J. Pym
The logic of bunched implications (BI) can be seen as the free combination of intuitionistic propositional logic (IPL) and intuitionistic multiplicative linear logic (IMLL). We present here a base-extension semantics (B-eS) for BI in the spirit of Sandqvist’s B-eS for IPL, deferring an analysis of proof-theoretic validity (in the sense of Dummett and Prawitz) to another occasion. Essential to BI’s formulation in proof-theoretic terms is the concept of a ‘bunch’ of hypotheses, a notion familiar from relevance logic. Bunches amount to trees whose internal vertices are labelled with either the IMLL or the IPL context-former and whose leaves are labelled with propositions or units for the context-formers. This structure presents significant technical challenges in setting up a base-extension semantics for BI. Our approach starts from the B-eS for IPL and the B-eS for IMLL and provides a systematic combination. Such a combination requires that base rules carry bunched structure, and so requires a more complex notion of derivability in a base and a correspondingly richer notion of support in a base. One reason why BI is a substructural logic of interest is that the ‘resource interpretation’ of its semantics, given in terms of sharing and separation and which gives rise to Separation Logic in the field of program verification, is quite distinct from the ‘number-of-uses’ interpretation of propositions in linear logic. This resource reading of BI provides useful intuitions in the formulation of its proof-theoretic semantics. We discuss a simple example of the use of the given B-eS in security modelling.

14 September 2023
Verified
Book Chapter
Open access
PDF file
AGAlexander V. Gheorghiu
Alexander V. Gheorghiu
TGTao Gu
Tao Gu
DPDavid J. Pym
David J. Pym
This work is the first exploration of proof-theoretic semantics for a substructural logic. It focuses on the base-extension semantics (B-eS) for intuitionistic multiplicative linear logic ( $$\mathrm IMLL$$ ). The starting point is a review of Sandqvist’s B-eS for intuitionistic propositional logic (IPL), for which we propose an alternative treatment of conjunction that takes the form of thegeneralizedelimination rule for the connective. The resulting semantics is shown to be sound and complete. This motivates our main contribution, a B-eS for $$\mathrm IMLL$$ , in which the definitions of the logical constants all take the form of their elimination rule and for which soundness and completeness are established.