Embedding Sequential Circuits for their Polynomial Formal Verification

As digital circuits are at the core of most of our everyday technologies, society heavily relies on their precise and predictable behavior. However, this demand for correctness often clashes with the speed of today's design workflows. Whereas a design can be proven to be free of errors based on formal methods, the required time and memory resources of this can often not be predicted. This conflict is addressed by Polynomial Formal Verification (PFV): By selecting adequate data structures and verification techniques, polynomial resource bounds can be proven for the entire procedure so that an efficient verification is guaranteed.

This book adds to this field by applying PFV to circuits with storage elements, also known as sequential circuits. Counter circuits are verified using a polynomial number of steps, even though they have an exponential sequential depth. This is addressed from a theoretical and from a practical point of view.

Autorentext

Caroline Dominik is a doctoral researcher at the Group of Computer Architecture (AGRA) at the University of Bremen, with a research focus on self-explaining cyber-physical systems. She completed her Master's degree in Computer Science in December 2024.

Inhalt

Introduction.- Polynomial Formal Verification.- Preliminaries.- Verification of Full Counter Circuits.- Verification of Modulo Counter Circuits.- Experimental Results.- Conclusion.