1. IFIP TCS 2000: Sendai, Japan

@proceedings{DBLP:conf/ifipTCS/2000,
  editor    = {Jan van Leeuwen and
               Osamu Watanabe and
               Masami Hagiya and
               Peter D. Mosses and
               Takayasu Ito},
  title     = {Theoretical Computer Science, Exploring New Frontiers of Theoretical
               Informatics, International Conference IFIP TCS 2000, Sendai,
               Japan, August 17-19, 2000, Proceedings},
  booktitle = {IFIP TCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1872},
  year      = {2000},
  isbn      = {3-540-67823-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Keynote Plenary Talk 1

• Martín Abadi, Phillip Rogaway:
  Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). 3-22
  

Keynote Plenary Talk 2

• Masami Hagiya:
  Theory and Construction of Molecular Computers. 23-24
  

Keynote Plenary Talk 3

• Madhu Sudan:
  List Decoding: Algorithms and Applications. 25-41
  

Track (1) on Algorithms, Complexity and Models of Computation

Session 1.1

• Giancarlo Mauri, Giulio Pavesi:
  Approximation Algorithms for String Folding Problems. 45-58
  
• Kimmo Fredriksson, Gonzalo Navarro, Esko Ukkonen:
  An Index for Two Dimensional String Matching Allowing Rotations. 59-75
  

Session 1.2

• Chang-Sung Jeong, Sung-Up Cho, Sun-Chul Whang, Mi-Young Choi:
  Parallel Edge Coloring of a Tree on a Mesh Connected Computer. 76-83
  
• Ryuhei Uehara, Zhi-Zhong Chen:
  Paralle Approximation Algorithms for Maximum Weighted Matching in General Graphs. 84-98
  

Invited Talk 1.1

• Ernst W. Mayr:
  In Is on the Boundary: Complexity Considerations for Polynominal Ideals. 99
  

Session 1.3

• Yoojin Chung, Kunsoo Park, Hyuk-Chul Kwon:
  An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks. 100-111
  
• Evgeny V. Shchepin, Nodari Vakhania:
  Task Distributions on Multiprocessor Systems. 112-125
  
• Olivier Sarzeaud, Yann Stéphan:
  Fast Interpolation Using Kohonen Self-Organizing Neural Networks. 126-139
  
• Carlo Blundo, Clemente Galdi:
  Steganography Using Modern Arts. 140-151
  

Session 1.4

• Philippe Flajolet, Kostas P. Hatzis, Sotiris E. Nikoletseas, Paul G. Spirakis:
  Trade-Offs between Density and Robustness in Random Interconnection Graphs. 152-168
  
• Satoshi Taoka, Toshimasa Watanabe:
  The (sigma+1)-Edge-Connectivity Augmentation Problem without Creating Multiple Edges of a Graph. 169-185
  
• Sounaka Mishra, Kripasindhu Sikdar:
  On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem. 186-199
  
• Stephan Eidenbenz, Christoph Stamm:
  MAXIMUM CLIQUE and MINIMUM CLIQUE PARTITION in Visibility Graphs. 200-212
  

Session 1.5

• Thomas Buchholz, Andreas Klein, Martin Kutrib:
  Real-Time Language Recognition by Alternating Cellular Automata. 213-225
  
• Bruno Martin:
  Damage Spreading and µ-Sensitivity on Cellular Automata. 226-242
  

Invited Talk 1.2

• Shu Tezuka:
  Discrepancy Theory and Its Application to Finance. 243-256
  

Session 1.6

• Endre Boros, Toshihide Ibaraki, Kazuhisa Makino:
  Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bits. 257-272
  
• Takaaki Mizuki, Hiroki Shizuya, Takao Nishizeki:
  Characterization of Optimal Key Set Protocols. 273-285
  
• Valentin E. Brimkov, Stefan S. Dantchev:
  On the Complexity of Integer Programming in the Blum-Shub-Smale Computational Model. 286-300
  
• Andreas Alexander Albrecht, Chak-Kuen Wong:
  On Logarithmic Simulated Annealing. 301-314
  

Invited Talk 1.3

• Mihalis Yannakakis:
  Hierarchical State Machines. 315-330
  

Track (2) on Logic, Semantics, Specification, and Verification

Session 2.1

• Luca Cardelli, Giorgio Ghelli, Andrew D. Gordon:
  Ambient Groups and Mobility Types. 333-347
  
• Cédric Fournet, Jean-Jacques Lévy, Alan Schmitt:
  An Asynchronous, Distributed Implementation of Mobile Ambients. 348-364
  

Invited Talk 2.1

• Naoki Kobayashi:
  Type Systems for Concurrent Processes: From Deadlock-Freedom to Livelock-Freedom, Time-Boundedness. 365-389
  

Session 2.2

• Massimo Merro, Josva Kleist, Uwe Nestmann:
  Local pi-Calculus at Work: Mobile Objects as Mobile Processes. 390-408
  
• Silvano Dal-Zilio:
  An Interpretation of Typed Concurrent Objects in the Blue Calculus. 409-424
  

Session 2.3

• Joëlle Despeyroux:
  A Higher-Order Specification of the pi-Calculus. 425-439
  
• Roberto Bruni, Ugo Montanari, Vladimiro Sassone:
  Open Ended Systems, Dynamic Bisimulation and Tile Logic. 440-456
  
• Marcelo P. Fiore:
  Fibred Models of Processes: Discrete, Continuous, and Hybrid Systems. 457-473
  
• Richard Mayr:
  On the Complexity of Bisimulation Problems for Pushdown Automata. 474-488
  

Session 2.4

• Yukiyoshi Kameyama:
  A Type-Theoretic Study on Partial Continuations. 489-504
  
• Ken-etsu Fujita, Aleksy Schubert:
  Partially Typed Terms between Church-Style and Curry-Style. 505-520
  
• Christof Löding, Wolfgang Thomas:
  Alternating Automata and Logics over Infinite Words. 521-535
  
• Yann Loyer, Nicolas Spyratos, Daniel Stamate:
  Hypothesis Support for Information Integration in Four-Valued Logics. 536-548
  

Invited Talk 2.2

• Thomas A. Henzinger:
  Masaccio: A Formal Model for Embedded Components. 549-563
  

Session 2.5

• Karl Lermer, Paul A. Strooper:
  A Single Complete Refinement Rule for Demonic Specifications. 564-579
  
• Michel Charpentier, K. Mani Chandy:
  Reasoning about Composition Using Property Transformers and Their Conjugates. 580-595
  

Invited Talk 2.3

• Gordon D. Plotkin:
  Some New Directions in the Syntax and Semantics of Formal Languages. 596
  

Panel Discussion on New Challenges for TCS

• Jozef Gruska:
  New Challenges for Theoretical Computer Science. 599-601
  
• Giorgio Ausiello:
  Algorithm Design Challenges. 602-603
  
• Jozef Gruska:
  Quantumization of Theoretical Informatics. 604-608
  
• Ugo Montanari:
  Two Problems in Wide Area Network Programming. 609-611
  
• Yoshihito Toyama:
  New Challenges for Compuational Models. 612-613
  
• Jirí Wiedermann:
  Towards a Computational Theory of Everything. 614-615
  

Open Lectures

• Jan van Leeuwen, Jirí Wiedermann:
  On the Power of Interactive Computing. 619-623
  
• Peter D. Mosses:
  The Varieties of Programming Language Semantics. 624-628