Two elementary proofs of the Wigner theorem on symmetry in quantum mechanics

In quantum theory, symmetry has to be defined necessarily in terms of the family of unit rays, the state space. The theorem of Wigner asserts that a symmetry so defined at the level of rays can always be lifted into a linear unitary or an antilinear antiunitary operator acting on the underlying Hilbert space. We present two proofs of this theorem which are both elementary and economical. Central to our proofs is the recognition that a given Wigner symmetry can, by post-multiplication by a unitary symmetry, be taken into either the identity or complex conjugation. Our analysis often focuses on the behaviour of certain two-dimensional subspaces of the Hilbert space under the action of a given Wigner symmetry, but the relevance of this behaviour to the larger picture of the whole Hilbert space is made transparent at every stage.

A Note on the Genericity of Simultaneous Stabilizability and Pole Assignability

n this paper we study the genericity of simultaneous stabilizability, simultaneous strong stabilizability, and simultaneous pole assignability, in linear multivariable systems. The main results of the paper had been previously established by Ghosh and Byrnes using state-space methods. In contrast, the proofs in the present paper are based on input-output arguments, and are much simpler to follow, especially in the case of simultaneous and simultaneous strong stabilizability. Moreover, the input-output methods used here suggest computationally reliable algorithms for solving these two types of problems. In addition to the main results, we also prove some lemmas on generic greatest common divisors which are of independent interest.

Forms of relativistic dynamics with World Line Condition and separability

he Dirac generator formalism for relativistic Hamiltonian dynamics is reviewed along with its extension to constraint formalism. In these theories evolution is with respect to a dynamically defined parameter, and thus time evolution involves an eleventh generator. These formulations evade the No-Interaction Theorem. But the incorporation of separability reopens the question, and together with the World Line Condition leads to a second no-interaction theorem for systems of three or more particles. Proofs are omitted, but the results of recent research in this area is highlighted.

Binary decompositions and acyclic schemes

It is well known that the notions of normal forms and acyclicity capture many practical desirable properties for database schemes. The basic schema design problem is to develop design methodologies that strive toward these ideals. The usual approach is to first normalize the database scheme as far as possible. If the resulting scheme is cyclic, then one tries to transform it into an acyclic scheme. In this paper, we argue in favor of carrying out these two phases of design concurrently. In order to do this efficiently, we need to be able to incrementally analyze the acyclicity status of a database scheme as it is being designed. To this end, we propose the formalism of "binary decompositions". Using this, we characterize design sequences that exactly generate theta-acyclic schemes, for theta = agr,beta. We then show how our results can be put to use in database design. Finally, we also show that our formalism above can be effectively used as a proof tool in dependency theory. We demonstrate its power by showing that it leads to a significant simplification of the proofs of some previous results connecting sets of multivalued dependencies and acyclic join dependencies.

Natural actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic, natural-gradient and functi approximation ideas,and we provide their convergence proofs. Actor-critic reinforcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their compatibility with function-approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of special interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further reduce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal difference learning in the actor and by incorporating natural gradients. Our results extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.

Automata and logics over finitely varying functions

We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called View the MathML source’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich (2002) [15]. We also identify a “counter-free” subclass of View the MathML source’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic (MTL) Chevalier et al. (2006, 2007) [6] and [7].

Performance analysis of a slotted-ALOHA protocol on a capture channel with fading

We consider the slotted ALOHA protocol on a channel with a capture effect. There are M proofs will be shown to hold also for the slotted ALOHA protocol without capture.

Control of Agent Swarms using Generalized Centroidal Cyclic Pursuit Laws

One of the major tasks in swarm intelligence is to design decentralized but homogenoeus strategies to enable controlling the behaviour of swarms of agents. It has been shown in the literature that the point of convergence and motion of a swarm of autonomous mobile agents can be controlled by using cyclic pursuit laws. In cyclic pursuit, there exists a predefined cyclic connection between agents and each agent pursues the next agent in the cycle. In this paper we generalize this idea to a case where an agent pursues a point which is the weighted average of the positions of the remaining agents. This point correspond to a particular pursuit sequence. Using this concept of centroidal cyclic pursuit, the behavior of the agents is analyzed such that, by suitably selecting the agents' gain, the rendezvous point of the agents can be controlled, directed linear motion of the agents can be achieved, and the trajectories of the agents can be changed by switching between the pursuit sequences keeping some of the behaviors of the agents invariant. Simulation experiments are given to support the analytical proofs.

A monolithic strategy for fluid-structure interaction problems

In this work, we present a new monolithic strategy for solving fluid-structure interaction problems involving incompressible fluids, within the context of the finite element method. This strategy, similar to the continuum dynamics, conserves certain properties, and thus provides a rational basis for the design of the time-stepping strategy; detailed proofs of the conservation of these properties are provided. The proposed algorithm works with displacement and velocity variables for the structure and fluid, respectively, and introduces no new variables to enforce velocity or traction continuity. Any existing structural dynamics algorithm can be used without change in the proposed method. Use of the exact tangent stiffness matrix ensures that the algorithm converges quadratically within each time step. An analytical solution is presented for one of the benchmark problems used in the literature, namely, the piston problem. A number of benchmark problems including problems involving free surfaces such as sloshing and the breaking dam problem are used to demonstrate the good performance of the proposed method. Copyright (C) 2010 John Wiley & Sons, Ltd.

Qualitative theorem proving in linear constraints

We know, from the classical work of Tarski on real closed fields, that elimination is, in principle, a fundamental engine for mechanized deduction. But, in practice, the high complexity of elimination algorithms has limited their use in the realization of mechanical theorem proving. We advocate qualitative theorem proving, where elimination is attractive since most processes of reasoning take place through the elimination of middle terms, and because the computational complexity of the proof is not an issue. Indeed what we need is the existence of the proof and not its mechanization. In this paper, we treat the linear case and illustrate the power of this paradigm by giving extremely simple proofs of two central theorems in the complexity and geometry of linear programming.

Multi-hop Cooperative Wireless Networks: Diversity Multiplexing Tradeoff and Optimal Code Design

We consider single-source single-sink (ss-ss) multi-hop relay networks, with slow-fading links and single-antenna half-duplex relay nodes. While two-hop cooperative relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this paper, we identify two families of networks that are multi-hop generalizations of the two-hop network: K-Parallel-Path (KPP)networks and layered networks.KPP networks, can be viewed as the union of K node-disjoint parallel relaying paths, each of length greater than one. KPP networks are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the DMT of these families of networks completely for K > 3. Layered networks are networks comprising of layers of relays with edges existing only between adjacent layers, with more than one relay in each layer. We prove that a linear DMT between the maximum diversity dmax and the maximum multiplexing gain of 1 is achievable for single-antenna fully-connected layered networks. This is shown to be equal to the optimal DMT if the number of relaying layers is less than 4.For multiple-antenna KPP and layered networks, we provide an achievable DMT, which is significantly better than known lower bounds for half duplex networks.For arbitrary multi-terminal wireless networks with multiple source-sink pairs, the maximum achievable diversity is shown to be equal to the min-cut between the corresponding source and the sink, irrespective of whether the network has half-duplex or full-duplex relays. For arbitrary ss-ss single-antenna directed acyclic networks with full-duplex relays, we prove that a linear tradeoff between maximum diversity and maximum multiplexing gain is achievable.Along the way, we derive the optimal DMT of a generalized parallel channel and derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. We also give alternative and often simpler proofs of several existing results and show that codes achieving full diversity on a MIMO Rayleigh fading channel achieve full diversity on arbitrary fading channels. All protocols in this paper are explicit and use only amplify-and-forward (AF) relaying. We also construct codes with short block-lengths based on cyclic division algebras that achieve the optimal DMT for all the proposed schemes.Two key implications of the results in the paper are that the half-duplex constraint does not entail any rate loss for a large class of cooperative networks and that simple AF protocols are often sufficient to attain the optimal DMT

Incremental natural-gradient actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic and natural-gradient ideas, and provide their convergence proofs. Actor-critic rein- forcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their com- patibility with function approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further re- duce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal differ- ence learning in the actor and by incorporating natural gradients, and they extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.

A unification-based decision procedure for cryptographic protocol analysis

We present a sound and complete decision procedure for the bounded process cryptographic protocol insecurity problem, based on the notion of normal proofs [2] and classical unification. We also show a result about the existence of attacks with “high” normal cuts. Our proof of correctness provides an alternate proof and new insights into the fundamental result of Rusinowitch and Turuani [9] for the same setting.

Minimal Triangulations of Manifolds

Finding vertex-minimal triangulations of closed manifolds is a very difficult problem. Except for spheres and two series of manifolds, vertex-minimal triangulations are known for only few manifolds of dimension more than 2 (see the table given at the end of Section 5). In this article, we present a brief survey on the works done in last 30 years on the following:(i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers n and d, construction of n-vertex triangulations of different d-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of vertices.In Section 1, we have given all the definitions which are required for the remaining part of this article. A reader can start from Section 2 and come back to Section 1 as and when required. In Section 2, we have presented a very brief history of triangulations of manifolds. In Section 3,we have presented examples of several vertex-minimal triangulations. In Section 4, we have presented some interesting results on triangulations of manifolds. In particular, we have stated the Lower Bound Theorem and the Upper Bound Theorem. In Section 5, we have stated several results on minimal triangulations without proofs. Proofs are available in the references mentioned there. We have also presented some open problems/conjectures in Sections 3 and 5.

A unified view of the Apriori-based algorithms for frequent episode discovery

Frequent episode discovery framework is a popular framework in temporal data mining with many applications. Over the years, many different notions of frequencies of episodes have been proposed along with different algorithms for episode discovery. In this paper, we present a unified view of all the apriori-based discoverymethods for serial episodes under these different notions of frequencies. Specifically, we present a unified view of the various frequency counting algorithms. We propose a generic counting algorithm such that all current algorithms are special cases of it. This unified view allows one to gain insights into different frequencies, and we present quantitative relationships among different frequencies.Our unified view also helps in obtaining correctness proofs for various counting algorithms as we show here. It also aids in understanding and obtaining the anti-monotonicity properties satisfied by the various frequencies, the properties exploited by the candidate generation step of any apriori-based method. We also point out how our unified view of counting helps to consider generalization of the algorithm to count episodes with general partial orders.