Publications related to Complete Boolean algebra

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

IEEE2024

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Mario Bucev, Dragana Milovancevic

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

Three-Input Gates for Logic Synthesis

Giovanni De Micheli, Mathias Soeken, Dewmini Sudara Marakkalage, Eleonora Testa, Heinz Riener

Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Forbidden induced subposets of given height

Istvan Tomon

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) su ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

On the Number of Containments in P-free Families

Abhishek Methuku

A subfamily {F-1, F-2, ..., F-vertical bar P vertical bar} subset of F is a copy of the poset P if there exists a bijection i : P -> {F-1, F-2, ..., F-vertical bar P vertical bar}, such that p

Springer2019

Unique decomposition of homogeneous languages and application to isothetic regions

Nicolas René Jean Ninin

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of ho ...

2019

The Myers-Steenrod Theorem For Finsler Manifolds Of Low Regularity

Marc Troyanov

We prove a version of Myers-Steenrod's theorem for Finsler manifolds under the minimal regularity hypothesis. In particular we show that an isometry between C-k,C-alpha-smooth (or partially smooth) Finsler metrics, with k + alpha > 0, k is an element of N ...

Amer Mathematical Soc2017

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Giovanni De Micheli, Mathias Soeken

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Ieee2017

Majority-Inverter Graph: A New Paradigm for Logic Optimization

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

In this paper, we propose a paradigm shift in representing and optimizing logic by using only majority (MAJ) and inversion (INV) functions as basic operations. We represent logic functions by Majority-Inverter Graph (MIG): a directed acyclic graph c ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Modelling Architecture Styles

Anastasia Mavridou

Software systems tend to increase over time in size and complexity. Their development usually spans a long period of time and often results in systems that are hard to understand, debug and maintain. Architectures are common means for organising coordinati ...

EPFL2016

Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

In this paper, we present Majority-Inverter Graph (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented e ...

2014

Redox properties of cobalt(II) complexes with azole-pyridines

Michael Graetzel, Mohammad Khaja Nazeeruddin

We report nine new homoleptic octahedral cobalt(II) complexes Co((NN)-N-boolean AND)(3) and Co((NNN)-N-boolean AND-N-boolean AND)(2) with bidentate or tridentate azole-pyridine ligands (where azole is 1,2,4-triazole or a substituted pyrazole). ...

Elsevier2013

Steric hindrance at metal centre quenches green phosphorescence of cationic iridium(III) complexes with 1-(2-pyridyl)-pyrazoles

Michael Graetzel, Mohammad Khaja Nazeeruddin, Rosario Scopelliti

Cationic cyclometalated iridium(III) complexes (N,C-2'-2-phenylpyridyl)(2)Ir((NN)-N-boolean AND) with alkyl-substituted 1-(2'-pyridyl)-pyrazole (NN)-N-boolean AND ligands exhibit green phosphorescence from a cyclometalating-ligand-centered excited s ...

Elsevier2013

Extreme Tuning of Redox and Optical Properties of Cationic Cyclometalated Iridium(III) Isocyanide Complexes

Michael Graetzel, Mohammad Khaja Nazeeruddin, Rosario Scopelliti

We report seven heteroleptic cationic iridium(III) complexes with cyclometalating N-arylazoles and alkyl/aryl isocyanides, ((CN)-N-boolean AND)(2)Ir(CNR)(2), and characterize two of them by crystal structure analysis. The complexes are air- and m ...

American Chemical Society2013

Near-UV to red-emitting charged bis-cyclometallated iridium(III) complexes for light-emitting electrochemical cells

Michael Graetzel, Mohammad Khaja Nazeeruddin, Rosario Scopelliti, Davide Di Censo

Herein we report a series of charged iridium complexes emitting from near-UV to red using carbene-based (NC)-C-boolean AND: ancillary ligands. Synthesis, photophysical and electrochemical properties of this series are described in detail together with X-ra ...

Royal Society of Chemistry2012

Sets with Cardinality Constraints in Satisfiability Modulo Theories

Viktor Kuncak, Philippe Paul Henri Suter, Robin Steiger

Boolean Algebra with Presburger Arithmetic (BAPA) is a decidable logic that can express constraints on sets of elements and their cardinalities. Problems from verification of complex properties of software often contain fragments that belong to quantifier- ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

A Global Version Of The Darboux Theorem With Optimal Regularity And Dirichlet Condition

Bernard Dacorogna, Olivier Kneuss

Let n > 2 be even; r >= 1 be an integer; 0 < alpha < 1; Omega be a bounded, connected, smooth, open set in R-n; and nu be its exterior unit normal. Let f, g is an element of C-r,C-alpha((Omega) over bar; Lambda(2)) be two symplectic forms (i.e., closed and ...

2011

Overlap properties of geometric expanders

The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) is an element of (0, 1] such that no matter how we map the vertices of H into R-d, there is a point covered by at least a c(H)-fraction of the simplices induced by the ...

De Gruyter2011

Ordered Sets in the Calculus of Data Structures

Viktor Kuncak, Philippe Paul Henri Suter, Ruzica Piskac

Our goal is to identify families of relations that are useful for reasoning about software. We describe such families using decidable quantifier-free classes of logical constraints with a rich set of operations. A key challenge is to define such classes of ...

Springer2010