A note on unscrambling address lines

A writer stores some data in memory accessible via address lines. If an adversary permutes the address lines after the writer leaves the message, then how can a reader find the permutation? This is the so-called unscrambling address lines problem of Broder et al. [SODA'99, 1999, pp. 870-871]. By a divide-and-conquer approach, we give a very simple algorithm to recover the permutation. Our method is much easier to understand than Broder et al.'s previous ad hoc solution.     

A note on the coprime fractional representation of nonlinear feedback systems

A very large infinite-dimensional Banach space of bounded nonlinear operators is suggested as an underlying framework for studies of nonlinear systems control. Meanwhile, it is pointed out that all results obtained in Verma [6] can be extended to this much larger family of nonlinear control systems.     

A note on asynchronous multi-exponentiation algorithm using binary representation

A basic but expensive operation in implementations of several famous public-key cryptosystems is the computation of the multi-exponentiation in a certain finite multiplication group. In 2007, Yang et al. presented an interesting asynchronous multi-exponentiation algorithm called the ${\mathit{SU}}_t$ method, which uses the binary representations for the exponents. In this note, we analyze the computational efficiency of the ${\mathit{SU}}_t$ method by modeling the scanning process as a Markov chain. It shows that their computational efficiency result is incorrect. Moreover, we make a performance comparison among the published techniques and show that the performance of a modified sliding window method is better than that of the ${\mathit{SU}}_t$ method, when there are 4 or more additional registers. We hope that our research will be convenient to the development of the cryptographic devices.     

Discrete representation of straight lines

If a continuous straight line segment is digitized on a regular grid, obviously a loss of information occurs. As a result, the discrete representation obtained (e.g., a chaincode string) can be coded more conveniently than the continuous line segment, but measurements of properties (such as line length) performed on the representation have an intrinsic inaccuracy due to the digitization process. In this paper, two fundamental properties of the quantization of straight line segments are treated. 1) It is proved that every ``straight' chaincode string can be represented by a set of four unique integer parameters. Definitions of these parameters are given. 2) A mathematical expression is derived for the set of all continuous line segments which could have generated a given chaincode string. The relation with the chord property is briefly discussed.     

A note on extension of Pascal by coroutines

In this communication, a simplification is suggested for the coroutine extension of Pascal described by Kriz and Sandmayr. In addition to being simpler to implement, it is also more user-friendly and secure because most of the strict sequence constraints on procedure invocations are lifted. The scheme uses the Pascal-P compiler, without modification except for the addition of a few built-in procedures, together with a macroassembler for Pcode preprocessing.     

A representation of trees by languages I

A tree can be represented by a language consisting of a suitable coding of its finite branches. We investigate this representation and derive a number of reductions between certain equivalence problems for context-free tree grammars and recursive program schemes and the (open) equivalence problem for DPDA's. This is the first part of this work: it is devoted to technical results on prefix-free languages and strict deterministic grammars. Application to context-free tree grammars will be published in the second part.     

A note on the dipole coordinates

A couple of orthogonal coordinates for dipole geometry are proposed for numerical simulations of plasma geophysics in the Earth's dipole magnetic field. These coordinates have proper metric profiles along field lines in contrast to the standard dipole coordinate system that is commonly used in analytical studies for dipole geometry.     

A note on the Routh-Hurwitz test

This note demonstrates how the ε-method in the original Routh-Hurwitz test can be applied when the Routh array contains a row with zero leftmost element together with an all-zero row. The complete root distribution is determined by applying the criterion only once to the given polynomialD(s)without either factoring out a common divisor or shifting the imaginary axis. Since the test may become computationally tedious due to the inclusion of cumbersome ε-terms, the recently reported method of Shamash [1] is used to simplify the computational scheme. This method, being restricted to the case whereD(s)has purely imaginary roots constituting the whole set of roots of the greatest common even divisor, is here refined and generalized to accommodate all cases in which all-zero rows appear.     

A note on the Gamma test

This note describes a simple technique, the Gamma (or Near Neighbour) test, which in many cases can be used to considerably simplify the design process of constructing a smooth data model such as a neural network. The Gamma test is a data analysis routine, that (in an optimal implementation) runs in time O(MlogM)as M,where Mis the number of sample data points, and which aims to estimate the best Mean Squared Error (MSError) that can be achieved by any continuous or smooth (bounded first partial derivatives) data model constructed using the data.First presented at NCAF seminar, Portsmouth, UK on 20 September 1995     

A note on the FRPDF distribution

The paper by Varghese et al. [Varghese P, Braswell RN, Wang B, Zhang C. Statistical tolerance analysis using FRPDF and numerical convolution. Computer Aided Design 1996;28:723-32] provided a novel approach for statistical tolerance analysis. This required convolution of the FRPDF distribution and the paper pursued a numerical approach for this. Here, it is shown that one can derive elementary closed form expressions for the convolution and that the numerical approach can be avoided.     

A note on the factorization conjecture

We give partial results on the factorization conjecture on codes proposed by Schützenberger. We consider a family of finite maximal codes $C$ over the alphabet $A = \{a, b\}$ and we prove that the factorization conjecture holds for these codes. This family contains $(p,4)$ -codes, where a $(p,4)$ -code $C$ is a finite maximal code over $A$ such that each word in $C$ has at most four occurrences of $b$ and $a^p \in C$ , for a prime number $p$ . We also discuss the structure of these codes. The obtained results once again show relations between factorizations of finite maximal codes and factorizations of finite cyclic groups.