Search

The 3D orientation of clasts within a deposit are known to be informative on processes that formed that deposit. In archaeological sites, a portion of the clasts in the deposit are introduced by non-geological processes, and these are typically systematically recorded in archaeological excavations with total stations. By recording a second point on elongated clasts it is possible to quickly and precisely capture their orientation. The statistical and graphical techniques for analyzing these data are well published, and there is a growing set of actualistic and archaeological comparative data to help with the interpretation of the documented patterns. This paper advances this area of research in presenting methods to address some shortcomings in current methodologies. First, a method for calculating confidence intervals on orientation statistics is presented to help address the question of how many objects are needed to assess the formation of a deposit based on orientations. Second, a method for assessing the probability that two assemblages have different orientations is presented based on permutations testing. This method differs from existing ones in that it considers three-dimensional orientations rather than working separately with the two-dimensional bearing and plunge components. Third, a method is presented to examine spatial variability in orientations based on a moving windows approach. The raw data plus the R code to build this document and to implement these methods plus those already described by McPherron are included to help further their use in assessing archaeological site formation processes. [ABSTRACT FROM AUTHOR]

In [8] , G. Kyureghyan showed that the function F ( x ) = x + γ f ( x ) is a permutation of F q m when f : F q m → F q is a function, γ ∈ F q m is a b -linear translator for f for some b ( ≠ − 1 ) ∈ F q . His idea has been extended in [19] by Qin et al. and in [9] by M. Kyureghyan and Abrahamyan to finitely many function–linear translator pairs. In this paper, we study the permutations generated by function–linear translator pairs along G. Kyureghyan's idea and prove that these permutations form groups whose group structures are well understood. [ABSTRACT FROM AUTHOR]

In a system that performs both encryption and lossy compression, the conventional way is to compress first and then encrypt the compressed data. This separation approach has been proved to be optimal. In certain applications where sensitive information should be protected as early as possible, it is preferable to perform the encryption first and then compress the encrypted data, which leads to the concept of the reversed system. Johnson et al. proposed an achievable scheme for the reversed system, where a modulo-sum encryption is followed by a compression using the Wyner–Ziv distributed source coding with side information. However, in general, this reversed system performs worse than the conventional system in the sense that it requires more compression rate and secrecy key rate. In this paper, we propose a new achievable scheme for the reversed system, where the encryption is conducted by a permutation cipher, and then, the encrypted data is compressed using the optimal rate-distortion code. The proposed scheme can achieve the optimal compression rate and secret key rate. As a result, we show that reversing the order of the encryption and compression does not necessarily compromise the performance of an encryption-compression system. We show that the proposed system attains strong secrecy, and the information leakage vanishes exponentially. [ABSTRACT FROM PUBLISHER]

Abstract: This paper is concerned with the Constraint Satisfaction Problem (CSP). It is well-known that the general CSP is NP-hard. However, there has been significant success in discovering subproblems which are tractable (polynomial time solvable). One of the most effective ways to obtain a tractable subproblem has been to force all of the constraint relations to lie in some tractable language. In this paper we define a new way of identifying tractable subproblems of the CSP. Let P be an arbitrary CSP instance and Γ be any tractable language. Suppose there exists, for each variable of P, a permutation of the domain such the resultant permuted constraint relations of P all lie in Γ. The domain permuted instance is then an instance of a tractable class and can be solved by the polynomial time algorithm for Γ. Solutions to P can be obtained by inverting the domain permutations. The question, for a given class of instances and language Γ, whether such a set of domain permutations can be found efficiently is the key to this method''s tractability. One of the important contributions made in this paper is the notion of a “lifted constraint instance” which is a powerful tool to study this question. [•] We consider the open problem of discovering domain permutations which make instances max-closed. We show that, for bounded arity instances over a Boolean domain this problem is tractable, while for domain size three it is intractable even for binary instances. [•] We give a simple proof verifying the tractability of discovering domain permutations which make instances row convex. We refute a published result by giving a simple proof of the intractability of discovering domain permutations which make instances, even with domain size four, connected row convex. [•] We demonstrate that triangulated and stable marriage instances are reducible, via domain permutations, to max-closed instances. This provides a simple explanation for arc consistency deciding these instances. [•] We verify with a simple direct proof the tractability of identification of renamable Horn instances, and the intractability of finding the largest renamable Horn subset of clauses of an instance of SAT. [•] We describe natural tractable classes which properly extend the maximal relational classes arising from tractable constraint languages. We believe that domain permutation reductions have a significant chance of being useful in practical applications. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a fundamental solution method for the problems of steady three-dimensional Stokes flow past obstacles in a planar periodic array. The solutions of these problems are periodic functions which are difficult to be approximated by the conventional fundamental solution method. In the presented method, we approximate the solutions by linear combinations of the periodic fundamental solutions presented by Ishii. Some numerical examples are also included in this paper and their results make a good agreement with the ones of the previous works. [Copyright &y& Elsevier]

Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n) = 1 and t(n) = n!. For n odd, we prove (nφ(n))/2k ≤ s(n) ≤ n!·2-(n-1)/2/((n-1)/2)! and 2(n-1)/2·(n-1/2)! ≤ t(n) ≤ 2k · (n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function. [ABSTRACT FROM AUTHOR]

Abstract: Recently, Deutsch and Elizalde have studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let denote the number of partitions of with the largest singleton for . In this paper, several explicit formulas for , involving a Dobinski-type analog, are obtained by algebraic and combinatorial methods. Furthermore, many combinatorial identities involving and Bell numbers are presented by operator methods, and congruence properties of are also investigated. It is shown that the sequences and (mod ) are periodic for any prime , and contain a string of consecutive zeroes. Moreover their minimum periods are conjectured to be . [Copyright &y& Elsevier]

It is well known that multiple frequency sources are necessary for accurate geoacoustic inversion. This paper presents an inversion method which uses the low frequency (LF) spectrum only to estimate bottom properties even in the presence of expected errors in source location, phone depths, and ocean sound-speed profiles. Matched field processing (MFP) along a vertical array is used. The LF method first conducts an exhaustive search of the (five) parameter search space (sediment thickness, sound-speed at the top of the sediment layer, the sediment layer sound-speed gradient, the half-space sound-speed, and water depth) at 25 Hz and continues by retaining only the high MFP value parameter combinations. Next, frequency is slowly increased while again retaining only the high value combinations. At each stage of the process, only those parameter combinations which give high MFP values at all previous LF predictions are considered (an ever shrinking set). It is important to note that a complete search of each relevant parameter space seems to be necessary not only at multiple (sequential) frequencies but also at multiple ranges in order to eliminate sidelobes, i.e., false solutions. Even so, there are no mathematical guarantees that one final, unique “solution” will be found. [ABSTRACT FROM AUTHOR]

A k-uniform hypergraph H = (V;E) is said to be self-complementary whenever it is isomorphic with its complement H̅ = (V; (kV) - E). Every permutation σ of the set V such that σ(e) is an edge of H̅ if and only if e ∈ E is called self-complementing. 2-self-comlementary hypergraphs are exactly self complementary graphs introduced independently by Ringel (1963) and Sachs (1962). For any positive integer n we denote by λ(n) the unique integer such that n = 2λ(n) c, where c is odd. In the paper we prove that a permutation σ of [1; n] with orbits O1,..., Om is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l ≥ 0 such that k = a2l + s, a is odd, 0 ≤ s < 2l and the following two conditions hold: (i) n = b2l+1 + r, r ∈ {0,...,2l - 1 + s}, and (ii) ∑i:λ(|Oi|)≤l|Oi|≤ r. For k = 2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs. [ABSTRACT FROM AUTHOR]

Abstract: An edge cut of a connected graph is a -restricted edge cut if is disconnected, and every component of has at least vertices. The -restricted edge connectivity is defined as the minimum cardinality over all -restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The -restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum -edge degree. In this paper some sufficient conditions guaranteeing optimal -restricted edge connectivity and super -restricted edge connectivity for permutation graphs are presented for . [Copyright &y& Elsevier]

Abstract: For a graph , its cubicity is the minimum dimension such that is representable as the intersection graph of (axis-parallel) cubes in -dimensional space. (A -dimensional cube is a Cartesian product , where is a closed interval of the form on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113–118] showed that for a -dimensional hypercube , . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph is defined as the minimum dimension such that is representable as the intersection graph of axis-parallel boxes in -dimensional space. Since for any graph , our result implies that . The problem of determining a non-trivial lower bound for is left open. [Copyright &y& Elsevier]

Abstract: We consider pattern containment and avoidance with a very tight definition that was used first in several papers more than 60 years ago. Using this definition, we prove that the monotone pattern is easier to avoid than almost any other pattern of the same length. We also show that with this definition, almost all patterns of length are avoided by the same number of permutations of length . The corresponding statements are not known to be true for more relaxed definitions of pattern containment. This is the first time we know of that expectations have been used to compare numbers of permutations avoiding certain patterns. [Copyright &y& Elsevier]

Abstract: Permutominoes are polyominoes defined by suitable pairs of permutations. In this paper we provide a formula to count the number of convex permutominoes of given perimeter. To this aim we define the transform of a generic pair of permutations, we characterize the transform of any pair defining a convex permutomino, and we solve the counting problem in the transformed space. [Copyright &y& Elsevier]

Abstract: The past decade has seen a flurry of research into pattern avoiding permutations but little of it is concerned with their exhaustive generation. Many applications call for exhaustive generation of permutations subject to various constraints or imposing a particular generating order. In this paper we present generating algorithms and combinatorial Gray codes for several families of pattern avoiding permutations. Among the families under consideration are those counted by Catalan, large Schröder, Pell, even-index Fibonacci numbers and the central binomial coefficients. We thus provide Gray codes for the set of all permutations of avoiding the pattern for all and the Gray codes we obtain have distances 4 or 5. [Copyright &y& Elsevier]

Abstract: In this paper we investigate infinite, locally finite, connected, transitive digraphs with more than one end. For undirected graphs with these properties it has been shown that they are trees as soon as they are 2-arc transitive. In the case of digraphs the situation is much more involved. We show that these graphs can have both thick and thin ends, even if they are highly arc transitive. Hence they are far away from being ‘tree-like’. On the other hand all known examples of digraphs with more than one end are either highly arc transitive or at most 1-arc transitive. We conjecture that infinite, locally finite, connected, 2-arc transitive digraphs with more than one end are highly arc transitive and prove that this conjecture holds for digraphs with prime in- and out-degree and connected cuts. [Copyright &y& Elsevier]

Abstract: Let be a permutation of . Define and over all the unordered pairs of distinct vertices of G. Let denote the smallest positive value of among all the permutations f of . The permutation f with is called a near automorphism of G. In this paper, we study the near automorphisms of cycles and we prove that , moreover, we obtain the set of near automorphisms of . [Copyright &y& Elsevier]

Abstract: The problem of reconstructing signed permutations on n elements from their erroneous patterns distorted by reversal errors is considered in this paper. A reversal is the operation of taking a segment of the signed permutation, reversing it, and flipping the signs of its elements. The reversal metric is defined as the least number of reversals transforming one signed permutation into another. It is proved that for any an arbitrary signed permutation is uniquely reconstructible from three distinct signed permutations at reversal distance at most one from the signed permutation. The proposed approach is based on the investigation of structural properties of a Cayley graph whose vertices form a subgroup of the symmetric group . It is also proved that an arbitrary signed permutation is reconstructible from two distinct signed permutations with probability as . In the case of at most two reversal errors it is shown that at least distinct erroneous patterns are required in order to reconstruct an arbitrary signed permutation. [Copyright &y& Elsevier]

Abstract: We say the pair of patterns is multiset Wilf equivalent if, for any multiset M, the number of permutations of M that avoid is equal to the number of permutations of M that avoid . In this paper, we find a large new class of multiset Wilf equivalent pairs, namely, the pair (, ), for and a permutation of . It is the most general multiset Wilf equivalence result to date. [Copyright &y& Elsevier]

Abstract: It is known that the area of all Catalan paths of length is equal to , which coincides with the number of inversions of all 321-avoiding permutations of length . In this paper, a bijection between the two sets is established. Meanwhile, a number of interesting bijective results that pave the way to the required bijection are presented. [Copyright &y& Elsevier]

Abstract: We present various techniques to count proportions of permutations with restricted cycle structure in finite permutation groups. For example, we show how a generalized block theory for symmetric groups, developed by Külshammer, Olsson, and Robinson, can be used for such calculations. The paper includes improvements of recurrence relations of Glasby, results on average numbers of fixed points in certain permutations, and a remark on a conjecture of Robinson related to the so-called -problem of representation theory. We extend and give alternative proofs for previous results of Erdős and Turán; Glasby; and Beals, Leedham-Green, Niemeyer, Praeger and Seress. [Copyright &y& Elsevier]

Abstract: Many approaches to deciding the satisfiability of quantifier-free formulae with respect to a background theory T—also known as Satisfiability Modulo Theory, or SMT(T)—rely on the integration between an enumerator of truth assignments and a decision procedure for conjunction of literals in T. When the background theory T is the combination of two simpler theories, the approach is typically instantiated by means of a theory combination schema (e.g. Nelson–Oppen, Shostak). In this paper we propose a new approach to SMT, where the enumerator of truth assignments is integrated with two decision procedures, one for T 1 and one for T 2, acting independently from each other. The key idea is to search for a truth assignment not only to the atoms occurring in the formula, but also to all the equalities between variables which are shared between the theories. This approach is simple and expressive: for instance, no modification is required to handle non-convex theories (as opposed to traditional Nelson-Oppen combinations which require a mechanism for splitting). Furthermore, it can be made practical by leveraging on state-of-the-art boolean and SMT search techniques, and on theory layering (i.e., cheaper reasoning first, and more often). We provide thorough experimental evidence to support our claims: we instantiate the framework with two decision procedures for the combinations of Equality and Uninterpreted Functions () and Linear Arithmetic (), both for (the convex case of) reals and for (the non-convex case of) integers; we analyze the impact of the different optimizations on a variety of test cases; and we compare the approach with state-of-the-art competitor tools, showing that our implemented tool compares positively with them, sometimes with dramatic gains in performance. [Copyright &y& Elsevier]

The article explores the so-called λ-permutations shown by Steven Krantz and Jeffery McNeal in their paper "Creating more convergent series." They specified that a permutation σ of the positive integers is a λ-permutation if it has two characteristics. The first property is that for every convergent series, the summation of ak from k =1 to infinity, the summation of aσ(k) from k =1 to infinity also converges. The second property is that there is at least one divergent series which is the summation of ak from k =1 to infinity such that the summation of aσ(k) from k =1 to infinity converges.

Hyperspectral images are used for aerial and space imagery applications, including target detection, tracking, agricultural, and natural resource exploration. Unfortunately, atmospheric scattering, secondary illumination, changing viewing angles, and sensor noise degrade the quality of these images. Improving their resolution has a high payoff, but applying super- resolution techniques separately to every spectral band is problematic for two main reasons. First, the number of spectral bands can be in the hundreds, which increases the computational load excessively. Second, considering the bands separately does not make use of the information that is present across them. Furthermore, separate band super resolution does not make use of the inherent low dimensionality of the spectral data, which can effectively be used to improve the robustness against noise. In this paper, we introduce a novel super-resolution method for hyperspectral images. An integral part of our work is to model the hyperspectral image acquisition process. We propose a model that enables us to represent the hyperspectral observations from different wavelengths as weighted linear combinations of a small number of basis image planes. Then, a method for applying super resolution to hyperspectral images using this model is presented. The method fuses information from multiple observations and spectral bands to improve spatial resolution and reconstruct the spectrum of the observed scene as a combination of a small number of spectral basis functions. [ABSTRACT FROM AUTHOR]

This paper introduces new approaches to the data distribution-partition problem for sparse matrices in a multiprocessor environment. In this work, the data partition problem of a sparse matrix is modeled as a Min-Max Problem subject to the uniformity constrain when the goal is to balance the load for both sparse and dense operations. This problem is NP-Complete and two heuristic solutions (ABO and GPB) are proposed. The key of ABO and GPB is to determine the permutation of rows/columns of the input sparse matrix to obtain a sorted matrix with a homogeneous density of nonzero elements. Due to the heuristic nature of the proposed methods their validation is carried out by a comparative study of the parallel efficiency of two types of problems (sparse and mixed) when ABO, GPB, Block, Cyclic and MRD data distributions are applied. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a novel Mamdani-type fuzzy model, referred to as the all-permutations fuzzy rule base (APFRB), and show that it is mathematically equivalent to a standard feedforward neural network. We describe several applications of this equivalence between a neural network and our fuzzy rule base (FRB), including knowledge extraction from and knowledge insertion into neural networks. [ABSTRACT FROM AUTHOR]

The paper discusses complexity of circuit realization through Haar wavelet series. The efficiency in circuit synthesis using a method for minimization of the number of non-zero Haar coefficients by permutation of binary coordinates of indices of Haar functions is considered. Some applications of Haar wavelet transform and efficient ways of its calculation for logic domain are also discussed. [ABSTRACT FROM AUTHOR]

Abstract: The problem of sorting signed permutations by reversals (SBR) is a fundamental problem in computational molecular biology. The goal is, given a signed permutation, to find a shortest sequence of reversals that transforms it into the positive identity permutation, where a reversal is the operation of taking a segment of the permutation, reversing it, and flipping the signs of its elements. In this paper we describe a randomized algorithm for SBR. The algorithm tries to sort the permutation by repeatedly performing a random oriented reversal. This process is in fact a random walk on the graph where permutations are the nodes and an arc from to corresponds to an oriented reversal that transforms to . We show that if this random walk stops at the identity permutation, then we have found a shortest sequence. We give empirical evidence that this process indeed succeeds with high probability on a random permutation. To implement our algorithm we describe a data structure to maintain a permutation, that allows to draw an oriented reversal uniformly at random, and perform it in sub-linear time. With this data structure we can implement the random walk in time, thus obtaining an algorithm for SBR that almost always runs in sub-quadratic time. The data structures we present may also be of independent interest for developing other algorithms for SBR, and for other problems. Finally, we present the first efficient parallel algorithm for SBR. We obtain this result by developing a fast implementation of the recent algorithm of Bergeron (Proceedings of CPM, 2001, pp. 106–117) for sorting signed permutations by reversals that is parallelizable. Our implementation runs in time on a regular RAM, and in time on a PRAM using n processors. [Copyright &y& Elsevier]

Abstract: Let G be a group that is a set-theoretic union of finitely many proper subgroups. Cohn defined to be the least integer m such that G is the union of m proper subgroups. Tomkinson showed that can never be 7, and that it is always of the form (q a prime power) for solvable groups G. In this paper we give exact or asymptotic formulas for . In particular, we show that , while for alternating groups we find unless or 9. An application of this result is also given. [Copyright &y& Elsevier]

Recently, Green and Losonczy [5, 6] introduced freely braided permutations as a special class of restricted permutations that has arisen in the study of Schubert varieties. They suggest as an open problem to enumerate the number of freely braided permutations in Sn. In this paper, we prove that the generating function for the number of freely braided permutations in Sn is given by 1-3x-2x²+(1+x)√p1-4x/1-4x-x²+(1-x²)√1-4x. [ABSTRACT FROM AUTHOR]