Bibliographic record and links to related information available from the Library of Congress catalog. Note: Electronic data is machine generated. May be incomplete or contain other coding.
CHAPTER 1 COMPUTATIONAL COMPLEXITY by E. Allender and guest authors Introductory Remarks A Machine Model for the Complexity of NP-Approximation Problems (by R. Chang) Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front (by E. Allender) Propositional Proof Complexity: Past, Present, and Future (by P. Beame and T. Pitassi) Progress in Descriptive Complexity (by N. Immerman) Twelve Problems in Resource-Bounded Measure (by J.H. Lutz and E. Mayordomo) Diagonalization (by L. Fortnow) CHAPTER 2 FORMAL SPECIFICATION by H. Ehrig and guest authors Introductory Remarks Theory and Practice of Software Development: A Review of Driving Forces and Expectations of TAPSOFT from 1985 to 1997 (by H. Ehrig and B. Mahr) On the Role of Formal Specification Techniques: From TAPSOFT 1985 to ETAPS 2000 (by H. Ehrig) Algebraic Techniques in Software Development: A Review of Progress up to the Mid Nineties (by H. Ehrig and B. Mahr) CoFI: The Common Framework Initiative for Algebraic Specification and Development (by P.D. Mosses) GETGRATS and APPLIGRAPH: Theory and Applications of Graph Transformation (by A. Corradini and H.-J. Kreowski) Classification of Petri Nets Using Adjoint Functors (by J. Padberg) Dynamic Abstract Data Types: An Informal Proposal in 1994 (by H. Ehrig and F. Orejas) Integration Paradigm for Data Type and Process Specification Techniques (by H. Ehrig and F. Orejas) From Basic Views and Aspects to Integration of Specification Formalisms (by H. Ehrig, J. Padberg and F. Orejas) On a Reference Model for the Formalization and Integration of Software Specification Languages (by M. Grofie-Rhode) On Formal Semantics and Integration of Object-Oriented Modeling Languages (by H. Ehrig, R. Geisler, M. Groie-Rhode, M. Klar and S. Mann) CHAPTER 3 LOGIC IN COMPUTER SCIENCE by Y. Gurevich and guest authors Introductory Remarks Characterizations of Regular Languages in Low Level Complexity Classes (by K.J. Compton, H. Straubing) AMAST'91 Banquet Talk (by Y. Gurevich) Logic on Words (by J.-E. Pin) The Value, if Any, of Decidability (by Y. Gurevich) Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand (by Y. Gurevich) Herbrand's Theorem and Equational Reasoning: Problems and Solutions (by A. Degtyarev, Y. Gurevich and A. Voronkov) From Invariants to Canonization (by Y. Gurevich) The Complexity of Propositional Proofs (by A. Urquhart) Functions Versus Algorithms (by L. Colson) The Sequential ASM Thesis (by Y. Gurevich) Why are Modal Logics so Robustly Decidable? (by E. Gridel) The Underlying Logic of Hoare Logic (by A. Blass and Y. Gurevich) CHAPTER 4 CONCURRENCY by M. Nielsen and guest authors Introductory Remarks Does Concurrency Theory Have Anything to Say About Parallel Programming? (by P. Panangaden) lomotopy and Concurrency (by J. Gunawardena) Towards Global Computations Guided by Concurrency Theory (by B. Thomsen and L.L. Thomsen) What is Branching Time Semantics and Why to Use it? (by R.J. van Glabbeek) More Infinite Results (by O. Burkart and J. Esparza) Conservative Extension in Structural Operational Semantics (by L. Aceto, W. Fokkink, and C. Verhoef) Security Analysis Using Flow Logics (by C. Bodei, P. Degano, F. Nielson, and H.R. Nielson) CHAPTER 5 NATURAL COMPUTING by G. Rozenberg and guest authors Introductory Remarks Theory of Genetic Algorithms (by T. Back, J.M. de Graaf, J.N. Kok, and W.A. Kosters) Why Evolutionary Algorithms? (by D.B. Fogel and Z. Michalewicz) Natural Data Mining Techniques (by J.N. Kok and W.A. Kosters) Theoretical and Experimental DNA Computation (by M. Amos) The Genomics Revolution and its Challenges for Algorithmic Research (by R.M. Karp) An Introduction to Quantum Computing (by M. Hirvensalo) Quantum Computing and Communication Complexity (by H. Buhrman) Neural Computation: A Research Topic for Theoretical Computer Science? Some Thoughts and Pointers (by W. Maass) CHAPTER 6 FORMAL LANGUAGE THEORY by A. Salomaa and guest authors Introductory Remarks Many-Valued Truth Functions, Cernys' Conjecture, and Road Coloring (by A. Mateescu and A. Salomaa) On Slender Languages (by. J. Honkala) Simple Words in Equality Sets (by M. Lipponen and A. Salomaa) The DOL Problem Revisited (by J. Honkala) Lindenmayer and DNA: Watson-Crick DOL Systems (by V. Mihalache and A. Salomaa) Words on Trajectories (by A. Mateescu) Networks of Language Processors (by E. Csuhaj-Varju) Networks of Language Processors: Parallel Communicating Systems (by E. Csuhaj-Varju and A. Salomaa) DNA Computers: Tomorrow's Reality (by L. Kari) Splicing: A Challenge for Formal Language Theorists (by G. Paun) Computing with Membranes (P Systems): An Introduction (by G. Paun)