动态描述逻辑推理的并行计算技术

在设计用于处理大规模本体和数据的推理引擎时,推理引擎的可扩展性是一个需要研究的重要问题.动态描述逻辑要在真实环境中获得成功应用,需要在推理中采用并行计算技术.提出了两种方法将并行计算技术应用于动态描述逻辑推理.方法1是设计分布式动态描述逻辑框架.分布式动态描述逻辑由若干独立的动态描述逻辑所组成,这些动态描述逻辑两两之间通过桥规则联系起来.提出了基于Tableau的分布式推理算法,从而为分布式动态描述逻辑提供了全局推理能力,并且该算法可以将大的推理任务分解为若干子任务,而这些子任务可以被不同的推理主体并行处理.方法2是并行化动态描述逻辑的Tableau算法的不确定分支.不确定分支的并行计算使得推理任务可以在若干独立机器上同时执行.最后,介绍了推理引擎的原型实现并评估了其性能.实验结果表明提出的两种方法取得了明显的推理加速效果.     

Conservative extension concepts for nonmonotonic knowledge bases

Conservative extensions of logical theories play an important role in software engineering. They provide a formal basis for program refinement and guarantee the integrity and transparency of modules and objects. This paper provides a detailed analysis of conservative extension concepts in the context of nonmonotonic knowledge bases, in particular default theories. Since there are different approaches to nonmonotonic reasoning based on different strategies for dealing with multiple extensions, we define several alternative refinement concepts and study their interrelationships. We also show that refinement is well behaved with respect to strong stratification, a technique for reducing computational effort in default reasoning. © 2000 John Wiley & Sons, Inc.     

Model checking probabilistic social commitments for intelligent agent communication

Interaction among autonomous agents in Multi-Agent Systems (MASs) is a key aspect for agents to coordinate with one another. Social approaches, as opposed to the mental approaches, have recently received a considerable attention in the area of agent communication. They exploit observable social commitments to develop a verifiable formal semantics through which communication protocols can be specified. Developing and implementing algorithmic model checking for social commitments have been recently addressed. However, model checking social commitments in the presence of uncertainty is yet to be investigated.In this paper, we propose a model checking technique for verifying social commitments in uncertain settings. Social commitments are specified in a modal logical language called Probabilistic Computation Tree Logic of Commitments (PCTLC). The modal logic PCTLC extends PCTL, the probabilistic extension of CTL, with modalities for commitments and their fulfillments. The proposed verification method is a reduction-based model checking technique to the model checking of PCTL. The technique is based upon a set of reduction rules that translate PCTLC formulae to PCTL formulae to take benefit of existing model checkers such as PRISM. Proofs that confirm the soundness of the reduction technique are presented. We also present rules that transform our new version of interpreted systems into models of Markov Decision Processes (MDPs) to be suitable for the PRISM tool. We implemented our approach on top of the PRISM model checker and verified some given properties for the Oblivious Transfer Protocol from the cryptography domain. Our simulation demonstrates the effectiveness of our approach in verifying and model checking social commitments in the presence of uncertainty. We believe that the proposed formal verification technique will advance the literature of social commitments in such a way that not only representing social commitments in uncertain settings is doable, but also verifying them in such settings becomes achievable.     

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.     

Supporting distributed product configuration by integrating heterogeneous variability modeling approaches

ContextIn industrial settings products are developed by more than one organization. Software vendors and suppliers commonly typically maintain their own product lines, which contribute to a larger (multi) product line or software ecosystem. It is unrealistic to assume that the participating organizations will agree on using a specific variability modeling technique—they will rather use different approaches and tools to manage the variability of their systems.ObjectiveWe aim to support product configuration in software ecosystems based on several variability models with different semantics that have been created using different notations.MethodWe present an integrative approach that provides a unified perspective to users configuring products in multi product line environments, regardless of the different modeling methods and tools used internally. We also present a technical infrastructure and a prototype implementation based on web services.ResultsWe show the feasibility of the approach and its implementation by using it with the three most widespread types of variability modeling approaches in the product line community, i.e., feature-based, OVM-style, and decision-oriented modeling. To demonstrate the feasibility and flexibility of our approach, we present an example derived from industrial experience in enterprise resource planning. We further applied the approach to support the configuration of privacy settings in the Android ecosystem based on multiple variability models. We also evaluated the performance of different model enactment strategies used in our approach.ConclusionsTools and techniques allowing stakeholders to handle variability in a uniform manner can considerably foster the initiation and growth of software ecosystems from the perspective of software reuse and configuration.     

Product-based workflow support

Despite the industrial need for the improvement of information-intensive business processes, few scientifically grounded approaches exist to support such initiatives. In this paper, we propose a new approach that builds on concepts that are part of a product-oriented view on process optimization. Essentially, this approach allows end users to flexibly decide on the best possible way to create an informational product within the limits that are imposed by regulations and logical dependencies. We argue that this provides various benefits in comparison to earlier work. To support end users in making sensible decisions, we describe two alternative approaches to provide them with recommendations to this end. We formalize these alternatives and discuss their relative strengths and weaknesses. The feasibility of the overall approach, which we refer to as Product-Based Workflow Support, is demonstrated by a workflow system that is realized using ProM and DECLARE.     

A geometric approach for constructing coteries and k-coteries

Quorum-based mutual exclusion algorithms are resilient to node and communication line failures. Recently, some mutual exclusion algorithms successfully use logical structures to construct coteries with small quorums sizes. In this paper, we introduce a geometric approach on dealing with the logical structures and present some useful geometric properties for constructing coteries and k-coteries. Based on those geometric properties, a logical structure named three-sided graph is proposed to provide a new scheme for constructing coteries with small quorums: The smallest quorum size is O(√N) in a homogeneous system with N nodes and O(1) in a heterogeneous system. In addition, we also extend the three-sided graph to the O-sided graph for constructing k-coteries     

Logical foundations of nonmonotonic reasoning

In this paper we shall review the main appraches to nonmonotonic reasoning which we classify from the perspective of their underlying logical settings as classical, intuitionistic, three-valued/partial models, and conditional. We shall be placing special emphasis on some of the prominent approaches. We shall also give hints on potential future directions and emphasize that more theoretical work is still needed before a move to application is made.     

Unravelling infectious disease eco-epidemiology using Bayesian networks and scenario analysis: A case study of leptospirosis in Fiji

Regression models are the standard approaches used in infectious disease epidemiology, but have limited ability to represent causality or complexity. We explore Bayesian networks (BNs) as an alternative approach for modelling infectious disease transmission, using leptospirosis as an example. Data were obtained from a leptospirosis study in Fiji in 2013. We compared the performance of naïve versus expert-structured BNs for modelling the relative importance of animal species in disease transmission in different ethnic groups and residential settings. For BNs of animal exposures at the individual/household level, R² for predicted versus observed infection rates were 0.59 for naïve and 0.75–0.93 for structured models of ethnic groups; and 0.54 for naïve and 0.93–1.00 for structured models of residential settings. BNs provide a promising approach for modelling infectious disease transmission under complex scenarios. The relative importance of animal species varied between subgroups, with important implications for more targeted public health control strategies.     

An architecture-driven software mobility framework

Software architecture has been shown to provide an appropriate level of granularity for assessing a software system’s quality attributes (e.g., performance and dependability). Similarly, previous research has adopted an architecture-centric approach to reasoning about and managing the run-time adaptation of software systems. For mobile and pervasive software systems, which are known to be innately dynamic and unpredictable, the ability to assess a system’s quality attributes and manage its dynamic run-time behavior is especially important. In the past, researchers have argued that a software architecture-based approach can be instrumental in facilitating mobile computing. In this paper, we present an integrated architecture-driven framework for modeling, analysis, implementation, deployment, and run-time migration of software systems executing on distributed, mobile, heterogeneous computing platforms. In particular, we describe the framework’s support for dealing with the challenges posed by both logical and physical mobility. We also provide an overview of our experience with applying the framework to a family of distributed mobile robotics systems. This experience has verified our envisioned benefits of the approach, and has helped us to identify several avenues of future work.     

一种自动的形式化验证技术-模型检测

模型检测是针对有限状态系统行为的逻辑性质的一种自动验证技术,已有许多工业应用.其主要缺陷是空间爆炸问题.本文通过一简单实例介绍其基本思想、检测步骤和相关理论,给出一些处理状态空间爆炸问题的优化技术,并与其它验证方法进行了比较,最后简单介绍了软件模型检测的新进展.     

A content-search information retrieval process based on conceptual graphs

An intelligent information retrieval system is presented in this paper. In our approach, which complies with the logical view of information retrieval, queries, document contents and other knowledge are represented by expressions in a knowledge representation language based on the conceptual graphs introduced by Sowa. In order to take the intrinsic vagueness of information retrieval into account, i.e. to search documents imprecisely and incompletely represented in order to answer a vague query, different kinds of probabilistic logic are often used. The search process described in this paper uses graph transformations instead of probabilistic notions. This paper is focused on the content-based retrieval process, and the cognitive facet of information retrieval is not directly addressed. However, our approach, involving the use of a knowledge representation language for representing data and a search process based on a combinatorial implementation of van Rijsbergen’s logical uncertainty principle, also allows the representation of retrieval situations. Hence, we believe that it could be implemented at the core of an operational information retrieval system. Two applications, one dealing with academic libraries and the other concerning audiovisual documents, are briefly presented.     

CONSISTENCY CHECKING ALONG TIME

Most model-based approaches to diagnosis require a consistency-checking procedure to perform their task. When dealing with a dynamically changing system, such a procedure must take into account time-varying data. This requires suitable techniques for reasoning over time. Additional difficulties arise when delays are involved in interactions between variables. The worst case occurs when some of the delays are completely unspecified. This report presents an approach to consistency checking that handles qualitative models of dynamic systems exhibiting time lags. A component-centered ontology is adopted to model the structure of the physical system, and an episode-based approach is adopted for representing its behavior over time. An example consisting of a physical process exhibiting transportation lags is used to illustrate the power of the approach. We present algorithms and an implementation in PROLOG called C-CAT (consistency checking along time). Some meaningful outputs from the program are used as examples. The solution proposed represents an extension to B. C. Williams' temporal constraint propagation methodology. It also extends the applicability range of existing approaches to model-based diagnosis, permitting its use in tasks such as online diagnosis of dynamic systems.     

The indefinite closed world assumption

The inadequacy of the Closed World Assumption in dealing with indefinite information has led to the Generalised Closed World Assumption and the Extended Generalised Closed World Assumption. However, these approaches have serious shortcomings. In this paper, the Indefinite Closed World Assumption is proposed to overcome the shortcomings. It provides a desirable and simple logical interpretation of a database containing indefinite information.     

The implications of complexity for integrated resources management

Integrated environmental resources management is a purposeful activity with the goal to maintain and improve the state of an environmental resource affected by human activities. In many cases different goals are in conflict and the notion “integrated” clearly indicates that resources management should be approached from a broad perspective taking all potential trade-offs and different scales in space and time into account. However, we are yet far from putting into practice integrated resources management fully taking into account the complexity of human-technology-environment systems. The tradition of resources management and of dealing with environmental problems is characterized by a command and control approach. The increasing awareness for the complexity of environmental problems and of human-technology-environment systems has triggered the development of new management approaches. The paper discusses the importance of focusing on the transition to new management paradigms based on the insight that the systems to be managed are complex adaptive systems. It provides arguments for the role of social learning processes and the need to develop methods combining approaches from hard and soft systems analysis. Soft systems analysis focuses on the importance of subjective perceptions and socially constructed reality. Soft systems methods and group model building techniques are quite common in management science where the prime target of management has always been the social system. Resources management is still quite slow to take up such innovations that should follow as a logical consequence of adopting an integrated management approach. Integrated water resources management is used as example to provide evidence for the need to implement participatory and adaptive management approaches that are able to cope with increasing uncertainties arising from fast changing socio-economic conditions and global and climate change. Promising developments and future research directions are discussed. The paper concludes with pointing out the need for changes in the scientific community to improve the conditions for interdisciplinary, system-oriented and trans-disciplinary research.     

Exception representation and management in open multi-agent systems

One of the major issues in dealing with exceptions in open multi-agent systems (MAS) is lack of uniform representation of exceptions and their shared semantics. In the absence of a uniform framework different business organizations may use different representations for the same exception or may interpret the same exception in different ways. In order to address this issue we apply an ontological approach as a uniform way of representing and interpreting exceptions in cross-organizational settings. This helps agents from different organizations interpret exceptional situations in an unambiguous way and exchange exception related information using standard structures. We believe that an exception ontology along with a domain ontology increases the open MAS reliability and also enhances its fault tolerance capability. The proposed ontology is built using the ontological support provided by the JADE agent framework and exception diagnoses agents are implemented using the JACK™ agent framework.     

On vague logics and approximate reasoning based on vague linear transformation

As a generalisation of the Fuzzy Sets theory, vague set has been proven to be a new tool in dealing with vague information. In this article, we attempt to generalise the techniques of fuzzy inference in a vague environment. In the rule-based inference system, an ‘if?…?then?…’ rule can be considered a transformer that implements information conversion between input–output ends. Thus, according to the logical operations of vague linguistic variables, we introduce an approach to approximation inference based on linear transformation, and then discuss the representations for several inference structures regarding single rule, multi-rules and compound rules. By defining the inclusion function of vague sets, we provide vague rough approximation based on measure of inclusion, and then present a method on rule creation from a decision system. A case study on the prediction for welding deformation is used to illustrate the effectiveness of the proposed approaches.     

An optimal allocation of memory buffers for complex multicore platforms

In deeply embedded heterogeneous multicores the allocation of data to memories is crucial for application performance. For applications with stringent throughput constraints, the allocation is often done manually by carefully assigning static memory locations to the logical buffers of the application. Today, designers are confronted with applications with thousands of buffers and architectures with hundreds of memories, rendering manual approaches impractical. In this paper we present an automatic approach for statically allocating logical buffers to physical memories, assuming a fixed task-to-processor mapping and respecting multiple throughput constraints.In our approach, we model the application in a data-centric way, by explicitly defining buffers and associating computational tasks that access the buffers within well-specified time intervals. Besides, we use an architecture model that allows to perform an allocation that is aware of the topology of the multicore and the physical bandwidth constraints of the interconnect. We present a layered approach to describe and solve the buffer-allocation problem as well as related subproblems, using mixed-integer linear programming. We show that the buffer-allocation problem is NP-complete, and present a more scalable formulation as a semi-definite programming problem. We evaluate the proposed LP methods by allocating around 1000 buffers corresponding to processing one frame in the Long-Term Evolution (LTE) standard, onto a multicore with 80 processing elements. We introduce a solution approach that allowed to find an optimal allocation in around 2 hours, which is at least two orders of magnitude faster than a straightforward formulation.     

Fast unsupervised feature selection with anchor graph and <Emphasis Type="Italic">ℓ</Emphasis><Subscript>2,1</Subscript>-norm regularization

Graph-based unsupervised feature selection has been proven to be effective in dealing with unlabeled and high-dimensional data. However, most existing methods face a number of challenges primarily due to their high computational complexity. In light of the ever-increasing size of data, these approaches tend to be inefficient in dealing with large-scale data sets. We propose a novel approach, called Fast Unsupervised Feature Selection (FUFS), to efficiently tackle this problem. Firstly, an anchor graph is constructed by means of a parameter-free adaptive neighbor assignment strategy. Meanwhile, an approximate nearest neighbor search technique is introduced to speed up the anchor graph construction. The ?_2,1-norm regularization is then performed to select more valuable features. Experiments on several large-scale data sets demonstrate the effectiveness and efficiency of the proposed method.