Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax

While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal logics of trees in two ways. First, we demonstrate that for each stronger logic, there exists a tree language that can only be defined in a weaker logic with inessential features. Second, we show that any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined with inessential features. Additionally, we consider Kracht’s definition of inessential features more closely. It turns out that there are features whose distribution can be predicted, but who fail to be inessential in Kracht’s sense. We will look at ways to modify his definition.     

A Hybrid Logic for Reasoning about Knowledge and Topology

We extend Moss and Parikh’s bi-modal system for knowledge and effort by means of hybrid logic. In this way, some additional concepts from topology related to knowledge can be captured. We prove the soundness and completeness as well as the decidability of the extended system. Special emphasis will be placed on algebras.     

Learning to trust in the competence and commitment of agents

For agents to collaborate in open multi-agent systems, each agent must trust in the other agents’ ability to complete tasks and willingness to cooperate. Agents need to decide between cooperative and opportunistic behavior based on their assessment of another agents’ trustworthiness. In particular, an agent can have two beliefs about a potential partner that tend to indicate trustworthiness: that the partner is competent and that the partner expects to engage in future interactions. This paper explores an approach that models competence as an agent’s probability of successfully performing an action, and models belief in future interactions as a discount factor. We evaluate the underlying decision framework’s performance given accurate knowledge of the model’s parameters in an evolutionary game setting. We then introduce a game-theoretic framework in which an agent can learn a model of another agent online, using the Harsanyi transformation. The learning agents evaluate a set of competing hypotheses about another agent during the simulated play of an indefinitely repeated game. The Harsanyi strategy is shown to demonstrate robust and successful online play against a variety of static, classic, and learning strategies in a variable-payoff Iterated Prisoner’s Dilemma setting.     

A proof-theoretic foundation of abortive continuations

We give an analysis of various classical axioms and characterize a notion of minimal classical logic that enforces Peirce’s law without enforcing Ex Falso Quodlibet. We show that a “natural” implementation of this logic is Parigot’s classical natural deduction. We then move on to the computational side and emphasize that Parigot’s λ μ corresponds to minimal classical logic. A continuation constant must be added to λ μ to get full classical logic. The extended calculus is isomorphic to a syntactical restriction of Felleisen’s theory of control that offers a more expressive reduction semantics. This isomorphic calculus is in correspondence with a refined version of Prawitz’s natural deduction. This article is an extended version of the conference article “Minimal Classical Logic and Control Operators” (Ariola and Herbelin, Lecture Notes in Computer Science, vol. 2719, pp. 871–885, 2003). A longer version is available as a technical report (Ariola et al., Technical Report TR608, Indiana University, 2005). Z.M. Ariola supported by National Science Foundation grant number CCR-0204389. A. Sabry supported by National Science Foundation grant number CCR-0204389, by a Visiting Researcher position at Microsoft Research, Cambridge, U.K., and by a Visiting Professor position at the University of Genova, Italy.     

A Framed Temporal Logic Programming Language

We discuss the projection temporal logic (PTL), based on a primitive projection operator, prj. A framing technique is also presented, using which a synchronization operator, await, is defined within the underlying logic. A framed temporal logic programming language (FTLL) is presented. To illustrate how to use both the language and framing technique, some examples are given.     

Bio-informatic activity modeling for human-artifacts symbiosis under resource boundedness

We investigate a biologically inspired design of an interface agent that is embedded inside human-artifact interactions rather than as an external observer, and has to work as an intelligent associate for a human user/operator in a time-critical situation like in an emergency. First, recent paradigmatic shifts of artifact design principles are discussed from an interdisciplinary viewpoint. Then, after the idea of Clancey’s activity modeling, we discuss the design principles of a situated interface agent. That is, different from the conventional supervisory agent’s task of seeking to optimize an isolated control task, such an agent has to be able to maintain its identity as an organism living within multiple contexts and looking inwards to consider the the nature of memory and perception, and looking outwards to consider the nature of social action with a human operator. Initially, our prior work using such a design principle is presented, and then decision-theoretic formulations of an interface agent’s activities are provided. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

The Cortexionist architecture: behavioural intelligence of artificial creatures

Traditionally, producing intelligent behaviours for artificial creatures involves modelling their cognitive abilities. This approach raises two problems. On the one hand, defining manually the agent’s knowledge is a heavy and error-prone task that implies the intervention of the animator. On the other hand, the relationship between cognition and intelligence has not been theoretically nor experimentally proven so far. The ecological approaches provide a solution for these problems, by exploring the links between the creature, its body and its environment. Using an artificial life approach, we propose an original model of memory based on the synthesis of several neuroscience theories. The Cortexionist controller integrates cortex-like structure into a connectionist architecture in order to enhance the agent’s adaptation in a dynamic environment, ultimately leading to the emergence of intelligent behaviour. Initial experiments presented in this paper prove the validity of the model.     

Using OWL ontologies for adaptive patient information modelling and preoperative clinical decision support

We here present our research and experience regarding the design and implementation of a knowledge-based preoperative assessment decision support system. We discuss generic design considerations as well as the practical system implementation. We developed the system using semantic web technology, including modular ontologies developed in the OWL web ontology language, the OWL Java application programming interface and an automated logic reasoner. We discuss how the system enables to tailor patient information collection according to personalized medical context. The use of ontologies at the core of the system’s architecture permits to efficiently manage a vast repository of preoperative assessment domain knowledge, including classification of surgical procedures, classification of morbidities and guidelines for routine preoperative tests. Logical inference on the domain knowledge according to individual patient’s medical context enables personalized patients’ reports consisting of a risk assessment and clinical recommendations such as relevant preoperative tests.     

n-Fold implicative basic logic is G?del logic

We prove that Haveshki’s and Eslami’s n-fold implicative basic logic is G?del logic and n-fold positive implicative basic logic is a fragment of ukasiewicz logic.     

Proving self-utterances

We study the Knights and Knaves problem, and find that for a proper treatment via theorem-proving, an interaction with natural language processing research is helpful. In particular, we discuss Ohlbach's claim that first-order logic is not well suited to handling this problem. Then we provide an interpretation of the problem using indexicals, axiomatize it, and prove the desired result. We conclude by suggesting a broader context for dealing with self-utterances in automatic theorem-proving.     

Logic-based automated multi-issue bilateral negotiation in peer-to-peer e-marketplaces

We present a novel logic-based framework to automate multi-issue bilateral negotiation in e-commerce settings. The approach exploits logic as communication language among agents, and optimization techniques in order to find Pareto-efficient agreements. We introduce , a propositional logic extended with concrete domains, which allows one to model relations among issues (both numerical and non-numerical ones) via logical entailment, differently from well-known approaches that describe issues as uncorrelated. Through it is possible to represent buyer’s request, seller’s supply and their respective preferences as formulas endowed with a formal semantics, e.g., “if I spend more than 30000 € for a sedan then I want more than a two-years warranty and a GPS system included”. We mix logic and utility theory in order to express preferences in a qualitative and quantitative way. We illustrate the theoretical framework, the logical language, the one-shot negotiation protocol we adopt, and show we are able to compute Pareto-efficient outcomes, using a mediator to solve an optimization problem. We prove the computational adequacy of our method by studying the complexity of the problem of finding Pareto-efficient solutions in our setting.     

An elementary and unified approach to program correctness

We present through the algorithmic language DHL (Dijkstra-Hehner language), a practical approach to a simple first order theory based on calculational logic, unifying Hoare and Dijkstra’s iterative style of programming with Hehner’s recursive predicative programming theory, getting the “best of the two worlds” and without having to recur in any way to higher-order approaches such as predicate transformers, Hoare logic, fixed-point or relational theory.     

An institution theory of formal meta-modelling in graphically extended BNF

Meta-modelling plays an important role in model driven software development.In this paper,a graphic extension of BNF (GEBNF) is proposed to define the abstract syntax of graphic modelling languages.Fro...     

A generalization of the Lin-Zhao theorem

The theorem on loop formulas due to Fangzhen Lin and Yuting Zhao shows how to turn a logic program into a propositional formula that describes the program’s stable models. In this paper we simplify and generalize the statement of this theorem. The simplification is achieved by modifying the definition of a loop in such a way that a program is turned into the corresponding propositional formula by adding loop formulas directly to the conjunction of its rules, without the intermediate step of forming the program’s completion. The generalization makes the idea of a loop formula applicable to stable models in the sense of a very general definition that covers disjunctive programs, programs with nested expressions, and more.     

Reinforcement learning technique using agent state occurrence frequency with analysis of knowledge sharing on the agent’s learning process in multiagent environments

Reinforcement learning techniques like the Q-Learning one as well as the Multiple-Lookahead-Levels one that we introduced in our prior work require the agent to complete an initial exploratory path followed by as many hypothetical and physical paths as necessary to find the optimal path to the goal. This paper introduces a reinforcement learning technique that uses a distance measure to the goal as a primary gauge for an autonomous agent’s action selection. In this paper, we take advantage of the first random walk to acquire initial information about the goal. Once the agent’s goal is reached, the agent’s first perceived internal model of the environment is updated to reflect and include said goal. This is done by the agent tracing back its steps to its origin starting point. We show in this paper, no exploratory or hypothetical paths are required after the goal is initially reached or detected, and the agent requires a maximum of two physical paths to find the optimal path to the goal. The agent’s state occurrence frequency is introduced as well and used to support the proposed Distance-Only technique. A computation speed performance analysis is carried out, and the Distance-and-Frequency technique is shown to require less computation time than the Q-Learning one. Furthermore, we present and demonstrate how multiple agents using the Distance-and-Frequency technique can share knowledge of the environment and study the effect of that knowledge sharing on the agents’ learning process.     

On the logic of preference and judgment aggregation

Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow’s theorem and Condorcet’s paradox—which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation—including classical preference aggregation. As a case study we present a logical study of, including a formal proof of, the neutrality lemma, the main ingredient in a well-known proof of Arrow’s theorem.     

Compact preference representation and Boolean games

Game theory is a widely used formal model for studying strategical interactions between agents. Boolean games (Harrenstein, Logic in conflict, PhD thesis, 2004; Harrenstein et al., Theoretical Aspects of Rationality and Knowledge, pp. 287–298, San Francisco Morgan Kaufmann, 2001) yield a compact representation of 2-player zero-sum static games with binary preferences: an agent’s strategy consists of a truth assignment of the propositional variables she controls, and a player’s preferences are expressed by a plain propositional formula. These restrictions (2-player, zero-sum, binary preferences) strongly limit the expressivity of the framework. We first generalize the framework to n-player games which are not necessarily zero-sum. We give simple characterizations of Nash equilibria and dominated strategies, and investigate the computational complexity of the associated problems. Then, we relax the last restriction by coupling Boolean games with a representation, namely, CP-nets. This article is a revised and extended version of the two conference articles [4] and [3].