Narrow Results

Additive noise could be encountered in various mechanical systems. It could be observed as part of ongoing system degradation and defect evolution. Here, we empirically demonstrate inherent challenges of permutation entropy (PE) in remaining useful life (RUL) analysis, the analysis of time to failure or time to unacceptable wear of the system. We perform numerical experiments by adding various amounts of additive Gaussian noise to vibrational signal and investigate how the PE changes. The data or signal are often comprised of several parts such as fundamental component, noise and other components related to perturbations out of the evolving defects. Here, we gain an additional insight on what part of the signal is related to the RUL. By joining these two problems together, we can draw a practical conclusion on how robust to additive noise the PE is to a particular dataset.

We consider words over an arbitrary alphabet admitting multiple pseudoperiods according to permutations. We describe the conditions under which such a word exists. Moreover, a natural generalization of Fine and Wilf's Theorem is proved. Finally, we introduce and describe a new family of words sharing properties with the so-called central words. In particular, under some simple conditions, we prove that these words are pseudopalindromes, a result consistent with the fact that central words are palindromes.

A universal cycle for permutations of length $n$ is a cyclic word or permutation, any factor of which is order-isomorphic to exactly one permutation of length $n$, and containing all permutations of length $n$ as factors. It is well known that universal cycles for permutations of length $n$ exist. However, all known ways to construct such cycles are rather complicated. For example, in the original paper establishing the existence of the universal cycles, constructing such a cycle involves finding an Eulerian cycle in a certain graph and then dealing with partially ordered sets.

In this paper, we offer a simple way to generate a universal cycle for permutations of length $n$, which is based on applying a greedy algorithm to a permutation of length $n-1$. We prove that this approach gives a unique universal cycle ${\mathrm{\Pi }}_n$ for permutations, and we study properties of ${\mathrm{\Pi }}_n$.

We describe a simple parallel algorithm for generating all permutations of n elements. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. The algorithm is cost-optimal, assuming the time to output the permutations is counted.

We investigate the problem of permuting n data items on an EREW PRAM with p processors using little additional storage. We present a simple algorithm with run time O((n/p)log n) and an improved algorithm with run time O(n/p + log n log log(n/p)). Both algorithms require n additional global bits and O(1) local storage per processor. If prefix summation is supported at the instruction level, the run time of the improved algorithm is O(n/p). The algorithms can be used to rehash the address space of a PRAM emulation.

We study probability distributions of permutations and binary words, which arise in symbolic analysis of time series and their differences. Under the assumptions that the series is stationary and independent we show that these probability distributions are universal and we derive a recursive algorithm for computing the distribution of binary words. This provides a general framework for performing chi square tests of goodness of fit of empirical distributions versus universal ones. We apply these methods to analyze heartbeat time series; in particular, we measure the extent to which atrial fibrillation can be modeled as an independent sequence.

The number of permutations appearing in data series is used for detecting changes in the structure of such series. We show the influence of the permutations length (embedding dimension) in order to get good results. We use permutations to analyze real data from medical and biological origins. Some problems that appear in applying these techniques are pointed out.

For an integer $m\ge 2$, let ${{𝒫}}_m$ be the partition of the unit interval $I$ into $m$ equal subintervals, and let ${{ℱ}}_m$ be the class of piecewise linear maps on $I$ with constant slope ${\pm }m$ on each element of ${{𝒫}}_m$. We investigate the effect on mixing properties when $f\in {{ℱ}}_m$ is composed with the interval exchange map given by a permutation $\sigma \in S_N$ interchanging the $N$ subintervals of ${{𝒫}}_N$. This extends the work in a previous paper [N. P. Byott, M. Holland and Y. Zhang, DCDS 33 (2013) 3365–3390], where we considered only the “stretch-and-fold” map $f_{\mathrm{\text{sf}}}(x)=mx\mathrm{\text{mod}}1$.

Motivated by the combinatorial properties of products in Lie algebras, we investigate the subset of permutations that naturally appears when we write the long commutator $[x_1,x_2,\dots ,x_m]$ as a sum of associative monomials. We characterize this subset and find some useful equivalences. Moreover, we explore properties concerning the action of this subset on sequences of $m$ elements. In particular, we describe sequences that share some special symmetries which can be useful in the study of combinatorial properties in graded Lie algebras.

We endow the space of rooted planar trees with the structure of a Hopf algebra. We prove that variations of such a structure lead to Hopf algebras on the spaces of labeled trees, $n$-trees, increasing planar trees and sorted trees. These structures are used to construct Hopf algebras on different types of permutations. In particular, we obtain new characterizations of the Hopf algebras of Malvenuto–Reutenauer and Loday–Ronco via planar rooted trees.

Various indicators of observed-theoretical spectrum matches were compared and the resulting statistical significance was characterized using permutation resampling. Novel decoy databases built by resampling the terminal positions of peptide sequences were evaluated to identify the conditions for accurate computation of peptide match significance levels. The methodology was tested on real and manually curated tandem mass spectra from peptides across a wide range of sizes. Spectra match indicators from complementary database search programs were profiled and optimal indicators were identified. The combination of the optimal indicator and permuted decoy databases improved the calculation of the peptide match significance compared to the approaches currently implemented in the database search programs that rely on distributional assumptions. Permutation tests using p-values obtained from software-dependent matching scores and E-values outperformed permutation tests using all other indicators. The higher overlap in matches between the database search programs when using end permutation compared to existing approaches confirmed the superiority of the end permutation method to identify peptides. The combination of effective match indicators and the end permutation method is recommended for accurate detection of peptides.

Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ($2+\lambda$)-approximation algorithms for these problems, where $\lambda$ is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.

One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species’ genome. When we represent genomes as permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so, the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the cost of that sequence is minimum. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about the lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for five versions of this problem involving reversals and transpositions. We also give bounds for the diameters concerning these problems and provide an improved approximation factor for simple permutations considering transpositions.

In this essay, which began as a Review Article of the book X, Y & Z: The Real Story of How Enigma was Broken by Dermot Turing, I discuss some of the background details of the Enigma Cypher Machine. The machine was supposed to be ‘unbreakable’, as claimed (in particular) by the manufacturers. It was repeatedly broken by Polish and British mathematicians, employed in their respective countries’ (and France’s) bureaus; in particular, heroically, by Alan Turing (at Bletchley Park, UK) and Marian Rejewski (in Poznań, Warsaw and France) — but others played important parts, too.

Let n ≥ 3 be an integer. For any permutation σ of A = {0, 1, …, n-1}, set . It is proved that n is prime if and only if 〈σ, n〉 ≡ 0 (mod n) for any σ. When n is composite, we show that there exist cycles of any length satisfying this congruence. We show as well that the analog statement is true for cycles of length at least 2 not satisfying the congruence.

Let $n\ge 5$ be an odd integer. It is shown that $\{1^{\sigma (1)},\dots ,n^{\sigma (n)}\}$ is a complete residue system modulo $n$ for some permutation $\sigma$ of $\{1,\dots ,n\}$ if and only if $\frac{1}{2}(n-1)$ is a Sophie Germain prime. Partial results are obtained also for the case $n$ even.

The aim of this paper is to provide a comparison of various algorithms and parameters to build reduced semantic spaces. The effect of dimension reduction, the stability of the representation and the effect of word order are examined in the context of the five algorithms bearing on semantic vectors: Random projection (RP), singular value decomposition (SVD), non-negative matrix factorization (NMF), permutations and holographic reduced representations (HRR). The quality of semantic representation was tested by means of synonym finding task using the TOEFL test on the TASA corpus. Dimension reduction was found to improve the quality of semantic representation but it is hard to find the optimal parameter settings. Even though dimension reduction by RP was found to be more generally applicable than SVD, the semantic vectors produced by RP are somewhat unstable. The effect of encoding word order into the semantic vector representation via HRR did not lead to any increase in scores over vectors constructed from word co-occurrence in context information. In this regard, very small context windows resulted in better semantic vectors for the TOEFL test.

In this paper, we explore the existence and nonlinearity of affine $k$-cycle permutations on ${\mathbb{Z}}_n$ for different values of $k$ and $n$. It is proved that a transposition $f$ on ${\mathbb{Z}}_n$ has nonlinearity $2$ for $n>4$, a $3$-cycle permutation on ${\mathbb{Z}}_p$ has nonlinearity $3$ for $p>5$, $p$ a prime. The number of affine $k$-cycle permutations on ${\mathbb{Z}}_n$ and a bound for their nonlinearity have been obtained. Some results on the cyclic decomposition of a permutation on ${\mathbb{Z}}_p$, $p$ a prime, have also been proved.

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n²) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n²) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n²) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).

A permutation over alphabet $\mathrm{\Sigma }=(1,2,3,\dots ,n)$ is a sequence over $\mathrm{\Sigma }$, where every element occurs exactly once. $S_n$ denotes symmetric group defined over $\mathrm{\Sigma }$. $I_n=(1,2,3,\dots ,n)\in S_n$ denotes the Identity permutation. $R_n\in S_n$ is the reverse permutation i.e., $R_n=(n,n-1,n-2,\dots ,2,1)$. An operation, that we call as an LE operation, has been defined which consists of exactly two generators: set-rotate that we call Rotate and pair-exchange that we call Exchange (OEIS). At least two generators are the required to generate $S_n$. Rotate rotates all elements to the left (moves leftmost element to the right end) and Exchange is the pair-wise exchange of the two leftmost elements. The optimum number of moves for transforming $R_n$ into $I_n$ with LE operation are known for $n\le 10$; as listed in OEIS with identity A048200. However, no general upper bound is known. The contributions of this article are: (a) a novel upper bound for the number of moves required to sort $R_n$ with LE has been derived; (b) the optimum number of moves to sort the next larger $R_n$ i.e., $R_{11}$ has been computed; (c) an algorithm conjectured to compute the optimum number of moves to sort a given $R_n$ has been designed.