Representation and uniformization of algebraic transductions

This paper explores different means of representation for algebraic transductions, i.e., word relations realized by pushdown transducers. The relevance of this work lies more in its point of view rather than any particular result. We are aiming at giving specific techniques for obtaining, or perhaps explaining, decompositions of algebraic (and incidentally, rational) relations, relying solely on their “machine” definition rather than some complex algebraic apparatus. From this point of view, we are hoping to have demystified the heavy formalism employed in the present literature. Some of the novelties of our work are: the use of “stack languages” and “embeddings,” which eliminate the need of arbitrary context-free languages in our characterizations, the study of uniformizations for algebraic transductions and the use of the so-called stack transductions for exposing the anatomy of pushdown transducers.This work was supported by the Natural Science and Engineering Research Council of Canada grants R220259 and OGP0041630.     

Optimization techniques for curved path computing

Participating media with an inhomogeneous index of refraction make light follow curved paths. Simulating this in a global illumination environment has usually been neglected due to the complexity of the calculations involved, sacrificing accurate physical simulations for efficient visual results. This paper aims to simulate non-linear media in a more reasonable time than previous works without losing physical correctness. Accuracy is achieved by solving the Eikonal equation of geometrical optics, which describes the path followed by a light beam that traverses a non-linear medium. This equation is used in the context of a photon mapping extension.     

Correlations in a General Theory of Quantum Measurement

The paper investigates correlations in a general theory of quantum measurement based on the notion of instrument. The analysis is performed in the algebraic formalism of quantum theory in which the observables of a physical system are described by a von Neumann algebra, and the states—by normal positive normalized functionals on this algebra. The results extend and generalise those obtained for the classical case where one deals with the full algebra of operators on a Hilbert space.     

Six Synthesis Methods for Reversible Logic

The (2 ^w )! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S ₂ ^w . Therefore, we investigate the group S _n as well as one of its subgroups isomorphic to S _n/2 × S _n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice.     

SQL extension for spatio-temporal data

An SQL extension is formalized for the management of spatio-temporal data, i.e. of spatial data that evolves with respect to time. The extension is dedicated to applications such as topography, cartography, and cadastral systems, hence it considers discrete changes both in space and in time. It is based on the rigid formalization of data types and of SQL constructs. Data types are defined in terms of time and spatial quanta. The SQL constructs are defined in terms of a kernel of few relational algebra operations, composed of the well-known operations of the 1NF model and of two more, Unfold and Fold. In conjunction with previous work, it enables the uniform management of 1NF structures that may contain not only spatio-temporal but also either purely temporal or purely spatial or conventional data. The syntax and semantics of the extension is fully consistent with the {SQL:2003} standard.     

Representations by Contact and Intersection of Segments

A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact family of segments and points. We deduce that any four-connected three-colorable plane graph is the contact graph of a family of segments and that any four-colored planar graph without an induced C₄ using four colors is the intersection graph of a family of straight line segments.     

Fast Recognition of Fibonacci Cubes

Fibonacci cubes are induced subgraphs of hypercubes based on Fibonacci strings. They were introduced to represent interconnection networks as an alternative to the hypercube networks. We derive a characterization of Fibonacci cubes founded on the concept of resonance graphs. The characterization is the basis for an algorithm which recognizes these graphs in O(mlog n) time. A. Vesel supported by the Ministry of Science of Slovenia under the grant 0101-P-297.     

Two-Way Protocol with Imperfect Devices

The security of a deterministic quantum scheme for communication, namely the LM05 [1], is studied in presence of a lossy channel under the assumption of imperfect generation and detection of single photons. It is shown that the scheme allows for a rate of distillable secure bits higher than that pertaining to BB84 [2]. We report on a first implementation of LM05 with weak pulses.     

A Survey on the Numerics and Computations for the Landau-Lifshitz Equation of Micromagnetism

The Landau-Lifshitz (LL)equation of micromagnetism governs rich variety of the evolution of magnetization patterns in ferromagnetic media. This is due to the complexity of physical quantities appearing in the LL equation. This complexity causes also an interesting mathematical properties of the LL equation: nonlocal character for some quantities,nonconvex side-constraints, strongly nonlinear terms. These effects influence also the numerical approximations. In this work, recent developments on the approximation of weak solutions, together with the overview of well-known methods for strong solutions,are addressed. Author is supported by the Fund for Scientific Research - Flanders FWO (Belgium).