Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

A parametric approach to deductive databases with uncertainty

Numerous frameworks have been proposed in recent years for deductive databases with uncertainty. On the basis of how uncertainty is associated with the facts and rules in a program, we classify these frameworks into implication-based (IB) and annotation-based (AB) frameworks. We take the IB approach and propose a generic framework, called the parametric framework, as a unifying umbrella for IB frameworks. We develop the declarative, fixpoint, and proof-theoretic semantics of programs in our framework and show their equivalence. Using the framework as a basis, we then study the query optimization problem of containment of conjunctive queries in this framework and establish necessary and sufficient conditions for containment for several classes of parametric conjunctive queries. Our results yield tools for use in the query optimization for large classes of query programs in IB deductive databases with uncertainty     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

The power of inequality semijoins

Semijoin is a relational operator used in many relational query processing algorithms. Semijoins can be used to “reduce” the database by delimitting portions of the database that contain data relevant to a given query. For some queries, there exist sequences of semijoins that delimit the exact portions of the database needed to answer the query. Such sequences are called full reducers.

This paper considers a class of queries called natural inequality queries (NI queries), and characterizes a subclass for which full reducers exist. We also present an efficient algorithm that decides whether an NI query lies within this subclass, and constructs a full reducer for the query. The NI queries are a subset of the aggregate-free, conjunctive queries of QUEL, and permit join clauses to include <, , =, , >.     

On querying simple conceptual graphs with negation

We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query.

This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

A general procedure to check conjunctive query containment

In this paper, we present a general procedure to test conjunctive query containment. We divide the containment problem into four categories, taking into account the underlying semantics (set or bag theoretic) and the presence or absence of built-in predicates in the queries. After a brief review of previous work on conjunctive query containment, we present a new procedure, called QCC (Query Containment Checker), which we show to be a general and uniform procedure to check the containment among conjunctive queries under the four categories mentioned above. We briefly describe the use of QCC to check bag containment of conjunctive queries, and explain in detail how to use QCC to check set containment of conjunctive queries with built-in predicates. In our conclusions, we point out some uses of QCC for other types of containment. Received: 21 January 2000 / 19 November 2001     

A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

Decidable containment of recursive queries

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.     

Learning counting functions with queries

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Z_qⁿ (or Zⁿ) for any given integer q 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Z_p. In general, a counting function may have a composite modulus. We prove that, for any given integer q 2, over the domain Z₂ⁿ, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(n^q) membership queries.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

On the finite controllability of conjunctive query answering in databases under open-world assumption

In this paper we study queries over relational databases with integrity constraints (ICs). The main problem we analyze is OWA query answering, i.e., query answering over a database with ICs under open-world assumption. The kinds of ICs that we consider are inclusion dependencies and functional dependencies, in particular key dependencies; the query languages we consider are conjunctive queries and unions of conjunctive queries. We present results about the decidability of OWA query answering under ICs. In particular, we study OWA query answering both over finite databases and over unrestricted databases, and identify the cases in which such a problem is finitely controllable, i.e., when OWA query answering over finite databases coincides with OWA query answering over unrestricted databases. Moreover, we are able to easily turn the above results into new results about implication of ICs and query containment under ICs, due to the deep relationship between OWA query answering and these two classical problems in database theory. In particular, we close two long-standing open problems in query containment, since we prove finite controllability of containment of conjunctive queries both under arbitrary inclusion dependencies and under key and foreign key dependencies. The results of our investigation are very relevant in many research areas which have recently dealt with databases under an incomplete information assumption: e.g., data integration, data exchange, view-based information access, ontology-based information systems, and peer data management systems.