Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Towards binary circuit models that faithfully reflect physical (un)solvability.
Speaker:Matthias Függer
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:Matthias Függer received his M.Sc. (2006) and his PhD (2010) in computer engineering from TU Wien, Austria. He is currently a post-doctoral researcher at LIX, Ecole polytechnique. His main research interest is the formal study of the fundamentals of computationally extremely restricted distributed devices manmade or models of natural systems). Specifically this includes (fault-tolerant) distributed algorithms in hardware and biology.
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Wednesday, 13 August 2014
Duration:30 Minutes
Building:E1 4
Binary circuit models are high-level abstractions intended to reflect

the behavior of digital circuits, while restricting signal values to 0
and 1. Such models play an important role in assessing the correctness
and performance characteristics of digital circuit designs: (i) modern
circuit design relies on fast digital timing simulation tools and,
hence, on accurate binary-valued circuit models that faithfully model
signal propagation, even throughout a complex design, and (ii) binary
circuit models provide a level of abstraction that is amenable to
formal analysis.

Of particular importance is the ability to trace glitches and other
short pulses, as their presence may affect a circuit's correctness and
its performance characteristics.

In this talk we first show that that no existing binary-valued circuit
model proposed so far faithfully captures glitch propagation.

We then propose a class of binary circuit models that do not suffer
from this deficiency: We prove that, in sharp contrast to what is
possible with classical models, the proposed circuit models allow to
solve the Short-Pulse Filtration (SPF) problem, which is related to a
circuit's ability to suppress a single glitch, precisely when this is
possible in physical circuits.

This renders them a promising candidate, both, for simulation and the
formal analysis of circuits.

Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Christoph Lenzen, 08/11/2014 10:41 AM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Christoph Lenzen, 08/11/2014 03:16 PM
  • Christoph Lenzen, 08/11/2014 11:07 AM
  • Christoph Lenzen, 08/11/2014 10:41 AM -- Created document.