Publications associées à On the Number of Containments in P-free Families

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

The Complexity of Self-Dual Monotone 7-Input Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa, Winston Jason Haaswijk

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 i ...

2019

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa

The equivalence of Boolean functions with respect to five invariance (aka translation) operations has been well considered with respect to the Rademacher-Walsh spectral domain. In this paper, we introduce a hybrid approach that uses both the Reed-Muller an ...

IEEE2019

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

Almost tiling of the Boolean lattice with copies of a poset

Istvan Tomon

Let P be a partially ordered set. If the Boolean lattice (2[n],⊂) can be partitioned into copies of P for some positive integer n, then P must satisfy the following two trivial conditions: (1) the size of P is a power of 2, (2) P has a unique maximal and m ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Functional Decomposition Using Majority

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such decomp ...

ASSOC COMPUTING MACHINERY2018

Functional Decomposition Using Majority

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

IEEE2018

A Novel Basis for Logic Rewriting

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Winston Jason Haaswijk

Given a set of logic primitives and a Boolean function, exact synthesis finds the optimum representation (e.g., depth or size) of the function in terms of the primitives. Due to its high computational complexity, the use of exact synthesis is limite ...

Ieee2017

Heuristic NPN classification for large functions using AIGs and LEXSAT

Giovanni De Micheli, Paolo Ienne, Mathias Soeken, Ana Petkovska

Two Boolean functions are NPN equivalent if one can be ob- tained from the other by negating inputs, permuting inputs, or negating the output. NPN equivalence is an equivalence relation and the number of equivalence classes is significantly smaller than th ...

Springer Int Publishing Ag2016

On the Number of Containments in P-free Families

Graph Chatbot

Chattez avec Graph Search

The Complexity of Self-Dual Monotone 7-Input Functions

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Forbidden induced subposets of given height

A proof of a sumset conjecture of Erdős

Almost tiling of the Boolean lattice with copies of a poset

Functional Decomposition Using Majority

Functional Decomposition Using Majority

The Myers-Steenrod Theorem For Finsler Manifolds Of Low Regularity

A Novel Basis for Logic Rewriting

Heuristic NPN classification for large functions using AIGs and LEXSAT

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Functional Decomposition Using Majority

The Myers-Steenrod Theorem For Finsler Manifolds Of Low Regularity

A proof of a sumset conjecture of Erdős

The Complexity of Self-Dual Monotone 7-Input Functions

Almost tiling of the Boolean lattice with copies of a poset

Forbidden induced subposets of given height

Functional Decomposition Using Majority

A Novel Basis for Logic Rewriting

Heuristic NPN classification for large functions using AIGs and LEXSAT