Narrow Results

In this paper, we discuss the group consisting of some good automorphisms of representation ring of the non-pointed Hopf algebra $D(n)$, the quotient of the non-pointed prime Hopf algebras of GK-dimension one, which is generated by $x,y,z$ with the relations:

We consider the routing number of trees, denoted by rt(), with respect to the matching routing model. For an arbitrary n-node tree T, it is known that rt(T) < 3n/2 + O(log n). In this paper, by providing a recursive off-line permutation routing algorithm, we show that the routing number of an n-node complete d-ary tree of height h(T) > 1 is bounded from above by n + o(n). This is near optimal since, for an n-node complete d-ary tree T of height h(T) > 1 it holds that rt(T) ≥ n.

For each alphabet Σ_n = {a₁,a₂,…,a_n}, linearly ordered by a₁ < a₂ < ⋯ < a_n, let C_n be the language of circular or cyclic shifts over Σ_n, i.e., C_n = {a₁a₂ ⋯ a_n-1a_n, a₂a₃ ⋯ a_na₁,…,a_na₁ ⋯ a_n-2a_n-1}. We study a few families of context-free grammars G_n (n ≥1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of G_n. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for negative bases beta.

This paper introduces the penmutational graph, a new network topology, which preserves the same desirable properties as those of a star graph topology. A permutational graph can be decomposed into subgraphs induced by node sets defined by equivalence classes. Using this decomposition, its structual properties as well as the relationship among graph families, permutational graphs, star graphs, and complete graphs are studied. Moreover, the diameters of permutational graphs are investigated and good estimates are obtained which are better than those of some network topologies of similar orders.

We study the wavelength problem and arc (edge) congestion problem for communicating permutation instances on a ring. We prove the best possible upper bounds on the number of wavelengths and arc (edge) congestion in both directed and undirected cases.

Most semi-quantum secret sharing protocols are suitable for the application with three participants. Based on the n-level states, a multiparty semi-quantum secret sharing protocol is proposed. Compared with similar protocols, it has the merits as follows. (1) The dealer only needs to prepare the single photon sequence without using any product state or entangle state. (2) To share a secret, the classical parties need not have the ability of measurement. They only need to reorder the photon sequence and send it to the receiver. (3) The dealer knows nothing about any agent’s secret shadow. Therefore, it is infeasible for the dealer to impersonate the classical participant to pool the secret shadow during the secret recovering phase. (4) Theoretically, the qubit efficiency of the proposed protocol is asymptotically 100%. The protocol is secure against famous attacks such as intercept-resend attack, measurement-resend attack and entangle-measure attack.

In processing a page image by a given zoning algorithm (automatic or manual), a certain text string is generated which may not be the same as the correct string. The difference may be due to the incorrect reading order selected by the employed zoning algorithm or poor recognition of characters. A difference algorithm is commonly used to find the best match between the generated string and the correct string. The output of such an algorithm will then be a sequence of matched substrings which are not in the correct order. To determine the performance of a given zoning algorithm, it is of interest to find the minimum number of moves needed to obtain the correct string from the string generated by that algorithm. The problem can be modeled as a sorting problem where a string of n integers ordered in a random manner, must be sorted in ascending (or descending) order. In this paper, we derive bounds on the time complexity of sorting a given string and present a near-optimal algorithm for that.

Internet of things (IoT) has evolved as the internet of everything, and it has grabbed the interest of all the researchers in recent days. Almost all the objects, including nonelectronics devices, can also be connected with the internet through radio frequency identification (RFID) technology. The security of the perception layer is crucial to secure the entire IoT network. RFID-enabled IoT perception layer has secured reader-to-server channel and unsecured tag to reader channel. Hence, securing the unsecured communication channel between the reader and the tag is the need of the hour. This work proposes a simple yet secure permutation approximate adder (SYSPXA)-based RFID mutual authentication protocol to address the need. The proposed protocol dramatically reduces the tag’s storage and computational overhead. It needs 40% less storage and 66.7% less permutation operation in comparison with the existing protocols. Nondisclosure of the key and freshness of key, IDS and random numbers at every mutual authentication process gives resistance to the protocol against de-synchronization attack, disclosure attack, tag tracking, replay attack. The SYSPXA protocol is validated for its security features using Burrows–Abadi–Needham (BAN) logic formal verification. The performance and security of the proposed protocol are contrasted with various futuristic permutation-based protocols, and its superiority over other protocols is highlighted. We have simulated the SYSPXA protocol with ModelSim tool for verifying its functionality. The protocol encoder architecture is implemented in the Intel cyclone IV Field Programmable Gate Array (FPGA) EP4CE115F29C7 device.

The purpose of this paper is to show that the lattice of permutations on a n -element set is bounded. This result strengthens the semi-distributive nature of the lattice . To prove this property, we use a characterization of the class of bounded lattices in terms of arrows relations defined on the join-irreducible elements of a lattice or, more precisely, in terms of the A-table of a lattice.

A quandle is a set equipped with a binary operation satisfying three quandle axioms. It also can be expressed as a sequence of permutations of the underlying set satisfying certain conditions. In this paper, we will calculate the second rack homology group of the disjoint union of two finite quandles and the second and third rack homology groups of certain type of finite quandles.

In this paper, we introduce a new method for counting the number of connected components of multi-curves. Our method is based on associating multi-curves with permutations, where we can see that the number of connected components of a multi-curve is directly related to the number of cycles in a cycle decomposition of the corresponding permutation. Our ultimate goal is to obtain a formula about multi-curves that gives the number of connected components of the curves, and obtaining a formula for the number of cycles of a permutation will also accomplish this goal. While we have several naive methods for counting the number of cycles of permutations, none of them gives us such a formula. As an approach, we develop a new combinatorial technique to count the number of cycles of permutations by introducing a new notation of permutation.

Algebraic theory of coding is one of modern fields of applications of algebra. This theory uses matrix algebra intensively. This paper is devoted to an application of Kronecker's matrix forms of presentations of the genetic code for algebraic analysis of a basic scheme of degeneracy of the genetic code. Similar matrix forms are utilized in the theory of signal processing and encoding. The Kronecker family of the genetic matrices is investigated, which is based on the genetic matrix [C A; U G], where C, A, U, G are the letters of the genetic alphabet. This matrix in the third Kronecker power is the (8*8)-matrix, which contains all 64 genetic triplets in a strict order with a natural binary numeration of the triplets by numbers from 0 to 63. Peculiarities of the basic scheme of degeneracy of the genetic code are reflected in the symmetrical black-and-white mosaic of this genetic (8*8)-matrix. This mosaic matrix is connected algorithmically with Hadamard matrices unexpectedly, which are famous in the theory of signal processing and encoding, spectral analysis, quantum mechanics and quantum computers. Furthermore, many kinds of cyclic permutations of genetic elements lead to reconstruction of initial Hadamard matrices into new Hadamard matrices unexpectedly. This demonstrates that matrix algebra is one of promising instruments and of adequate languages in bioinformatics and algebraic biology.

This paper proposes a technique to modify a Multistage Interconnection Network (MIN) to augment it with fault tolerant capabilities. The augmented MIN is referred to as Enhanced MIN (E-MIN). The technique employed for construction of E-MIN is compared with the two known physical fault tolerance techniques, namely, extra staging and chaining. EMINs are found to be more generic than extra staged networks and less expensive than chained networks. The EMIN realizes all the permutations realizable by the original MIN. The routing strategies under faulty and fault free conditions are shown to be very simple in the case of E-MINs.

Cumulative residual entropy (CRE) has been suggested as a new measure to quantify uncertainty of nonlinear time series signals. Combined with permutation entropy and Rényi entropy, we introduce a generalized measure of CRE at multiple scales, namely generalized cumulative residual entropy (GCRE), and further propose a modification of GCRE procedure by the weighting scheme — weighted generalized cumulative residual entropy (WGCRE). The GCRE and WGCRE methods are performed on the synthetic series to study properties of parameters and verify the validity of measuring complexity of the series. After that, the GCRE and WGCRE methods are applied to the US, European and Chinese stock markets. Through data analysis and statistics comparison, the proposed methods can effectively distinguish stock markets with different characteristics.

Several chaos-based image encryption schemes have been proposed in the last decade. Each encryption scheme has pros and cons regarding its speed, complexity, and security. This paper proposes a new chaotic map called Power-Chaotic Map (PCM). Characteristics of the proposed PCM, such as chaotic behaviour, randomness, sensitivity, and s-unimodality, are investigated. As an application of the proposed chaotic map, an image encryption scheme is proposed to encrypt greyscale and text images. The proposed three-phase image encryption scheme performs a series of substitution and permutation operations. The Pixel-Level phase utilises the PCM’s generated keystreams to perform the substitution operation of image pixels. The Row-Level phase permutates, via a proposed pseudorandom number generator, pixel locations of each row and then shuffles row locations. Finally, the Column-Level phase performs a substitution operation on pixels of each column. Performance of the proposed PCM-based image encryption scheme is investigated through histogram analysis, statistical correlation analysis, key sensitivity, encryption performance of text images, and permutation and substitution properties. Experimental results indicate that the PCM has a wider range of chaotic behaviour than well-known one-dimensional maps, meets the s-unimodality property, has high sensitivity, and generates keystreams with random-like behaviour. Furthermore, results indicate that the PCM-based image encryption scheme provides high encryption security for text images, high key sensitivity, immunity against brute-force attacks, strong statistical correlation results, strong encryption performance, and low computational complexity.

In this paper, an efficient novel dual permutation–substitution structure-based color image encryption algorithm is proposed. Initially, the Secure Hash Algorithm-512 (SHA-512) is applied to the input image to generate the initial values for the Lü system dynamically. In the first stage of permutation, inter-color-component pixel shuffling is carried out with a circular pixel-swapping mechanism. In the second stage, intra-color-component pixel shuffling is executed, based on pseudorandom positions generated by the Lü chaotic system. Pixel values are changed in the substitution stage, based on float-valued chaotic sequences generated by the Lü system. The performance of the proposed algorithm is evaluated with metrics such as key space, key sensitivity, histograms, correlation coefficients (vertical, horizontal and diagonal), information entropy, number of pixel changes rate (NPCR), unified average changing intensity (UACI), peak signal-to-noise ratio (PSNR), mean absolute error (MAE), contrast analysis, encryption time and the National Institute of Standards and Technology Special Publication 800-22 (NIST SP 800-22) statistical test. The experimental results obtained and performance assessment show that the proposed scheme has produced good results.

A class of nonparametric statistical methods, including a nonparametric empirical Bayes (EB) method, the Significance Analysis of Microarrays (SAM) and the mixture model method (MMM) have been proposed to detect differential gene expression for replicated microarray experiments. They all depend on constructing a test statistic, for example, a t-statistic, and then using permutation to draw inferences. However, due to special features of microarray data, using standard permutation scores may not estimate the null distribution of the test statistic well, leading to possibly too conservative inferences. We propose a new method of constructing weighted permutation scores to overcome the problem: posterior probabilities of having no differential expression from the EB method are used as weights for genes to better estimate the null distribution of the test statistic. We also propose a weighted method to estimate the false discovery rate (FDR) using the posterior probabilities. Using simulated data and real data for time-course microarray experiments, we show the improved performance of the proposed methods when implemented in MMM, EB and SAM.

Protein structure alignment plays a key role in protein structure prediction and fold family classification. An efficient method for multiple protein structure alignment in a mathematical manner is presented, based on deterministic annealing technique. The alignment problem is mapped onto a nonlinear continuous optimization problem (NCOP) with common consensus chain, matching assignment matrices and atomic coordinates as variables. At each step in the annealing procedure, the NCOP is decomposed into as many subproblems as the number of protein chains, each of which is actually an independent pairwise structure alignment between a protein chain and the consensus chain and hence can be efficiently solved by the parallel computation technique. The proposed method is robust with respect to choice of iteration parameters for a wide range of proteins, and performs well in both multiple and pairwise structure alignment cases, compared with existing alignment methods.

The operators with large scaling dimensions can be labeled by Young diagrams. Among other bases, the operators using restricted Schur polynomials have been known to have a large N but nonplanar limit under which they map to states of a system of harmonic oscillators. We analyze the oscillator algebra acting on pairs of long rows or long columns in the Young diagrams of the operators. The oscillator algebra can be reached by a Inonu–Wigner contraction of the u(2) algebra inside of the u(p) algebra of p giant gravitons. We present evidences that integrability in this case can persist at higher loops due to the presence of the oscillator algebra which is expected to be robust under loop corrections in the nonplanar large N limit.