Booléen | EPFL Graph Search

vignette|George Boole (1864-1865) L'homme ayant mis en place la première structure algébrique utilisée en logique mathématique, en informatique et en électronique. En programmation informatique, un booléen est un type de variable à deux états (généralement notés vrai et faux), destiné à représenter les valeurs de vérité de la logique et l'algèbre booléenne. Il est nommé ainsi d'après George Boole, fondateur dans le milieu du de l'algèbre portant son nom. Le type de données booléen est principalement associé à des états conditionnels. C'est un cas particulier du type de données logique, la logique n'étant pas toujours de type booléen. Généralités Dans les langages de programmation avec un type de données booléen, comme le Pascal ou le Java, les opérateurs de comparaison tels que > et ≠ sont généralement définis pour retourner une valeur booléenne. Les structures conditionnelles et itératives peuvent être définies afin de tester des expressions booléennes. Les langages sans

The use of Boolean concepts in general classification contexts

Luis Miguel Moreira

Data classification, in the present context, concerns the use of computers in order to create systems that learn how to automatically decide to which of a predefined set of classes a given object belongs. Boolean concepts have long been present in data classification, and still are today, at various levels. We consider a kind of Boolean elements, called patterns, which consist of specific conjunctions of Boolean facts. Assuming the existence of two classes of objects, the positive and the negative, patterns can be expressed as conditionals of the type "If A and B and not C, then positive", where A, B, and C are Boolean values, each associated with a specific attribute describing the objects to be classified. From the classification system point of view, patterns are basic Boolean expressions that can be processed in a purely mathematical manner. However, if the values of the conjunction have an intuitive meaning, then this type of representation provides an intuitive perspective of the classification system, which can be interpreted by humans. The use of sets of patterns for building classification systems is justified by the fact that certain conjunctions of the type described above are matched by objects of one class but not by those of the other class. In this sense, patterns possess distinguishing properties that can be used to determine whether an object belongs to a class (if it matches certain patterns) or not. In this thesis, we consider the use of classification systems based on patterns, which we have seen to be inherently Boolean, in the context of classification tasks where nothing is Boolean, that is to say, where the objects are described by multi-valued or continuous attributes and instead of a positive/negative decision, suitable to situations where only two classes are involved, the output is rather the selection of a class among several. The work presented here extends along different directions. It starts by the study of a suitable way of transforming the attributes describing the objects to be classified into equivalent Boolean attributes. We describe the constraints that must be satisfied by this transformation and present a procedure allowing it to be done in a short amount of time. Another research direction explores the possibility of generating multi-class divisions with systems whose output is Boolean. This study has the benefit of also being applicable to other types of classification systems adapted to two-class situations, but whose internal language is not necessarily Boolean. This is the case of some current state-of-the-art systems. To realize this adaptation, the common approach consists in decomposing the original problem into several two-class sub-problems and generating an independent classification system to solve each one of them. The final class decision is obtained from the combination of the partial Boolean decisions. We analyze and compare several existing procedures for this purpose, and in addition propose an interesting new procedure. Finally, we consider the possibility of sharing patterns among several classes and develop a Boolean-based classification system which is directly adapted to multi-class problems, but maintaining the property of being understandable by humans. We show that the performance of this type of system is not in all cases comparable to the best available systems, but they have the advantage of providing, in certain circumstances, a better understanding of the problem at hand.

EPFL2000

Miniboxing: An Encoding for Specialization

Cristian Talau

In the presence of parametric polymorphism, erasure-based languages such as Java and Scala handle primitives (boolean values, integers and floating point numbers) in a suboptimal way: in order to provide a uniform representation on the low level, all primitive values are stored in heap objects, in a process known as boxing. This leads to access overheads, wasteful usage of the heap space and broken cache locality. Specialization enables Scala to optimally handle primitive values in the context of generic classes, but this is done at the expense of duplicating classes up to 10 times for each type parameter, for each of the 9 Scala primitive types and heap objects. This prevents specialization of key classes in the Scala library, such as Function2, List, Map and so on. This project aims at testing the hypothesis that encoding several primitive types into a larger stack-based primitive type can maintain the performance of specialized code, while dramatically decreasing the generated bytecode size.

2012

Algebraic and Boolean Optimization Methods for AQFP Superconducting Circuits

Giovanni De Micheli, Siang-Yun Lee, Heinz Riener, Eleonora Testa

Adiabatic quantum-flux-parametron (AQFP) circuits are a family of superconducting electronic (SCE) circuits that have recently gained growing interest due to their low-energy consumption, and may serve as alternative technology to overcome the down-scaling limitations of CMOS. The AQFP circuits logic design differs from classic digital design in many respects. For this reason, as of today, the design of AQFP complex circuits is still limited by the ability of design tools to efficiently take into account the different AQFP technology requirements. For instance, AQFP logic cells are abstracted by the majority operation, require data and clocking in specific timing windows and have fan-out limitations. In this work, we implement a novel majority-based logic synthesis flow addressing AQFP technology. In particular, we present both algebraic and Boolean methods over majority-inverter graphs (MIGs) aiming at optimizing size and depth of logic circuits. The technology limitations and constraints of the AQFP technology (e.g., path balancing and maximum fanout) are considered during the optimization steps. The experimental results show that our flow reduces both size and depth of MIGs, while meeting the constraint set by the AQFP technology. Further, we demonstrate an improvementfor both area and delay when the MIGs are mapped into the AQFP technology.

Association for Computing Machinery2021

The use of Boolean concepts in general classification contexts

Luis Miguel Moreira

EPFL2000