Computation Engineering: Applied Automata Theory and LogicSpringer 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. |
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 |
461 | |
Outras edições - Ver todos
Computation Engineering: Applied Automata Theory and Logic Ganesh Gopalakrishnan Prévia não disponível - 2010 |
Computation Engineering: Applied Automata Theory and Logic Ganesh Gopalakrishnan Prévia não disponível - 2006 |
Termos e frases comuns
accepts algorithm alphabet automaton BDDs bijection binary relation Boolean Büchi automata cardinality Chapter complement computation history computation tree concatenation Consider context-free grammars decidable defined definition denoted deterministic DFA in Figure discussed DPDA Eclosure empty encoding equation equivalence classes equivalence relation example Exercise exists finite finite-state formal formula Fred function given graph Hence Illustration induction infinite input Kripke structure Lambda Lambda calculus least fixed-point logic loop mapping reduction mathematical minimal DFAs model checking natural numbers NDTM nodes non-regular non-terminals nondeterministic notion NP-complete NPDA obtain operator pairs parsing path powerset preorder problem production proof prove Pumping Lemma Qmain reachable recursive regular expressions regular language result Schröder-Bernstein Theorem Section solution stack step string subset symbol tape tion transition true Turing machine undecidable upall variables verify