On zigzag permutations and comparisons of adjacent elements

Each permutation (a₁, a₂,…, a_n) of 1, 2,…, n determines a sequence of “<” and “>” relations determined by the relat holding between adjacent values (a_i, a_{i + 1}). A new and elementary algorithm is given, which, for every such pattern of “<”, “>” relations, computes the number of permutations with that pattern. The algorithm enables one to calculate (in bits) the amount of information gained by comparing all adjacent pairs of elements in a list. It also has a simple extension to circular patterns of relations.     

Calculation of the number of complete mappings for permutations

The computation time for counting “good” permutations rapidly grows as the length of permutations increases. The paper presents algorithms for enumeration of “good” permutations. Algorithms reducing twice the number of “good” permutations that should be counted are considered along with the algorithm employing the concept of weight of a “good” permutation. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 106–110, March–April, 2000.     

On the decomposition of rational functions

Let f:=p/q∈K(x)$f:=p/q\in \mathbb{K}\left(x\right)$ be a rational function in one variable. By Lüroth’s theorem, the collection of intermediate fields K(f)?L?K(x)$\mathbb{K}\left(f\right)?\mathbb{L}?\mathbb{K}\left(x\right)$ is in bijection with inequivalent proper decompositions f=g°h$f=g°h$, with g,h∈K(x)$g,h\in \mathbb{K}\left(x\right)$ of degrees ≥2$\ge 2$. In [Alonso, Cesar, Gutierrez, Jaime, Recio, Tomas, 1995. A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19, 527–544] an algorithm is presented to calculate such a function decomposition. In this paper we describe a simplification of this algorithm, avoiding expensive solutions of linear equations. A MAGMA implementation shows the efficiency of our method. We also prove some indecomposability criteria for rational functions, which were motivated by computational experiments.     

On the revision of preferences and rational inference processes

Orderings and inference relations can be successfully used to model the behavior of a rational agent. This behavior is indeed represented either by a set of ordered pairs that reflect the agent's preferences, or by a rational inference relation that describes the agent's internal logics. In the finite case where we work, both structures admit a simple representation by means of logical chains. The problem of revising such inference processes arises when it appears necessary to modify the original model in order to take into account new facts about the agent's behavior. How is it then possible to perform the desired modification? We study here the possibilities offered by the technique of ‘chain revision’ which appears to be the easiest way to treat this kind of problem: the revision is performed through a simple modification of the logical chain attached to the agent's behavior, and the revision problem boils down to adding, retracting or modifying some of the links of the original chain. This perspective permits an effective treatment of the problems of both simple and multiple revision. The technique developed can also be used in some limiting cases, when the agent's inference process is only partially known, encoded by an incomplete set of preferences or a conditional knowledge base.     

On non-linearity and affine equivalence of permutations over an arbitrary finite commutative ring with unity

Cryptographic properties of permutations viz non-linearity, affine equivalence, and mode transform have been studied in the literature, treating them as bijections on ?_n. In this article, the authors consider them as bijection on an arbitrary finite commutative ring with unity. Treating them this way, they achieve a generalization of the above mentioned properties. The authors also propose an algorithm for computing non-linearity in their generalized scenario, which is faster compared to the direct approach in many cases.     

An improvement on the upper bounds of the magnitudes of derivatives of rational triangular Bézier surfaces

New bounds on the magnitudes of the first- and second-order partial derivatives of rational triangular Bézier surfaces are presented. Theoretical analysis shows that the proposed bounds are tighter than the existing ones. The superiority of the proposed new bounds is also illustrated by numerical tests.     

On the minimum size of visibility graphs

In this paper we give tight lower bounds on the size of the visibility graph, the contracted visibility graph, and the bar-visibility graph of n disjoint line segments in the plane, according to their vertex-connectivity.     

On problems without polynomial kernels

Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input.In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.     

On the uselessness of quantum queries

Given a prior probability distribution over a set of possible oracle functions, we define a number of queries to be useless for determining some property of the function if the probability that the function has the property is unchanged after the oracle responds to the queries. A familiar example is the parity of a uniformly random Boolean-valued function over {1,2,…,N}, for which N−1 classical queries are useless. We prove that if 2k classical queries are useless for some oracle problem, then k quantum queries are also useless. For such problems, which include classical threshold secret sharing schemes, our result also gives a new way to obtain a lower bound on the quantum query complexity, even in cases where neither the function nor the property to be determined is Boolean.     

Applying fast simulation to find the number of good permutations

A permutation (s₀, s₁,…, s_{N − 1}) of symbols 0, 1,…, N − 1, is called good if the set (t₀, t₁,…, t_{N − 1}) formed according to the rule t_i = i + s_i (mod N), i = 0, 1, … N − 1, is also a permutation. A fast simulation method is proposed. It allows the number of good permutations to be evaluated with high accuracy for large N (in particular, N > 100). Empirical upper and lower bounds for the number of good permutations are presented and verified against numerical data. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 80–89, November–December 2007.     

More restrictive Gray codes for some classes of pattern avoiding permutations

In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three positions which is optimal for n odd. Other refinements have been found for permutation sets enumerated by the numbers of Schröder, Pell, even index Fibonacci numbers and the central binomial coefficients. A general efficient generating algorithm is also given.     

On the performance of trace locality of reference

In this paper, trace locality of reference (LoR) is identified as a mechanism to predict the behavior of a variety of systems. If two objects were accessed nearby in the past and the first one is accessed again, trace LoR predicts that the second one will be accessed in near future. To capture trace LoR, trace graph is introduced. Although trace LoR can be observed in a variety of systems, but the focus of this paper is to characterize it for data accesses in memory management systems. In this field, it is compared with recency-based prediction (LRU stack) and it is shown that not only the model is much simpler, but also it outperforms recency-based prediction in all cases. The paper examines various parameters affecting trace LoR such as object size, caching effects (address reference stream versus miss address stream), and access type (read, write, or both). It shows that object size does not have meaningful effects on trace LoR; in average the predictability of miss address stream is 30% better than address reference stream; and identifying access type can increase predictability. Finally, two enhancements are introduced to the model: history and multiple LRU prediction. A main contribution of this paper is the introduction of the n-stride prediction¹. For a prediction to be useful, we should have sufficient time to load the object, and n-stride prediction shows that trace LoR can predict an access far ahead from its occurrence.     

Upper and Lower Bounds for Selection on the Mesh

A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we explain, using the notion of adaptiveness, why techniques used in the currently best selection algorithms cannot lead to a distance-optimal algorithm. For worst-case inputs we apply new techniques to improve the previous best upper bound of 1.22n of Kaklamanis et al. [7] to 1.15n . This improvement is obtained in part by increasing the adaptiveness of previous algorithms. Received May 25, 1995; revised June 1, 1996.     

Error analysis of the derivative of rational interpolation with a linear denominator

This paper deals with the approximation properties of the derivatives of rational cubic interpolation with a linear denominator. Error expressions of the derivatives of interpolating functions are derived, convergence is established and the optimal error coefficient c _i is proved to be symmetric about the parameters of the rational interpolation. The unified integral form of the error of the second derivative in all subintervals is obtained. A simple expression of the jump of the second derivative at the knots and the conditions for the interpolating function to be C ² in the interpolating interval are given.     

On the design of on-chip instruction caches

Cache memories reduce memory latency and traffic in computing systems. Most existing caches are implemented as board-based systems. Advancing VLSI technology will soon permit significant caches to be integrated on chip with the processors they support. In designing on-chip caches, the constraints of VLSI become significant. The primary constraints are economic limitations on circuit area and off-chip communications. The paper explores the design of on-chip instruction-only caches in terms of these constraints. The primary contribution of this work is the development of a unified economic model of on-chip instruction-only cache design which integrates the points of view of the cache designer and of the floorplan architect. With suitable data, this model permits the rational allocation of constrained resources to the achievement of a desired cache performance. Specific conclusions are that random line replacement is superior to LRU replacement, due to an increased flexibility in VLSI floorplan design; that variable set associativity can be an effective tool in regulating a chip's floorplan; and that sectoring permits area efficient caches while avoiding high transfer widths. Results are reported on economic functionality, from chip area and transfer width to miss ratio. These results, or the underlying analysis, can be used by microprocessor architects to make intelligent decisions regarding appropriate cache organizations and resource allocations.     

A Kalman filter solution of the inverse scattering problem with a rational reflection coefficient

This paper presents a new inverse scattering method for reconstructing the reflectivity function of symmetric two-component wave equations, or the potential of a Schrödinger equation, when the reflection coefficient is rational. This method relies on the so-called Chandrasekhar equations which implement the Kalman filter associated to a stationary state-space model. These equations are derived by using first a general layer stripping principle to obtain some differential equations for reconstructing a general scattering medium, and by specializing these recursions to the case when the probing waves have a state-space model.     

Lower bounds on the rotation distance of binary trees

The rotation distanced(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T)?2n−6, a well-known conjecture states that there are trees for which this bound is sharp for any value of n?11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some “regular” tree structures for which d(S,T)=3n/2−O(1), or d(S,T)=5n/3−O(1).