Vectorial MV-algebras

 In this paper we introduce the concepts of vectorial MV-algebra, vectorial complete MV-algebra, modulus of continuity and continuous function with values in a vectorial complete MV-algebra. The main result of this paper is a Weierstrass type approximation theorem for functions taking values on vectorial complete MV-algebras. As examples, we construct such a structure on the RGB model (this represents the colours model of a pixel on the screen) and on the space of fuzzy subsets of a set. 2000 Mathematics Subject Classification 06D35; 06B23; 41A10 Current address: Armatei Romane 5, 3700 Oradea, Romania e-mail address: dnoje@uoradea.ro     

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols

We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ɛ∈ (0,1) , runs in time polynomial in n| \cal F |/ɛ and produces a \pm 1 -matrix M with n columns and m=O(log | \cal F |/ɛ ² ) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n -vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ɛ)/2 and (1+ɛ)/2 . In the case that \cal F is the set of all subsets of size at most k , k constant, this gives a polynomial time construction for a k -wise ɛ -biased sample space of size O(log n/ɛ ² ) , compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/ɛ ⁴ ) and O(log ² n/ɛ ² ) . The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files. Received October 30, 1997; revised September 17, 1999, and April 17, 2000.     

Ideals and quotients in lattice ordered effect algebras

 We show that a quotient of a lattice ordered effect algebra L with respect to a Riesz ideal I is linearly ordered if and only if I is a prime ideal, and the quotient is an MV-algebra if and only if I is an intersection of prime ideals. A generalization of the commutators in OMLs is defined in the frame of lattice ordered effect algebras, such that the quotient with respect to a Riesz ideal I is an MV-algebra if and only if I contains all generalized commutators. If L is an OML, generalized commutators coincide with the usual Marsden commutators.     

Convergence with a fixed regulator in lattice ordered groups and applications to MV-algebras

A convergence with a fixed regulator v in lattice ordered groups is applied to MV-algebras. For each Archimedean MV-algebra A there exists a v-Cauchy completion A ^* and it is uniquely determined up to isomorphisms over A. The relation between the Dedekind completion A ^∧ of A and A ^* is established. There is solved a question of the existence of the greatest v-Cauchy complete ideal of A.     

A note on overshoot estimation in pole placements

In this note we show that for a given controllable pair (A, B) and any λ>0, a gain matrix K can be chosen so that the transition matrix e~((A+BK)t) of the system =(A+BK)x decays at the exponential rate e~(-λt) and the overshoot of the transition matrix can be bounded by Mλ~L for some constants M and L that are independent of λ. As a consequence, for any h>0, a gain matrix K can be chosen so that the magnitude of the transition matrix e~((A+BK)t) can be reduced by1/2 (or by any given portion) over [0, h]. An interesting application of the result is in the stabilization of switched linear systems with any given switching rate (see [1]).     

State BL-algebras

The concept of a state MV-algebra was firstly introduced by Flaminio and Montagna (An algebraic approach to states on MV-algebras. In: Novák V (ed) Fuzzy logic 2, proceedings of the 5th EUSFLAT conference, September 11–14, Ostrava, vol II, pp 201–206, 2007; Int J Approx Reason 50:138–152, 2009) as an MV-algebra with internal state as a unary operation. Di Nola and Dvurečenskij (Ann Pure Appl Logic 161:161–173, 2009a; Math Slovaca 59:517–534, 2009b) gave a stronger version of a state MV-algebra. In the present paper, we introduce the notion of a state BL-algebra, or more precisely, a BL-algebra with internal state. We present different types of state BL-algebras, like strong state BL-algebras and state-morphism BL-algebras, and we study some classes of state BL-algebras. In addition, we give a sample of important examples of state BL-algebras and present some open problems.     

An Eulerian approach to transport and diffusion on evolving implicit surfaces

In this article we define a level set method for a scalar conservation law with a diffusive flux on an evolving hypersurface Γ(t) contained in a domain W ì \mathbb Rⁿ⁺¹{\Omega \subset \mathbb R^{n+1}} . The partial differential equation is solved on all level set surfaces of a prescribed time dependent function Φ whose zero level set is Γ(t). The key idea lies in formulating an appropriate weak form of the conservation law with respect to time and space. A major advantage of this approach is that it avoids the numerical evaluation of curvature. The resulting equation is then solved in one dimension higher but can be solved on a fixed grid. In particular we formulate an Eulerian transport and diffusion equation on evolving implicit surfaces. Using Eulerian surface gradients to define weak forms of elliptic operators naturally generates weak formulations of elliptic and parabolic equations. The finite element method is applied to the weak form of the conservation equation yielding an Eulerian Evolving Surface Finite Element Method. The computation of the mass and element stiffness matrices, depending only on the gradient of the level set function, are simple and straightforward. Numerical experiments are described which indicate the power of the method. We describe how this framework may be employed in applications.     

The individual ergodic theorem on the IF-events with product

The ergodic theory and particularly the individual ergodic theorem were studied in many structures. Recently the individual ergodic theorem has been proved for MV-algebras of fuzzy sets (Riečan in Czech Math J 50(125):673–680, 2000; Riečan and Neubrunn in Integral, measure, and ordering. Kluwer, Dordrecht, 1997) and even in general MV-algebras (Jurečková in Int J Theor Phys 39:757–764, 2000). The notion of almost everywhere equality of observables was introduced by Riečan and Jurečková (Int J Theor Phys 44:1587–1597, 2005). They proved that the limit of Cesaro means is an invariant observable for P-observables. In Lendelová (Int J Theor Phys 45(5):915–923, 2006c) showed that the assumption of P-observable can be omitted. In this paper we prove the individual ergodic theorem on family of IF-events and show that each P {\mathcal{P}} -preserving transformation in this family can be expressed by two corresponding P^\flat,P^\sharp {\mathcal{P}}^\flat,{\mathcal{P}}^\sharp -preserving transformations in tribe T. {\mathcal{T}}.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

On covering problems of codes

LetC be a binary code of lengthn (i.e., a subset of {0, 1} ⁿ ). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1} ⁿ is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete. This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1} ⁿ ,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem. A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v ₁ v ₂ …v _2n ) | ∀i:v _2i =v _2i−1}. We show that there is a setY ⊂ {0, 1}²ⁿ such that for everyv ε {0, 1}²ⁿ :v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn.     

Geometric Restrictions on Producible Polygonal Protein Chains

Fixed-angle polygonal chains in three dimensions serve as an interesting model of protein backbones. Here we consider such chains produced inside a "machine" modeled crudely as a cone, and examine the constraints this model places on the producible chains. We call this notion producible, and prove as our main result that a chain whose maximum turn angle is α is producible in a cone of half-angle ≥ α if and only if the chain is flattenable, that is, the chain can be reconfigured without self-intersection to lie flat in a plane. This result establishes that two seemingly disparate classes of chains are in fact identical. Along the way, we discover that all producible configurations of a chain can be moved to a canonical configuration resembling a helix. One consequence is an algorithm that reconfigures between any two flat states of a "nonacute chain" in O(n) "moves," improving the O(n²)-move algorithm in [ADD+]. Finally, we prove that the producible chains are rare in the following technical sense. A random chain of n links is defined by drawing the lengths and angles from any "regular" (e.g., uniform) distribution on any subset of the possible values. A random configuration of a chain embeds into ℝ³ by in addition drawing the dihedral angles from any regular distribution. If a class of chains has a locked configuration (and no nontrivial class is known to avoid locked configurations), then the probability that a random configuration of a random chain is producible approaches zero geometrically as n → ∞.     

Weakly distributive domains(Ⅱ)

In our previous work (Inform. and Comput., 2005, 202: 87–103), we have shown that for any ω-algebraic meet-cpo D, if all higher-order stable function spaces built from D are ω-algebraic, then D is finitary. This accomplishes the first of a possible, two-step process in solving the problem raised (LNCS, 1991, 530: 16–33; Domains and lambda-calculi, Cambridge Univ. Press, 1998) whether the category of stable bifinite domains of Amadio-Droste-G?bel (LNCS, 1991, 530: 16–33; Theor. Comput. Sci., 1993, 111: 89–101) is the largest cartesian closed full subcategory within the category of ω-algebraic meet-cpos with stable functions. This paper presents the results of the second step, which is to show that for any ω-algebraic meet-cpo D satisfying axioms M and I to be contained in a cartesian closed full sub-category using ω-algebraic meet-cpos with stable functions, it must not violate MI^∞. We introduce a new class of domains called weakly distributive domains and show that for these domains to be in a cartesian closed category using ω-algebraic meet-cpos, property MI^∞ must not be violated. Further, we demonstrate that principally distributive domains (those for which each principle ideal is distributive) form a proper subclass of weakly distributive domains, and Birkhoff’s M ₃ and N ₅ (Introduction to Lattices and order, Cambridge Univ. Press, 2002) are weakly distributive (but non-distributive). Then, we establish characterization results for weakly distributive domains. We also introduce the notion of meet-generators in constructing stable functions and show that if an ω-algebraic meet-cpo D contains an infinite number of meet-generators, then [D → D] fails I. However, the original problem of Amadio and Curien remains open.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

The Quantum Complexity of Set Membership

   Abstract. We study the quantum complexity of the static set membership problem: given a subset S (|S| ≤ n ) of a universe of size m ( >> n ), store it as a table, T: {0,1} ^r --> {0,1} , of bits so that queries of the form ``Is x in S ?' can be answered. The goal is to use a small table and yet answer queries using few bit probes. This problem was considered recently by Buhrman et al. [BMRV], who showed lower and upper bounds for this problem in the classical deterministic and randomized models. In this paper we formulate this problem in the ``quantum bit probe model'. We assume that access to the table T is provided by means of a black box (oracle) unitary transform O _T that takes the basis state | y,b > to the basis state | y,b

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power s ^α for some constant α>1. For processes that may have side effects or that are not checkpointable, we show an W(m^(a-1)/a2)\Omega(m^{(\alpha -1)/\alpha^{2}}) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log ^1/α m) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects.     

Learning two-tape automata from queries and counterexamples

We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of ∑*, a 2-tape DFA over an alphabet ∑ accepts a subset of ∑* × ∑*, and therefore, it can specify a binary relation on ∑*. In [3] Angluin showed that the class of deterministic finite automata (DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from a minimally adequate teacher (MAT). In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any languageL accepted by an unknown 2-tape DFAM, learns from MAT a two-tape nonde-terministic finite automaton (2-tape NFA)M′ acceptingL in time polynomial inn andl, wheren is the size ofM andl is the maximum length of any counterexample provided during the learning process. This work was supported in part by Grants-in-Aid for Scientific Research No. 04229105 from the Ministry of Education, Science, and Culture, Japan.     

Design of exponential observers for nonlinear systems by embedding

For nonlinear systems in ?ⁿ which are observable but not uniformly, we study how to design explicitly exponential observers, after having the system immersed in ?^m with m>n. The central issue concerns the determination of a lipschitzian extension in ?^m of the dynamics, which is defined exclusively on a subset of empty interior. We propose some constructive tools and illustrate their utility on a biological example. Copyright © 2004 John Wiley & Sons, Ltd.     

Smallest Enclosing Cylinders

This paper addresses the complexity of computing the smallest-radius infinite cylinder that encloses an input set of n points in 3-space. We show that the problem can be solved in time O(n ⁴ log ^O(1) n) in an algebraic complexity model. We also achieve a time of O(n ⁴ L⋅μ(L)) in a bit complexity model where L is the maximum bit size of input numbers and μ(L) is the complexity of multiplying two L bit integers. These and several other results highlight a general linearization technique which transforms nonlinear problems into some higher-dimensional but linear problems. The technique is reminiscent of the use of Plücker coordinates, and is used here in conjunction with Megiddo's parametric searching. We further report on experimental work comparing the practicality of an exact with that of a numerical strategy. Received September 10, 1997; revised August 28, 1988.