Generation of Inequivalent Generalized Bell Bases

The notion of equivalence of maximally entangled bases of bipartite d–dimensional Hilbert spaces _{d d} is introduced. An explicit method of inequivalent bases construction is presented. PACS: 03.67.-a     

Cut point languages of markov DTOL systems

Letp satisfy 0 p < 1, then by (p) we denote the family of Markov DTOL languages with cut pointp. In this paper we present a complete classification of the collection of such families (p), 0 p < 1, showing that forms an infinite nondense hierarchy with (0) being its only accumulation point from below. Furthermore it is proved that each language in (p) can be expressed as a finite union of DDTOL languages.Work supported partially by the Natural Sciences and Engineering Research Council of Canada grants Nos. A-3590 and A-7700, and partially by Deutsche Forschungsgemeinschaft.     

The University of Texas at Arlington Autonomous Aerial Vehicle—An overview

This paper reports on the status of The University of Texas at Arlington student effort to design, build and fly an Autonomous Aerial Vehicle. Both the 1991 entry into the First International Aerial Robotics Competition as well as refinements being made for 1992 are described. Significant technical highlights include a real-time vision system for target objective tracking, a real-time ultrasonic locator system for position sensing, a novel mechanism for gradually moving from human to computer control, and a hierarchical control structure implemented on a 32-bit microcontroller. Detailed discussion about the design of multivariable automatic controls for stability augmentation is included. Position and attitude control loops are optimized according to a combined ₂ and criteria. We present a modification of a recently published procedure for recovering a desired open-loop transfer function shape within the framework of the mixed ₂/ problem. This work has led to a new result that frees a design parameter related to imposing the constraint. The additional freedom can be used to improve upon the performance and robustness characteristics of the system.     

The Eigenvalue Problem for the 2D Laplacian in ℋ-Matrix Arithmetic and Application to the Heat and Wave Equation

A class of matrices (-matrices) has recently been introduced by Hackbusch for approximating large and fully populated matrices arising from FEM and BEM applications. These matrices are data-sparse and allow approximate matrix operations of almost linear complexity. In the present paper, we choose a special class of -matrices that provides a good approximation to the inverse of the discrete 2D Laplacian. For these 2D -matrices we study the blockwise recursive schemes for block triangular linear systems of equations and the Cholesky and LDL^T factorization in an approximate arithmetic of almost linear complexity. Using the LDL^T factorization we compute eigenpairs of the discrete 2D Laplacian in -matrix arithmetic by means of a so-called simultaneous iteration for computing invariant subspaces of non-Hermitian matrices due to Stewart. We apply the -matrix techniques to approximate the solutions of the high-frequency 2D wave equation for smooth initial data and the 2D heat equation for arbitrary initial data by spectral decomposition of the discrete 2D Laplacian in, up to logarithmic factors, optimal complexity.     

Continuous-time time-varying entropy

In this paper we present a definition for the entropy for time-varying continuous-time systems. This entropy differs significantly from the entropy for discrete-time systems, which is defined as the memoryless component of the spectral factor of an operator related to the system. Properties of this entropy are discussed, the relationships with ₂ and , as well as the relationship with the discrete-time entropy.The work of P. A. Iglesias was supported in part by the National Science Foundation, under Contract ECS-9309387.     

Sound and complete Hoare-like calculi based on copy rules

Summary This paper presents a uniform approach to known and new results on relative completeness of Hoare-like calculi for languages of ALGOL-like programs with procedures as procedure parameters. First the notion of a copy rule is introduced. It provides a uniform framework for dealing with different variants of semantics reaching from dynamic to static scope. Then for each copy rule a Hoare-like calculus () is presented, the soundness of which is shown by using an approximating semantics. The key to the completeness results lies in a general completeness theorem on the calculi () which has these results as corollaries. Finally, a new type of theorem on Hoare-like calculi is proved by which the notion of formal provability in () is completely characterized. This characterization theorem is the main result of the paper. It covers both soundness and completeness of the calculi () and additionally gives an idea of what the limits of presently known Hoare-like proof techniques for programming languages with procedures are.     

Unification in partially commutative semigroups

Unification algorithms have been constructed for semigroups and commutative semigroups. This paper considers the intermediate case of partially commutative semigroups. We introduce classesN and of such semigroups and justify their use. We present an equation-solving algorithm for any member of the classN. This algorithm is relative to having an algorithm to determine all non-negative solutions of a certain class of diophantine equations of degree 2 which we call -equations. The difficulties arising when attempting to solve equations in members of the class are discussed, and we present arguments that strongly suggest that unification in these semigroups is undecidable.     

Model-checking discrete duration calculus

Duration Calculus was introduced in [ZHR91] as a logic to specify and reason about requirements for real-time systems. It is an extension of Interval Temporal Logic [Mos85] where one can reason about integrated constraints over time-dependent and Boolean valued states without explicit mention of absolute time. Several major case studies, e.g. the gas burner system in [RRH93], have shown that Duration Calculus provides a high level of abstraction for both expressing and reasoning about specifications. Using Timed Automata [A1D92] one can express how real-time systems can be constructed at a level of detail which is close to an actual implementation. We consider in the paper the correctness of Timed Automata with respect to Duration Calculus formulae. For a subset of Duration Calculus, we show that one can automatically verify whether a Timed Automaton is correct with respect to a formulaD, abbreviated D, i.e. one can domodel-checking. The subset we consider is expressive enough to formalize the requirements to the gas burner system given in [RRH93]; but only for a discrete time domain. Model-checking is done by reducing the correctness problem D to the inclusion problem of regular languages.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Stabilizability of linear systems defined overC *-algebras

LetF andG be elements of aC ^*-algebraA. Assume that, for each irreducible^*-representation ofA on a Hilbert space210B; , there is a bounded linear operatorL B( ) such that the spectrum of(F) –(G)L is contained in the open left half plane. We prove that there is then an elementL A such that the spectrum ofF — GL is contained in the open left half plane. That is, if the system (F, G) is locally stabilizable, then it is stabilizable. We also consider the analogous problem with the open left half plane replaced by the open unit disk.This paper was supported in part by the National Science Foundation under Grant NSF-MCS-8002138.     

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.     

A New Class of Depth-Size Optimal Parallel Prefix Circuits

Given n values x₁, x₂, ... ,x_n and an associative binary operation o, the prefix problem is to compute x₁ox₂o··· ox_i, 1in. Many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. It has been proved that the size s(D(n)) and the depth d(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n))+s(D(n))2n–2; thus, a prefix circuit is depth-size optimal if d(D(n))+s(D(n))=2n–2. In this paper, we construct a new depth-size optimal prefix circuit SL(n). In addition, we can build depth-size optimal prefix circuits whose depth can be any integer between d(SL(n)) and n–1. SL(n) has the same maximum fan-out lgn+1 as Snir's SN(n), but the depth of SL(n) is smaller; thus, SL(n) is faster. Compared with another optimal prefix circuit LYD(n), d(LYD(n))+2d(SL(n))d(LYD(n)). However, LYD(n) may have a fan-out of at most 2 lgn–2, and the fan-out of LYD(n) is greater than that of SL(n) for almost all n12. Because an operation node with greater fan-out occupies more chip area and is slower in VLSI implementation, in most cases, SL(n) needs less area and may be faster than LYD(n). Moreover, it is much easier to design SL(n) than LYD(n).     

Utilizing deontic operators in information systems specification

One major task in requirements specification is to capture the rules relevant to the problem at hand. Declarative, rule-based approaches have been suggested by many researchers in the field. However, when it comes to modeling large systems of rules, not only for the behavior of the computer system but also for the organizational environment surrounding it, current approaches have problems with limited expressiveness, flexibility, and poor comprehensibility. Hence, rule-based approaches may benefit from improvements in two directions: (1) improvement of the rule languages themselves and (2) better integration with other, complementary modeling approaches.In this article, both issues are addressed in an integrated manner. The proposal is presented in the context of the Tempora project on rule-based information systems development, but has also been integrated with PPP. Tempora has provided a rule language based on an executable temporal logic working on top of a temporal database. The rule language is integrated with static (ER-like) and dynamic (SA/RT-like) modeling approaches. In the current proposal, the integration with complementary modeling approaches is extended by including organization modeling (actors, roles), and the expressiveness of the rule language is increased by introducing deontic operators and rule hierarchies. The main contribution of the article is not seen as any one of the above-mentioned extensions, but as the resulting comprehensive modeling support. The approach is illustrated by examples taken from an industrial case study done in connection with Tempora.C. List of Symbols Subset of set - Not subset of set - Element of set - Not element of set - Equivalent to - Not equivalent to - ¬ Negation - Logical and - Logical or - Implication - Sometime in past - Sometime in future - Always in past - Always in future - Just before - Just after - u Until - s Since - Trigger - Condition - _s State condition - Consequence - _a Action - _s State - Role - Actor - ¬ - General deontic operator - O Obligatory - R Recommended - P Permitted - D Discouraged - F Forbidden - (/–) General rule - t _R Real time - t _M Model time     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Transformation of programs for fault-tolerance

In this paper we describe how a program constructed for afault-free system can be transformed into afault-tolerant program for execution on a system which is susceptible to failures. A program is described by a set of atomic actions which perform transformations from states to states. We assume that a fault environment is represented by a programF. Interference by the fault environmentF on the execution of a programP can then be described as afault-transformation which transformsP into a program (P). This is proved to be equivalent to the programPP _F , whereP _F is derived fromP andF, and defines the union of the sets of actions ofP andF _P . A recovery transformation transformsP into a program (P) =PR by adding a set ofrecovery actions R, called arecovery program. If the system isfailstop and faults do not affect recovery actions, we have ((P))=(P)R=PP _F R We illustrate this approach to fault-tolerant programming by considering the problem of designing a protocol that guarantees reliable communication from a sender to a receiver in spite of faults in the communication channel between them.     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

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.     

Categories of fuzzy sets

In this paper we look at two categories, the category of fuzzy subsets and a quotient category / of fuzzy sets. The category / is an extension of the category of sets, and the standard constructions in fuzzy set theory arise naturally within this category. This paper was presented at a workshop in the Czech Republic, hosted by Professors Vilém Novák and Irina Perfilieva. I thank them for their warm hospitality and the opportunity to participate in an inspiring workshop.     

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.     

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)