In Ockhamist branching-time logic [Prior 67], formulas are meant to be evaluated on a specified branch, or history, passing through the moment at hand. The linguistic counterpart of the manifoldness of future is a possibility operator which is read as `at some branch, or history (passing through the moment at hand)'. Both the bundled-trees semantics [Burgess 79] and the $\langle moment, history\rangle$ semantics [Thomason 84] for the possibility operator involve a quantification over sets of moments. The Ockhamist frames (...) are (3-modal) Kripke structures in which this second-order quantification is represented by a first-order quantification. The aim of the present paper is to investigate the notions of modal definability, validity, and axiomatizability concerning 3-modal frames which can be viewed as generalizations of Ockhamist frames. (shrink)

In this paper we present BTC, which is a complete logic for branchingtime whose modal operator quantifies over histories and whose temporal operators involve a restricted quantification over histories in a given possible choice. This is a technical novelty, since the operators of the usual logics for branching-time such as CTL express an unrestricted quantification over histories and moments. The value of the apparatus we introduce is connected to those logics of agency that are interpreted on branching- (...) class='Hi'>time, as for instance Stit Logics. (shrink)

While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature. We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it. We analyze the expressive power of hybrid branching-time logics (...) and the complexity of their satisfiability problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME -complete. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics. As a result of independent interest, the nonemptiness problem for alternating one-pebble Büchi tree automata is shown to be 2EXPTIME -complete. A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL * has nonelementary complexity. (shrink)

The branching-time logic called Peircean by Arthur Prior is considered and given an infinite axiomatization. The axiomatization uses only the standard deduction rules for tense logic.

Branching time logics have been studied in computer science since the 1980s primarily to model the tree of computations for discrete transition systems. Inconsistency measures for propositional log...

The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.

When we make a prediction we select, among the conceivable future descriptions of the world, those that appear to us to be most plausible. We capture this by means of two binary relations, ≺c and ≺p: if t1 and t2 are points in time, we interpret t1 ≺ct2 as sayingthat t2 is in the conceivable future of t1, while t1 ≺pt2 is interpreted to mean that t2 isin the predicted future of t1. Within a branching-time framework we (...) propose the following notion of “consistency of prediction”. Suppose that at t1 some future moment t2 is predicted to occur, then every moment t on the unique path from t1 to t2 should also be predicted at t1 and the prediction of t2 should continue to hold at every such t. A sound and complete axiomatization is provided. (shrink)

This paper deals with the historical and philosophical background of the introduction of the notion of branching time in philosophical logic as it is revealed in the hitherto unpublished mail-correspondence between Saul Kripke and A.N. Prior in the late 1950s. The paper reveals that the idea was first suggested by Saul Kripke in a letter to A.N. Prior, dated September 3, 1958, and it is shown how the elaboration of the idea in the course of the correspondence was (...) intimately intervowen with considerations of how to represent indeterminism and of the adequacy of tensed logic in light of special relativity. The correspondence underpins the point that Prior's later development of branching time may be understood as a crucial part of his attempt at the formulating a conceptual framework integrating basic human notions of time and free choice. (shrink)

Trees with indistinguishability relations provide a semantics for a temporal language “composed by” the Peircean tense operators and the Ockhamist modal operator. In this paper, a finite axiomatization with a non standard rule for this language interpreted over bundled trees with indistinguishability relations is given. This axiomatization is proved to be sound and strongly complete.

In the tree-like representation of Time, two histories are undivided at a moment t whenever they share a common moment in the future of t. In the present paper, it will first be proved that Ockhamist and Peircean branching-time logics are unable to express some important sentences in which the notion of undividedness is involved. Then, a new semantics for branching-time logic will be presented. The new semantics is based on trees endowed with an indistinguishability (...) function, a generalization of the notion of undividedness. It will be shown that Ockhamist and Peircean semantics can be viewed as limit cases of the semantics developed in this paper. (shrink)

Temporal logic can be used to describe processes: their behaviour ischaracterized by a set of temporal models axiomatized by a temporaltheory. Two types of models are most often used for this purpose: linearand branching time models. In this paper a third approach, based onsocalled joint closure models, is studied using models which incorporateall possible behaviour in one model. Relations between this approach andthe other two are studied. In order to define constructions needed torelate branching time models, (...) appropriate algebraic notions are defined(in a category theoretical manner) and exploited. In particular, thenotion of joint closure is used to construct one model subsuming a setof models. Using this universal algebraic construction we show that aset of linear models can be merged to a unique branching time model.Logical properties of the described algebraic constructions are studied.The proposed approach has been successfully aplied to obtain anappropriate semantics for non-monotonic reasoning processes based ondefault logic. References are discussed that show the details of theseapplications. (shrink)

This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for (...) possible paths. We then consider a hierarchy of natural classes of trees and bundled trees arising from a given class of linear orders and show that in general they provide different semantics. We also discuss transfer of definability from linear orders to trees and introduce a uniform translation from Priorean to Peircean formulae which transfers definability of properties of linear orders to definability of properties of all paths in trees. (shrink)

We introduce a natural deduction system for the until-free subsystem of the branching time logic Although we work with labelled formulas, our system differs conceptually from the usual labelled deduction systems because we have no relational formulas. Moreover, no deduction rule embodies semantic features such as properties of accessibility relation or similar algebraic properties. We provide a suitable semantics for our system and prove that it is sound and weakly complete with respect to such semantics.

For branching-time temporal logic based on an Ockhamist semantics, we explore a temporal language extended with two additional syntactic tools. For reference to the set of all possible futures at a moment of time we use syntactically designated restricted variables called fan-names. For reference to all possible futures alternative to the actual one we use a modification of a difference modality, localized to the set of all possible futures at the actual moment of time.We construct an (...) axiomatic system for this extended branching-time logic and prove its soundness and completeness with respect to bundle tree semantics. Finally, we show how our axiomatic system can be extended with a variety of important additional operators, such as Since and Until, a global difference operator, operators for undivided and divided histories, reference pointers, etc. (shrink)

O propósito desse artigo é fornecer um tratamento formal para um tipo de ação até o momento negligenciada nas lógicas modais filosóficas da ação: ação em plano. Ao fazer isso nós seguimos a abordagem padrão nas lógicas modais da ação exemplificados pelos trabalhos de Belnap, Chellas and Pörn. Como nós acreditamos que existe uma relação forte entre plano, tempo e indeterminismo, nós usamos a teoria do tempo ramificado para investigar as características básicas da ação em plano. Além de introduzir uma (...) semântica do tempo ramificado, nós também apresentamos um cálculo correto e completo com relação a essa semântica. DOI:10.5007/1808-1711.2010v14n3p421. (shrink)

We present a temporal logic of branching time with four primitive operators: |$\exists {\mathcal {C}}$| – it may change whether; |$\forall {\mathcal {C}} $| – it must change whether; |$\exists \Box $| – it may be endlessly unchangeable that; and |$\forall \Box $| – it must be endlessly unchangeable that. Semantically, operator |$\forall {\mathcal {C}}$| expresses a change in the logical value of the given formula in every state that may be an immediate successor of the one considered, (...) while |$\exists {\mathcal {C}}$| expresses a change in the logical value of the given formula in some state that is a possible immediate successor. |$\forall {\mathcal {C}} $| and |$\exists {\mathcal {C}}$| are not normal operators, they are not mutually definable and have unusual properties: |$\forall {\mathcal {C}} A\leftrightarrow \forall {\mathcal {C}} \neg A$| and |$\exists {\mathcal {C}} A \leftrightarrow \exists {\mathcal {C}} \neg A$| are axioms. Operators |$\exists \Box $| and |$\forall \Box $| express endless unchangeability in some and all paths, respectively. Our axiomatization contains two infinitary rules that allow one to obtain |$\exists \Box A$| from infinitely many combinations of formulas with |$A, \neg, \forall {\mathcal {C}}, \land $|⁠, and to get |$\forall \Box A$| from infinitely many combinations of formulas with |$A, \neg, \exists {\mathcal {C}}, \land $|⁠. We show that our formalism is complete by presenting a bridge between our logic and logic |$\textsf {UB}$|⁠, which is a fragment of |$\textsf {CTL}$| in which until operators does not occur. (shrink)

The logical foundations of game-theoretic solution concepts have so far been explored within the con¯nes of epistemic logic. In this paper we turn to a di®erent branch of modal logic, namely temporal logic, and propose to view the solution of a game as a complete prediction about future play. The branching time framework is extended by adding agents and by de¯ning the notion of prediction. A syntactic characterization of backward induction in terms of the property of internal consistency (...) of prediction is given. (shrink)

The basic notions in Prior’s Ockhamist and Peircean logics of branching-time are the notion of moment and that of history (or course of events). In the tree semantics, histories are defined as maximal linearly ordered sets of moments. In the geometrical approach, both moments and histories are primitive entities and there is no set theoretical (and ontological) dependency of the latter on the former. In the topological approach, moments can be defined as the elements of a rank 1 (...) base of a non-Archimedean topology on the set of histories. In this paper, it will be shown that the topological approach, and hence the other approaches, can be reconstructed in a framework in which the basic notions are those of history and of relative closeness relation among histories. (shrink)

The basic notions in Prior's Ockhamist and Peircean logics of branching-time are the notion of moment and that of history. In the tree semantics, histories are defined as maximal linearly ordered sets of moments. In the geometrical approach, both moments and histories are primitive entities and there is no set theoretical dependency of the latter on the former. In the topological approach, moments can be defined as the elements of a rank 1 base of a non-Archimedean topology on (...) the set of histories. In this paper, it will be shown that the topological approach, and hence the other approaches, can be reconstructed in a framework in which the basic notions are those of history and of relative closeness relation among histories. (shrink)

In this paper we develop a novel propositional semantics based on the framework of branching time. The basic idea is to replace the moment-history pairs employed as parameters of truth in the standard Ockhamist semantics by pairs consisting of a moment and a consistent, downward closed set of so-called transitions. Whereas histories represent complete possible courses of events, sets of transitions can represent incomplete parts thereof as well. Each transition captures one of the alternative immediate future possibilities open (...) at a branching point. The transition semantics exploits the structural resources a branching time structure has to offer and provides a fine-grained picture of the interrelation of modality and time. In addition to temporal and modal operators, a so-called stability operator becomes interpretable as a universal quantifier over the possible future extensions of a given transition set. The stability operator allows us to specify how and how far time has to unfold for the truth value of a sentence at a moment to become settled and enables a perspicuous treatment of future contingents. We show that the semantics developed along those lines generalizes and extends extant approaches: both Peirceanism and Ockhamism can be viewed as limiting cases of the transition approach that build on restricted resources only, and on both accounts, stability collapses into truth. (shrink)

Weak ontic necessity is the ontic necessity expressed by “should” or “ought to”. An example of it is “I should be dead by now”. A feature of this necessity is that whether it holds is irrelevant to whether its underlying proposition holds. This necessity essentially involves time. This paper presents a logic for conditional weak ontic necessity in branching time. The logic’s language includes the next instant operator, the last instant operator, and the operator for conditional weak (...) ontic necessity. Formulas are evaluated at tuples consisting of a tree-based model, a context, a timeline, and an instant. A context is a set of ordered ontic laws determining expected timelines. When evaluating conditional weak ontic necessity, we first update the context with the antecedent, then check whether the consequent holds with respect to the updated context. We discuss some consequences of the formalization and compare it to some related work. We study the logic’s expressivity and axiomatize a special validity of it. (shrink)

In this paper I analyze the temporal structures that are appropriate to study the notion of point of view. When we analyze the points of view and their structure, it seems clear that we must take into account the time t in which a point of view is attributed to a subject. A two-dimensional temporal logic which combines a modal dimension for possibilities and a temporal one for the flow of time, offers a clear view of the temporary (...) location of a point of view. In this logic, we have histories, thanks to the temporal dimension, and evaluation is in two indices, time and history. These stories can be seen as different scenarios, providing a clear advantage when applying to the analysis of the notion of point of view. The conclusion is that, in order to give a proper approach for the notion of point of view, all these aspects should be combined. (shrink)

We propose a theory of events and causes against the background of branching time. Notions discussed include possibility based on reality, transitions, events, determinacy, contingency, causes and effects. The main idea in defining causal relations is to introduce a certain preconditioning circumstance under which one event follows another. We also briefly compare this theory with some other theories.

The aim of this paper is to present a new perspective under which branching-time semantics can be viewed. The set of histories (maximal linearly ordered sets) in a tree structure can be endowed in a natural way with a topological structure. Properties of trees and of bundled trees can be expressed in topological terms. In particular, we can consider the new notion of topological validity for Ockhamist temporal formulae. It will be proved that this notion of validity is (...) equivalent to validity with respect to bundled trees. (shrink)

We study belief change in the branching-time structures introduced in Bonanno (Artif Intell 171:144–160, 2007 ). First, we identify a property of branching-time frames that is equivalent (when the set of states is finite) to AGM-consistency, which is defined as follows. A frame is AGM-consistent if the partial belief revision function associated with an arbitrary state-instant pair and an arbitrary model based on that frame can be extended to a full belief revision function that satisfies the (...) AGM postulates. Second, we provide a set of modal axioms that characterize the class of AGM-consistent frames within the modal logic introduced in Bonanno (Artif Intell 171:144–160, 2007 ). Third, we introduce a generalization of AGM belief revision functions that allows a clear statement of principles of iterated belief revision and discuss iterated revision both semantically and syntactically. (shrink)

The concept of event is one of the key notions of many theories dealing with causality or agency. In this paper we study different approaches to events that share the basic assumption that events can be analyzed fruitfully in branching-time structures. The terminological framework developed thereby may be helpful for further analyses in the fields of causality and agency and also in those fields of computational semantics, where similar concepts are considered.

The species of indeterminist tense logic called Peircean by A. N. Prior is proved to be recursively decidable.

A probabilistic and counterfactual theory of causality is developed within the framework of branching time. The theory combines ideas developed by James Fetzer, Donald Nute, Patrick Suppes, Ming Xu, John Pollock, David Lewis and Mellor among others.

Branching is a set-theoretical model of reality that is in accord with contemporary physics. This structure is also a model for some logical calculi. However, if the formal language defined on the basis of branching is to correspond to our ways of speaking about possible events, a number of issues must be clarified. All of them are connected with the notion of possibility that is employed in this language. Yet the apparent need to supplement this language with an (...) additional notion of possibility means that branching ceases to be attractive as a candidate for a model of physical reality, as it contains considerably more elements than we would like to see in reality. Thus, the connection between this logical tool and ontology becomes questionable. (shrink)

It is argued that reconstructions of the so-called ‘Master Argument’ of Dideros Cronos to the effect that possibility should be understood as present or future truth, essentially relies on two axioms: i) that every true proposition concerning the past is necessary, and ii) that it follows necessarily from a proposition being true that it always has been the case that it would be true. It is furthermore argued that these two axioms are inconsistent in the sense that any tense/modal semantics (...) which incorporates both collapses either modally (fails to distinguish between truth simpliciter and modalised truth) or temporally (fails to offer a plausible semantical account for propositions about the future). This finding is, furthermore, taken as indicator for the more generel claim that there are principled difficulties involved in construing semantics for combined tense/modal logical systems. (shrink)

In his famous letter to A. N. Prior dated 3 September 1958, Saul Kripke suggested the use of branching time in temporal logic. In this paper, however, it is argued that Prior worked with an idea close to the notion of branching time (‘the big Y’) already the year before he received Kripke’s letter. It is likely that Prior’s findings based on this early study can explain why Prior so quickly accepted the idea of branching (...) time when he received Kripke’s letter. (shrink)

Temporal logic is one of the many areas in which a possible world semantics is adopted. Prior's Ockhamist and Peircean semantics for branching-time, though, depart from the genuine Kripke semantics in that they involve a quantification over histories, which is a second-order quantification over sets of possible worlds. In the paper, variants of the original Prior's semantics will be considered and it will be shown that all of them can be viewed as first-order counterparts of the original semantics.

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted (...) with respect to a version of the bundle semantics. (shrink)

Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted (...) with respect to a version of the bundle semantics. (shrink)

The paper gives a physicist's view on the framework of branching space-time, 385--434). Branching models are constructed from physical state assignments. The models are then employed to give a formal semantics for the modal operators ``possibly'' and ``necessarily'' and for the counterfactual conditional. The resulting formal language can be used to analyze quantum correlation experiments. As an application sketch, Stapp's premises LOC1 and LOC2 from his purported proof of non-locality, 300--304) are analyzed.

Indicative conditionals with present tense antecedents can have ‘shifted’ readings that are unexpected given the semantic behavior of the tenses outside of conditionals. In this paper, we compare two accounts of this phenomenon due to Kaufmann (J Semant 22(3):231–280, 2005) and Schulz (SALT XVIII, pp. 694–710, 2008), by reconstructing them in the framework of branching time. We then propose a novel account of indicative conditionals based on the branching time semantics suggested in Rumberg (J Logic Lang (...) Inf 25(1):77–108, 2016), viz. transition semantics. We show that not only is the account of ‘shifted’ readings with present tense antecedents within this semantics very natural, but it also is empirically superior to its rivals in some respects. (shrink)

The article discusses the relation between two intuitive properties of time, namely its flow and branching. Both properties are introduced first in an informal way and compared. The conclusion of this informal analysis is that the two properties do not entail each other nor are they in contradiction. In order to verify this, we briefly introduced the branching temporal structures called branching space-time, branching continuation and their versions Minkowski branching structure and branching (...) time with Instants. Two possible ways how to formalize flow of time are given, one based on the definition of flow of time from temporal logics and the other based on relativistic physics. The latter is used to define flow of time with the use of linearly ordered points on worldines while respecting the ontological definiteness given by the difference of the past and the future. This is formalized in each of the branching models and it is concluded by comparing the resulting properties that branching and flow, even in the formal sense, do not entail each other. However, notions connected with flow of time represent a useful basis for semantics of the branching models. (shrink)

This work aims to make tense logic a more robust tool for ontologists, philosophers, knowledge engineers and programmers by outlining a fusion of tense logic and ontology of time. In order to make tense logic better understandable, the central formal primitives of standard tense logic are derived as theorems from an informal and intuitive ontology of time. In order to make formulation of temporal propositions easier, temporal operators that were introduced by Georg Henrik von Wright are developed, and (...) mapped to the ontology of time. (shrink)

The logical theory of branching space-times, which is intended to provide a framework for studying objective indeterminism, remains at a certain distance from the discussion of space-time theories in the philosophy of physics. In a welcome attempt to clarify the connection, Earman has recently found fault with the branching approach and suggested ``pruning some branches from branching space-time''. The present note identifies the different---order theoretic vs. topological---points of view of both discussion as a reason for (...) certain misunderstandings, and tries to remove them. Most importantly, we give a novel, topological criterion of modal consistency that usefully generalizes the order-theoretic criterion of directedness, and we introduce a differential-geometrical version of BST based on the theory of non-Hausdorff manifolds. (shrink)

Expert knowledge regularly informs personal and civic-decision making. To decide which experts to trust, lay publics —including policymakers and experts from other domains—use different epistemic and non-epistemic cues. Epistemic cues such as honesty, like when experts are forthcoming about conflicts of interest, are a popular way of understanding how people evaluate and decide which experts to trust. However, many other epistemic cues, like the evidence supporting information from experts, are inaccessible to lay publics. Therefore, lay publics simultaneously use second-order social (...) cues in their environment to inform decisions to trust. These second-order social cues, or ‘social indicators of trust’, prevent lay publics from having to trust blindly. Social indicators of trust therefore inform lay publics’ epistemic vigilance, or constant low level-monitoring of testimony from experts. This special issue examines the nature, acquisition and application of social indicators of trust for scientific experts and institutions. It also raises questions about the types of trust asked of lay publics and challenges traditional normative assumptions about the relationship between science and lay publics through study of attitudes, values, and experiences. The issue descriptively re-examines the structure of institutions, their role and methods for ferrying information, as well as how social indicators operate in times of crisis. In this collection of works, we bridge history, science, philosophy of science, science and technology studies, science communication and social epistemology, to broaden the discourse on trust in experts and more accurately reflect the imperfect yet indispensable endeavour that trusting is. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as Alternating-time Temporal (...) Logic (ATL). The key insight in ATL is that the path quantifiers of CTL could be replaced by cooperation modalities, of the form , where is a set of agents. The intended interpretation of an ATL formula is that the agents can cooperate to ensure that holds (equivalently, that have a winning strategy for ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as group can cooperate to bring about iff it is common knowledge in that . The resulting logic — Alternating-time Temporal Epistemic Logic (ATEL) — shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)

The metaphor of a branching tree of future possibilities has a number of important philosophical and logical uses. In this paper we trace this metaphor through some of its uses and argue that the metaphor works the same way in physics as in philosophy. We then give an overview of formal systems for branching possibilities, viz., branching time and (briefly) branching space-times. In a next step we describe a number of different notions of possibility, thereby (...) sketching a landscape of possibilities. In the final section of the paper we look at the place of branching-based possibilities in that larger landscape of possibilities. Our main message is that far from being an outlandish metaphysical extravagancy, branching-based possibilities are epistemically as well as metaphysically basic. (shrink)

The theory of branching space-times is designed as a rigorous framework for modelling indeterminism in a relativistically sound way. In that framework there is room for "funny business", i.e., modal correlations such as occur through quantummechanical entanglement. This paper extends previous work by Belnap on notions of "funny business". We provide two generalized definitions of "funny business". Combinatorial funny business can be characterized as "absence of prima facie consistent scenarios", while explanatory funny business characterizes situations in which no localized (...) explanation of inconsistency can be given. These two definitions of funny business are proved to be equivalent, and we provide an example that shows them to be strictly more general than the previously available definitions of "funny business". (shrink)