Boolean functional synthesis: hardness and practical algorithms

DOI10.1007/S10703-020-00352-2MaRDI QIDQ2050108zbMATH OpenOpenAlexFDO

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

(17)

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

Describes a project that uses

Uses Software

• GitHub
• CAQE
• ABC

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)