Displaying similar documents to “On the Influence of the State Encoding on OBDD-Representations of Finite State Machines”

On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Ordered binary decision diagrams (OBDDs) and several more general BDD models have turned out to be representations of Boolean functions which are useful in applications like verification, timing analysis, test pattern generation or combinatorial optimization. The hidden weighted bit function (HWB) is of particular interest, since it seems to be the simplest function with exponential OBDD size. The complexity of this function with respect to different circuit models, formulas,...

On maximal QROBDD's of Boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

On maximal QROBDD’s of boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

The Boolean space of higher level orderings

Katarzyna Osiak (2007)

Fundamenta Mathematicae

Similarity:

Let K be an ordered field. The set X(K) of its orderings can be topologized to make it a Boolean space. Moreover, it has been shown by Craven that for any Boolean space Y there exists a field K such that X(K) is homeomorphic to Y. Becker's higher level ordering is a generalization of the usual concept of ordering. In a similar way to the case of ordinary orderings one can define a topology on the space of orderings of fixed exact level. We show that it need not be Boolean. However, our...

Algorithms for Computing the Linearity and Degree of Vectorial Boolean Functions

Bouyuklieva, Stefka, Bouyukliev, Iliya (2016)

Serdica Journal of Computing

Similarity:

In this article, we study two representations of a Boolean function which are very important in the context of cryptography. We describe Möbius and Walsh Transforms for Boolean functions in details and present effective algorithms for their implementation. We combine these algorithms with the Gray code to compute the linearity, nonlinearity and algebraic degree of a vectorial Boolean function. Such a detailed consideration will be very helpful for students studying the design of block...

Local Boolean manifolds from knowledge representation systems.

Gianpiero Cattaneo (1996)

Mathware and Soft Computing

Similarity:

We introduce a structure to represent observations on entities in order to obtain knowledge about some of their characteristic properties or attributes. This structure is based on the Pawlak's definition of information systems (also knowledge representation systems) and lead us to obtain algebraic structures of lattice depending from the choice of an observational context. The semantical algebraic structure so obtained is of local Boolean manifold whose global structure is an orthoposet...