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.     

Uncertain deductive databases: A hybrid approach

Uncertainty in deductive databases and logic programming has been modeled using a variety of (numeric and non-numeric) formalisms in the past, including probabilistic, possibilistic, and fuzzy set-theoretic approaches, and many valued logic programming. In this paper, we consider a hybrid approach to the modeling of uncertainty in deductive databases. Our model, called deductive IST (DIST) is based on an extension of the Information Source Tracking (IST) model, recently proposed for relational databases. The DIST model permits uncertainty to be modeled and manipulated in essentially qualitative terms with an option to convert qualitative expressions of uncertainty into numeric form (e.g., probabilities). An uncertain deductive database is modeled as a Horn clause program in the DIST framework, where each fact and rule is annotated with an expression indicating the “sources” contributing to this information and their nature of contribution. (1) We show that positive DIST programs enjoy the least model/least fixpoint semantics analogous to classical logic programs. (2) We show that top-down (e.g., SLD-resolution) and bottom-up (e.g., magic sets rewriting followed by semi-naive evaluation) query processing strategies developed for datalog can be easily extended to DIST programs. (3) Results and techniques for handling negation as failure in classical logic programming can be easily extended to DIST. As an illustration of this, we show how stratified negation can be so extended. We next study the problem of query optimization in such databases and establish the following results. (4) We formulate query containment in qualitative as well as quantitative terms. Intuitively, our qualitative sense of containment would say a query Q₁ is contained in a query Q₂ provided for every input database D, for every tuple t, t ε Q₂(D) holds in every “situation” in which t ε Q₁(D) is true. The quantitative notion of containment would say Q₁ is contained in Q₂ provided on every input, the certainty associated with any tuple computed by Q₁ is no more than the certainty associated with the same tuple by Q₂ on the given input. We also prove that qualitative and quantitative notions of containment (both absolute and uniform versions) coincide. (5) We establish necessary and sufficient conditions for the qualitative containment of conjunctive queries. (6) We extend the well-known chase technique to develop a test for uniform containment and equivalence of positive DIST programs. (7) Finally, we prove that the complexity of testing containment of conjunctive DIST queries remains the same as in the classical case when number of information sources is regarded as a constant (so, it's NP-complete in the size of the queries). We also show that testing containment of conjunctive queries is co-NP-complete in the number of information sources.     

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₀).     

A comment on “L∞ optimal control of SISO continuous-time systems”

The paper “L_∞ optimal control of SISO continuous-time systems” by Wang and Sznaier (Wang & Sznaier (1997). Automatica, 33 (1), 85–90) studies the problem of designing a controller that optimally minimizes the peak absolute value of system output, due to a fixed input signal. With a newly defined function space A_∞, it was claimed that the set of all L_∞-bounded outputs could be parameterized and that the problem could be transformed to a minimal distance problem on L_∞ space. We believe, however, their formulation has essential flaws.     

Characterization of some gain conditions via the Hamilton-Jacobi inequality

This paper gives a characterization of three gain conditions, i.e., L_2∞ gain, L_2∞ gain subject to an L₂ gain constraint, and the Hankel gain, of nonlinear systems via the Hamilton-Jacobi inequalities. It is shown that the obtained results for the L_2∞ gain and the Hankel gain are analog to that derived for the L₂ gain so far.     

McClellan transformation and the construction of biorthogonal wavelet bases of LR

Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω₁,ω₂) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L²(R²). Finally, the construction method is illustrated by means of numerical examples.     

Micromachined sol–gel carbon nanotube/SnO2 nanocomposite hydrogen sensor

A novel micromachined single wall carbon nanotube (SWCNT) reinforced nanocrystalline tin dioxide gas sensor has been developed. The presence of SWCNT in SnO₂ matrix was realized by a spin-on sol–gel process. The SWCNT/SnO₂ sensor's sensitivity for hydrogen detection has greatly increased by a factor of three, in comparison to that of pure SnO₂ sensor. The novel sensor also lowers the working temperature, response time and recovery time. The greatly improved performances are mainly attributed to the effective gas accessing nano passes through SWCNT plus the smaller distance between adjacent gas accessing boundaries formed by the distribution of tiny SWCNTs. Therefore, both the spatial requirement (D ≤ 2L, D is the distance between adjacent gas accessing boundaries and L is the space charge layer thickness) and surficial requirement (adequate gas activation area) are met and the maximum inherent sensitivity of SnO₂ is achieved.     

First-order spectra with one binary predicate

The spectrum, Sp(), of a sentence is the set of cardinalities of finite structures which satisfy . We prove that any set of integers which is in Func₁^∞, i.e. in the class of spectra of first-order sentences of type containing only unary function symbols, is also in BIN¹, i.e. in the class of spectra of first-order sentences of type involving only a single binary relation.

We give similar results for generalized spectra and some corollaries: in particular, from the fact that the large complexity class _cNTIME_RAM(cn) is included in Func₁^∞ for unary languages (n denotes the input integer), we deduce that the set of primes and many “natural” sets belong to BIN¹.

We also give some consequences for the image of spectra under polynomials of .     

基于Hadoop平台的并行DHP数据分析方法

由候选项集C₂生成频繁2-项集L₂是关联规则Apriori算法的一个瓶颈。直接哈希修剪（DHP）算法利用一个生成的Hash表H₂删减C₂中无用的候选项集,以此提高L₂的生成效率。但传统DHP算法是一个串行算法,不能有效处理较大规模数据。针对这一问题,提出DHP的并行化算法——H_DHP。首先,对DHP算法并行化策略的可行性进行了理论分析与证明;其次,基于Hadoop平台,把Hash表H₂的生成以及频繁项集L₁、L₃~L_k的生成方法进行了并行实现,并借助Hbase数据库生成关联规则。仿真实验结果表明：与传统DHP算法相比,H_DHP算法在数据的处理时间效率、处理数据集的规模大小,以及加速比和可扩展性等方面都有较好的性能。     

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.     

A small gain theorem for linear stochastic systems

A well-known result in linear control theory is the so-called “small gain” theorem stating that if given two plants with transfer matrix functions T₁ and T₂ in H^∞ such that T₁ < γ and T₂ < 1/γ, when coupling T₂ to T₁ such that u₂ = y₁ and u₁ = y₂ one obtains an internally stable closed system. The aim of the present paper is to describe a corresponding result for stochastic systems with state-dependent white noise.     

Independence results about context-free languages and lower bounds

We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive representation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the ‘opaqueness’ of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a nonregular context-free language L₀ such that for no cf-grammar G, L(G) = L₀, it is provable in F that “L(G) is not regular”. We also show, among other results about P and NP, that there exists a recursive oracle A such that NP^A ≠ P^A, and that this fact is not provable in F for any recursive representation of A.

The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (p-isomorphisms) of NP-complete sets. We show that for every NP-complete set, L, there is a representation of L by a nondeterministic polynomial time machine for which we can prove that L is NP-complete. Furthermore, if L is p-isomorphic to SAT, then this is also provable in F for some representation of L. On the other hand, if there exist NP-complete sets not p-isomorphic to SAT, then there exists an NP-complete set L for which, independent of its representation, there is no proof in F that L is or is not p-isomorphic to SAT.     

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.     

Self-embedded context-free grammars with regular counterparts

In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as and , that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain.Received: 17 January 2003, Published online: 17 February 2004Stefan Andrei: stefan@infoiasi.ro     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

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.     

Computations of model narrow nanotubes closed by fragments of smaller fullerenes and quasi-fullerenes

New type of carbon nanotubes—narrow nanotubes—has recently been observed with diameters of 4–5 Å. It has been postulated that the narrow nanotubes are closed by fullerene fragments of C₂₀ and C₃₆. This paper presents computational results on related model nanotubes with stoichiometries such as C₈₀, C₈₄, C₉₆, C₁₀₈, or C₁₂₀. The computations were carried out at the PM3, AM1, SAM1, HF/3-21G, HF/4-31G, and B3LYP/6-31G^* levels. Two C₃₆ fullerenes were considered, D_6h and D_2d. At the PM3 level and with the C₈₄ nanotube stoichiometry, the D_2d cage closure gave a lower energy (by 185 kcal/mol and a diameter of 5.42 Å). There is another possible candidate, a C₃₂ cage with D_4d symmetry (two four-membered rings). At the PM3 level and with the C₉₆ nanotube stoichiometry, the D_4d closure (with a diameter of 5.43 Å) had energy lower by 210 kcal/mol than that of the D_6h nanotube closure. On the other hand, four-membered rings should not play a significant role for narrow nanotubes with a diameter of 4 Å, where the dodecahedron-related closure should be exclusive. Still narrower nanotubes are briefly discussed.     

THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context-free grammars, multiple context-free grammars, and their subclasses are discussed.