In this paper we study Secrecy-Preserving Query Answering problem under Open World Assumption (OWA) for ELH Knowledge Bases (KBs). We employ two tableau procedures designed to compute some consequences of ABox (A) and TBox (T ) denoted by A∗ and T ∗ respectively. A secrecy set of a querying agent is subset S of A∗ âˆa T ∗ which the agent is not allowed to access. An envelope is a superset of the secrecy set which provides logical protection to the secrecy set against the reasoning of the querying agent. Once envelopes are computed, they are used to efficiently answer assertional and GCI queries without compromising the secret information in S. Answering GCI queries while preserving secrecy has not been studied in the current literature. When the querying agent asks a query q, the reasoner answers “Yes” if KB |= q and q does not belong to the envelopes; otherwise, the reasoner answers “Unknown”. Being able to answer “Unknown” plays a key role in protecting secrecy under OWA. Since we are not computing all the consequences of the KB, answers to the queries based on just A∗ and T ∗ could be erroneous. To fix this problem, we further augment our algorithms to make the query answering procedure foolproof.

In many applications, Knowledge Bases (KBs) contain confidential or private information (secrets). The KB should be able to use this secret information in its reasoning process but in answering user queries care must be exercised so that secrets are not revealed to unauthorized users. We consider this problem under the Open World Assumption (OWA) in a setting with multiple querying agents M 1 ,…, M m that can pose queries against the KB K and selectively share answers that they receive from K with one or more other querying agents. We assume that for each M i , the KB has a prespecified set of secrets S i that need to be protected from M i . Communication between querying agents is modeled by a communication graph, a directed graph with self-loops. We introduce a general framework and propose an approach to secrecy-preserving query answering based on sound and complete proof systems. The idea is to hide the truthful answer from a querying agent M i by feigning ignorance without lying (i.e., to provide the answer ‘Unknown’ to a query q if it needs to be protected. Under the OWA, a querying agent cannot distinguish between the case that q is being protected (for reasons of secrecy) and the case that it cannot be inferred from K . In the pre-query stage we compute a set of envelopes E 1 , …, E m (restricted to a finite subset of the set of formulae that are entailed by K ) so that S i ⊆ E i , and a query α posed by agent M i can be answered truthfully whenever α ∉ E i and ¬ α ∉ E i . After the pre-query stage, the envelope is updated as needed. We illustrate this approach with two simple cases: the Propositional Horn KBs and the Description Logic AL KBs.

We introduce F-ALCI, a federated version of the description logic ALCI. An F-ALCI ontology, like its package-based counterpart ALCIP-, consists of multiple ALCI ontologies that can import concepts or roles defined in other modules. Unlike ALCIP-which supports only contextualized negation, F-ALCI, supports contextualization of each of the logical connectives, a feature that allows more flexible reuse of knowledge from independently developed ontologies. We provide a new semantics for F-ALCI based on image domain relations and establish the conditions that need to be imposed on domain relations to ensure properties, such as preservation of unsatisfiability and monotonicity of inference, that are desirable in distributed web applications. We also establish the decidability of F-ALCI.

Anonymous communication systems built on P2P infrastructures using anonymity forwarders are frequently affected by the churn problem, i.e. frequent joins and leaves of nodes. The problem unavoidably affects the quality of provided anonymity: The availability of anonymity forwarders will be decreased, which reduces the anonymity set; and the frequency of path reformation will increase, which increases the chance of successful intersection attacks. We propose an incentive-based P2P mechanism as an approach to providing reliable anonymity forwarding. It uses incentives to induce the peer nodes to provide anonymity forwarding as reliable service and to make stable and distributed forwarding decisions to minimize the frequency of path reformations. To support incentive, a payment system has been designed which meet the anonymity requirement and can handle typical scenarios of cheating and malicious attacks. To make sound forwarding decisions, we use game theory to carefully design the forwarding strategies used by the peer nodes. We have used event-driven simulations to evaluate the quality of anonymity provided by the mechanism under high churn and with the presence of malicious nodes. The results show that the quality of anonymity is maintained in those scenarios.

Many semantic web applications require selective sharing of ontologies between autonomous entities due to copyright, privacy or security concerns. In such cases, an agent might want to hide a part of its ontology while sharing the rest. However, prohibiting any use of the hidden part of the ontology in answering queries from other agents may be overly restrictive. We provide a framework for privacy- preserving reasoning in which an agent can safely answer queries against its knowledge base using inferences based on both the hidden and visible part of the knowledge base, without revealing the hidden knowledge. We show an application of this framework in the widely used special case of hierarchical ontologies.

We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n/sup 4/) whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on. the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 213 environment.For a simple polygon with n edges, the algorithm uses O(n 2) time to decide whether the polygon can be cleared by a 1-searcher, and if so, constructs a search schedule.The key ideas in this algorithm include a representation called the visibility obstruction diagram and a decomposition of this diagram based on a skeleton that arises from critical visibility events.An implementation is presented along with a computed example.

We present an algorithm for searching a 2D environment for unpredictable moving targets using only beam-based detection. One or more pursuers move along the environment boundary, and carry a rotating beam that detects evaders. The beam could correspond in practice to a laser or a camera. The task is to compute motions for pursuers and their beams that ensure that all evaders will be detected. For a 2D polygonal environment, we solve a long-standing open problem by presenting a complete O(n/sup 3/)-time algorithm that is guaranteed to find a successful motion strategy for a single pursuer and its beam, if a solution exists. This algorithm is extended to the case of coordinating multiple pursuers, but the number of pursuers used in a solution is not necessarily optimal. An implementation is presented, and several computed examples are shown.

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.

In this paper we consider the complexity of several problems involving finite algebraic structures. Given finite algebras A and B, these problems ask the following. (1) Do A and B satisfy precisely the same identities? (2) Do they satisfy the same quasi-identities? (3) Do A and B have the same set of term operations? In addition to the general case in which we allow arbitrary (finite) algebras, we consider each of these problems under the restrictions that all operations are unary and that A and B have cardinality two. We briefly discuss the relationship of these problems to algebraic specification theory.

The problem of deciding whether a full join dependency (JD) ⋈ [R] and a set of functional dependencies (FDs) F imply an embedded join dependency (EJD) ⋈ [S] is known to be NP-complete. We show that the problem can be decided in polynomial time if S ⊆ R and F is embedded in R. Our work uses arguments based on an extension of complete intersection graphs rather than tableaus. This approach has facilitated our results and should prove useful for future research.

Finite State Linear Programs (FSLP) are introduced to model simple data processing applications. Essentially these are finite automata with the added capability of performing linear operations on a set of registers and the input. Algorithmic constructions are given to test equivalence of FSLP programs, and to minimize the number of states and registers. Linear algebraic methods are used for the register minimization procedure (and its correctness proof).

This extended abstract is a condensed version of the results presented in two technical reports ([16] and [13]). In [16] a systematic treatment of the relationships between parallel rewriting systems (top-down tree transducer, ETOL system) and two-way machines (2-way gsm, tree-walking automaton, checking stack automaton) is given. Particular attention is paid to the effect of restricting the copying power of these devices. In [13] the results of [16] are employed to show that the iteration of nondeterministic top-down tree transducers, of nondeterministic 2-way gsm's and of control on ETOL systems each gives rise to a proper hierarchy.