Search

Software-controlled bots, also called social bots, are computer programs that act like human users on social media platforms. Recent work on detection of social bots is dominated by machine learning approaches. In this paper we explore bot detection as a model checking problem. We introduce Temporal Network Logic (TNL) which we use to specify social networks where agents can post and follow each other. In this logic we formalize different types of social bot behavior. These are formulas that are satisfied in a model of a network with bots. We provide a simple algorithm to extract a logical model from a real-life social network. We show that we can reduce TNL to a fragment of linear temporal logic with past and use this to establish the computational efficiency of model checking for social bot detection.

This paper proposes a formal framework for modeling the interaction of causal and (qualitative) epistemic reasoning. To this purpose, we extend the notion of a causal model with a representation of the epistemic state of an agent. On the side of the object language, we add operators to express knowledge and the act of observing new information. We provide a sound and complete axiomatization of the logic, and discuss the relation of this framework to causal team semantics., This is the long version of a paper that is to be published in the post-proceedings of the 3rd Dali Workshop on Dynamic Logic: New Trends and Applications. The post-proceedings will be published by Springer as a Lecture Notes in Computer Science volume

This paper is part of a series of proposals for using logic to analyse social networks. It studies the intertwining of two forms of information dynamics: social influence, through which an agent’s behaviour, opinions or features are affected by those of her social connections, and friendship selection, through which an agent chooses her social connections based on their common behaviour, opinions or features. The text provides a logical analysis of the two forms of dynamics (the main ingredients in the phenomenon known as homophily) as well as of their interaction, discussing also some of their variations.

The paper focuses on a recent challenge brought forward against the interventionist approach to the meaning of counterfactual conditionals. According to this objection, interventionism cannot in general account for the interpretation of right-nested counterfactuals, the problem being its strict interventionism. We will report on the results of an empirical study supporting the objection, and we will extend the well-known logic of actual causality with a new operator expressing an alternative notion of intervention that does not suffer from the problem (and thus can account for some critical examples). The core idea of the alternative approach is a new notion of intervention, which operates on the evaluation of the variables in a causal model, and not on their functional dependencies. Our result provides new insights into the logical analysis of causal reasoning.

Taking a broad historical line, we discuss major aspects of rationality that can be analyzed in a logical and computational perspective. Topics include classical notions from the foundations of computability, insights from the development of computer science and AI, and the richer picture of rationality emerging in current logical studies of agency. We also discuss two challenges. Distributed computing and evolutionary games replace 'high rationality' by 'low rationality' in behavior, machine learning defies classical views of representation and inference. Both trigger new logical themes in the study of rationality.

We propose a refinement of STIT logic to make it suitable to model causal agency and responsibility in basic multi-agent scenarios in which agents can interfere with one another. We do this by supplementing STIT semantics, first, with action types and, second, with a relation of opposing between action types. We exploit these novel elements to represent a test for potential causation, based on an intuitive notion of expected result of an action, and two tests for actual causation from the legal literature, i.e., the but-for and the NESS tests. We then introduce three new STIT operators modeling corresponding notions of causal responsibility, which we call potential, strong, and plain responsibility, and use them to provide a fine-grained analysis of a number of case studies involving both individual agents and groups.

In this paper we look at different ways of modally defining properties related to the concept of balance in signed social networks where relations can be either positive or negative. The motivation is to be able to formally reason about the social phenomenon of group polarization, for which balance theory forms a network-theoretical underpinning. The starting point is a recently developed basic modal logic that axiomatizes the class of social networks that are balanced up to a certain degree. This property is not modally definable but can be captured using a deduction rule. In this paper we examine different possibilities for extending this basic language, in order to, first, be able to define frame properties such as balance and related properties such as non-overlapping positive and negative relations and collective connectedness as axioms, and, second, be able to define the property of full balance rather than balanced-up-to-a-degree. We consider extensions with both static modalities such as the universal and the difference modality, the intersection modality, and nominals known from hybrid logic, as well as dynamic global bridge modalities known from sabotage logic. Along the way we provide axioms for weak balance. Finally, to explore measures of how far a network is from polarization, we consider and compare variations of distance measures between models in relation to balance.

This paper is part of an on-going programme in which we provide a logical study of social network formations. In the proposed setting, agent a will consider agent b as part of her network if the number of features (properties) on which they differ is small enough, given the constraints on the size of agent a’s ‘social space’. We import this idea about a limit on one’s social space from the cognitive science literature. In this context we study the creation of new networks and use the tools of Dynamic Epistemic Logic to model the updates of the networks. By providing a set of reduction axioms we are able to provide sound and complete axiomatizations for the logics studied in this paper.

We introduce a new topological semantics for belief logics in which the belief modality is interpreted as the interior of the closure of the interior operator. We show that the system wKD45, a weakened version of KD45, is sound and complete with respect to the class of all topological spaces. While generalizing the topological belief semantics proposed in [1, 2] to all spaces, we model conditional beliefs and updates and give complete axiomatizations of the corresponding logics with respect to the class of all topological spaces.

Echo chamber is a widely used term describing a situation where certain information is reinforced within a closed network. To reason about echo chambers, we introduce a two-sorted hybrid logic of strong and weak ties based on a logic of positive and negative relations known from the literature. We show that some classical property definitions can be formalized and that a known claim from social network analysis is a validity. We also prove that the logic is axiomatizable, sound and strongly complete. We combine our results with research on homophily and social group formation to represent relations between similar agents. Lastly, we add a knowledge modality and dynamic operators to analyze change in these networks.

In this paper, we study doxastic attitudes that emerge on the basis of argumentational reasoning. In order for an agent’s beliefs to be called ‘rational’, they ought to be well-grounded in strong arguments that are constructed by combining her available evidence in a specific way. A study of how these rational and grounded beliefs emerge requires a new logical setting. The language of the logical system in this paper serves this purpose: it is expressive enough to reason about concepts such as factive combined evidence, correctly grounded belief, and infallible knowledge, which are the building blocks on which our notions of argument and grounded belief can be defined. Building further on previous work, we use a topological semantics to represent the structure of an agent’s collection of evidence, and we use input from abstract argumentation theory to single out the relevant sets of evidence to construct the agent’s beliefs. Our paper provides a sound and complete axiom system for the presented logical language, which can describe the given models in full detail, and we show how this setting can be used to explore more intricate epistemic notions.

In this paper we design a new logical system to explicitly model the different deductive reasoning steps of a boundedly rational agent. We present an adequate system in line with experimental findings about an agent’s reasoning limitations and the cognitive effort that is involved. Inspired by Dynamic Epistemic Logic, we work with dynamic operators denoting explicit applications of inference rules in our logical language. Our models are supplemented by (a) impossible worlds (not closed under logical consequence), suitably structured according to the effect of inference rules, and (b) quantitative components capturing the agent’s cognitive capacity and the cognitive costs of rules with respect to certain resources (e.g. memory, time). These ingredients allow us to avoid problematic logical closure principles, while at the same time deductive reasoning is reflected in our dynamic truth clauses. We finally show that our models can be reduced to awareness-like plausibility structures that validate the same formulas and a sound and complete axiomatization is given with respect to them.

This paper studies the logical features of social group creation. We focus on the mechanisms which indicate when agents can form a team based on the correspondence in their set of features (behavior, opinions, etc.). Our basic approach uses a semi-metric on the set of agents, which is used to construct a network topology. Then it is extended with epistemic features to represent the agents’ epistemic states, allowing us to explore group-creation alternatives where what matters is not only the agent’s differences but also what they know about them. We use tools of dynamic epistemic logic to study the properties of different strategies to network formations.

Learning and learnability have been long standing topics of interests within the linguistic, computational, and epistemological accounts of inductive inference. Johan van Benthem’s vision of the “dynamic turn” has not only brought renewed life to research agendas in logic as the study of information processing, but likewise helped bring logic and learning in close proximity. This proximity relation is examined with respect to learning and belief revision, updating and efficiency, and with respect to how learnability fits in the greater scheme of dynamic epistemic logic and scientific method.

We present a logical setting that incorporates a belief-revision mechanism within Dynamic-Epistemic logic. As the “static” basis for belief revision, we use epistemic plausibility models, together with a modal language based on two epistemic operators: a “knowledge” modality K (the standard S5, fully introspective, notion), and a “safe belief” modality □ (“weak”, non-negatively-introspective, notion, capturing a version of Lehrer’s “indefeasible knowledge”). To deal with “dynamic” belief revision, we introduce action plausibility models, representing various types of “doxastic events”. Action models “act” on state models via a modified update product operation: the “Action-Priority” Update. This is the natural dynamic generalization of AGM revision, giving priority to the incoming information (i.e., to “actions”) over prior beliefs. We completely axiomatize this logic, and show how our update mechanism can “simulate”, in a uniform manner, many different belief-revision policies.

I report on joint work with A. Baltag, Z. Christoff and J.U. Hansen in [3], based on our investigation of the decision processes of individuals that lead to the social herding phenomenon known as informational cascades. The question we address in our paper deals with whether rational agents who use their higher-order reasoning powers and who can reflect on the fact that they are part of an informational cascade, can ultimately stop the cascade from happening. To answer this question we use dynamic epistemic logic to give a complete analysis of the information flow in an informational cascade, capturing the agent’s observations, their communication and their higher-order reasoning power. Our models show that individual rationality isn’t always a cure that can help us to stop a cascade. However, other factors that deal with the underlying communication protocol or that focus on the reliability of agents in the group, give rise to conditions that can be imposed to prevent or stop an informational cascade from happening in certain scenarios.

Background Clay deposits such as the Opalinus Clay formation are studied as host rocks for geological disposal of high- and intermediate-level long-lived radioactive waste in several European countries. Bituminized intermediate-level long-lived radioactive waste contains, besides bitumen and radionuclides, also large amounts of organics, nitrates and sulphates. Over time, these salts will dissolve, leach and diffuse into the surrounding clay host rock, together with water soluble organic substances. To mimic the potential effect of such inorganic– and organic leachates, pulses of nitrate and/or acetate have been injected in intervals of an in situ experiment, called Bitumen-Nitrate-Clay interaction (BN) experiment, running at the Mont Terri geological laboratory (St. Ursanne, Switzerland). Objectives To elucidate whether the microbial communities, present in the BN experiment, are affected or involved in the observed biogeochemical changes. Methods Beside classical microbial analyses, at pivotal moments (i.e. before, during and after these pulse injection tests), priority was given to DNA-based molecular biology analysis methods, as these methods provide very accurate information on the composition, the metabolic capacity and possible evolution of bacterial communities in response to the nitrate and/or acetate injections. Conclusions The changes observed in the bacterial populations appeared to correlate well with the imposed physico-chemical changes. As soon as nitrate was added an overwhelming community shift appeared to nitrate reducing bacteria. If in parallel acetate was offered, the community composition did not alter that much, but the speed of nitrate reduction was increased twentyfold. This high nitrate removal speed was maintained as long as the easily consumable carbon source was abundant.

We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision is "universal", i.e., that every solvable problem is solvable by AGM conditioning.

This chapter gives an overview of current dynamic logics that describe belief update and revision, both for single agents and in multi-agent settings. We employ a mixture of ideas from AGM belief revision theory and dynamic-epistemic logics of information-driven agency. After describing the basic background, we review logics of various kinds of beliefs based on plausibility models, and then go on to various sorts of belief change engendered by changes in current models through hard and soft information. We present matching complete logics with dynamic-epistemic recursion axioms, and develop a very general perspective on belief change by the use of event models and priority update. The chapter continues with three topics that naturally complement the setting of single steps of belief change: connections with probabilistic approaches to belief change, long-term temporal process structure including links with formal learning theory, and multi-agent scenarios of information flow and belief revision in games and social networks. We end with a discussion of alternative approaches, further directions, and windows to the broader literature, while links with relevant philosophical traditions are discussed throughout.

Clay deposits such as the Opalinus Clay formation are studied as host rocks for geological disposal of high- and intermediate-level long-lived radioactive waste in several European countries. Bituminized intermediate-level long-lived radioactive waste contains, besides bitumen and radionuclides, also large amounts of nitrates and sulphates. Over time, these salts will dissolve, leach and diffuse into the surrounding clay host rock, together with water soluble organic substances. The presence of these compounds will induce several processes (e.g. ionic strength changes, ion exchange reactions with Na+, redox reactions with NO3-) that may affect the barrier properties of the clay host rock. To study the fate of such inorganic– and organic leachates, an in situ experiment, called Bitumen-Nitrate-Clay interaction (BN) experiment, was installed in the Opalinus Clay at the Mont Terri underground research laboratory (St. Ursanne, Switzerland). The BN experiment aims to investigate the impact of a nitrate plume, with or without acetate, on the biogeochemistry of the near-field host rock. Acetate is used as representative of the organic water soluble fraction of bitumen degradation products. At a later stage, the BN experiment also aims to investigate the impact of nitrate and acetate on radionuclide reactivity and transport, especially for the redox sensitive radionuclides (e.g. 79Se, 99Tc, 23xU, …). The microbial analyses of the BN experiment intend to elucidate if and how currently present microbial communities are affected, and if and how microbes are involved in the observed biogeochemical processes. In this respect it is noteworthy to mention that the current BN set-up does not take into account any cement matrix or backfill, and offers the microbes only a pure aquatic environment, at almost neutral pH, in the form of a water-filled borehole. Such set-up allows free movement of nutrients, energy sources and dissolved electron donors and – acceptors, and does not impose any physical and/or chemical restriction on the microorganisms. In a real radioactive waste repository, the conditions will mostly deviate from the ones present in the BN experiment. Therefore, the in situ BN experiment can only be considered as a well engineered disposal 'test case'...

Dependence logic extends the language of first order logic by means of dependence atoms and aims to establish a basic theory of dependence and independence underlying such seemingly unrelated subjects as causality, random variables, bound variables in logic, database theory, the theory of social choice, and even quantum physics. In this work we summarize the setting of dependence logic and recall the main results of this rapidly developing area of research.

In this chapter we overview the main structures of epistemic and doxastic logic. We start by discussing the most celebrated models for epistemic logic, i.e., epistemic Kripke structures. These structures provide a very intuitive interpretation of the accessibility relation, based on the notion of information. This also naturally extends to the multi-agent case. Based on Kripke models, we then look at systems that add a temporal or a computational component, and those that provide a ‘grounded’ semantics for knowledge. We also pay special attention to ‘non-standard semantics’ for knowledge and belief, i.e., semantics that are not based on an underlying relation on the sets of states. In particular, we discuss here neighbourhood semantics and topological semantics. In all of these approaches, we can clearly point at streams of results that are inspired by work by Johan van Benthem. We are extremely pleased and honoured to be part of this book dedicated to his work and influences.

In this chapter we re-evaluate Segerberg’s “full DDL” (Dynamic Doxastic Logic) from the perspective of Dynamic Epistemic Logic (DEL), in its belief-revision-friendly incarnation. We argue that a correct version of full DDL must give up the Success Postulate for dynamic revision. Next, we present (an appropriately generalized and simplified version of) full DDL, showing that it is a generalization of the so-called Topo-logic of Moss and Parikh. We construct AGM-friendly versions of full DDL, corresponding to various revising/contracting operations considered in the Belief Revision literature. We show that DDL can internalize inside one model the “external” doxastic dynamics of DEL, as well as the evidential dynamics investigated by van Benthem and Pacuit. In our Conclusions section, we compare three styles of modeling doxastic dynamics: DDL, DEL and PDL/ETL (the Propositional Dynamic Logic approach, with its Epistemic Temporal Logic variant).

One of van Benthem’s seminal results is the Bisimulation Theorem characterizing modal logic as the bisimulation-invariant fragment of first-order logic. Janin and Walukiewicz extended this theorem to include fixpoint operators, showing that the modal \({\mu }\)-calculus \({\mu }\)ML is the bisimulation-invariant fragment of monadic second-order logic MSO. Their proof uses parity automata that operate on Kripke models, and feature a transition map defined in terms of certain fragments of monadic first-order logic. In this paper we decompose their proof in three parts: (1) two automata-theoretic characterizations, of MSO and \(\mu \)ML respectively, (2) a simple model-theoretic characterization of the identity-free fragment of monadic first-order logic, and (3) an automata-theoretic result, stating that (a strong version of) the second result somehow propagates to the level of full fixpoint logics. Our main contribution shows that the third result is an instance of a more general phenomenon that is essentially coalgebraic in nature. We prove that if one set \(\varLambda \) of predicate liftings (or modalities) for a certain set functor \(T\) uniformly corresponds to the \(T\)-natural fragment of another such set \(\varLambda ^{\prime }\), then the fixpoint logic associated with \(\varLambda \) is the bisimulation-invariant logic of the fixpoint logic associated with \(\varLambda ^{\prime }\).

It has usually been assumed that monadic value notions can be defined in terms of dyadic value notions, whereas definitions in the opposite direction are not possible. In this paper, inspired by van Benthem’s work, it is shown that the latter direction is feasible with a method in which shifts in context have a crucial role. But although dyadic preference orderings can be defined from context-indexed monadic notions, the monadic notions cannot be regained from the preference relation that they gave rise to. Two formal languages are proposed in which reasoning about context can be represented in a fairly general way. One of these is a modal language much inspired by van Benthem’s work. Throughout the paper the focus is on relationships among the value notions “good”, “bad”, and “better”. Other interpretations like “tall” and “taller” are equally natural. It is hoped that the results of this paper can be relevant for the analysis of natural language comparatives and of vague predicates in general.

This chapter surveys the use of logic and computational complexity theory in cognitive science. We emphasize in particular the role played by logic in bridging the gaps between Marr’s three levels: representation theorems for non-monotonic logics resolve algorithmic/implementation debates, while complexity theory probes the relationship between computational task analysis and algorithms. We argue that the computational perspective allows feedback from empirical results to guide the development of increasingly subtle computational models. We defend this perspective via a survey of the role of logic in several classic problems in cognitive science (the Wason selection task, the frame problem, the connectionism/symbolic systems debate) before looking in more detail at case studies involving quantifier processing and social cognition. In these examples, models developed by Johan van Benthem have been supplemented with complexity analysis to drive successful programs of empirical research.

Dynamic epistemic logic, broadly conceived, is the study of rational social interaction in context, the study, that is, of how agents update their knowledge and change their beliefs on the basis of pieces of information they exchange in various ways. The information that gets exchanged can be about what is the case in the world, about what changes in the world, and about what agents know or believe about the world and about what others know or believe. This chapter gives an overview of dynamic epistemic logics, and traces some connections with propositional dynamic logic, with planning and with probabilistic updating.

We present a new topological semantics for doxastic logic, in which the belief modality is interpreted as the closure of the interior operator. We show that this semantics is the most general (extensional) semantics validating Stalnaker’s epistemic-doxastic axioms [22] for “strong belief”, understood as subjective certainty. We prove two completeness results, and we also give a topological semantics for update (dynamic conditioning), i.e. the operation of revising with “hard information” (modeled by restricting the topology to a subspace). Using this, we show that our setting fits well with the defeasibility analysis of knowledge [18]: topological knowledge coincides with undefeated true belief. Finally, we compare our semantics to the older topological interpretation of belief in terms of Cantor derivative [23].

In this paper, we investigate the social herding phenomenon known as informational cascades, in which sequential inter-agent communication might lead to epistemic failures at group level, despite availability of information that should be sufficient to track the truth. We model an example of a cascade, and check the correctness of the individual reasoning of each agent involved, using two alternative logical settings: an existing probabilistic dynamic epistemic logic, and our own novel logic for counting evidence. Based on this analysis, we conclude that cascades are not only likely to occur but are sometimes unavoidable by "rational" means: in some situations, the group’s inability to track the truth is the direct consequence of each agent’s rational attempt at individual truth-tracking. Moreover, our analysis shows that this is even so when rationality includes unbounded higher-order reasoning powers (about other agents’ minds and about the belief-formation-and-aggregation protocol, including an awareness of the very possibility of cascades), as well as when it includes simpler, non-Bayesian forms of heuristic reasoning (such as comparing the amount of evidence pieces).