Current Trends in Theoretical Computer Science : Entering the 21st Century

by Paun, Gheorghe; Salomaa, Arto

• ISBN13: 9789810244736
• ISBN10: 9810244738
• Format: Hardcover
• Copyright: 2001-04-01
• Publisher: WORLD SCIENTIFIC PUB CO INC

Summary

The scientific developments at the end of the past millennium were dominated by the huge increase and diversity of disciplines with the common label "computer science". The theoretical foundations of such disciplines have become known as theoretical computer science. This book highlights some key issues of theoretical computer science as they seem to us now, at the beginning of the new millennium.The text is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science in the period 1995 -- 2000. The columnists themselves selected the material they wanted for the book, and the editors had a chance to update their work. Indeed, much of the material presented here appears in a form quite different from the original. Since the presentation of most of the articles is reader-friendly and does not presuppose much knowledge of the area, the book constitutes suitable supplementary reading material for various courses in computer science.

Table of Contents

Computational Complexity	1	(114)
E. Allender
Introductory Remarks	2	(2)
A Machine Model for the Complexity of NP-Approximation Problems	4	(21)
R. Chang
Some Pointed Questions Concerning Asymptotic Lower Bounds, and News from the Isomorphism Front	25	(17)
E. Allender
Propositional Proof Complexity: Past, Present, and Future	42	(29)
P. Beame
T. Pitassi
Progress in Descriptive Complexity	71	(12)
N. Immerman
Twelve Problems in Resource-Bounded Measure	83	(19)
J.H. Lutz
E. Mayordomo
Diagonalization	102	(13)
L. Fortnow
Formal Specification	115	(118)
H. Ehrig
Introductory Remarks	116	(2)
Theory and Practice of Software Development: A Review of Driving Forces and Expectations of TAPSOFT from 1985 to 1997	118	(13)
H. Ehrig
B. Mahr
On the Role of Formal Specification Techniques: From TAPSOFT 1985 to ETAPS 2000	131	(3)
H. Ehrig
Algebraic Techniques in Software Development: A Review of Progress up to the Mid Nineties	134	(19)
H. Ehrig
B. Mahr
CoFI: The Common Framework Initiative for Algebraic Specification and Development	153	(11)
P.D. Mosses
Getgrats and Appligraph: Theory and Applications of Graph Transformation	164	(7)
A. Corradini
H.-J. Kreowski
Classification of Petri Nets Using Adjoint Functors	171	(9)
J. Padberg
Dynamic Abstract Data Types: An Informal Proposal in 1994	180	(12)
H. Ehrig
F. Orejas
Integration Paradigm for Data Type and Process Specification Techniques	192	(10)
H. Ehrig
F. Orejas
From Basic Views and Aspects to Integration of Specification Formalisms	202	(13)
H. Ehrig
J. Padberg
F. Orejas
On a Reference Model for the Formalization and Integration of Software Specification Languages	215	(11)
M. Groe-Rhode
On Formal Semantics and Integration of Object-Oriented Modeling Languages	226	(7)
H. Ehrig
R. Geisler
M. Groe-Rhode
M. Klar
S. Mann
Logic in Computer Science	233	(204)
Y. Gurevich
Introductory Remarks	234	(1)
Characterizations of Regular Languages in Low Level Complexity Classes	235	(12)
K.J. Compton
H. Straubing
AMAST'91 Banquet Talk	247	(7)
Y. Gurevich
Logic on Words	254	(20)
J.-E. Pin
The Value, if Any, of Decidability	274	(7)
Y. Gurevich
Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand	281	(22)
Y. Gurevich
Herbrand's Theorem and Equational Reasoning: Problems and Solutions	303	(24)
A. Degtyarev
Y. Gurevich
A. Voronkov
From Invariants to Canonization	327	(5)
Y. Gurevich
The Complexity of Propositional Proofs	332	(11)
A. Urquhart
Functions Versus Algorithms	343	(20)
L. Colson
The Sequential ASM Thesis	363	(30)
Y. Gurevich
Why are Modal Logics so Robustly Decidable?	393	(16)
E. Gradel
The Underlying Logic of Hoare Logic	409	(28)
A. Blass
Y. Gurevich
Concurrency	437	(106)
M. Nielsen
Introductory Remarks	438	(1)
Does Concurrency Theory Have Anything to Say About Parallel Programming?	439	(8)
P. Panangaden
Homotopy and Concurrency	447	(13)
J. Gunawardena
Towards Global Computations Guided by Concurrency Theory	460	(9)
B. Thomsen
L.L. Thomsen
What is Branching Time Semantics and Why to Use it?	469	(11)
R.J. van Glabbeek
More Infinite Results	480	(24)
O. Burkart
J. Esparza
Conservative Extension in Structural Operational Semantics	504	(21)
L. Aceto
W. Fokkink
C. Verhoef
Security Analysis Using Flow Logics	525	(18)
C. Bodei
P. Degano
F. Nielson
H.R. Nielson
Natural Computing	543	(148)
G. Rozenberg
Introductory Remarks	544	(2)
Theory of Genetic Algorithms	546	(33)
T. Back
J.M. de Graaf
J.N. Kok
W.A. Kosters
Why Evolutionary Algorithms?	579	(24)
D.B. Fogel
Z. Michalewicz
Natural Data Mining Techniques	603	(11)
J.N. Kok
W.A. Kosters
Theoretical and Experimental DNA Computation	614	(17)
M. Amos
The Genomics Revolution and its Challenges for Algorithmic Research	631	(12)
R.M. Karp
An Introduction to Quantum Computing	643	(21)
M. Hirvensalo
Quantum Computing and Communication Complexity	664	(16)
H. Buhrman
Neural Computation: A Research Topic for Theoretical Computer Science? Some Thoughts and Pointers	680	(11)
W. Maass
Formal Language Theory	691	(176)
A. Salomaa
Introductory Remarks	692	(1)
Many-Valued Truth Functions, Cernys' Conjecture, and Road Coloring	693	(15)
A. Mateescu
A. Salomaa
On Slender Languages	708	(9)
J. Honkala
Simple Words in Equality Sets	717	(17)
M. Lipponen
A. Salomaa
The DOL Problem Revisited	734	(6)
J. Honkala
Lindenmayer and DNA: Watson-Crick DOL Systems	740	(12)
V. Mihalache
A. Salomaa
Words on Trajectories	752	(19)
A. Mateescu
Networks of Language Processors	771	(20)
E. Csuhaj-Varju
Networks of Language Processors: Parallel Communicating Systems	791	(20)
E. Csuhaj-Varju
A. Salomaa
DNA Computers: Tomorrow's Reality	811	(19)
L. Kari
Splicing: A Challenge for Formal Language Theorists	830	(15)
G. Paun
Computing with Membranes (P Systems): An Introduction	845	(22)
G. Paun
About the Editors	867