Boolean functional synthesis: hardness and practical algorithms

DOI10.1007/S10703-020-00352-2OpenAlexW3093494889MaRDI QIDQ2050108FDOQ2050108

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

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

zbMATH Keywords

Skolem functionsBoolean functional synthesisexpansion-based algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

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

Cited In (12)

• Towards Parallel Boolean Functional Synthesis
• Title not available (Why is that?)
• What's hard about Boolean functional synthesis?
• 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
• Asymptotically best method for synthesis of Boolean recursive circuits
• Title not available (Why is that?)
• Boolean functional synthesis: from under the hood of solvers
• Title not available (Why is that?)
• Counterexample guided knowledge compilation for Boolean functional synthesis
• Bridging Boolean and quantitative synthesis using smoothed proof search

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)