Boolean functional synthesis: hardness and practical algorithms

DOI10.1007/s10703-020-00352-2OpenAlexW3093494889MaRDI QIDQ2050108

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

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)

Related Items

Boolean functional synthesis: from under the hood of solvers

Uses Software

• ABC
• GitHub
• CAQE

Cites Work

• Unnamed Item
• On the complexity of Boolean unification
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Unification in Boolean rings and Abelian groups
• Turing machines that take advice
• Boolean unification - the story so far
• Unified QBF certification and its applications
• Parametric solutions of Boolean equations
• Incremental Determinization
• Towards Parallel Boolean Functional Synthesis
• Quantifier Elimination via Functional Composition
• Graph-Based Algorithms for Boolean Function Manipulation
• BDD-Based Boolean Functional Synthesis
• The Exponential Time Hypothesis and the Parameterized Clique Problem
• Decomposable negation normal form
• On the complexity of \(k\)-SAT
• Understanding and extending incremental determinization for 2QBF