Finite model theory is an area of mathematical logic that grew out of computer science applications. The main sources of motivational examples for finite model theory are found in database theory, computational complexity, and formal languages, although in recent years connections with other areas, such as formal methods and verification, and artificial intelligence, have been discovered. The birth of finite model theory is often identified with Trakhtenbrot's result from 1950 stating that validity over finite models is not recursively enumerable; in other words, completeness fails over...

The authors are much indebted to many friends and collaborators whose con tributions to automata and language theory approach to DNA computing can be recognized in the present book. The bibliography specifies their names and we shall not repeat them here. Some of them have also read previous versions of various chapters, suggesting modifications which have improved the readability of the text. Many thanks are due in this respect to Tom Head, Hendrik Jan Hoogeboom, Vincenzo Manca, Alexandru Mateescu, Victor Mi trana, Andrei Paun, and Nike van Vugt. In particular, we are grateful to our...

to Circuit COIllplexity A Uniform Approach With 29 Figures, Springer Author Dr. Heribert Vollmer Universitiit Wurzburg Theoretische Informatik Am Exerzierplatz 3 D-97072 Wurzburg, Germany vollmer@informatik. uni-wuerzburg. de Series Editors Prof. Dr. Wilfried Brauer Institut fUr Informatik, Technische Universitiit Munchen Arcisstrasse 21, D-80333 Munchen, Germany Prof. Dr. Grzegorz Rozenberg Department of Computer Science, University of Leiden Niels Bohrweg 1, P. O. Box 9512, 2300 RA Leiden, The Netherlands Prof. Dr. Arto Salomaa Data City, Turku Centre for Computer Science FIN-20520 Turku,...

Invitation Invitation Secret Secret 1 1 Algorithms Algorithms are are at at the the heart heart of of complexity complexity theory. theory. That That is is the the dark dark secret secret of of complexity complexity theory. theory. It It is is recognized recognized by by complex- complex- ity ity theorists, theorists, but but would would be be literally literally incredible incredible to to most most others. others. In In this this book, book, we we hope hope to to make make this this secret secret credible. credible. In In fact, fact, the the real real secret secret is is even even more more...

Preface Due to the development of hardware technologies (such as VLSI) in the early 1980s, the interest in parallel and distributive computing has been rapidly growingandinthelate1980sthestudyofparallelalgorithmsandarchitectures became one of the main topics in computer science. To bring the topic to educatorsandstudents, severalbooksonparallelcomputingwerewritten. The involvedtextbook"IntroductiontoParallelAlgorithmsandArchitectures"by F. Thomson Leighton in 1992 was one of the milestones in the development of parallel architectures and parallel algorithms. But in the last decade or so the...

Finite model theory is an area of mathematical logic that grew out of computer science applications. The main sources of motivational examples for finite model theory are found in database theory, computational complexity, and formal languages, although in recent years connections with other areas, such as formal methods and verification, and artificial intelligence, have been discovered. The birth of finite model theory is often identified with Trakhtenbrot's result from 1950 stating that validity over finite models is not recursively enumerable; in other words, completeness fails over...

Personal motivation. The dream of creating artificial devices that reach or outperform human inteUigence is an old one. It is also one of the dreams of my youth, which have never left me. What makes this challenge so interesting? A solution would have enormous implications on our society, and there are reasons to believe that the AI problem can be solved in my expected lifetime. So, it's worth sticking to it for a lifetime, even if it takes 30 years or so to reap the benefits. The AI problem. The science of artificial intelligence (AI) may be defined as the construction of intelligent systems...

This text discusses DNA computing, a molecular approach that may revolutionize computing-replacing silicon with carbon and microchips with DNA molecules. It starts with an introduction to DNA computing, exploring the power of complementarity, the basics of biochemistry, and language and computation theory.

Automated and semi-automated manipulation of so-called labelled transition systems has become an important means in discovering flaws in software and hardware systems. Process algebra has been developed to express such labelled transition systems algebraically, which enhances the ways of manipulation by means of equational logic and term rewriting.
The theory of process algebra has developed rapidly over the last twenty years, and verification tools have been developed on the basis of process algebra, often in cooperation with techniques related to model checking. This textbook gives a...