Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics: International Conference IFIP TCS 2000 Sendai, Japan, August 17–19, 2000 Proceedings

Martí;n Abadi, Phillip Rogaway (auth.), Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito (eds.)3540678239, 9783540678236

In 1996 the International Federation for Information Processing (IFIP) establ- hed its rst Technical Committee on foundations of computer science, TC1. The aim of IFIP TC1 is to support the development of theoretical computer science as a fundamental science and to promote the exploration of fundamental c- cepts, models, theories, and formal systems in order to understand laws, limits, and possibilities of information processing. This volume constitutes the proceedings of the rst IFIP International C- ference on Theoretical Computer Science (IFIP TCS 2000) { Exploring New Frontiers of Theoretical Informatics { organized by IFIP TC1, held at Tohoku University, Sendai, Japan in August 2000. The IFIP TCS 2000 technical program consists of invited talks, contributed talks, and a panel discussion. In conjunction with this program there are two special open lectures by Professors Jan van Leeuwen and Peter D. Mosses. The decision to hold this conference was made by IFIP TC1 in August 1998, and since then IFIP TCS 2000 has bene ted from the e orts of many people; in particular, the TC1 members and the members of the Steering Committee, the Program Committee, and the Organizing Committee of the conference. Our special thanks go to the Program Committee Co-chairs: Track (1): Jan van Leeuwen (U. Utrecht), Osamu Watanabe (Tokyo Inst. Tech.) Track (2): Masami Hagiya (U. Tokyo), Peter D. Mosses (U. Aarhus).

---

Table of contents :
Reconciling Two Views of Cryptography….Pages 3-22
Theory and Construction of Molecular Computers….Pages 23-24
List Decoding: Algorithms and Applications….Pages 25-41
Approximation Algorithms for String Folding Problems….Pages 45-58
An Index for Two Dimensional String Matching Allowing Rotations….Pages 59-75
Parallel Edge Coloring of a Tree on a Mesh Connected Computer….Pages 76-83
Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs….Pages 84-98
It Is on the Boundary: Complexity Considerations for Polynomial Ideals….Pages 99-99
An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks….Pages 100-111
Task Distributions on Multiprocessor Systems….Pages 112-125
Fast Interpolation Using Kohonen Self-Organizing Neural Networks….Pages 126-139
Steganography Using Modern Arts….Pages 140-151
Trade-Offs between Density and Robustness in Random Interconnection Graphs….Pages 152-168
The ( σ + 1)-Edge-Connectivity Augmentation Problem without Creating Multiple Edges of a Graph….Pages 169-185
On the Hardness of Approximating Some NP-Optimization Problems Related to Minimum Linear Ordering Problem….Pages 186-199
Maximum Clique and Minimum Clique Partition in Visibility Graphs….Pages 200-212
Real-Time Language Recognition by Alternating Cellular Automata….Pages 213-225
Damage Spreading and μ-Sensitivity on Cellular Automata….Pages 226-241
Discrepancy Theory and Its Application to Finance….Pages 243-256
Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bitsv….Pages 257-272
Characterization of Optimal Key Set Protocols….Pages 273-285
On the Complexity of Integer Programming in the Blum-Shub-Smale Computational Model….Pages 286-300
On Logarithmic Simulated Annealing….Pages 301-314
Hierarchical State Machines….Pages 315-330
Ambient Groups and Mobility Types….Pages 333-347
An Asynchronous, Distributed Implementation of Mobile Ambients….Pages 348-364
Type Systems for Concurrent Processes: From Deadlock-Freedom to Livelock-Freedom, Time-Boundedness….Pages 365-389
Local π-Calculus at Work: Mobile Objects as Mobile Processes….Pages 390-408
An Interpretation of Typed Concurrent Objects in the Blue Calculus….Pages 409-424
A Higher-Order Specification of the π-Calculus….Pages 425-439
Open Ended Systems, Dynamic Bisimulation and Tile Logic….Pages 440-456
Fibred Models of Processes: Discrete, Continuous, and Hybrid Systems….Pages 457-473
On the Complexity of Bisimulation Problems for Pushdown Automata….Pages 474-488
A Type-Theoretic Study on Partial Continuations….Pages 489-504
Partially Typed Terms between Church-Style and Curry-Style….Pages 505-520
Alternating Automata and Logics over Infinite Words….Pages 521-535
Hypothesis Support for Information Integration in Four-Valued Logics….Pages 536-548
Masaccio: A Formal Model for Embedded Components….Pages 549-563
A Single Complete Refinement Rule for Demonic Specifications….Pages 564-579
Reasoning about Composition Using Property Transformers and Their Conjugates….Pages 580-595
Some New Directions in the Syntax and Semantics of Formal Languages….Pages 596-596
New Challenges for Theoretical Computer Science….Pages 599-601
Algorithm Design Challenges….Pages 602-603
Quantumization of Theoretical Informatics….Pages 604-608
Two Problems in Wide Area Network Programming….Pages 609-611
New Challenges for Computational Models….Pages 612-613
Towards a Computational Theory of Everything….Pages 614-615
On the Power of Interactive Computing….Pages 619-623
The Varieties of Programming Language Semantics….Pages 624-628