Reichl, F.-X., Slivovsky, F., & Szeider, S. (2023). Circuit Minimization with QBF-Based Exact Synthesis. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (pp. 4087–4094). AAAI Press. https://doi.org/10.1609/aaai.v37i4.25524
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Proceedings of the 37th AAAI Conference on Artificial Intelligence
-
ISBN:
978-1-57735-880-0
-
Volume:
37
-
Date (published):
2023
-
Event name:
The 37th AAAI Conference on Artificial Intelligence (AAAI -23)
en
Event date:
7-Feb-2023 - 14-Feb-2023
-
Event place:
Washington DC, United States of America (the)
-
Number of Pages:
8
-
Publisher:
AAAI Press, Washington DC
-
Peer reviewed:
Yes
-
Keywords:
Satisfiability; APP: Design; Boolean circuits
en
Abstract:
This paper presents a rewriting method for Boolean circuits that minimizes small subcircuits with exact synthesis. Individual synthesis tasks are encoded as Quantified Boolean Formulas (QBFs) that capture the full flexibility for implementing multi-output subcircuits. This is in contrast to SAT-based resynthesis, where "don't cares" are computed for an individual gate, and replacements are confined to the circuitry used exclusively by that gate. An implementation of our method achieved substantial size reductions compared to state-of-the-art methods across a wide range of benchmark circuits.
en
Project (external):
Vienna Science and Technology Fund (WWTF) Austrian Science Fund (FWF) Austrian Science Fund (FWF)
