Computation Engineering: Applied Automata Theory and Logic

Capa
Springer Science & Business Media, 10 de set de 2006 - 472 páginas
It takes more e?ort to verify that digital system designs are correct than it does to design them, and as systems get more complex the proportion of cost spent on veri?cation is increasing (one estimate is that veri?cation complexity rises as the square of design complexity). Although this veri?cation crisis was predicted decades ago, it is only recently that powerful methods based on mathematical logic and automata theory have come to the designers’ rescue. The ?rst such method was equivalence checking, which automates Boolean algebra calculations.Nextcamemodelchecking,whichcanautomatically verify that designs have – or don’t have – behaviours of interest speci?ed in temporal logic. Both these methods are available today in tools sold by all the major design automation vendors. It is an amazing fact that ideas like Boolean algebra and modal logic, originating frommathematicians andphilosophersbeforemodern computers were invented, have come to underlie computer aided tools for creating hardware designs. The recent success of ’formal’ approaches to hardware veri?cation has lead to the creation of a new methodology: assertion based design, in which formal properties are incorporated into designs and are then validated by a combination of dynamic simulation and static model checking. Two industrial strength property languages based on tem- ral logic are undergoing IEEE standardisation. It is not only hardwaredesignand veri?cation that is changing: new mathematical approaches to software veri?cation are starting to be - ployed. Microsoft provides windows driver developers with veri?cation tools based on symbolic methods.
 

O que estão dizendo - Escrever uma resenha

Não encontramos nenhuma resenha nos lugares comuns.

Conteúdo

Introduction
1
Exercises
14
Exercises
31
Cardinalities and Diagonalization
37
Exercises
50
Exercises
67
Exercises
86
Dealing with Recursion
93
Contextfree Languages
217
Exercises
242
Exercises
268
Exercises
288
Exercises
306
Exercises
320
Complexity Theory and NPCompleteness
345
Exercises
365

Exercises
103
Strings and Languages
105
Exercises
116
Exercises
130
Exercises
157
Exercises
181
Exercises
200
The Pumping Lemma 205
204
Exercises
380
Basics
381
Exercises
396
Exercises
414
Exercises
436
Conclusions
439
Index
461
Direitos autorais

Outras edições - Visualizar todos

Termos e frases comuns

Informações bibliográficas