Answering atomic queries in indefinite deductive databases

Answering queries in indefinite systems is a difficult problem both computationally, since it involves non-Horn clauses and factoring, and conceptually, concerning producing beliefs for formulas not derivable from the system. to provide a basis for reasonable beliefs, we propose new criteria as an alternative to the Full Information Principle. Then an approach to producing stable beliefs, called Plausible World Assumption (PWA), is introduced. It is shown how a set of non-Horn clauses can be transformed into a set of so called singleton-head-rules such that evaluation of a given query is reduced to processing of a set of Horn clauses relevant to the query. Finally, algorithms are presented for computing facts and beliefs for atomic queries in accord with the PWA. This method is shown to be more efficient than the known techniques for query evaluation in indefinite systems.     

Deduction, Strategies, and Rewriting

Automated deduction methods should be specified not procedurally, but declaratively, as inference systems which are proved correct regardless of implementation details. Then, different algorithms to implement a given inference system should be specified as strategies to apply the inference rules. The inference rules themselves can be naturally specified as (possibly conditional) rewrite rules. Using a high-performance rewriting language implementation and a strategy language to guide rewriting computations, we can obtain in a modular way implementations of both the inference rules of automated deduction procedures and of algorithms controling their application. This paper presents the design of a strategy language for the Maude rewriting language that supports this modular decomposition: inference systems are specified in system modules, and strategies in strategy modules. We give a set-theoretic semantics for this strategy language, present its different combinators, illustrate its main ideas with several examples, and describe both a reflective prototype in Maude and an ongoing C++ implementation.     

Two Natural Deduction Systems for Hybrid Logic: A Comparison

In this paper two different natural deduction systems forhybrid logic are compared and contrasted.One of the systems was originally given by the author of the presentpaper whereasthe other system under consideration is a modifiedversion of a natural deductionsystem given by Jerry Seligman.We give translations in both directions between the systems,and moreover, we devise a set of reduction rules forthe latter system bytranslation of already known reduction rules for the former system.     

Contextual preference mining for user profile construction

The emerging of ubiquitous computing technologies in recent years has given rise to a new field of research consisting in incorporating context-aware preference querying facilities in database systems. One important step in this setting is the Preference Elicitation task which consists in providing the user ways to inform his/her choice on pairs of objects with a minimal effort. In this paper we propose an automatic preference elicitation method based on mining techniques. The method consists in extracting a user profile from a set of user preference samples. In our setting, a profile is specified by a set of contextual preference rules verifying properties of soundness and conciseness. After proving that the problem is NP-complete, we propose a resolution in 2 phases. The first phase extracts all individual user preferences by means of contextual preference rules. The second phase builds the user profile starting from this collection of rules using a greedy method. To assess the quality of user profiles, we propose three ranking techniques benefiting from these profiles that enable us to rank objects according to user preferences. We evaluate the efficacy of our three ranking strategies and compare them with a well-known ranking method (SVMRank). The evaluation is carried out through an extensive set of experiments executed on a real-world database of user preferences about movies.     

Tree regular model checking: A simulation-based approach

Regular model checking is the name of a family of techniques for analyzing infinite-state systems in which states are represented by words, sets of states by finite automata, and transitions by finite-state transducers. In this framework, the central problem is to compute the transitive closure of a transducer. Such a representation allows to compute the set of reachable states of the system and to detect loops between states. A main obstacle of this approach is that there exists many systems for which the reachable set of states is not regular. Recently, regular model checking has been extended to systems with tree-like architectures. In this paper, we provide a procedure, based on a new implementable acceleration technique, for computing the transitive closure of a tree transducer. The procedure consists of incrementally adding new transitions while merging states, which are related according to a pre-defined equivalence relation. The equivalence is induced by a downward and an upward simulation relation, which can be efficiently computed. Our technique can also be used to compute the set of reachable states without computing the transitive closure. We have implemented and applied our technique to various protocols.     

A Faster One-Dimensional Topological Compaction Algorithm with Jog Insertion

We consider the problem of one-dimensional topological compaction with jog insertions. By combining both geometric and graph-theoretic approaches we present a faster and simpler algorithm to improve over previous results. The compaction algorithm takes as input a sketch consisting of a set F of features and a set W of wires, and minimizes the horizontal width of the sketch while maintaining its routability. The algorithm consists of the following steps: constructing a horizontal constraint graph, computing all possible jog positions, computing the critical path, relocating the features, and reconstructing a new sketch homotopic to the input sketch, which is suitable for detailed routing. The algorithm runs in O(|F| ⋅ |W|) worst-case time and space, which is asymptotically optimal in the worst case. Experimental results are also presented. Received May 16, 1997; revised January 11, 1999.     

Computability in planar dynamical systems

In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time planar dynamical systems. We consider C ¹ systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular, we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction are semi-computable if and only if the system is stable.     

The <Emphasis Type="Italic">λ</Emphasis>-Calculus and the Unity of Structural Proof Theory

In the context of intuitionistic implicational logic, we achieve a perfect correspondence (technically an isomorphism) between sequent calculus and natural deduction, based on perfect correspondences between left-introduction and elimination, cut and substitution, and cut-elimination and normalisation. This requires an enlarged system of natural deduction that refines von Plato’s calculus. It is a calculus with modus ponens and primitive substitution; it is also a “coercion calculus”, in the sense of Cervesato and Pfenning. Both sequent calculus and natural deduction are presented as typing systems for appropriate extensions of the λ-calculus. The whole difference between the two calculi is reduced to the associativity of applicative terms (sequent calculus = right associative, natural deduction = left associative), and in fact the achieved isomorphism may be described as the mere inversion of that associativity. The novel natural deduction system is a “multiary” calculus, because “applicative terms” may exhibit a list of several arguments. But the combination of “multiarity” and left-associativity seems simply wrong, leading necessarily to non-local reduction rules (reason: normalisation, like cut-elimination, acts at the head of applicative terms, but natural deduction focuses at the tail of such terms). A solution is to extend natural deduction even further to a calculus that unifies sequent calculus and natural deduction, based on the unification of cut and substitution. In the unified calculus, a sequent term behaves like in the sequent calculus, whereas the reduction steps of a natural deduction term are interleaved with explicit steps for bringing heads to focus. A variant of the calculus has the symmetric role of improving sequent calculus in dealing with tail-active permutative conversions.     

H∞ model reduction of Markovian jump linear systems

In this paper, the H_∞ model reduction problem for linear systems that possess randomly jumping parameters is studied. The development includes both the continuous and discrete cases. It is shown that the reduced order models exist if a set of matrix inequalities is feasible. An effective iterative algorithm involving linear matrix inequalities is suggested to solve the matrix inequalities characterizing the model reduction solutions. Using the numerical solutions of the matrix inequalities, the reduced order models can be obtained. An example is given to illustrate the proposed model reduction method.     

Worst‐case control policies for (terminal) linear–quadratic control problems under disturbances

We consider linear control systems under uncertainties. For such systems we solve the problem of constructing worst‐case feedback control policies that are allowed to be corrected at m fixed intermediate time moments. We propose two types of the approximative control policies. All of them guarantee that for all admissible uncertainties the terminal system state lies in a prescribed neighborhood of a given state x_* at a given final moment, and the value of the cost function does not exceed a given estimate. It is shown that computation of the estimate for each policy is equivalent to solving a corresponding convex mathematical programming (MP) problem with m decision variables. Based on the solution of the MP problem, we derive simple explicit rules (which can be easily implemented on‐line) for constructing the corresponding control policy in the original control problem. Copyright © 2009 John Wiley & Sons, Ltd.     

Time-optimal output regulators for linear multivariate discrete-time systems Part 2. All classes of right-invertible systems

In Part 1 of this paper (Hassan and Amin 1987) a simple algebraic solution for the time-optimal output regulator problem was presented. This solution, which consists of a state feedback control law, has been obtained for all classes of right-invertible decouplable systems S(A, B, C, E). The results of Part 1 are here extended to all classes of right-invertible systems S(A, B, C, E). A set of optimal output deadbeat indices (called the ‘optimal set’) is defined and related to the observability indices of the optimal closed-loop system. The time-optimal output regulator problem for a right-invertible non-decouplable system S(A, B, C, E) is resolved by transforming S into a decouplable system S_c(A, B, C_c, E_c) having the optimal output deadbeat index σ* of S. First, an algorithm is presented to construct iteratively, in a well-defined optimal sense, a unimodular left compensator L(z) and a compensated decouplable system S_c(A, B, C_c, E_c) from the state-space parameters of S. Then, a family of optimal state feedback matrices F_c *, which attains the optimal set of S_c , is given as the optimal solution F* of S. For any right-invertible system S(A, B, C, E), it is shown that the optimal number of control iterations required at most to zero its outputs is equal to the associated uniquely defined μ ₁ index of the right Wiener-Hopf factorization at infinity of H(z) (the transfer function matrix of the system). A numerical example is worked out to illustrate the design procedures of time-optimal output regulators for non-decouplable systems.     

Argumentation frameworks as constraint satisfaction problems

Argumentation is a promising approach for defeasible reasoning. It consists of justifying each plausible conclusion by arguments. Since the available information may be inconsistent, a conclusion and its negation may both be justified. The arguments are thus said to be conflicting. The main issue is how to evaluate the arguments. Several semantics were proposed for that purpose. The most important ones are: stable, preferred, complete, grounded and admissible. A semantics is a set of criteria that should be satisfied by a set of arguments, called extension, in order to be acceptable. Different decision problems related to these semantics were defined (like whether an argumentation framework has a stable extension). It was also shown that most of these problems are intractable. Consequently, developing algorithms for these problems is not trivial and thus the implementation of argumentation systems not obvious. Recently, some solutions to this problem were found. The idea is to use a reduction method where a given problem is translated in another one like SAT or ASP. This paper follows this line of research. It studies how to encode the problem of computing the extensions of an argumentation framework (under each of the previous semantics) as a constraint satisfaction problem (CSP). Such encoding is of great importance since it makes it possible to use the very efficient solvers (developed by the CSP community) for computing the extensions. Our encodings take advantage of existing reductions to SAT problems in the case of Dung’s abstract framework. Among the various ways of translating a SAT problem into a CSP one, we propose the most appropriate one in the argumentation context. We also provide encodings in case two other families of argumentation frameworks: the constrained version of Dung’s abstract framework and preference-based argumentation framework.     

Reasoning About Data Provided By Federated Deductive Databases

This paper focuses on the problem of reasoning with information provided by a group of databases which share a common set of rules (deductive rules, integrity constraints). Each database is assumed to be consistent with the rules, but federating them may lead to contradictions. This paper describes a logic of beliefs, based on KD logic, for reasoning with contradictory information provided by several databases. It also presents a theorem prover, associated with this logic. This prover, described as a meta-interpreter of PROLOG allows us to derive formulas of the form: given the databases and the rules, assuming an order of relative reliability between the databases, is a given formula deducible? or, what are the individuals which satisfy a given formula? When the set of rules is not recursive, we prove the correctness of this theorem-prover.     

Regaining cut admissibility in deduction modulo using abstract completion

Deduction modulo is a way to combine computation and deduction in proofs, by applying the inference rules of a deductive system (e.g. natural deduction or sequent calculus) modulo some congruence that we assume here to be presented by a set of rewrite rules. Using deduction modulo is equivalent to proving in a theory corresponding to the rewrite rules, and leads to proofs that are often shorter and more readable. However, cuts may be not admissible anymore.We define a new system, the unfolding sequent calculus, and prove its equivalence with the sequent calculus modulo, especially w.r.t. cut-free proofs. It permits to show that it is even undecidable to know if cuts can be eliminated in the sequent calculus modulo a given rewrite system.Then, to recover the cut admissibility, we propose a procedure to complete the rewrite system such that the sequent calculus modulo the resulting system admits cuts. This is done by generalizing the Knuth–Bendix completion in a non-trivial way, using the framework of abstract canonical systems.These results enlighten the entanglement between computation and deduction, and the power of abstract completion procedures. They also provide an effective way to obtain systems admitting cuts, therefore extending the applicability of deduction modulo in automated theorem proving.     

Karnaugh map analysis and synthesis of threshold functions

A unate function can easily be identified on a Karnaugh map from the well-known property that it consists only of essential prime implicants which intersect at a common implicant. The additional property that the plot of a unate function F(x₁ ?x_n ) on a Karnaugh map should possess in order that F may also be 1-realizable (n≤6) has been found. It has been shown that the 1-realizability of a unate function F corresponds to the ‘ compactness ’ of the plot of F. No resort to the inequalities is made, and no pre-processing such as positivizing and ordering of the given function is required.     

Complexity of evolution in maximum cooperative P systems

We introduce a variant of P systems called maximum cooperative P systems; it consists of transition P systems with cooperative rules that evolve at each step by consuming the maximum number of objects. The problem of distributing objects to rules in order to achieve a maximum consuming evolution is studied by introducing the resource mapping problem. The decision version of this optimization problem is proved to be NP-complete. We describe a new simulation technique for the evolution of the maximum cooperative P systems based on integer linear programming. Finally we illustrate the evolution by an example.     

Perturbing Bézier coefficients for best constrained degree reduction in the L2-norm

This paper first shows how the Bézier coefficients of a given degree n polynomial are perturbed so that it can be reduced to a degree m (<n) polynomial with the constraint that continuity of a prescribed order is preserved at the two endpoints. The perturbation vector, which consists of the perturbation coefficients, is determined by minimizing a weighted Euclidean norm. The optimal degree n−1 approximation polynomial is explicitly given in Bézier form. Next the paper proves that the problem of finding a best L₂-approximation over the interval [0,1] for constrained degree reduction is equivalent to that of finding a minimum perturbation vector in a certain weighted Euclidean norm. The relevant weights are derived. This result is applied to computing the optimal constrained degree reduction of parametric Bézier curves in the L₂-norm.     

Rule acquisition and attribute reduction in real decision formal contexts

Formal Concept Analysis of real set formal contexts is a generalization of classical formal contexts. By dividing the attributes into condition attributes and decision attributes, the notion of real decision formal contexts is introduced. Based on an implication mapping, problems of rule acquisition and attribute reduction of real decision formal contexts are examined. The extraction of “if–then” rules from the real decision formal contexts, and the approach to attribute reduction of the real decision formal contexts are discussed. By the proposed approach, attributes which are non-essential to the maximal s rules or l rules (to be defined later in the text) can be removed. Furthermore, discernibility matrices and discernibility functions for computing the attribute reducts of the real decision formal contexts are constructed to determine all attribute reducts of the real set formal contexts without affecting the results of the acquired maximal s rules or l rules.     

Complexity of computing with extended propositional logic programs

In this paper we introduce the notion of anF-program, whereF is a collection of formulas. We then study the complexity of computing withF-programs.F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) ofF-programs are built of formulas fromF. In particular, formulas other than atoms are allowed as building blocks ofF-program rules. Typical examples ofF are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case ofF-programs. The resulting notions are called in this paperminimal andstable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.This work was partially supported by National Science Foundation under grant IRI-9012902.This work was partially supported by National Science Foundation under grant CCR-9110721.