Efficient Solution of A, x ( k )?= b ( k ) Using A ?1

In this work, we consider the problem of solving , , where b ^(k+1) = f(x ^(k)). We show that when A is a full matrix and , where depends on the specific software and hardware setup, it is faster to solve for by explicitly evaluating the inverse matrix A ⁻¹ rather than through the LU decomposition of A. We also show that the forward error is comparable in both methods, regardless of the condition number of A.     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence     

Population Variance under Interval Uncertainty: A New Algorithm

In statistical analysis of measurement results, it is often beneficial to compute the range V of the population variance when we only know the intervals of possible values of the x_i. In general, this problem is NP-hard; a polynomialtime algorithm is known for the case when the measurements are sufficiently accurate, i.e., when for all In this paper, we show that we can efficiently compute V under a weaker (and more general) condition .     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

Translational lemmas for DLOGTIME-uniform circuits,alternating TMs,and PRAMs

We present translational lemmas for the three standard models of parallel computation, and apply them to obtain tight hierarchy results. It is shown that, for arbitrarily small rational constant , (i) there is a language which can be accepted by a -uniform circuit family of depth and size but not by any -uniform circuit family of depth and size , (ii) there is a language which can be accepted by a -time -space ATM with l worktapes but not by any -time -space ATM with the same l worktapes if the number of tape symbols is fixed, and (iii) there is a language which can be accepted by a -time PRAM with processors but not by any -time PRAM with processors. Here, c > 0, d ≥ 1, r ₁ > 1, and r ₂ ≥ 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. Preliminary versions of different parts of this paper appeared in Proc. MCU 2004 (LNCS 3354) and Proc. FCT 2005 (LNCS 3623).     

Simple a posteriori error estimators for the <Emphasis Type="Italic">h</Emphasis>-version of the boundary element method

The h-h/2-strategy is one well-known technique for the a posteriori error estimation for Galerkin discretizations of energy minimization problems. One considers to estimate the error , where is a Galerkin solution with respect to a mesh and is a Galerkin solution with respect to the mesh obtained from a uniform refinement of . This error estimator is always efficient and observed to be also reliable in practice. However, for boundary element methods, the energy norm is non-local and thus the error estimator η does not provide information for a local mesh-refinement. We consider Symm’s integral equation of the first kind, where the energy space is the negative-order Sobolev space . Recent localization techniques allow to replace the energy norm in this case by some weighted L ²-norm. Then, this very basic error estimation strategy is also applicable to steer an h-adaptive algorithm. Numerical experiments in 2D and 3D show that the proposed method works well in practice. A short conclusion is concerned with other integral equations, e.g., the hypersingular case with energy space and , respectively, or a transmission problem. Dedicated to Professor Ernst P. Stephan on the occasion of his 60th birthday.     

A new bound for the D0L sequence equivalence problem

The D0L sequence equivalence problem consists of deciding, given two morphisms , and a word , whether or not g ⁱ (w) = h ⁱ (w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence equivalence problem, it suffices to consider the terms of the sequences with , where n is the cardinality of X.     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

The complexity of constructing pseudorandom generators from hard functions

We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant such that every circuit of size fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function (i.e. there is a constant such that every circuit of size fails to compute f on some input) for every positive constant there is no black-box construction of a computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes.     

Classifications of Dense Languages

Let X be a finite alphabet containing more than one letter. A dense language over X is a language containing a disjunctive language. A language L is an n-dense language if for any distinct n words there exist two words such that In this paper we classify dense languages into strict n-dense languages and study some of their algebraic properties. We show that for each n ≥ 0, the n-dense language exists. For an n-dense language L, n ≠ 1, the language L ∩ Q is a dense language, where Q is the set of all primitive words over X. Moreover, for a given n ≥ 1, the language L is such that , then for some m, n ≤ m ≤ 2n + 1. Characterizations on 0-dense languages and n-dense languages are obtained. It is true that for any dense language L, there exist such that for some. We show that everyn-dense language, n ≥ 0, can be split into disjoint union of infinitely many n-dense languages.     

Topology on the set of R 0 semantics for R 0 algebras

This paper introduces the concepts of R ₀ valuation, R ₀ semantic, countable R ₀ category , R ₀ fuzzy topological category , etc. It is established in a natural way that the fuzzy topology δ and its cut topology on the set Ω _M consisting of all R ₀ valuations of an R ₀ algebra M, and some properties of fuzzy topology δ and its cut topology are investigated carefully. Moreover, the representation theorem for R ₀ algebras by means of fuzzy topology is given, that is to say the category is equivalent to the category . By studying the relation between valuations and filters, the Loomis–Sikorski theorem for R ₀ algebras is obtained. As an application, K-compactness of the R ₀ logic is discussed.     

Free algebras in varieties of Stonean residuated lattices

Given a variety of bounded residuated lattices satisfying the Stone identity , the free algebras in over a set X of cardinality |X| are represented as weak Boolean products over the Cantor space 2^|X| of a family of free algebras in an associated variety of (not necessarily bounded) residuated lattices with a bottom added.     

Strong non-standard completeness for fuzzy logics

In this paper we are going to introduce the notion of strong non-standard completeness (SNSC) for fuzzy logics. This notion naturally arises from the well known construction by ultraproduct. Roughly speaking, to say that a logic is strong non-standard complete means that, for any countable theory Γ over and any formula φ such that , there exists an evaluation e of -formulas into a -algebra such that the universe of is a non-Archimedean extension of the real unit interval [0,1], e is a model for Γ, but e(φ) < 1. Then we will apply SNSC to prove that various modal fuzzy logics allowing to deal with simple and conditional probability of infinite-valued events are complete with respect to classes of models defined starting from non-standard measures, that is measures taking value in .     

Computing Population Variance and Entropy under Interval Uncertainty: Linear-Time Algorithms

In statistical analysis of measurement results it is often necessary to compute the range of the population variance when we only know the intervals of possible values of the x _i . While can be computed efficiently, the problem of computing is, in general, NP-hard. In our previous paper “Population Variance under Interval Uncertainty: A New Algorithm” (Reliable Computing 12 (4) (2006), pp. 273–280) we showed that in a practically important case we can use constraints techniques to compute in time O(n · log(n)). In this paper we provide new algorithms that compute (in all cases) and (for the above case) in linear time O(n). Similar linear-time algorithms are described for computing the range of the entropy when we only know the intervals of possible values of probabilities p _i . In general, a statistical characteristic ƒ can be more complex so that even computing ƒ can take much longer than linear time. For such ƒ, the question is how to compute the range in as few calls to ƒ as possible. We show that for convex symmetric functions ƒ, we can compute in n calls to ƒ.     

Fuzzy logic models in a category of fuzzy relations

We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models . Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572.