Synthesizing multiple boolean functions using interpolation on a single proof

G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, R. Bloem, in:, 2013 Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 77–84.


Conference Paper | Published | English
Author
; ; ; ;
Department
Abstract
It is often difficult to correctly implement a Boolean controller for a complex system, especially when concurrency is involved. Yet, it may be easy to formally specify a controller. For instance, for a pipelined processor it suffices to state that the visible behavior of the pipelined system should be identical to a non-pipelined reference system (Burch-Dill paradigm). We present a novel procedure to efficiently synthesize multiple Boolean control signals from a specification given as a quantified first-order formula (with a specific quantifier structure). Our approach uses uninterpreted functions to abstract details of the design. We construct an unsatisfiable SMT formula from the given specification. Then, from just one proof of unsatisfiability, we use a variant of Craig interpolation to compute multiple coordinated interpolants that implement the Boolean control signals. Our method avoids iterative learning and back-substitution of the control functions. We applied our approach to synthesize a controller for a simple two-stage pipelined processor, and present first experimental results.
Publishing Year
Date Published
2013-12-11
Proceedings Title
2013 Formal Methods in Computer-Aided Design
Acknowledgement
This research was supported by the European Commission through project DIAMOND (FP7-2009-IST-4-248613), and QUAINT (I774-N23),
Page
77 - 84
Conference
FMCAD: Formal Methods in Computer-Aided Design
Conference Location
Portland, OR, United States
Conference Date
2013-10-20 – 2013-10-23
IST-REx-ID

Cite this

Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. Synthesizing multiple boolean functions using interpolation on a single proof. In: 2013 Formal Methods in Computer-Aided Design. IEEE; 2013:77-84. doi:10.1109/FMCAD.2013.6679394
Hofferek, G., Gupta, A., Könighofer, B., Jiang, J., & Bloem, R. (2013). Synthesizing multiple boolean functions using interpolation on a single proof. In 2013 Formal Methods in Computer-Aided Design (pp. 77–84). Portland, OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679394
Hofferek, Georg, Ashutosh Gupta, Bettina Könighofer, Jie Jiang, and Roderick Bloem. “Synthesizing Multiple Boolean Functions Using Interpolation on a Single Proof.” In 2013 Formal Methods in Computer-Aided Design, 77–84. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679394.
G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, and R. Bloem, “Synthesizing multiple boolean functions using interpolation on a single proof,” in 2013 Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013, pp. 77–84.
Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. 2013. Synthesizing multiple boolean functions using interpolation on a single proof. 2013 Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design 77–84.
Hofferek, Georg, et al. “Synthesizing Multiple Boolean Functions Using Interpolation on a Single Proof.” 2013 Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 77–84, doi:10.1109/FMCAD.2013.6679394.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1308.4767

Search this title in

Google Scholar