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.     

t-norms induced by metrics on Boolean algebras

Let d _ν be the metric associated with a strictly positive submeasure ν on some Boolean algebra . If d _ν is bounded from above by 1, E _ν=1−d _ν is a (fuzzy) similarity relation on at least w.r.t. the Lstrok ukasiewicz t-norm, but possibly also w.r.t. numerous further t-norms.In this paper, we show that under certain assumptions on and ν, we may associate with ν in a natural way a continuous t-norm w.r.t. which E _ν is a similarity relation and which, in a certain sense, is the weakest such t-norm. Up to isomorphism, every continuous t-norm arises in this way     

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     

A Novel Class of Symmetric and Nonsymmetric Periodizing Variable Transformations for Numerical Integration

Variable transformations for numerical integration have been used for improving the accuracy of the trapezoidal rule. Specifically, one first transforms the integral via a variable transformation that maps [0,1] to itself, and then approximates the resulting transformed integral by the trapezoidal rule. In this work, we propose a new class of symmetric and nonsymmetric variable transformations which we denote , where r and s are positive scalars assigned by the user. A simple representative of this class is . We show that, in case , or but has algebraic (endpoint) singularities at x = 0 and/or x = 1, the trapezoidal rule on the transformed integral produces exceptionally high accuracies for special values of r and s. In particular, when and we employ , the error in the approximation is (i) O(h ^r ) for arbitrary r and (ii) O(h ^2r ) if r is a positive odd integer at least 3, h being the integration step. We illustrate the use of these transformations and the accompanying theory with numerical examples.      

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.     

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.     

On the computability power and the robustness of set agreement-oriented failure detector classes

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is Ω. This paper considers failure detector classes from the literature that solve k-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes (1 ≤ x ≤ n), and (0 ≤ y ≤ n), can be “added” to provide a failure detector of the class Ω ^z (1 ≤ z ≤ n, a generalization of Ω). It also characterizes the power of such an “addition”, namely, , can construct Ω ^z iff y + z > t, and can construct Ω ^z iff x + z > t + 1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while allows solving 2-set agreement (but not consensus) and allows solving t-set agreement (but not (t − 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes , and Ω ^z , and shows which reductions among these classes are possible and which are not. The paper also presents a message-passing Ω ^k -based k-set agreement protocol and shows that Ω ^k is not enough to solve (k − 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the k-set agreement problem. An extended abstract of this paper has appeared in the proceedings of PODC 2006 [20]. This work has been supported partially by a grant from LAFMI (Franco-Mexican Lab in Computer Science), the European Network of Excellence ReSIST and PAPIIT-UNAM.     

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.     

Generalized fuzzy filters of <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript>-algebras

In this paper, we introduce the notions of interval valued -fuzzy filters and interval valued -fuzzy Boolean (implicative) filters in R ₀-algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that an interval valued fuzzy set F in R ₀-algebras is an interval valued -fuzzy Boolean filter if and only if it is an interval valued -fuzzy implicative filter.     

Strong Completeness and Limited Canonicity for PDL

Propositional dynamic logic () is complete but not compact. As a consequence, strong completeness (the property ) requires an infinitary proof system. In this paper, we present a short proof for strong completeness of relative to an infinitary proof system containing the rule from [α; β ⁿ ]φ for all , conclude . The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. Also, we show that the universal canonical model of lacks the property of modal harmony, the analogue of the Truth lemma for modal operators.     

On very true operators on pocrims

Hájek introduced the logic enriching the logic BL by a unary connective vt which is a formalization of Zadeh’s fuzzy truth value “very true”. algebras, i.e., BL-algebras with unary operations, called vt-operators, which are among others subdiagonal, are an algebraic counterpart of Partially ordered commutative integral residuated monoids (pocrims) are common generalizations of both BL-algebras and Heyting algebras. The aim of our paper is to introduce and study algebraic properties of pocrims endowed by “very-true” and “very-false”-like operators. Research is supported by the Research and Development Council of Czech Government via project MSN 6198959214.     

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.     

Improved Bounds on Quantum Learning Algorithms

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.

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 ƒ.