Página 1 dos resultados de 61 itens digitais encontrados em 0.002 segundos

Bent and generalized bent Boolean functions

Stanica, Pantelimon; Martinsen, Thor; Gangopadhyay, Sugata; Singh, Brajesh Kumar
Fonte: Escola de Pós-Graduação Naval Publicador: Escola de Pós-Graduação Naval
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
Mathematics Subject Classification (2000) 94A60 · 94C10 · 06E30; The article of record as published may be found at http://dx.doi.org/10.1007/s10623-012-9622-5;; In this paper, we investigate the properties of generalized bent functions defined on Zn2 with values in Zq, where q ≥ 2 is any positive integer. We characterize the class of generalized bent functions symmetric with respect to two variables, provide analogues of Maiorana–McFarland type bent functions and Dillon’s functions in the generalized set up. A class of bent functions called generalized spreads is introduced and we show that it contains all Dillon type generalized bent functions and Maiorana–McFarland type generalized bent functions. Thus, unification of two different types of generalized bent functions is achieved. The crosscorrelation spectrum of generalized Dillon type bent functions is also characterized. We further characterize generalized bent Boolean functions defined on Zn2 with values in Z4 and Z8. Moreover, we propose several constructions of such generalized bent functions for both n even and n odd.

Designing Parity Preserving Reversible Circuits

Paul, Goutam; Chattopadhyay, Anupam; Chandak, Chander
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/08/2013 Português
Relevância na Pesquisa
153.65469%
Making a reversible circuit fault-tolerant is much more difficult than classical circuit and there have been only a few works in the area of parity-preserving reversible logic design. Moreover, all of these designs are ad hoc, based on some pre-defined parity preserving reversible gates as building blocks. In this paper, we for the first time propose a novel and systematic approach towards parity preserving reversible circuits design. We provide some related theoretical results and give two algorithms, one from reversible specification to parity preserving reversible specification and another from irreversible specification to parity preserving reversible specification. We also evaluate the effectiveness of our approach by extensive experimental results.

Counting polygon spaces, Boolean functions and majority games

Hausmann, Jean-Claude
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 29/01/2015 Português
Relevância na Pesquisa
153.65469%
We explain why numbers occurring in the classification of polygon spaces coincide with numbers of self-dual equivalence classes of threshold functions, or of regular Boolean functions, or of decisive weighted majority games.; Comment: 13 pages

The inverse problem for power distributions in committees

Kurz, Sascha
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/02/2014 Português
Relevância na Pesquisa
153.65469%
Several power indices have been introduced in the literature in order to measure the influence of individual committee members on the aggregated decision. Here we ask the inverse question and aim to design voting rules for a committee such that a given desired power distribution is met as closely as possible. We present an exact algorithm for a large class of different power indices based on integer linear programming. With respect to negative approximation results we generalize the approach of Alon and Edelman who studied power distributions for the Banzhaf index, where most of the power is concentrated on few coordinates. It turned out that each Banzhaf vector of an n-member committee that is near to such a desired power distribution, has to be also near to the Banzhaf vector of a k-member committee. We show that such Alon-Edelman type results are possible for other power indices like e.g. the Public Good index or the Coleman index to prevent actions, while they are principally impossible for e.g. the Johnston index.; Comment: 46 pages, 2 tables

Octal Bent Generalized Boolean Functions

Stanica, Pante; Martinsen, Thor
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
In this paper we characterize (octal) bent generalized Boolean functions defined on $\BBZ_2^n$ with values in $\BBZ_8$. Moreover, we propose several constructions of such generalized bent functions for both $n$ even and $n$ odd.

The consistency, the composition and the causality of the asynchronous flows

Vlad, Serban E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/04/2015 Português
Relevância na Pesquisa
153.65469%
Let $\Phi:\{0,1\}^{n}\longrightarrow\{0,1\}^{n}$. The asynchronous flows are (discrete time and real time) functions that result by iterating the coordinates $\Phi_{i}$ independently on each other. The purpose of the paper is that of showing that the asynchronous flows fulfill the properties of consistency, composition and causality that define the dynamical systems. The origin of the problem consists in modelling the asynchronous circuits from the digital electrical engineering.; Comment: 9 pages, 2 figures

Trading inference effort versus size in CNF Knowledge Compilation

Gwynne, Matthew; Kullmann, Oliver
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
Knowledge Compilation (KC) studies compilation of boolean functions f into some formalism F, which allows to answer all queries of a certain kind in polynomial time. Due to its relevance for SAT solving, we concentrate on the query type "clausal entailment" (CE), i.e., whether a clause C follows from f or not, and we consider subclasses of CNF, i.e., clause-sets F with special properties. In this report we do not allow auxiliary variables (except of the Outlook), and thus F needs to be equivalent to f. We consider the hierarchies UC_k <= WC_k, which were introduced by the authors in 2012. Each level allows CE queries. The first two levels are well-known classes for KC. Namely UC_0 = WC_0 is the same as PI as studied in KC, that is, f is represented by the set of all prime implicates, while UC_1 = WC_1 is the same as UC, the class of unit-refutation complete clause-sets introduced by del Val 1994. We show that for each k there are (sequences of) boolean functions with polysize representations in UC_{k+1}, but with an exponential lower bound on representations in WC_k. Such a separation was previously only know for k=0. We also consider PC < UC, the class of propagation-complete clause-sets. We show that there are (sequences of) boolean functions with polysize representations in UC...

Secure pseudo-random linear binary sequences generators based on arithmetic polynoms

Finko, Oleg; Dichenko, Sergey
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/09/2014 Português
Relevância na Pesquisa
153.65469%
We present a new approach to constructing of pseudo-random binary sequences (PRS) generators for the purpose of cryptographic data protection, secured from the perpetrator's attacks, caused by generation of masses of hardware errors and faults. The new method is based on use of linear polynomial arithmetic for the realization of systems of boolean characteristic functions of PRS' generators. "Arithmetizatio" of systems of logic formulas has allowed to apply mathematical apparatus of residue systems for multisequencing of the process of PRS generation and organizing control of computing errors, caused by hardware faults. This has guaranteed high security of PRS generator's functioning and, consequently, security of tools for cryptographic data protection based on those PRSs.

On composition-closed classes of Boolean functions

Waldhauser, Tamás
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/02/2011 Português
Relevância na Pesquisa
153.65469%
We determine all composition-closed equational classes of Boolean functions. These classes provide a natural generalization of clones and iterative algebras: they are closed under composition, permutation and identification (diagonalization) of variables and under introduction of inessential variables (cylindrification), but they do not necessarily contain projections. Thus the lattice formed by these classes is an extension of the Post lattice. The cardinality of this lattice is continuum, yet it is possible to describe its structure to some extent.; Comment: 20 pages, 8 figures

Structure functions and minimal path sets

Marichal, Jean-Luc
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/01/2014 Português
Relevância na Pesquisa
153.65469%
We give and discuss a general multilinear expression of the structure function of an arbitrary semicoherent system in terms of its minimal path and cut sets. We also examine the link between the number of minimal path and cut sets consisting of 1 or 2 components and the concept of structural signature of the system.

Generalization of Boole-Shannon expansion, consistency of Boolean equations and elimination by orthonormal expansion

Sule, Virendra
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
The well known Boole-Shannon expansion of Boolean functions in several variables (with co-efficients in a Boolean algebra $B$) is also known in more general form in terms of expansion in a set $\Phi$ of orthonormal functions. However, unlike the one variable step of this expansion an analogous elimination theorem and consistency is not well known. This article proves such an elimination theorem for a special class of Boolean functions denoted $B(\Phi)$. When the orthonormal set $\Phi$ is of polynomial size in number $n$ of variables, the consistency of a Boolean equation $f=0$ can be determined in polynomial number of $B$-operations. A characterization of $B(\Phi)$ is also shown and an elimination based procedure for computing consistency of Boolean equations is proposed.; Comment: 16 pages, revised December 5, 2013

On Universal Complexity Measures

Scoville, John
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
We relate the computational complexity of finite strings to universal representations of their underlying symmetries. First, Boolean functions are classified using the universal covering topologies of the circuits which enumerate them. A binary string is classified as a fixed point of its automorphism group; the irreducible representation of this group is the string's universal covering group. Such a measure may be used to test the quasi-randomness of binary sequences with regard to first-order set membership. Next, strings over general alphabets are considered. The complexity of a general string is given by a universal representation which recursively factors the codeword number associated with a string. This is the complexity of the representation recursively decoding a Godel number having the value of the string; the result is a tree of prime numbers which forms a universal representation of the string's group symmetries.; Comment: The paper has been withdrawn due to the poor predictive performance of circuit complexity vs. universal data compression. Given this fact, as well as the high computational complexity, the method seems to have little practical utility

Computing subsignatures of systems with exchangeable component lifetimes

Marichal, Jean-Luc
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
The subsignatures of a system with continuous and exchangeable component lifetimes form a class of indexes ranging from the Samaniego signature to the Barlow-Proschan importance index. These indexes can be computed through explicit linear expressions involving the values of the structure function of the system. We show how the subsignatures can be computed more efficiently from the reliability function of the system via identifications of variables, differentiations, and integrations.

Network Throughput Optimization via Error Correcting Codes

Tomic, Ratko V.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/01/2013 Português
Relevância na Pesquisa
153.65469%
A new network construction method is presented for building of scalable, high throughput, low latency networks. The method is based on the exact equivalence discovered between the problem of maximizing network throughput (measured as bisection bandwidth) for a large class of practically interesting Cayley graphs and the problem of maximizing codeword distance for linear error correcting codes. Since the latter problem belongs to a more mature research field with large collections of optimal solutions available, a simple translation recipe is provided for converting the existent optimal error correcting codes into optimal throughput networks. The resulting networks, called here Long Hop networks, require 1.5-5 times fewer switches, 2-6 times fewer internal cables and 1.2-2 times fewer `average hops' than the best presently known networks for the same number of ports provided and the same total throughput. These advantage ratios increase with the network size and switch radix. Independently interesting byproduct of the discovered equivalence is an efficient O(n*log(n)) algorithm based on Walsh-Hadamard transform for computing exact bisections of this class of Cayley graphs (this is NP complete problem for general graphs).; Comment: 45 pages

Generalized cofactors and decomposition of Boolean satisfiability problems

Desai, Madhav; Sule, Virendra
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/12/2014 Português
Relevância na Pesquisa
153.65469%
We propose an approach for decomposing Boolean satisfiability problems while extending recent results of \cite{sul2} on solving Boolean systems of equations. Developments in \cite{sul2} were aimed at the expansion of functions $f$ in orthonormal (ON) sets of base functions as a generalization of the Boole-Shannon expansion and the derivation of the consistency condition for the equation $f=0$ in terms of the expansion co-efficients. In this paper, we further extend the Boole-Shannon expansion over an arbitrary set of base functions and derive the consistency condition for $f=1$. The generalization of the Boole-Shannon formula presented in this paper is in terms of \emph{cofactors} as co-efficients with respect to a set of CNFs called a \emph{base} which appear in a given Boolean CNF formula itself. This approach results in a novel parallel algorithm for decomposition of a CNF formula and computation of all satisfying assignments when they exist by using the given data set of CNFs itself as the base.; Comment: 13 pages

Affine equivalence of cubic homogeneous rotation symmetric Boolean functions

Cusick, Thomas W.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
Homogeneous rotation symmetric Boolean functions have been extensively studied in recent years because of their applications in cryptography. Little is known about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in 2009. This paper studies the much more complicated cubic case for such functions. A new concept of \emph{patterns} is introduced, by means of which the structure of the smallest group G_n, whose action on the set of all such cubic functions in $n$ variables gives the affine equivalence classes for these functions under permutation of the variables, is determined. We conjecture that the equivalence classes are the same if all nonsingular affine transformations, not just permutations, are allowed. This conjecture is verified if n < 22. Our method gives much more information about the equivalence classes; for example, in this paper we give a complete description of the equivalence classes when n is a prime or a power of 3.; Comment: This is the author's version of a manuscript which has been accepted by Information Sciences. The ancillary Mathematica file contains a program which computes the equivalence classes described in the paper...

Reliability of systems with dependent components based on lattice polynomial description

Dukhovny, Alexander; Marichal, Jean-Luc
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/04/2011 Português
Relevância na Pesquisa
153.65469%
Reliability of a system is considered where the components' random lifetimes may be dependent. The structure of the system is described by an associated "lattice polynomial" function. Based on that descriptor, general framework formulas are developed and used to obtain direct results for the cases where a) the lifetimes are "Bayes-dependent", that is, their interdependence is due to external factors (in particular, where the factor is the "preliminary phase" duration) and b) where the lifetimes' dependence is implied by upper or lower bounds on lifetimes of components in some subsets of the system. (The bounds may be imposed externally based, say, on the connections environment.) Several special cases are investigated in detail.

On $\alpha$-roughly weighted games

Freixas, Josep; Kurz, Sascha
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
Gvozdeva, Hemaspaandra, and Slinko (2011) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class $\mathcal{C}_\alpha$ consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least 1 and each losing coalition a weight of at most $\alpha$. For a given game the minimal possible value of $\alpha$ is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation beween this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered.; Comment: 26 pages, 4 tables

An Algebraic Framework for Discrete Tomography: Revealing the Structure of Dependencies

Stolk, Arjen; Batenburg, K. Joost
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
153.65469%
Discrete tomography is concerned with the reconstruction of images that are defined on a discrete set of lattice points from their projections in several directions. The range of values that can be assigned to each lattice point is typically a small discrete set. In this paper we present a framework for studying these problems from an algebraic perspective, based on Ring Theory and Commutative Algebra. A principal advantage of this abstract setting is that a vast body of existing theory becomes accessible for solving Discrete Tomography problems. We provide proofs of several new results on the structure of dependencies between projections, including a discrete analogon of the well-known Helgason-Ludwig consistency conditions from continuous tomography.; Comment: 20 pages, 1 figure, updated to reflect reader input

Universal regular autonomous asynchronous systems: omega-limit sets, invariance and basins of attraction

Vlad, Serban E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/12/2010 Português
Relevância na Pesquisa
153.65469%
The asynchronous systems are the non-deterministic real time-binary models of the asynchronous circuits from electrical engineering. Autonomy means that the circuits and their models have no input. Regularity means analogies with the dynamical systems, thus such systems may be considered to be the real time dynamical systems with a 'vector field' {\Phi}:{0,1}^2 \rightarrow {0,1}^2. Universality refers to the case when the state space of the system is the greatest possible in the sense of the inclusion. The purpose of the paper is that of defining, by analogy with the dynamical systems theory, the {\omega}-limit sets, the invariance and the basins of attraction of the universal regular autonomous asynchronous systems.; Comment: accepted to be published in Mathematics and its Applications/Annals of the Academy of the Romanian Scientists