# Computation Engineering: Applied Automata Theory and Logic

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