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.     

New Concepts in Evolutionary Search for Boolean Functions in Cryptology

In symmetric cryptology the resistance to attacks depends critically on the nonlinearity properties of the Boolean functions describing cipher components like Substitution boxes (S-boxes). Some of the most effective methods known to generate functions that satisfy multiple criteria are based on evolutionary heuristics. In this paper, we improve on these algorithms by employing an adaptive strategy. Additionally, using recent improvements in the understanding of these combinatorial structures, we discover essential properties of the graph formed by affine equivalence classes of Boolean functions, which offers several advantages as a conceptual model for multiobjective seeking evolutionary heuristics. Finally, we propose the first major global cooperative effort to discover new bounds for cryptographic properties of Boolean functions.     

Nonlinear systems possessing linear symmetry

This paper tackles linear symmetries of control systems. Precisely, the symmetry of affine nonlinear systems under the action of a sub‐group of general linear group GL(n,?). First of all, the structure of state space (briefly, ss) symmetry group and its Lie algebra for a given system is investigated. Secondly, the structure of systems, which are ss‐symmetric under rotations, is revealed. Thirdly, a complete classification of ss‐symmetric planar systems is presented. It is shown that for planar systems there are only four classes of systems which are ss‐symmetric with respect to four linear groups. Fourthly, a set of algebraic equations are presented, whose solutions provide the Lie algebra of the largest connected ss‐symmetry group. Finally, some controllability properties of systems with ss‐symmetry group are studied. As an auxiliary tool for computation, the concept and some properties of semi‐tensor product of matrices are included. Copyright © 2006 John Wiley & Sons, Ltd.     

Feedback equivalence for general control systems

We discuss the solution to the problem of local equivalence of control systems with n states and p controls in a neighbourhood of a generic point, under the Lie pseudo-group of local time independent feedback transformations. We have shown earlier that this problem is identical with the problem of simple equivalence of the time optimal variational problem. Here we indicate the way in which this identification may be used to obtain closed loop time critical controls for general systems. We show that the classification of general nonlinear systems depends on the classification of all n−p dimensional affine subspaces of the space of symmetric forms in p variables and that the case of control linear systems depends on the classification of all n−p dimensional affine subspaces of the space of skew forms in p variables. We show that in the latter case the G-structure is the prolongation of one determined by a state space transformation group. We give a complete list of normal forms for control linear systems in the case p=n−1.     

Constructions of q-ary functions with good global avalanche characteristics

In this paper, we construct two classes of q-ary balanced functions which have good global avalanche characteristics (GAC) measured in terms of sum-of-squares-modulus indicator (SSMI), modulus indicator(MI), and propagation criterion (PC). We show that the SSMI, MI, and PC of q-ary functions are invariant under affine transformations. Also, we give a construction of q-ary s-plateaued functions and obtain their SSMI. We provide a relationship between the autocorrelation spectrum of a cubic Boolean function and the dimension of the kernel of the bilinear form associated with the derivative of the function. Using this result, we identify several classes of cubic semi-bent Boolean functions which have good bounds on their SSMI and MI, and hence show good behaviour with respect to the GAC.     

Equivalent logic programs and symmetric homogeneous forms of logic programs with equality

This article introduces the notion of CAS-equivalent logic programs: logic programs with identical correct answer substitutions. It is shown that the notions CAS-equivalence, refutational equivalence, and logical equivalence do not coincide in the case of definite clause logic programs. Least model criteria for refutational and CAS-equivalence are suggested and their correctness is proved. The least model approach is illustrated by two proofs of CAS-equivalence. It is shown that the symmetric extension of a logic program subsumes the symmetry axiom and the symmetric homogeneous form of a logic program with equality subsumes the symmetry, transitivity, and predicate substitutivity axioms of equality. These results contribute towards the goal of building equality into standard Prolog without introducing additional inference rules.     

A template-based approach for the generation of abstractable and reducible models of featured networks

We investigate the relationship between symmetry reduction and inductive reasoning when applied to model checking networks of featured components. Popular reduction techniques for combatting state space explosion in model checking, like abstraction and symmetry reduction, can only be applied effectively when the natural symmetry of a system is not destroyed during specification. We introduce a property which ensures this is preserved, open symmetry. We describe a template-based approach for the construction of open symmetric Promela specifications of featured systems. For certain systems (safely featured parameterised systems) our generated specifications are suitable for conversion to abstract specifications representing any size of network. This enables feature interaction analysis to be carried out, via model checking and induction, for systems of any number of featured components. In addition, we show how, for any balanced network of components, by using a graphical representation of the features and the process communication structure, a group of permutations of the underlying state space of the generated specification can be determined easily. Due to the open symmetry of our Promela specifications, this group of permutations can be used directly for symmetry reduced model checking.The main contributions of this paper are an automatic method for developing open symmetric specifications which can be used for generic feature interaction analysis, and the novel application of symmetry detection and reduction in the context of model checking featured networks.We apply our techniques to a well known example of a featured network – an email system.     

On the constructive orbit problem

Symmetry reduction techniques aim to combat the state-space explosion problem for model checking by restricting search to representative states from equivalence classes with respect to a group of symmetries. The standard approach to representative computation involves converting a state to its minimal image under a permutation group G, before storing the state. This is known as the constructive orbit problem (COP), and is NP{\mathit{NP}} hard. It may be possible to solve the COP efficiently if G is known to have certain structural properties: in particular if G is isomorphic to a full symmetry group, or G is a disjoint/wreath product of subgroups. We extend existing results on solving the COP efficiently for fully symmetric groups, and investigate the problem of automatically classifying an arbitrary permutation group as a disjoint/wreath product of subgroups. We also present an approximate COP strategy based on local search, and some computational group-theoretic optimisations to improve the basic approach of solving the COP by symmetry group enumeration. Experimental results using the TopSPIN symmetry reduction package, which interfaces with the computational group-theoretic system GAP, illustrate the effectiveness of our techniques.     

A transformation algorithm for incompatible information systems based on variable precision values

The variable precision rough set (VPRS) model extends the basic rough set (RS) theory with finite uni- verses and finite evaluative measures. VPRS is concerned with the equivalence and the contained relationship between two sets. In incompatible information systems, the inclusion degree and β upper (lower) approximation of the inconsistent equivalence class to the decision equivalence classes may be affected by the variable precision. The analysis of an example of incompatible decision table shows that there is a critical point in β available-values region. In the new β range limited at the critical point, the incompatible decision table can be converted to the coordination decision table reliably. The method and its algorithm implement are introduced for the critical value search. The examples of the inconsistent equivalence class transformation are exhibited. The results illustrate that this algorithm is rational and precise.     

On partitions of functions on finite sets

Let D and R be finite sets with cardinality n and m respectivelyR ^D be the set of all functions from D into R, and G and H be permutation groups acting on D and R respectively. Two functions f and g in R ^D are said to be related if there exists a σ in G and a τ in H with f(σd) = τg(d) for every d in D. Since the relation is an equivalence relation, R ^D is partitioned into disjoint classes. Roughly, by using the cycle indices of G and H, de Bruijn's theorem determines the number of equivalence classes, and Pólya's theorem, with H being the identity group, gives the function counting series, Pólya-de Bruijn's theorem has many applications (for instance, see Pólya and Read [6]). The theorem and its applications, basically, centered around the partitions of functions. Here, we present an algorithm to determine which functions in R ^D belong to the same equivalent class. Our algorithm does not use the cycle indices of G and H (to compute the cycle index of a given group, in general, is difficult), but it uses the generators of G and H, and the m-nary numbers to code the functions in R ^D . Our algorithm also gives the function counting series and the number of equivalence classes. An important application is that for each positive integer n, we use our algorithm and the symmetric group S _n to determine all isomorphic and nonisomorphic graphs and directed graphs with n vertices.     

Milne’s volume function and vector symmetric polynomials

The number of real roots of a system of polynomial equations fitting inside a given box can be counted using a vector symmetric polynomial introduced by P. Milne, the volume function. We provide the expansion of Milne’s volume function in the basis of monomial vector symmetric functions, and observe that only monomial functions of a particular kind appear in the expansion, the squarefree monomial functions.     

A Control Theory for Boolean Monomial Dynamical Systems

Recently criteria for determining when a certain type of nonlinear discrete dynamical system is a fixed point system have been developed. This theory can be used to determine if certain events modeled by those systems reach a steady state. In this work we formalize the idea of a “stabilizable” discrete dynamical system. We present necessary and sufficient conditions for a Boolean monomial dynamical control system to be stabilizable in terms of properties of the dependency graph associated with the system. We use the equivalence of periodicity of the dependency graph and loop numbers to develop a new O(n ²logn) algorithm for determining the loop numbers of the strongly connected components of the dependency graph, and hence a new O(n ²logn) algorithm for determining when a Boolean monomial dynamical system is a fixed point system. Finally, we show how this result can be used to determine if a Boolean monomial dynamical control system is stabilizable in time O(n ²logn).     

Complexity theoretic hardness results for query learning

We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general technique for proving hardness results for learning with membership and equivalence queries (and for more general query models). We apply the technique to show that, assuming , no polynomial-time membership and (proper) equivalence query algorithms exist for exactly learning read-thrice DNF formulas, unions of halfspaces over the Boolean domain, or some other related classes. Our hardness results are representation dependent, and do not preclude the existence of representation independent algorithms.?The general technique introduces the representation problem for a class F of representations (e.g., formulas), which is naturally associated with the learning problem for F. This problem is related to the structural question of how to characterize functions representable by formulas in F, and is a generalization of standard complexity problems such as Satisfiability. While in general the representation problem is in , we present a theorem demonstrating that for "reasonable" classes F, the existence of a polynomial-time membership and equivalence query algorithm for exactly learning F implies that the representation problem for F is in fact in co-NP. The theorem is applied to prove hardness results such as the ones mentioned above, by showing that the representation problem for specific classes of formulas is NP-hard. Received: December 6, 1994     

一些非一次相关置换和对合的产生方法

本文讨论非一次相关置换和对合的产生问题.对于置换，首先给出了由给定置换进行仿射变换产生一类相关次数相同置换的方法，然后给出了由低维非一次相关置换递归产生高维非一次相关置换的方法，并估计了这些方法产生的置换个数.对于对合，给出了一个从特定非一次相关对合的不动点上构作不相交p-组产生非一次相关对合的方法，并估计出一个对合个数的松下界.     

Analysis of affinely equivalent Boolean functions

By some basic transforms and invariant theory, we give two results: 1) an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.     

Conjugate symmetry

Conjugate symmetry is an entirely new approach to symmetric Boolean functions that can be used to extend existing methods for handling symmetric functions to a much wider class of functions. These are functions that currently appear to have no symmetries of any kind. Conjugate symmetries occur widely in practice. In fact, we show that even the simplest circuits exhibit conjugate symmetry. To demonstrate the effectiveness of conjugate symmetry we modify an existing simulation algorithm, the hyperlinear algorithm, to take advantage of conjugate symmetry. This algorithm can simulate symmetric functions faster than non-symmetric ones, but due to the rarity of symmetric functions, this optimization is of limited benefit. Because the standard benchmark circuits contain many symmetries it is possible to simulate these circuits faster than is possible with the fastest known event-driven algorithm. The detection and exploitation of conjugate symmetries makes use of GF(2) matrices. It is likely that conjugate symmetry and GF(2) matrices will find applications in many other areas of EDA.     

How to calculate symmetries of Petri nets

Symmetric net structure yields symmetric net behaviour. Thus, knowing the symmetries of a net, redundant calculations can be skipped. We present a framework for the calculation of symmetries for several net classes including place/transition nets, timed nets, stochastic nets, self–modifying nets, nets with inhibitor arcs, and many others. Our approach allows the specification of different symmetry groups. Additionally it provides facilities either to calculate symmetries on demand while running the actual analysis algorithm, or to calculate them in advance. For the latter case we define and calculate a ground set of symmetries. Such a set has polynomial size and is sufficient for an efficient implementation of the for all symmetries loop and the partition of net elements into equivalence classes. These two constructions are the usual way to integrate symmetries into an analysis algorithm. Received 7 July 1997 / 10 August 1999     

Solving Third Order Differential Equations with Maximal Symmetry Group

The largest group of Lie symmetries that a third-order ordinary differential equation (ode) may allow has seven parameters. Equations sharing this property belong to a single equivalence class with a canonical representative v ^′′′(u)=0. Due to this simple canonical form, any equation belonging to this equivalence class may be identified in terms of certain constraints for its coefficients. Furthermore a set of equations for the transformation functions to canonical form may be set up for which large classes of solutions may be determined algorithmically. Based on these steps a solution algorithm is described for any equation with this symmetry type which resembles a similar scheme for second order equations with projective symmetry group. Received March 9, 2000; revised June 8, 2000     

Algorithm 19 step-cycle generation

For given integerm>1, each step-cycle corresponds to a set of permutations such that the step-cycles constitute a set of equivalence classes on the set of all permutations onm elements. The algorithm has been used in connection with computations to search for groups consisting of a union of disjoint sets of permutations such that each set of permutations corresponds to a step-cycle, see [2] and [8].