Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Basin, David A.
Klarlund, Nils

dblp
dblp



BibTeX cite key*:

BasinKlarlund98

Title

Title*:

Automata Based Symbolic Reasoning in Hardware Verification

Journal

Journal Title*:

Formal Methods in Systems Design

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

13

Number:

3

Publishing Date:

November 1998

Pages*:

255-288

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

      We present a new approach to hardware verification based on describing
      circuits in Monadic Second-order Logic (MSL). We show how to use
      this logic to represent generic designs like $n$-bit adders, which are
      parameterized in space, and sequential circuits, where time is an
      unbounded parameter. MSL admits a decision procedure, implemented in
      the MONA tool, which reduces formulas to canonical automata.

      The decision problem for MSL is non-elementary decidable and
      thus unlikely to be usable in practice. However, we have used
      MONA to automatically verify, or find errors in, a number of
      circuits studied in the literature. Previously published machine
      proofs of the same circuits are based on deduction and may involve
      substantial interaction with the user. Moreover, our approach is
      orders of magnitude faster for the examples considered. We show why
      the underlying computations are feasible and how our use of
      MONA generalizes standard BDD-based hardware reasoning.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Programming Logics Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{BasinKlarlund98,
AUTHOR = {Basin, David A. and Klarlund, Nils},
TITLE = {Automata Based Symbolic Reasoning in Hardware Verification},
JOURNAL = {Formal Methods in Systems Design},
YEAR = {1998},
NUMBER = {3},
VOLUME = {13},
PAGES = {255--288},
MONTH = {November},
}


Entry last modified by Christine Kiesel, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
03/30/2000 02:46:16 PM
Revision
0.



Editor
Christine Kiesel



Edit Date
30/03/2000 14:49:16