Unextendible Product Bases and Locally Unconvertible Bound Entangled States

Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states _S and _T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping _S into a probabilistic ensemble (p, ), the fidelity between _T and any possible final state satisfies F(_T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c.     

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)     

Shape optimization of elasto-plastic bodies under plane strains: Sensitivity analysis and numerical implementation

Optimal shape design problems for an elastic body made from physically nonlinear material are presented. Sensitivity analysis is done by differentiating the discrete equations of equilibrium. Numerical examples are included.Notation U ^ad set of admissible continuous design parameters - U _h ^ad set of admissible discrete design parameters - function fromU _h ^ad defining shape of body - _h function fromU _h ^ad defining approximated shape of body - vector of nodal values of _h - { _n} sequence of functions tending to - () domain defined by - K bulk modulus - shear modulus - penalty parameter for contact condition - V() space of virtual displacements in() - V _h(_h) finite element approximation ofV() - J cost functional - J _h discretized cost functional - J algebraic form ofJ _h - (u) stress tensor - e(u) strain tensor - K stiffness matrix - f force vector - b(q) term arising from nonlinear boundary conditions - q vector of nodal degrees of freedom - p vector of adjoint state variables - J Jacobian of isoparametric mapping - |J| determinant ofJ - N vector of shape function values on parent element - L matrix of shape function derivatives on parent element - G matrix of Cartesian derivatives of shape functions - X matrix of nodal coordinates of element - D matrix of elastic coefficients - B strain-displacement matrix - _P part of boundary where tractions are prescribed - _u part of boundary where displacements are prescribed - variable part of boundary - strain invariant     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

Diagrammatic Analysis of Interval Linear Equations - Part II: The Two-Dimensional Case and Generalization to n Dimensions

Using the results obtained for the one-dimensional case in Part I (Reliable Computing 9(1) (2003), pp. 1–20) of the paper, an analysis of the two-dimensional relational expression a ₁ x ₁ + a ₂ x ₂ b, where {, , , =}, is conducted with the help of a midpoint-radius diagram and other auxiliary diagrams. The solution sets are obtained with a simple boundary-line selection rule derived using these tools, and are characterized by types of one-dimensional cuts through the solution space. A classification of basic possible solution types is provided in detail. The generalization of the approach for n-dimensional interval systems and avenues for further research are also outlined.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

Adaptive meshing — saving computational costs during the optimization of composite structures

Structural optimization methods are widely used for determining optimum designs of composite structures. The high complexity of the problem and the large number of design variables, such as lamina thicknesses and ply orientation angles of a multilayer composite, makes it difficult to examine large structures with adequate computational effort. Using the finite element method for structural and sensitivity analysis, a large number of finite elements is necessary to achieve a certain accuracy of the analysis results, which also increases computational costs.Adaptive meshing methods start with a coarse mesh and refine it locally during an iterative process, where high discretization error occurs in the structure. Adaptive meshing can be performed within the optimization process to reduce the number of elements during the first iterations of the optimization loop.This paper presents the adaptive refinement of multilayer composite finite element models. The development of a simple error indicator, which takes into account the oriented and multilayer properties of composites, is considered. An optimization system is presented that handles large composite structures using adaptive finite element meshing with the aim to minimize the computational effort at a high accuracy of the analysis and optimization results. An example from engineering practice is given to show the performance of the system.Notation A finite element surface - t element thickness - t _i thickness of plyi - e strain error vector - D _i material constitutive matrix of plyi - D _i * material constitutive matrix of plyi (rotated about fiber orientation angle) - V element volume - _FE strain vector (finite element solution) - strain vector (averaged finite element solution) - domain error estimator - h _i edge length of elementi - r residuum on element equilibrium - J interelement traction jumps - element boundary - CRP carbon fibre reinforced plastic - Lagrangian function - Lagrangian multiplier - W structural weight - g constraint function - X design variable - X ⁰ design variable at current design point - u displacement vector - N _i shape function of nodei - , rotational degrees of freedom - K _E element stiffness matrix - B strain-displacement relation matrix - , , local curvilinear element coordinates - percentage relative error bound     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

A Hyperbase for Binary Lattice Hyperidentities

We define an identity to be hypersatisfied by a variety V if, whenever the operation symbols of V, are replaced by arbitrary terms (of appropriate arity) in the operations of V, the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a V hyperidentity. For example, the identity x + x y = x (x + y) is hypersatisfied by the variety L of all lattices. A proof of this consists of a case-by-case examination of { + , } {x, y, x y, x y}, the set of all binary lattice terms. In an earlier work, we exhibited a hyperbase ^L for the set of all binary lattice (or, equivalently, quasilattice) hyperidentities of type 2, 2. In this paper we provide a greatly refined hyperbase _L . The proof that _L is a hyperbase was obtained by using the automated reasoning program Otter 3.0.4.     

Probabilistic analysis of the application of the cross ratio to model based vision: Misclassification

The cross ratio of four colinear points is of fundamental importance in model based vision, because it is the simplest numerical property of an object that is invariant under projection to an image. It provides a basis for algorithms to recognise objects from images without first estimating the position and orientation of the camera.A quantitative analysis of the effectiveness of the cross ratio in model based vision is made. A given imageI of four colinear points is classified by making comparisons between the measured cross ratio of the four image points and the cross ratios stored in the model database. The imageI is accepted as a projection of an objectO with cross ratio if |–|ntu, wheren is the standard deviation of the image noise,t is a threshold andu=. The performance of the cross ratio is described quantitatively by the probability of rejectionR, the probability of false alarmF and the probability of misclassificationp (), defined for two model cross ratios , . The trade off between these different probabilities is determined byt.It is assumed that in the absence of an object the image points have identical Gaussian distributions, and that in the presence of an object the image points have the appropriate conditional densities. The measurements of the image points are subject to small random Gaussian perturbations. Under these assumptions the trade offs betweenR,F andp () are given to a good approximation byR=2(1–(t)),F=r _F t, t|–|^–1, where is the relative noise level, is cumulative distribution function for the normal distribution,r _F is constant, ande is a function of only. The trade off betweenR andF is obtained in Maybank (1994). In this paper the trade off betweenR andp () is obtained.It is conjectured that the general form of the above trade offs betweenR,F andp () is the same for a range of invariants useful in model based vision. The conjecture prompts the following definition: an invariant which has trade offs betweenR,F,p () of the above form is said to benon-degenerate for model based vision.The consequences of the trade off betweenR andp () are examined. In particular, it is shown that for a fixed overall probability of misclassification there is a maximum possible model cross ratio _m , and there is a maximum possible numberN of models. Approximate expressions for _m andN are obtained. They indicate that in practice a model database containing only cross ratio values can have a size of order at most ten, for a physically plausible level of image noise, and for a probability of misclassification of the order 0.1.     

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

Convergence of trust region augmented Lagrangian methods using variable fidelity approximation data

To date the primary focus of most constrained approximate optimization strategies is that application of the method should lead to improved designs. Few researchers have focused on the development of constrained approximate optimization strategies that are assured of converging to a Karush-Kuhn-Tucker (KKT) point for the problem. Recent work by the authors based on a trust region model management strategy has shown promise in managing the convergence of constrained approximate optimization in application to a suite of single level optimization test problems. Using a trust-region model management strategy, coupled with an augmented Lagrangian approach for constrained approximate optimization, the authors have shown in application studies that the approximate optimization process converges to a KKT point for the problem. The approximate optimization strategy sequentially builds a cumulative response surface approximation of the augmented Lagrangian which is then optimized subject to a trust region constraint. In this research the authors develop a formal proof of convergence for the response surface approximation based optimization algorithm. Previous application studies were conducted on single level optimization problems for which response surface approximations were developed using conventional statistical response sampling techniques such as central composite design to query a high fidelity model over the design space. In this research the authors extend the scope of application studies to include the class of multidisciplinary design optimization (MDO) test problems. More importantly the authors show that response surface approximations constructed from variable fidelity data generated during concurrent subspace optimization (CSSOs) can be effectively managed by the trust region model management strategy. Results for two multidisciplinary test problems are presented in which convergence to a KKT point is observed. The formal proof of convergence and the successful MDO application of the algorithm using variable fidelity data generated by CSSO are original contributions to the growing body of research in MDO.Nomenclature k Lagrangian iteration - s approximate minimization iteration - i, j, l variable indices - m number of inequality constraints - n number of design variables - p number of equality constraints - f(x) objective function - g(x) inequality constraint vector - g _j (x) j-th inequality constraint - h(x) equality constraint vector - h _j (x) i-th equality constraint - c(x) generalized constraint vector - c _i (x) i-th generalized constraint - c ₁,c ₂,c ₃,c ₄ real constants - m(x) approximate model - q(x) approximate model - q(x) piecewise approximation - r _p penalty parameter - t, t ₁,t ₂ step size length - x design vector, dimensionn - x _l l-th design variable - x ^U upper bound vector, dimensionn - x _l ^U l-th design upper bound - x ^L lower bound vector, dimensionn - x _l ^L l-th design lower bound - B approximation of the Hessian - K constraints residual - S design space - , ₁, ₂, scalars - ₁, ₂ convergence tolerances - ₀, ₁, ₂, , trust region parameters - Lagrange multiplier vector, dimensionm+p - _i i-th Lagrange multiplier - trust region ratio - (x) alternative form for inequality constraints - (x, ,r _p ) augmented Lagrangian function - approximation of the augmented Lagrangian function - fidelity control - . Euclidean norm - , inner product - gradient operator with respect to design vector x - P(y(x)) projection operator; projects the vector y onto the set of feasible directions at x - trust region radius - x step size     

Maintaining Longest Paths Incrementally

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O( + || log||) time and O() time respectively, where || and are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.     

Almost surely continuous solutions of a nonlinear stochastic integral equation

A nonlinear stochastic integral equation of the Hammerstein type in the formx(t; ) = h(t, x(t; )) + _s k(t, s; )f(s, x(s; ); )d(s) is studied wheret S, a measure space with certain properties, , the supporting set of a probability measure space (,A, P), and the integral is a Bochner integral. A random solution of the equation is defined to be an almost surely continuousm-dimensional vector-valued stochastic process onS which is bounded with probability one for eacht S and which satisfies the equation almost surely. Several theorems are proved which give conditions such that a unique random solution exists. AMS (MOS) subject classifications (1970): Primary; 60H20, 45G99. Secondary: 60G99.     

On a random Volterra integral equation

Summary Tsokos [12] showed the existence of a unique random solution of the random Volterra integral equation (*)x(t; ) = h(t; ) + _o ^t k(t, ; )f(, x(; )) d, where , the supporting set of a probability measure space (,A, P). It was required thatf must satisfy a Lipschitz condition in a certain subset of a Banach space. By using an extension of Banach's contraction-mapping principle, it is shown here that a unique random solution of (*) exists whenf is (, )-uniformly locally Lipschitz in the same subset of the Banach space considered in [12].     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

Cardinality problems of compositions of morphisms and inverse morphisms

We show that we cannot effectively determine whether, for morphisms _i , _i ,card (u ₀ ^–1 ₁) =card(u ₀ ^–1 ₁) for all wordsu over the domain alphabets of the two given compositions. In contrast it is decidable for morphisms _i , _i and a regular setR whethercard(u _{0 1} ^–1 ) =card(u _{0 1} ^–1 ) for all wordsu inR. In order to prove the latter result we give a characterization of the multiplicity functions of simple finite automata by using cardinalities of compositions of the above form. Finally, we show that the above decidability result also holds when we consider rational functions rather than morphisms.