The Relative Entropy of Entanglement of Schmidt Correlated States and Distillation

We show that a mixed state = _mna_mn|mn| can be realized by an ensemble of pure states {p_k, |_k} where . Employing this form, we discuss the relative entropy of entanglement of Schmidt correlated states. Also, we calculate the distillable entanglement of a class of mixed states. PACS: 03.67.-a; 03.65.Bz; 03.65.Ud     

Query answering via cooperative data inference

This paper proposes the use of accessible information (data/knowledge) to infer inaccessible data in a distributed database system. Inference rules are extracted from databases by means of knowledge discovery techniques. These rules can derive inaccessible data due to a site failure or network partition in a distributed system. Such query answering requires combining incomplete and partial information from multiple sources. The derived answer may be exact or approximate. Our inference process involves two phases to reason with reconstructed information. One phase involves using local rules to infer inaccessible data. A second phase involves merging information from different sites. We shall call such reasoning processes cooperative data inference. Since the derived answer may be incomplete, new algebraic tools are developed for supporting operations on incomplete information. A weak criterion called toleration is introduced for evaluating the inferred results. The conditions that assure the correctness of combining partial results, known as sound inference paths, are developed. A solution is presented for terminating an iterative reasoning process on derived data from multiple knowledge sources. The proposed approach has been implemented on a cooperative distributed database testbed, CoBase, at UCLA. The experimental results validate the feasibility of this proposed concept and can significantly improve the availability of distributed knowledge base/database systems.List of notation Mapping - --< Logical implication - = Symbolic equality - ==< Inference path - Satisfaction - Toleration - Undefined (does not exist) - Variable-null (may or may not exist) - ^* Subtuple relationship - ^* s-membership - s-containment - Open subtuple - Open s-membership - Open s-containment - _P Open base - P Program - I Interpretation - DIP Data inference program - t Tuples - R Relations - Ø Empty interpretation - Open s-union - Open s-interpretation - Set of mapping from the set of objects to the set of closed objects - W Set of attributes - _W Set of sound inference paths on the set of attributes W - Set of relational schemas in a DB that satisfy MVD - ⁺ Range closure of W wrt      

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Directional differentiation of marginal functions in mathematical programming problems

We consider regular mathematical programming problems of the form f(x, y) inf, y F(x), x Rⁿ, where F(x) = {y R^m h_i| (x, y) 0, , h_i (x, y) = 0, . The directional derivatives offunctions (x) = inf{f(x, y)|y F(x)} are estimated.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–77, November–December, 1991.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple (logn) algorithm for the distance transform with respect to theL ₁-metric, an (log² n) algorithm for the transform with respect to theL -metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time (log³ n).This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1-1, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Indecomposable local maps of tessellation automata

Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet containing two or more symbols and for anyn 1, there exist indecomposable scope-n local maps over . (2) If is a finite field of prime order, then a linear scope-n local map over is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen – 1 over , except for a trivial case. (3) Result (2) is no longer true if is a finite field whose order is not prime.     

A Modular Algorithm for Computing Cohomologies of Lie Algebras and Superalgebras

The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H ^k( _p) dimH ^k() between the dimensions of cohomologies over an arbitrary modular field _p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH ^k( _p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary _p and, then, carry out all required computations over in these subcomplexes.     

Exact Linear Thermodynamic Evolution Equations from the Robertson Formalism

A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short , is time-independent for t > if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t > . is the Liouville operator. So long as C(t) is such that decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport.     

Exact optimal grillage layouts — Part I: Combinations of free and simply supported edges

In the first instalment of this three-part study, a comprehensive treatment of analytically derived, exact optimal grillage layouts for combinations of simply supported and free edges is given. In part two, grillages with combinations of simply supported, clamped and free edges will be considered.Notation k constant in specific cost function - M beam bending moment - r radius of circular edge - R ⁺,R ^–,S ⁺,S ^–,T optimal regions - x, x _j coordinate along a beam (j) - slope of the adjoint deflection at pointD in directionDA - t, v coordinates along the free edge - adjoint deflection - angle between long beams and free edge - angle between free and simply supported edges - curvature of the adjoint deflection - , angles for layouts with circular edge - total weight (cost) of grillage - coordinate along a beam in anR ⁺ region - distance defined in Fig. 3     

Factorisation of finite state machines under strong and observational equivalences

The factorisation problem is to construct the specification of a submoduleX when the specifications of the system and all submodules butX are given. It is usually described by the equation where P and X are submodules of system Q, ¦ is a composition operator, and is the equivalence criterion. In this paper we use a finite state machine (FSM) model consistent with CCS and study two factorisation problems:P |||P Q andP |||P Q, where ||| is a derived CCS composition operator, and represent strong and observational equivalences. Algorithms are presented and proved correct to find the most general specification of submoduleX forP |||P Q withQ -deterministic and forP |||P Q withQ deterministic. Conditions on the submachines of the most general solutions that remain solutions toP |||P Q(P |||P Q) are given. This paper extends and is based on the work of M. W. Shields.     

Sets with small generalized Kolmogorov complexity

Summary We study the class of sets with small generalized Kolmogorov complexity. The following results are established: 1. A set has small generalized Kolmogorov complexity if and only if it is semi-isomorphic to a tally set. 2. The class of sets with small generalized Kolmogorov complexity is properly included in the class of self-p-printable sets. 3. The class of self-p-printable sets is properly included in the class of sets with selfproducible circuits. 4. A set S has self-producible circuits if and only if there is a tally set T such that P(T)=P(S). 5. If a set S has self-producible circuits, then NP(S)=NP _B(S), where NP _B( ) is the restriction of NP( ) studied by Book, Long, and Selman [4]. 6. If a set S is such that NP(S) =NP _B(S), then NP(S) P(SSAT).     

On a Stroboscopic Approach to Quantum Tomography of Qudits Governed by Gaussian Semigroups

In this paper, we discuss the minimal number of observables Q ₁, ..., Q , where expectation values at some time instants t ₁, ..., t _r determine the trajectory of a d-level quantum system (qudit) governed by the Gaussian semigroup . We assume that the macroscopic information about the system in question is given by the mean values E _j(Q _i) = tr(Q _i(t _j)) of n selfadjoint operators Q ₁, ..., Q _n at some time instants t ₁ < t ₂ < ... < t _r, where n < d ²– 1 and r deg (, ). Here (, ) stands for the minimal polynomial of the generator of the Gaussian flow (t).     

L 1 Sensitivity minimization for plants with commensurate delays

In this paper we consider the problem ofL ¹ sensitivity minimization for linear plants with commensurate input delays. We describe a procedure for computing the minimum performance, and we characterize optimal solutions. The computations involve solving a one-parameter family of finite-dimensional linear programs. Explicit solutions are presented for important special cases.Notation X ^* Dual space of a normed linear spaceX - All elements inS with norm 1 - S The annihilator subspace defined as . - S The annihilator subspace defined as . - BV(X) Functions of bounded variation onX - C ₀(X) Continuous function on a locally compact spaceX such that for all > 0, {x X¦ ¦f(x)¦s is compact - C ^N (a, b) Vectors of continuous functions on (a, b) The authors acknowledge support from the Army Research Office, Center for Intelligent Control, under grant DAAL03-86-K-0171, and the National Science Foundation, under grant 8810178-ECS.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

Decision procedures for elementary sublanguages of set theory

In this paper we prove the decidability of the class of unquantified formulae of set theory involving the operators , , , \, {·}, pred _< and the predicates =, , , Finite, where pred _<(s) denotes the collection of all sets having rank strictly less than the rank of s.This work generalizes and combines earlier results published in the same series of papers.This work has been partially supported by ENI and ENIDATA within the AXL project.     

Use of potential functions in 3D rendering of fractal images from complex functions

Computer graphics is important in developing fractal images visualizing the Mandelbrot and Julia sets from a complex function. Computer rendering is a central tool for obtaining nice fractal images. We render 3D objects with the height of each complex point of a fractal image considering the diverging speed of its orbit. A potential function helps approximate this speed. We propose a new method for estimating the normal vector at the surface points given by a potential function. We consider two families of functions that exhibit interesting fractal images in a bounded region: a power function,f _{, c}(z)=z +c, where is a real number, and the Newton form of an equation, where ¦¦=1 and >0.     

Records of turing machines

Suppose a Turing machine is equipped with an extra tape. At each step of a computation being performed, it prints symbol read move symbol symbol printed on a square of the extra tape. It then moves the extra tape one square to the left. This procedure yields arecord of the computation.If is a finite alphabet, let be the set of triples (a, b, c) wherea ,c , andb {–1, 0, 1}. We will characterize those sequences of symbols of that are records of computations of Turing machines.This research was supported in part by AFOSR Grant GP-68-1402.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define (P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy . HeresQ denotes a scaling ofQ by the factors, andQ,Q are some translates ofQ. This function gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.)For integerk 3, define (k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with (P, Q) (k). Among other results, we prove that 2.118 ... <-(3) 2.25 and (k) = 1 + (k ^–2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes (T, P) among triangles. However, in linear time we can find a trianglet with (t, P)<-2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.Work of all authors was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Rudolf Fleischer and Kurt Mehlhorn acknowledge also DFG (Grant SPP Me 620/6). Chee Yap acknowledges also DFG (Grant Be 142/46-1) and NSF (Grants DCR-84-01898 and CCR-87-03458). This research was performed when Günter Rote and Chee Yap were at the Freie Universität Berlin.     

Algorithmic properties of maximal orders in simple algebras over Q

This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if is isomorphic to a full matrix algebra over the ground field and the problem of deciding if is a skewfield both belong toN P co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields.     

Generating Boolean \mu-expressions

In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times , where E is the size ofE andn _m is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas [17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.