Skolem and Herbrand functions are important certificates validating the truth and falsity, respectively, of quantified Boolean formulas (QBFs). They are essential in various synthesis and verification applications. Recent advancement established a linear time extraction of Skolem/Herbrand functions from QBF consensus/resolution proofs. However, the obtained functions are often excessively large and improper for practical applications. To overcome this limitation, this paper characterizes various flexibilities of QBF certificates, and exploits them for certificate simplification. Experiments show substantial reduction on QBF certificates in terms of circuit size and depth, which are of primary concerns for synthesis applications.

Testing integrated circuits under delay defects becomes an essential quality control step in nanometer fabrication technologies, which encounter inevitable process variations. Prior methods on automatic test pattern generation (ATPG) for delay defects, however, are either overly simplified (e.g., timing unaware) or computationally too expensive. This paper proposes a viable ATPG method based on a satisfiability (SAT) formulation using timed characteristic functions (TCFs), which gained notable scalability enhancement very recently. The approach provides a balanced trade-off between accuracy and efficiency. Experimental results show promising runtime and fault coverage improvements over prior SAT-based timing-aware ATPG methods. Moreover, our method provides a nice complement to commercial tools in enhancing test quality.

Due to the ever-increasing complexity of system design, it becomes not uncommon for some design error escaping all verification efforts and settling in final silicon realization. As hardware-based fixing is much more expensive than software-based fixing, this paper proposes a methodology as a first step toward generating software workarounds for erroneous processor designs. A generic formulation is introduced based on Skolem and Herbrand function extraction from quantified Boolean formula solving; reduction techniques are devised to further enhance practicality. Thereby, a program can be recompiled at the assembly code level for correct execution on a buggy processor. Experimental results show the feasibility of the proposed method.