Synthesizing optimal switching lattices

Graeme Gange, Harald Søndergaard, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

20 Citations (Scopus)


The use of nanoscale technologies to create electronic devices has revived interest in the use of regular structures for defining complex logic functions. One such structure is the switching lattice, a two-dimensional lattice of four-terminal switches. We show how to directly construct switching lattices of polynomial size from arbitrary logic functions; we also show how to synthesize minimal-sized lattices by translating the problem to the satisfiability problem for a restricted class of quantified Boolean formulas. The synthesis method is an anytime algorithm that uses modern SAT solving technology and dichotomic search. It improves considerably on an earlier proposal for creating switching lattices for arbitrary logic functions.

Original languageEnglish
Article number6
Number of pages14
JournalACM Transactions on Design Automation of Electronic Systems
Issue number1
Publication statusPublished - Nov 2014
Externally publishedYes


  • Logic synthesis
  • SAT
  • Switching lattice

Cite this