With intelligent devices’ prevalence, mobile edge computing (MEC) technology can effectively process the massive data in the Internet of Things (IoT). The metadata produced in MEC plays a role in colossal data management. However, it also includes lots of user privacy information. Traditional privacy protection solutions sacrifice the metadata’s availability or are incompatible with the distributed environment. To overcome this dilemma, we propose a blockchain-based secure searching strategy for metadata (BSSMeta) in MEC. By leveraging a lightweight proxy re-encryption scheme and a decentralized key generation method on the blockchain, BSSMeta keeps the security of the metadata searching tasks. Meanwhile, a main/secondary smart contract method and a buffer uploading strategy are proposed for the efficiency of the searching and uploading processes. As a byproduct, BSSMeta also supports searching metadata in a multiuser environment and gives users access control to metadata. Finally, we provide a security analysis of BSSMeta and implement a prototype on the Hyperledger Fabric platform. The results of experiments on various workloads show that BSSMeta is feasible and flexible in security and efficiency.

Existential rules, a.k.a. dependencies in databases, and Datalog+/- in knowledge representation and reasoning recently, are a family of important logical languages widely used in computer science and artificial intelligence. Towards a deep understanding of these languages in model theory, we establish model-theoretic characterizations for a number of existential rule languages such as (disjunctive) embedded dependencies, tuple-generating dependencies (TGDs), (frontier-)guarded TGDs and linear TGDs. All these characterizations hold for the class of arbitrary structures, and most of them also work on the class of finite structures. As a natural application of these results, complexity bounds for the rewritability of above languages are also identified.

A logic program with function symbols is called finitely ground if there is a finite propositional logic program whose stable models are exactly the same as the stable models of this program. Finite groundability is an important property for logic programs with function symbols because it makes feasible to compute such programs' stable models using traditional ASP solvers. In this paper, we introduce new decidable classes of finitely ground programs called poly-bounded and k-EXP-bounded programs, which, to the best of our knowledge, strictly contain all other decidable classes of finitely ground programs discovered so far in the literature. We also study the relevant complexity properties for these classes of programs. We prove that the membership complexities for poly-bounded and k-EXP-bounded programs are EXPTIME-complete and (k+1)-EXPTIME-complete, respectively.

With the popularity of cloud storage, how to verify the integrity of data on the cloud has become a challenging problem. Traditional verification framework involves the Third Party Auditors (TPAs) which are not entirely credible. In this paper, we present a framework for blockchain-based data integrity verification in P2P cloud storage, making verification more open, transparent, and auditable. In this framework, we present Merkle trees for data integrity verification, and analyze the system performance under different Merkle trees structures. Furthermore, we develop rational sampling strategies to make sampling verification more effective. Moreover, we discuss the optimal sample size to tradeoff the conflict between verification overhead and verification precision, and suggest two efficient algorithms of order of verification. Finally, we conduct a series of experiments to evaluate the schemes of our framework. The experimental results show that our schemes can effectively improve the performance of data integrity verification.

Stable model semantics had been recently generalized to non-Herbrand structures by several works, which provides a unified framework and solid logical foundations for answer set programming. This article focuses on the expressiveness of normal and disjunctive logic programs under general stable model semantics. A translation from disjunctive logic programs to normal logic programs is proposed for infinite structures. Over finite structures, some disjunctive logic programs are proved to be intranslatable to normal logic programs if the arities of auxiliary predicates and functions are bounded in a certain way. The equivalence of the expressiveness of normal logic programs and disjunctive logic programs over arbitrary structures is also shown to coincide with that over finite structures and coincide with whether the complexity class NP is closed under complement. Moreover, to obtain a more explicit picture of the expressiveness, some intertranslatability results between logic program classes, and fragments of second-order logic are established.

Classical inconsistency-tolerant query answering relies on selecting maximal components of an ABox/database which are consistent with the ontology. However, some rules in ontologies might be unreliable if they are extracted from ontology learning or written by unskillful knowledge engineers. In this paper we present a framework of handling inconsistent existential rules under stable model semantics, which is defined by a notion called rule repairs to select maximal components of the existential rules. Surprisingly, for R-acyclic existential rules with R-stratified or guarded existential rules with stratified negations, both the data complexity and combined complexity of query answering under the rule repair semantics remain the same as that under the conventional query answering semantics. This leads us to propose several approaches to handle the rule repair semantics by calling answer set programming solvers. An experimental evaluation shows that these approaches have good scalability of query answering under rule repairs on realistic cases.

Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied. In this work, we propose a novel approach for classifying the rule languages with finite chase. Using this approach, a family of decidable rule languages, which extend the existing languages with the finite chase property, are naturally defined. We then study the complexity of these languages. Although all of them are tractable for data complexity, we show that their combined complexity can be arbitrarily high. Furthermore, we prove that all the rule languages with finite chase that extend the weakly acyclic language are of the same expressiveness as the weakly acyclic one, while rule languages with higher combined complexity are in general more succinct than those with lower combined complexity.

This paper focuses on computing general first-order parallel and prioritized circumscription with varying constants. We propose linear translations from general first-order circumscription to first-order theories under stable model semantics over arbitrary structures, including Tr_v for parallel circumscription and Tr^s_v for conjunction of parallel circumscriptions (further for prioritized circumscription). To improve the efficiency, we give an optimization \Gamma_{\exists} to reduce logic programs in size when eliminating existential quantifiers during the translations. Based on these results, a general first-order circumscription solver, named cfo2lp, is developed by calling answer set programming (ASP) solvers. Using circuit diagnosis problem and extended stable marriage problem as benchmarks, we compare cfo2lp with a propositional circumscription solver circ2dlp and an ASP solver with complex optimization metasp on efficiency. Experimental results demonstrate that for problems represented by first-order circumscription naturally and intuitively, cfo2lp can compute all solutions over finite structures. We also apply our approach to description logics with circumscription and repairs in inconsistent databases, which can be handled effectively.

Attribute-Based Access Control (ABAC) maps of characteristics of users, objects and the environment to authorisations. ABAC is a highly versatile access control model well suited to domains such as web services. With the recent set of draft ABAC guidelines by NIST there is a clear desire to promote further adoption of the model. Despite this ABAC continues to face challenges relating to policy evaluation. In this paper we present a novel framework for ABAC policy evaluation based on negotiations and formalised in Answer Set Programming.

The ability of discarding or hiding irrelevant information has been recognized as an important feature for knowledge based systems, including answer set programming. The notion of strong equivalence in answer set programming plays an important role for different problems as it gives rise to a substitution principle and amounts to knowledge equivalence of logic programs. In this paper, we uniformly propose a semantic knowledge forgetting, called HT- and FLP-forgetting, for logic programs under stable model and FLP-stable model semantics, respectively. Our proposed knowledge forgetting discards exactly the knowledge of a logic program which is relevant to forgotten variables. Thus it preserves strong equivalence in the sense that strongly equivalent logic programs will remain strongly equivalent after forgetting the same variables. We show that this semantic forgetting result is always expressible; and we prove a representation theorem stating that the HT- and FLP-forgetting can be precisely characterized by Zhang-Zhou's four forgetting postulates under the HT- and FLP-model semantics, respectively. We also reveal underlying connections between the proposed forgetting and the forgetting of propositional logic, and provide complexity results for decision problems in relation to the forgetting. An application of the proposed forgetting is also considered in a conflict solving scenario.

In this article, we consider the issue of how first-order answer set programs can be extended for handling preference reasoning. To this end, we propose a progression-based preference semantics for first-order answer set programs while explicit preference relations are presented. We study essential properties of the proposed preferred answer set semantics. To understand the expressiveness of preferred first-order answer set programming, we further specify a second-order logic representation which precisely characterizes the progression-based preference semantics.

Online Social Networks hold vast amounts of readily accessible personal information leaving them particularly vulnerable to privacy breach attacks [6]. With the impact these breaches varying from simply embarrassing the user, to negatively influencing the decision of potential employers, identity theft and even physical harm it is important that they are addressed. In this research we approach privacy management in OSNs as an access control problem. We propose a formal Attribute-Based Access Control (ABAC) language; SocACL. SocACL is based on Answer Set Programming (ASP) and allows for policy specification using the most abundant sources of information available in OSNs; user attributes and relationships. This paper outlines SocACL's core concepts, features, syntax and semantics.

Abstract We consider disjunctive logic programs without function symbols but with existential quantification in rule heads, under the semantics of general stable models. There are at least two interesting prospects in these programs. The first is that a program can be made more succinct by using existential variables, and the second is on the potential in representing defeasible ontological knowledge by these logic programs. This paper studies some of the properties of these programs. First, we show a simple yet intuitive definition of stable models for these programs that does not resort to second-order logic. Second, the stable models of these programs can be characterized by an extension of progression for disjunctive programs, which provides a native characterization of justification for stable models. We then study the decidability issue. While the stable model existence problem for safe disjunctive programs is decidable, with existential quantification allowed in rule heads the problem becomes undecidable. We identify an interesting decidable fragment by exploring a new notion of stratification over existential quantification.

In this paper, we show that first-order logic programs with monotone aggregates under the stable model semantics can be captured in classical first-order logic. More precisely, we extend the notion of ordered completion for logic programs with a large variety of aggregates so that every stable model of a program with aggregates corresponds to a classical model of its enhanced ordered completion, and vice versa.

Role engineering (RE) aims to develop and maintain appropriate role-based access control (RBAC) configurations. However, RE with constraints in place is not well-studied. Constraints usually describe organizations' security and business requirements. An inconsistency between configurations and constraints compromises security and availability, as it may authorize otherwise forbidden access and deprive users of due privileges. In this paper, we apply answer set programming (ASP) to discover RBAC configurations that comply with constraints and meet various optimization objectives. We first formulate the need of supporting constraints as a problem independent of and complementary to existing RE problems. We then present a flexible framework for translating the proposed problem to ASP programs. In this way, the problem can be addressed via ASP solvers. Finally, we demonstrate the effectiveness and efficiency of our approach through experimental results.

The result of forgetting some predicates in a first-order sentence may not exist in the sense that it might not be captured by any first-order sentences. This, indeed, severely restricts the usage of forgetting in applications. To address this issue, we propose a notion called $k$-forgetting, also called bounded forgetting in general, for any fixed number $k$. We present several equivalent characterizations of bounded forgetting and show that the result of bounded forgetting, on one hand, can always be captured by a single first-order sentence, and on the other hand, preserves the information that we are concerned with.

In this paper, we extend the progression semantics for first-order disjunctive logic programs and show that it coincides with the stable model semantics. Based on it, we further show how disjunctive answer set programming is related to Satisfiability Modulo Theories.

We introduce a novel logical notion--partial entailment--to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set \Gamma intuitively means that under the circumstance of \Gamma, if P is true then some "part" of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.

In this paper, we propose a translation from normal first-order logic programs under the answer set semantics to first-order theories on finite structures. Specifically, we introduce ordered completions which are modifications of Clark's completions with some extra predicates added to keep track of the derivation order, and show that on finite structures, classical models of the ordered-completion of a normal logic program correspond exactly to the answer sets (stable models) of the logic program.

An answer set program with variables is first-order definable on finite structures if the set of its finite answer sets can be captured by a first-order sentence, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fraisse game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.

In distributed environments, statements from a number of principals, besides the central trusted party, may influence the derivations of authorization decisions. However, existing authorization logics put few emphasis on this set of principals - authorization provenance. Reasoning about provenance enables to (1) defend against a class of attacks, (2) understand and analyze authorizations and the status of policy bases, and (3) obtain potentially efficient logging and auditing guided by provenance information. This paper presents the design and applications of a provenance-enabled authorization logic, called DBT. More specifically, we give a sound and complete axiomatic system of DBT. We also examine a class of provenance-aware policy bases and queries. One can syntactically extract provenance information from the structure of these queries if they are evaluated positively in provenance-aware policy bases. Finally, two case studies are presented to demonstrate possible applications of DBT.

Model update is an approach to enhance model checking functions by providing computer aided modifications in system development [2, 9]. It has been observed that one major obstacle restricting the application of this approach, e.g. CTL model update [15], is that the update has to take the entire system model into account, and that is usually not feasible for large scale domains. In this paper, we develop a tree-like local model update approach under the framework of ACTL – a widely used fragment of CTL in property specification. We define a bisimulation based minimal change principle on tree-like local model update, reveal its relationship to traditional belief update and provide essential semantic characterizations. We also investigate primary semantic and computational properties in relation to tree-like local model update. Finally we briefly describe the update system prototype that we have implemented and summarize our experimental results.

The role-based access control (RBAC) has significantly simplified the management of users and permissions in computing systems. In dynamic environments, systems are usually undergoing changes, whereas the associated user-role, role-role and role-permission relations need to be updated accordingly in order to reflect the systems’ evolutions. However, such updating process is generally complicated as the resulting system state is expected to meet necessary constraints. This paper presents an approach for assisting administrators with the update task: using this approach, it is possible to check, in an automatic way, whether a required update is achievable or not, and if so, a reference model will be produced. In light of this model, administrators could fulfill the changes to RBAC systems. We propose a formalization of the update approach, investigate its properties, and develop an updating algorithm based on model checking techniques. Our experimental results demonstrate the effectiveness of our approach.

In distributed environments, access control decisions depend on statements of multiple agents rather than only one central trusted party. However, existing policy languages put few emphasis on authorization provenances. The capability of managing these provenances is important and useful in various security areas such as computer auditing and safeguarding delegations. Based on the newly proposed logic, we define one type of authorization provenances. We exemplify the applications of these provenances by a case study.

In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\' knowledge. In our framework, two notions namely agents\' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.

We consider the problem of updating non-monotonic knowledge bases represented by epistemic logic programs where disjunctive information and notions of knowledge and belief can be explicitly expressed. We propose a formulation for epistemic logic program update based on a principle called minimal change and maximal coherence. The central feature of our approach is that during an update or a sequence of updates, contradictory information is removed on a basis of minimal change under the semantics of epistemic logic programs and then coherent information is maximally retained in the update result. Through various update scenarios, we show that our approach provides both semantic and syntactic characterizations for an update problem. We also investigate essential semantic properties of epistemic logic program update.

Model checking is a promising technology, which has been applied for verification of many hardware and software systems. In this paper, we introduce the concept of model update towards the development of an automatic system modification tool that extends model checking functions. We define primitive update operations on the models of Computation Tree Logic (CTL) and formalize the principle of minimal change for CTL model update. These primitive update operations, together with the underlying minimal change principle, serve as the foundation for CTL model update. Essential semantic and computational characterizations are provided for our CTL model update approach. We then describe a formal algorithm that implements this approach. We also illustrate two case studies of CTL model updates for the well-known microwave oven example and the Andrew File System 1, from which we further propose a method to optimize the update results in complex system modifications.

Shapley's impossibility result indicates that the two-person bargaining problem has no non-trivial ordinal solution with the traditional game-theoretic bargaining model. Although the result is no longer true for bargaining problems with more than two agents, none of the well known bargaining solutions are ordinal. Searching for meaningful ordinal solutions, especially for the bilateral bargaining problem, has been a challenging issue in bargaining theory for more than three decades. This paper proposes a logic-based ordinal solution to the bilateral bargaining problem. We argue that if a bargaining problem is modeled in terms of the logical relation of players' physical negotiation items, a meaningful bargaining solution can be constructed based on the ordinal structure of bargainers' preferences. We represent bargainers' demands in propositional logic and bargainers' preferences over their demands in total preorder. We show that the solution satisfies most desirable logical properties, such as individual rationality (logical version), consistency, collective rationality as well as a few typical game-theoretic properties, such as weak Pareto optimality and contraction invariance. In addition, if all players' demand sets are logically closed, the solution satisfies a fixed-point condition, which says that the outcome of a negotiation is the result of mutual belief revision. Finally, we define various decision problems in relation to our bargaining model and study their computational complexity.

In logic program-based updates, contradictory information elimination, conflict resolution, and syntactic representation are three major issues that interfere with each other and significantly influence the update result. We observe that existing approaches of logic program-based updates, in one way or another, are problematic to deal with these issues. In this article, we address all these problems in a systematic manner. Our approach to the logic program-based update has the following features: (1) a prioritized logic programming language is employed for providing a formal basis of formalizing logic program-based updates, so that information conflict and its related problems in updates can be handled properly; (2) our approach presents both semantic characterization and syntactic representation for the underlying update procedure, and hence is consistent with the nature of updates within the logic program extent-declarative semantics and syntactic sensitivity; and (3) our approach also provides nontrivial solutions to simplify various update evaluation procedures under certain conditions.

In this paper, we propose an extended logic programming based formalization for a multi-agent system in mobile environments. Such a system consists of a number of agents connected via wire or wireless communication channels. Our formalization is knowledge oriented and has declarative semantics inherited from extended logic programming. This model can be used to study the details of knowledge transaction in mobile environments.

In this paper, we propose a formal approach of Artificial Intelligence (AI) in securing object oriented database systems. We combine the specification of object oriented database with security policies and provide its formal syntax and semantics. The properties in the inheritance of authorizations in object oriented database system and reasoning about authorizations on data objects are also investigated in detail.

Prioritized default reasoning has illustrated its rich expressiveness and flexibility in knowledge representation and reasoning. However, many important aspects of prioritized default reasoning have yet to be thoroughly explored. In this paper, we investigate two properties of prioritized logic programs in the context of answer set semantics. Specifically, we reveal a close relationship between mutual defeasibility and uniqueness of the answer set for a prioritized logic program. We then explore how the splitting technique for extended logic programs can be extended to prioritized logic programs. We prove splitting theorems that can be used to simplify the evaluation of a prioritized logic program under certain conditions.

Representing defeasibility is an important issue in common sense reasoning. In reasoning about action and change, this issue becomes more difficult because domain and action related defeasible information may conflict with general inertia rules. Furthermore, different types of defeasible information may also interfere with each other during the reasoning. In this paper, we develop a prioritized logic programming approach to handle defeasibilities in reasoning about action. In particular, we propose three action languages ${\cal AT}^{0}$ , ${\cal AT}^{1}$ , and ${\cal AT}^{2}$ which handle three types of defeasibilities in action domains named defeasible constraints, defeasible observations and actions with defeasible and abnormal effects respectively. Each language with a higher superscript can be viewed as an extension of the language with a lower superscript. These action languages inherit the simple syntax of ${\cal A}$ language but their semantics is developed in terms of transition systems where transition functions are defined based on prioritized logic programs. By illustrating various examples, we show that our approach eventually provides a powerful mechanism to handle various defeasibilities in temporal prediction and postdiction. We also investigate semantic properties of these three action languages and characterize classes of action domains that present more desirable solutions in reasoning about action within the underlying action languages.

The possible models approach is a classical minimal change semantics for knowledge base update, which provides an exclusive interpretation for disjunctive information in updates. It has been recognized that the exclusive interpretation for disjunction may be problematic under some circumstances. In this paper, we investigate inclusive interpretations for disjunctions in updates from both syntactical and semantical viewpoints. In particular, we propose two approaches for disjunctive update—the minimal change with exceptions (MCE) and the minimal change with maximal disjunctive inclusions (MCD). Both approaches provide inclusive interpretations for disjunctions in updates, though the first is syntax‐based and the second is model‐theoretic. We then characterize the MCE and MCD in terms of alternative minimal change criteria and relate them to traditional Katsuno and Mendelzon's update postulates.

Commonsense reasoning is an essential issue in knowledge representation, system dynamics modeling and information processing. However, logic based theories of commonsense reasoning always suffer from computational difficulties during their reasoning. For instance, even for a simple propositional case of default reasoning, the computation of a default theory's extension is intractable. On the other hand, recent research shows that the hybrid symbolic-neural network (HSNN) has both specification and computational advantages in commonsense reasoning. However, the major shortcoming of this neural network, as argued by some researchers, is a lack of formal semantics. The purpose of this paper is to investigate formal semantics of HSNNs and show that under some formalization, a formal semantics is actually embedded within HSNNs.

Recent work on reasoning about action has shown that there exists an interesting connection between action specifications and state constraints — it is possible to extract state constraints from action specifications. This work provides us another way to describe the behaviour of dynamic systems. In this paper, we address the problem of generating action invariants from action specifications, and generalizing action invariants into state constraints. We first propose a persistence-based formalism of actions, and show that the generation of action invariants is achieved from action specifications by reasoning about persistence. We then investigate the generalization of action invariants into state constraints. Blocks world examples illustrate the general procedure throughout.