There exists a considerable body of work on epistemic logics for resource-bounded reasoners. In this paper, we concentrate on a less studied aspect of resource-bounded reasoning, namely, on the ascription of beliefs and inference rules by the agents to each other. We present a formal model of a system of bounded reasoners which reason about each other’s beliefs, and investigate the problem of belief ascription in a resource-bounded setting. We show that for agents whose computational resources and memory are bounded, (...) correct ascription of beliefs cannot be guaranteed, even in the limit. We propose a solution to the problem of correct belief ascription for feasible agents which involves ascribing reasoning strategies , or preferences on formulas, to other agents, and show that if a resource-bounded agent knows the reasoning strategy of another agent, then its ascription of beliefs to the other agent is correct in the limit. (shrink)

Coalition announcement logic is one of the family of the logics of quantified announcements. It allows us to reason about what a coalition of agents can achieve by making announcements in the setting where the anti-coalition may have an announcement of their own to preclude the former from reaching its epistemic goals. In this paper, we describe a PSPACE-complete model checking algorithm for CAL that produces winning strategies for coalitions. The algorithm is implemented in a proof-of-concept model checker.

In the most popular logics combining knowledge and awareness, it is not possible to express statements about knowledge of unawareness such as “Ann knows that Bill is aware of something Ann is not aware of”—without using a stronger statement such as “Ann knows that Bill is aware of \(p\) and Ann is not aware of \(p\) ”, for some particular \(p\) . In Halpern and Rêgo (Proceedings of KR 2006; Games Econ Behav 67(2):503–525, 2009b) Halpern and Rêgo introduced a logic (...) in which such statements about knowledge of unawareness can be expressed. The logic extends the traditional framework with quantification over formulae, and is thus very expressive. As a consequence, it is not decidable. In this paper we introduce a decidable logic which can be used to reason about certain types of unawareness. Our logic extends the traditional framework with an operator expressing full awareness, i.e., the fact that an agent is aware of everything, and another operator expressing relative awareness, the fact that one agent is aware of everything another agent is aware of. The logic is less expressive than Halpern’s and Rêgo’s logic. It is, however, expressive enough to express all of the motivating examples in Halpern and Rêgo (Proceedings of KR 2006; Games Econ Behav 67(2):503–525, 2009b). In addition to proving that the logic is decidable and that its satisfiability problem is PSPACE-complete, we present an axiomatisation which we show is sound and complete. (shrink)

We present a framework for verifying systems composed of heterogeneous reasoning agents, in which each agent may have differing knowledge and inferential capabilities, and where the resources each agent is prepared to commit to a goal (time, memory and communication bandwidth) are bounded. The framework allows us to investigate, for example, whether a goal can be achieved if a particular agent, perhaps possessing key information or inferential capabilities, is unable (or unwilling) to contribute more than a given portion of its (...) available computational resources or bandwidth to the problem. We present a novel temporal epistemic logic, BMCL-CTL , which allows us to describe a set of reasoning agents with bounds on time, memory and the number of messages they can exchange. The bounds on memory and communication are expressed as axioms in the logic. As an example, we show how to axiomatise a system of agents which reason using resolution and prove that the resulting logic is sound and complete. We then show how to encode a simple system of reasoning agents specified in BMCL-CTL in the description language of the Mocha model checker (Alur et al., Proceedings of the tenth international conference on computer-aided verification (CAV) , 1998), and verify that the agents can achieve a goal only if they are prepared to commit certain time, memory and communication resources. (shrink)

We show how sequent calculi for some generalized quantifiers can be obtained by generalizing the Herbrand approach to ordinary first order proof theory. Typical of the Herbrand approach, as compared to plain sequent calculus, is increased control over relations of dependence between variables. In the case of generalized quantifiers, explicit attention to relations of dependence becomes indispensible for setting up proof systems. It is shown that this can be done by turning variables into structured objects, governed by various types of (...) structural rules. These structured variables are interpreted semantically by means of a dependence relation. This relation is an analogue of the accessibility relation in modal logic. We then isolate a class of axioms for generalized quantifiers which correspond to first-order conditions on the dependence relation. (shrink)

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR i, for every arityi (or an infinitary predicateR) which takesQxg(x, y1,..., yn) to x(R(x, y1,..., y1) (x,y1,...,yn)) (y 1,...,yn are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related (...) results were obtained by Andréka and Németi (1994) using the methods of algebraic logic. (shrink)

The effective reasoning capability of an agent can be defined as its capability to infer, within a given space and time bound, facts that are logical consequences of its knowledge base. In this paper we show how to determine the effective reasoning capability of an agent with limited memory by encoding the agent as a transition system and automatically verifying whether a state where the agent believes a certain conclusion is reachable from the start state. We present experimental results using (...) the Model Based Planner (MBP) which illustrates how the length of the deduction varies for different memory sizes. (shrink)

Practical reasoners are resource-bounded—in particular they require time to derive consequences of their knowledge. Building on the Timed Reasoning Logics (TRL) framework introduced in [1], we show how to represent the time required by an agent to reach a given conclusion. TRL allows us to model the kinds of rule application and conflict resolution strategies commonly found in rule-based agents, and we show how the choice of strategy can influence the information an agent can take into account when making decisions (...) at a particular point in time. We prove general completeness and decidability results for TRL, and analyse the impact of communication in an example system consisting of two agents which use different conflict resolution strategies. (shrink)

We propose a framework for modelling situated resource-bounded agents. The framework is based on an objective ascription of intentional modalities and can be easily tailored to the system we want to model and the properties we wish to specify. As an elaboration of the framework, we introduce a logic, OBA, for describing the observations, beliefs, goals and actions of simple agents, and show that OBA is complete, decidable and has an efficient model checking procedure, allowing properties of agents specified in (...) OBA to be verified using standard theorem proving or model checking techniques. (shrink)

Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, we consider belief revision (...) for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation. (shrink)

We show how sequent calculi for some generalized quantifiers can be obtained by generalizing the Herbrand approach to ordinary first order proof theory. Typical of the Herbrand approach, as compared to plain sequent calculus, is increased control over relations of dependence between variables. In the case of generalized quantifiers, explicit attention to relations of dependence becomes indispensible for setting up proof systems. It is shown that this can be done by turning variables into structured objects, governed by various types of (...) structural rules. These structured variables are interpreted semantically by means of a dependence relation. This relation is an analogue of the accessibility relation in modal logic. We then isolate a class of axioms for generalized quantifiers which correspond to first-order conditions on the dependence relation. (shrink)

We consider two systems of constructive modal logic which are computationally motivated. Their modalities admit several computational interpretations and are used to capture intensional features such as notions of computation, constraints, concurrency, etc. Both systems have so far been studied mainly from type-theoretic and category-theoretic perspectives, but Kripke models for similar systems were studied independently. Here we bring these threads together and prove duality results which show how to relate Kripke models to algebraic models and these in turn to the (...) appropriate categorical models for these logics. (shrink)

Public announcement logic is an extension of epistemic logic with dynamic operators that model the effects of all agents simultaneously and publicly acquiring the same piece of information. One of the extensions of PAL, group announcement logic, allows quantification over announcements made by agents. In GAL, it is possible to reason about what groups can achieve by making such announcements. It seems intuitive that this notion of coalitional ability should be closely related to the notion of distributed knowledge, the implicit (...) knowledge of a group. Thus, we study the extension of GAL with distributed knowledge, and in particular possible interaction properties between GAL operators and distributed knowledge. The perhaps surprising result is that, in fact, there are no interaction properties, contrary to intuition. We make this claim precise by providing a sound and complete axiomatisation of GAL with distributed knowledge. We also consider several natural variants of GAL with distributed knowledge, as well as some other related logic, and compare their expressive power. (shrink)

We consider a predicate logic Lfd where not all assignments of values to individual variables are possible. Some variables are functionally dependent on other variables. This makes sense if the models of logic are assumed to correspond to databases or states. We show that Lfd is undecidable but has a complete and sound sequent calculus formalisation.

(2012). Modal logics for reasoning about infinite unions and intersections of binary relations. Journal of Applied Non-Classical Logics: Vol. 22, No. 4, pp. 275-294. doi: 10.1080/11663081.2012.705960.

This special issue on Formal Models of Awareness contains five papers that concentrate on different approaches to the notion of awareness. They include syntactic and semantic approaches to modelling awareness and an alternative view from the multi-agent systems perspective where awareness is identified as the ability to perceive and understand actions of other agents.Velázquez-Quesada studies a logic of plausibility acknowledgement models used to interpret the notions of implicit and explicit beliefs. The models use the notion of a formula being acknowledged (...) as true that is similar to syntactic awareness in that the set of formulas acknowledged as true by an agent is not assumed to be closed under logical consequence. However it has a different meaning . A dynamic epistemic logic over such models is cons .. (shrink)

This LNCS book is part of the FOLLI book series and constitutes the proceedings of the 9th International Workshop on Logic, Rationality, and Interaction, LORI 2023, held in Jinan, China, in October 2023. The 15 full papers presented together with 7 short papers in this book were carefully reviewed and selected from 40 submissions. The workshop covers a wide range on the following topics such as agency; argumentation and agreement; belief representation; probability and uncertainty; belief revision and belief merging; knowledge (...) and action; dynamics of informational attitudes; intentions, plans, and goals; decision making and planning; preference and utility; cooperation; strategic reasoning and game theory; epistemology; social choice; social interaction; speech acts; knowledge representation; norms and normative systems; natural language; rationality; philosophical logic. (shrink)