Equivariant Unification

Nominal logic is a variant of first-order logic with special facilities for reasoning about names and binding based on the underlying concepts of swapping and freshness. It serves as the basis of logic programming, term rewriting, and automated theorem proving techniques that support reasoning about languages with name-binding. These applications often require nominal unification, or equational reasoning and constraint solving in nominal logic. Urban, Pitts and Gabbay developed an algorithm for a broadly applicable class of nominal unification problems. However, because of nominal logic’s equivariance property, these applications also require a different form of unification, which we call equivariant unification. In this article, we first study the complexity of the decision problem for equivariant unification and equivariant matching. We show that these problems are NP-hard in general, as is nominal unification without the ground-name restrictions employed in previous work on nominal unification. Moreover, we present an exponential-time algorithm for equivariant unification that can be used to decide satisfiability, or produce a complete finite set of solutions. We also study special cases that can be solved efficiently. In particular, we present a polynomial time algorithm for swapping-free equivariant matching, that is, for matching problems in which the swapping operation does not appear.     

A Reference Architecture to support the development of mobile applications based on self-adaptive services

Nowadays, most human daily tasks can be performed by means of Mobile Applications (MobApps). Devices running such applications have some limitations (e.g., processing and storage) compared to personal computers. Therefore, integration of MobApps into service-based systems has been a feasible alternative to overcome these limitations. Moreover, these applications must be prepared to deal with the changes at runtime (e.g., user’s new needs or modifications in their execution environment). In parallel, Reference Architectures (RA) have been used as an important way to support the development, standardization, and evolution of software systems. Although relevant, RA for the domain of MobApps based on services that require adaptation at runtime is still an issue to be explored in depth. This paper presents a RA for Self-MobApps (named RA4Self-MobApps), which aims to support the development of such applications. To show the applicability of our RA, a case study was conducted. As result, we observe our RA has good perspective to efficiently contribute to the Self-MobApps domain.     

ID-Services: an RFID middleware architecture for mobile applications

The use of RFID middleware to support application development for and integration of RFID hardware into information systems has become quite common in RFID applications where reader devices remain stationary, which currently represents the largest part of all RFID applications in use. Another field for applying RFID technology which is offering a huge set of novel possibilities and applications are mobile applications, where readers are no longer fixed. In order to address the specific issues of mobile RFID-enabled applications and to support developers in rapid application development, we present ID-Services, an architecture for an RFID middleware that is designed to support mobile applications. The ID-Services approach has been used to implement MoVIS (Mobile Visitor Information System), a mobile application which allows museum visitors to request individually adapted multimedia information about exhibits in an intuitive way.     

Intelligent databases: Old challenges and new opportunities

The evolution of existing information systems and a new wave of data-intensive applications are creating a strong demand for database-centered programming environments much more sophisticated and intelligent than those supported by current database systems. In this paper, we describe the contributions that deductive databases offer to the evolution of databases and information systems to satisfy said demands. In addition to all database essentials, deductive databases support rule-based logic-oriented languages that allow terse formulations of complete applications, along with reasoning and queries. Thus, they support a rule-based interface that eliminates the impedance mismatch problem (between programming language and query sublanguage) and elevates the design and development of database applications to the level of declarative, knowledge-based specifications. In this paper, we review the evolution of the enabling technology and architectures of deductive database prototypes; then we focus on their applications, as seen by the author through his experience with theLDL/LDL++ project. In particular, the paper describes the languages and the (bottom-up) execution technology used by the first generation of deductive database prototypes. Then the paper discusses how the experience with a first-generation system (LDL) guided the design and implementation of a second-generation prototype (LDL++).     

Logics to formalise p-adic valued probability and their applications

Abstract

In this paper, we focus on the main results which we have developed to obtain different propositional logics for reasoning about p-adic valued probabilities. Each of these logics is a sound, complete, and decidable extension of classical propositional logic. Also, we show some applications of these logics in modelling cognitions.     

Formalisations of Capabilities for BDI-Agents

Intentional agent systems are increasingly being used in a wide range of complex applications. Capabilities has recently been introduced into some of these systems as a software engineering mechanism to support modularity and reusability while still allowing meta-level reasoning. This paper presents possible formalisations of capabilities within the framework of beliefs, goals and intentions and indicates how capabilities can affect agent reasoning about its intentions. We define a style of agent commitment which we refer to as a self-aware agent which allows an agent to modify its goals and intentions as its capabilities change. We also indicate which aspects of the specification of a BDI interpreter are affected by the introduction of capabilities and give some indications of additional reasoning which could be incorporated into an agent system on the basis of both the theoretical analysis and the existing implementation.     

Robust reasoning with rules that have exceptions: From second-order probability to argumentation via upper envelopes of probability and possibility plus directed graphs

Rules having rare exceptions may be interpreted as assertions of high conditional probability. In other words, a rule If X then Y may be interpreted as meaning that Pr(Y∣X) 1. A general approach to reasoning with such rules, based on second-order probability, is advocated. Within this general approach, different reasoning methods are needed, with the selection of a specific method being dependent upon what knowledge is available about the relative sizes, across rules, of upper bounds on each rule's exception probabilities Pr(?Y∣X). A method of reasoning, entailment with universal near surety, is formulated for the case when no information is available concerning the relative sizes of upper bounds on exception probabilities. Any conclusion attained under these conditions is robust in the sense that it will still be attained if information about the relative sizes of exception probability bounds becomes available. It is shown that reasoning via entailment with universal near surety is equivalent to reasoning in a particular type of argumentation system having the property that when two subsets of the rule base conflict with each other, the effectively more specific subset overrides the other. As stepping stones toward attaining this argumentation result, theorems are proved characterizing entailment with universal near surety in terms of upper envelopes of probability measures, upper envelopes of possibility measures, and directed graphs. In addition, various attributes of entailment with universal near surety, including property inheritance, are examined.     

PERSONAF: framework for personalised ontological reasoning in pervasive computing

Pervasive computing creates possibilities for presenting highly personalised information about the people, places and things in a building. One of the challenges for such personalisation is the creation of the system that can support ontological reasoning for several key tasks: reasoning about location; personalisation of information about location at the right level of detail; and personalisation to match each person’s conceptions of the building based on their own use of it and their relationship to other people in the building. From pragmatic perspectives, it should be inexpensive to create the ontology for each new building. It is also critical that users should be able to understand and control pervasive applications. We created the PERSONAF (personalised pervasive scrutable ontological framework) to address these challenges. PERSONAF is a new abstract framework for pervasive ontological reasoning. We report its evaluation at three levels. First, we assessed the power of the ontology for reasoning about noisy and uncertain location information, showing that PERSONAF can improve location modelling. Notably, the best ontological reasoner varies across users. Second, we demonstrate the use of the PERSONAF framework in Adaptive Locator, an application built upon it, using our low cost mechanisms for non-generic layers of the ontology. Finally, we report a user study, which evaluated the PERSONAF approach as seen by users in the Adaptive Locator. We assessed both the personalisation performance and the understandability of explanations of the system reasoning. Together, these three evaluations show that the PERSONAF approach supports building of low cost ontologies, that can achieve flexible ontological reasoning about smart buildings and the people in them, and that this can be used to build applications which give personalised information that can provide understandable explanations of the reasoning underlying the personalisation.     

A timed semantics of Orc

Orc is a kernel language for structured concurrent programming. Orc provides three powerful combinators that define the structure of a concurrent computation. These combinators support sequential and concurrent execution, and concurrent execution with blocking and termination.Orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. Orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication.Our previous work on the semantics of Orc focused on its asynchronous behavior. The inclusion of time or the effect of delay on a computation had not been modeled. In this paper, we define an operational semantics of Orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. We develop a number of identities among Orc expressions and define an equality relation that is a congruence. We also present a denotational semantics in which the meaning of an Orc program is a set of traces, and show that the two semantics are equivalent.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.     

Temporal Granularity and Indeterminacy in Reasoning About Actions and Change: An Approach Based on the Event Calculus

In many real-world applications, temporal information is often imprecise about the temporal location of events (indeterminacy) and comes at different granularities. Formalisms for reasoning about events and change, such as the Event Calculus (EC) and the Situation Calculus, do not usually provide mechanisms for handling such information, and very little research has been devoted to the goal of extending them with these capabilities. In this paper, we propose TGIC (Temporal Granularity and Indeterminacy event Calculus), an approach based on the EC ontology to represent events with imprecise location and to deal with them on different timelines.     

Qualitative and quantitative temporal constraints and relationaldatabases: theory, architecture, and applications

Many different applications in different areas need to deal with both: databases, in order to take into account large amounts of structured data; and quantitative and qualitative temporal constraints about such data. We propose an approach that extends: temporal databases and artificial intelligence temporal reasoning techniques and integrate them in order to face such a need. Regarding temporal reasoning, we consider some results that we proved recently about efficient query answering in the Simple Temporal Problem framework and we extend them in order to deal with partitioned sets of constraints and to support relational database operations. Regarding databases, we extend the relational model in order to consider also qualitative and quantitative temporal constraints both in the data (data expressiveness) and in the queries (query expressiveness). We then propose a modular architecture integrating a relational database with a temporal reasoner. We also consider classes of applications that fit into our approach and consider patient management in a hospital as an example     

On Closure Under Stuttering

For over a decade, researchers in formal methods have tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully automated reasoning tools enables non-experts to use formal methods effectively—their responsibility reduces to specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use, sufficiently expressive and succinct. Linear-time temporal logic (LTL) is a formalism that has been used extensively by researchers for program specification and verification. One of the desired properties of LTL formulas is closure under stuttering. That is, we do not want the interpretation of formulas to change over traces where some states are repeated. This property is important from both practical and theoretical prospectives; all properties which are closed under stuttering can be expressed in LTL_–X—a fragment of LTL without the next operator. However, it is often difficult to express properties in this fragment of LTL. Further, determining whether a given LTL property is closed under stuttering is PSPACE-complete. In this paper, we introduce a notion of edges of LTL formulas and present a formal theory of closure under stuttering. Edges allow natural modelling of systems with events. Our theory enables syntactic reasoning about whether the resulting properties are closed under stuttering. Finally, we apply the theory to the pattern-based approach of specifying temporal formulas.     

Equilibrium-independent passivity: A new definition and numerical certification

We extend the traditional notion of passivity to a forced system whose equilibrium is dependent on the control input by defining equilibrium-independent passivity, a system property characterized by a dissipation inequality centered at an arbitrary equilibrium point. We provide a necessary input/output condition which can be tested for systems of arbitrary dimension and sufficient conditions to certify this property for scalar systems. An example from network stability analysis is presented which demonstrates the utility of this new definition. We then proceed to numerical certification of equilibrium-independent passivity using sum-of-squares programming. Finally, through numerical examples we show that equilibrium-independent passivity is less restrictive than incremental passivity.     

An Algorithm to Evaluate Quantified Boolean Formulae and Its Experimental Evaluation

The high computational complexity of advanced reasoning tasks such as reasoning about knowledge and planning calls for efficient and reliable algorithms for reasoning problems harder than NP. In this paper we propose Evaluate, an algorithm for evaluating quantified Boolean formulae (QBFs). Algorithms for evaluation of QBFs are suitable for experimental analysis of problems that belong to a wide range of complexity classes, a property not easily found in other formalisms. Evaluate is a generalization of the Davis–Putnam procedure for SAT and is guaranteed to work in polynomial space. Before presenting the algorithm, we discuss several abstract properties of QBFs that we singled out to make it more efficient. We also discuss various options that were investigated about heuristics and data structures and report the main results of the experimental analysis. In particular, Evaluate is orders of magnitude more efficient than a nested backtracking procedure that resorts to a Davis–Putnam algorithm for handling the innermost set of quantifiers. Moreover, experiments show that randomly generated QBFs exhibit regular patterns such as phase transition and easy-hard-easy distribution.     

ActiveCBR: An Agent System That Integrates Case-Based Reasoning and Active Databases

Case-based reasoning (CBR) is an artificial intelligence (AI) technique for problem solving that uses previous similar examples to solve a current problem. Despite its success, most current CBR systems are passive: they require human users to activate them manually and to provide information about the incoming problem explicitly. In this paper, we present an integrated agent system that integrates CBR systems with an active database system. Active databases, with the support of active rules, can perform event detection, condition monitoring, and event handling (action execution) in an automatic manner. The integrated ActiveCBR system consists of two layers. In the lower layer, the active database is rule-driven; in the higher layer, the result of action execution of active rules is transformed into feature–value pairs required by the CBR subsystem. The layered architecture separates CBR from sophisticated rule-based reasoning, and improves the traditional passive CBR system with the active property. The system has both real-time response and is highly exible in knowledge management as well as autonomously in response to events that a passive CBR system cannot handle. We demonstrate the system efficiency and effectiveness through empirical tests. Received 21 April 2000 / Revised 12 June 2000 / Accepted in revised form 14 July 2000     

A Note on Complexity Measures for Inductive Classes in Constructive Type Theory

It is notoriously hard to express computational complexity properties of programs in programming logics based on a semantics which respects extensional function equality. That is a serious impediment to applications of programming logics requiring reasoning about complexity. This paper shows how to use existing mechanisms to define internal computational complexity measures in logics that support inductively defined types, dependent products, and functions. The method exploits a feature of inductive definitions in constructive type theory, namely that implicit proof codes are kept with the objects showing how they are presented in the inductive class. The idea is illustrated by giving a formal inductive definition ofPTimebased on ideas from Leivant's work and on Bellantoni and Cook's approach. Then a complexity measure is defined on elements of this class. This paper discusses the limitations of this idea and the need forfaithfulnessguarantees that link internal complexity classes to the implementation of the logic. The paper concludes with a definition ofresource bounded logicsand a discussion of interesting lines of investigation of these logics which have the potential to make practical uses of results from computational complexity theory in formal reasoning about the efficiency of programs.     

Practical Reflection for Sequent Logics

It is well-known that adding reflective reasoning can tremendously increase the power of a proof assistant. In order for this theoretical increase of power to become accessible to users in practice, the proof assistant needs to provide a great deal of infrastructure to support reflective reasoning. In this paper we explore the problem of creating a practical implementation of such a support layer.Our implementation takes a specification of a logical theory (which is identical to how it would be specified if we were simply going to reason within this logical theory, instead of reflecting it) and automatically generates the necessary definitions, lemmas, and proofs that are needed to enable the reflected meta-reasoning in the provided theory.One of the key features of our approach is that the structure of a logic is preserved when it is reflected. In particular, all variables, including meta-variables, are preserved in the reflected representation. This also allows the preservation of proof automation—there is a structure-preserving one-to-one map from proof steps in the original logic to proof step in the reflected logic.To enable reasoning about terms with sequent context variables, we develop a principle for context induction, called teleportation.This work is fully implemented in the MetaPRL theorem prover.