On the efficiency of normal form systems for representing Boolean functions

DOI10.1016/j.tcs.2020.01.009zbMath1481.06031OpenAlexW3000194050WikidataQ126343109 ScholiaQ126343109MaRDI QIDQ1989340

Romain Péchoux, Erkko Lehtonen, Pierre Mercuriali, Miguel Couceiro

Publication date: 21 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02153506/file/TCS_HAL_CLMP.pdf

zbMATH Keywords

complexityBoolean functionefficient representationnormal-form system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Related Items (1)

Unnamed Item

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Galois theory for sets of operations closed under permutation, cylindrification, and composition
• Decompositions of functions based on arity gap
• Composition of Post classes and normal forms of Boolean functions
• Weighted lattice polynomials
• Size-depth tradeoffs for Boolean formulae
• Post classes characterized by functional terms
• Essential arities of term operations in finite algebras
• Alternation
• Function Algebras on Finite Sets
• The complexity of satisfiability problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: On the efficiency of normal form systems for representing Boolean functions