Table of contents for Current trends in theoretical computer science : entering the 21st century / edited by G. Paun, G. Rozenberg, A. Salomaa.


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.


Counter




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)








Library of Congress subject headings for this publication: Computer science