Boolean functional synthesis: hardness and practical algorithms

DOI10.1007/S10703-020-00352-2OpenAlexMaRDI QIDQ2050108FDO

Authors S. Akshay, Supratik Chakraborty, Shubham Goel, Sumith Kulal, Shetal Shah

Publication date 30 August 2021

Published in Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10703-020-00352-2

zbMATH Keywords

Skolem functionsBoolean functional synthesisexpansion-based algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• What's hard about Boolean functional synthesis?
• Towards Parallel Boolean Functional Synthesis
• BDD-based Boolean functional synthesis
• Lazy but effective functional synthesis
• SAT-Based Synthesis Methods for Safety Specs

Cites work

• scientific article; zbMATH DE number 3062907 (Why is no real title available?)
• BDD-based Boolean functional synthesis
• Boolean unification - the story so far
• Decomposable negation normal form
• Graph-Based Algorithms for Boolean Function Manipulation
• Incremental determinization
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• On the complexity of Boolean unification
• On the complexity of \(k\)-SAT
• Parametric solutions of Boolean equations
• Quantifier Elimination via Functional Composition
• The exponential time hypothesis and the parameterized clique problem
• Towards Parallel Boolean Functional Synthesis
• Turing machines that take advice
• Understanding and extending incremental determinization for 2QBF
• Unification in Boolean rings and Abelian groups
• Unified QBF certification and its applications

Cited in

(16)

• Functional synthesis via input-output separation
• What's hard about Boolean functional synthesis?
• scientific article; zbMATH DE number 3394051 (Why is no real title available?)
• Bridging Boolean and quantitative synthesis using smoothed proof search
• Asymptotically best method for synthesis of Boolean recursive circuits
• scientific article; zbMATH DE number 1775052 (Why is no real title available?)
• Set-theoretical Constructions of Boolean Functions and theirs Applications in Logic Synthesis
• Boolean functional synthesis: from under the hood of solvers
• scientific article; zbMATH DE number 6679846 (Why is no real title available?)
• Counterexample guided knowledge compilation for Boolean functional synthesis
• ZDD Boolean synthesis
• Towards Parallel Boolean Functional Synthesis
• Algorithms for synthesis of polynomials implementing weakly specified Boolean functions and systems
• BDD-based Boolean functional synthesis
• Tractable representations for Boolean functional synthesis
• Lazy but effective functional synthesis

Describes a project that uses

Uses Software

• ABC
• CAQE
• GitHub

This page was built for publication: Boolean functional synthesis: hardness and practical algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2050108)