Shinya MIYAKAWA <>
Wed May 17 09:00:14 CEST 2000

[Apologies for multiple copies]


IFIP International Conference on Theoretical Computer Science 
                   (IFIP TCS2000)
 --- Exploring New Frontiers of Theoretical Informatics ---

 August 17 - 19, 2000

 Aoba Memorial Bldg., Tohoku University, Sendai, Japan

 Further Information about IFIP TCS2000 can be obtained on the Web, at


 Any inquiry on IFIP TCS2000 Program and Registration may be directed to



      AUGUST 16: 15:00 Registration at Sendai Tokyu Hotel till 20:00
                 18:00 Welcome at Sendai Tokyu Hotel till 19:00

      AUGUST 17:  9:30 Opening Session 
                 10:00 Keynote Plenary Talk 1
                 11:10 - 17:30  TRACK (1)  ||  TRACK (2) 

      AUGUST 18:  9:10 Keynote Plenary Talk 2 
                 10:20 - 15:30  TRACK (1)  ||  TRACK (2)
                 15:50 Panel Discussion till 17:10
                 18:30 Banquet at Sendai Tokyu Hotel

      AUGUST 19:  9:10 Keynote Plenary Talk 3 
                 10:20 - 14:20  TRACK (1)  ||  TRACK (2)
                 14:30 Closing Session till 14:40
                 15:00 Open Lectures till 17:00
                 18:30 Japanese Dinner Party till 20:00

  15:00 REGISTRATION at Sendai Tokyu Hotel till 20:00

  18:00 WELCOME with light snack at Sendai Tokyu Hotel till 19:00

        Giorgio Ausiello (TC1 Chair and IFIP TCS2000 Co-Chair)
        Takayasu Ito (IFIP TCS2000 Co-Chair)
        Reconciling Two Views of Cryptography (The Computational Soundness 
        of Formal Encryption) 
        Martin Abadi (Bell Labs, Lucent)*, Phillip Rogaway (UC Davis)
           (*: speaker)

  10:50 Break

 [TRACK (1)]

            SESSION (1.1), 11:10 - 12:00

  11:10 Approximation Algorithms for String Folding Problems
        Giancarlo Mauri, Giulio Pavesi

  11:35 An Index for Two Dimensional String Matching Allowing Rotations
        Kimmo Fredriksson, Gonzalo Navarro, Esko Ukkonen

  12:00 Lunch Break

            SESSION (1.2),  13:30 - 14:20

  13:30 Parallel Edge Coloring of a Tree on a Mesh Connected Computer
        Chang-Sung Jeong, Sung-Up Cho, Sun-Chul Whang, Mi-Young Choi

  13:55 Parallel Approximation Algorithms for Maximum Weighted Matching
        in General Graphs
        Ryuhei Uehara, Zhi-Zhong Chen

  14:20 Break

        It is on the Boundary: Complexity Considerations for Polynomial 
        Ernst Mayr (TU Muenchen)

  15:30 Break

            SESSION (1.3), 15:50 - 17:30

  15:50 An Efficient Parallel Algorithm for Scheduling Interval Ordered 
        Yoojin Chung, Kunsoo Park, Hyuk-Chul Kwon

  16:15 Task Distributions on Multiprocessor Systems
        Evgeny V. Shchepin, Nodari N. Vakhania

  16:40 Fast Interpolation using Kohonen Self-Organizing Neural Networks
        Olivier Sarzeaud, Yann Stephan

  17:05 Steganography Using Modern Arts
        Carlo Blundo, Clemente Galdi

  17:30 Break


 [TRACK (2)]

            SESSION (2.1), 11:10 - 12:00

  11:10 Ambient Groups and Mobility Types
        Luca Cardelli, Giorgio Ghelli, Andrew D. Gordon

  11:35 An Asynchronous, Distributed Implementation of Mobile Ambients
        Cedric Fournet, Jean-Jacques Levy, Alan Schmitt

  12:00 Lunch Break

        Type Systems for Concurrent Processes: From Deadlock-Freedom to 
        Livelock-Freedom, Time-Boundedness
        Naoki Kobayashi (U. Tokyo)

  14:20 Break

            SESSION (2.2), 14:40 - 15:30

  14:40 Local pi-Calculus at Work: Mobile Objects as Mobile Processes
        Massimo Merro, Josva Kleist, Uwe Nestmann

  15:05 An Interpretation of Typed Concurrent Objects in the Blue Calculus
        Silvano Dal Zilio

  15:30 Break

            SESSION (2.3), 15:50 - 17:30

  15:50 A Higher-Order Specification of the pi-Calculus
        Joelle Despeyroux

  16:15 Open Ended Systems, Dynamic Bisimulation, and Tile Logic
        Roberto Bruni, Ugo Montanari, Vladimiro Sassone

  16:40 Fibred Models of Processes: Discrete, Continuous, and Hybrid Systems
        Marcelo P. Fiore

  17:05 On the Complexity of Bisimulation Problems for Pushdown Automata
        Richard Mayr

  17:30 Break

        Theory and Construction of Molecular Computers
        Masami Hagiya (U. Tokyo)

  10:00 Break

 [TRACK (1)]

            SESSION (1.4), 10:20 - 12:00

  10:20 Trade-offs between Density and Robustness in Random Interconnection
        P. Flajolet, K. Hatzis, S. Nikoletseas, P. Spirakis

  10:45 The ($\sigma$+1)-Edge-Connectivity Augmentation Problem without 
        Creating Multiple Edges of a Graph
        Satoshi Taoka, Toshimasa Watababe

  11:10 On the Hardness of Approximating Some NP-optimization Problems 
        Related to Minimum Linear Ordering Problem
        Sounaka Mishra, Kripasindhu Sikdar

  11:35 Maximum Clique and Minimum Clique Partition in Visibility Graphs
        Stephan Eidenbenz, Christoph Stamm

  12:00 Lunch Break

            SESSION (1.5), 13:30 - 14:20

  13:30 Real-Time Language Recognition by Alternating Cellular Automata
        Thomas Buchholz, Andreas Klein, Martin Kutrib

  13:55 Damage Spreading and $\mu$-Sensitivity on Cellular Automata
        Bruno Martin

  14:20 Break

        Discrepancy Theory and its Applications to Finance
        Shu Tezuka (IBM Tokyo Research Lab)

  15:30 Break


 [TRACK (2)]

            SESSION (2.4), 10:20 - 12:00

  10:20 A Type-theoretic Study on Partial Continuations
        Yukiyoshi Kameyama

  10:45 Partially Typed Terms between Church-Style and Curry-Style
        Ken-etsu Fujita, Aleksy Schubert

  11:10 Alternating Automata and Logics over Infinite Words
        Christof Loeding, Wolfgang Thomas

  11:35 Hypothesis Support for Information Integration in Four-Valued Logics
        Yann Loyer, Nicolas Spyratos, Daniel Stamate

  12:00 Lunch Break

        Masaccio: A Formal Model for Embedded Components
        Thomas A. Henzinger (UC Berkeley)

  14:20 Break

            SESSION (2.5), 14:40 - 15:30

  14:40 A Single Complete Refinement Rule for Demonic Specifications
        Karl Lermer, Paul Strooper

  15:05 Reasoning about Composition using Property Transformers and their 
        Michel Charpentier, K. Mani Chandy
  15:30 Break

  15:50 PANEL DISCUSSION on "New Challenges for TCS"
        Panelists: Giorgio Ausiello (U. Roma "La Sapienza")
                   Jozef Gruska <Co-Chair> (Masaryk U.)
                   Ugo Montanari (U. Pisa)
                   Takao Nishizeki <Co-Chair> (Tohoku U.)
                   Yoshihito Toyama (Tohoku U.)
                   Jiri Wiedermann (Inst. Informatics, Prague)

  17:10 Break

  18:30 BANQUET at Sendai Tokyu Hotel till 20:45
        Non-Random Thoughts about Randomization
        Michael O. Rabin (Harvard U.)

        List Decoding: Algorithms and Applications
        Madhu Sudan (MIT)

  10:00 Break

 [TRACK (1)]

            SESSION (1.6), 10:20 - 12:00

  10:20 Fully Consistent Extensions of Partially Defined Boolean Functions
        with Missing Bits
        Endre Boros, Toshihide Ibaraki, Kazuhisa Makino

  10:45 Characterization of Optimal Key Set Protocols
        Takaaki Mizuki, Hiroki Shizuya, Takao Nishizeki

  11:10 On the Complexity of Integer Programming in the Blum-Shub-Smale
        Computational Model
        Valentin E. Brimkov, Stefan S. Dantchev

  11:35 On Logarithmic Simulated Annealing
        A. Albrecht, C. K. Wong

  12:00 Lunch Break

        Hierarchical State Machines
        Mihalis Yannakakis (Bell Labs, Lucent)

  14:20 Break


 [TRACK (2)]

        Some New Directions in the Syntax and Semantics of Formal Languages
        Gordon D. Plotkin (Edinburgh U.)

  11:10 Break

  11:20 DEMO SESSION (1) on Verification Tools

  12:00 Lunch Break

  13:30 DEMO SESSION (2) on Verification Tools

  14:20 Break


  14:30 CLOSING SESSION till 14:40
        Giorgio Ausiello (TC1 Chair and IFIP TCS2000 Co-Chair) 
        Takayasu Ito (IFIP TCS2000 Co-Chair)



  15:00 On the Power of Interactive Computing
        Jan van Leeuwen (U. Utrecht)*, Jiri Wiedermann (Acad. Sciences, Czech)
           (*: speaker)

  16:00 The Varieties of Programming Language Semantics
        Peter D. Mosses (U. Aarhus)

  17:00 Break


  18:30 JAPANESE DINNER PARTY till 20:00



IFIP TCS2000 is the first International Conference on Theoretical Computer 
Science organized by IFIP TC1 on Foundations of Computer Science, and it 
consists of two tracks: TRACK (1) on Algorithms, Complexity and Models of 
Computation, and TRACK (2) on Logic, Semantics, Specification, and 
Verification. The conference proceedings will be published as a volume
of Lecture Notes in Computer Science, Springer-Verlag.

IFIP TCS2000 will be held on the campus of Tohoku University, Sendai, Japan.
The invited talks and contributed talks will be presented at the Aoba 
Memorial Building and Engineering Conference Hall, Faculty of Engineering 
located on the Aoba Hill about 3 km west of downtown Sendai. The conference
welcome reception and banquet will be held at Sendai Tokyu Hotel, located 
at downtown Sendai.

Please, register and make reservations by returning the completed form 
by email and fax, following the instructions below.
There will also be on-site registration at:
   * Sendai Tokyu Hotel, 15:00 - 20:00, August 16
   * Aoba Memorial Bldg., Tohoku Univ., 9:00 - 17:00 on August 17 - 19.


Conference participants arriving at the new Tokyo International (Narita) 
Airport are advised to take the JR Narita Express train from Narita Airport
to Tokyo Station. 
Then, take the Yamabiko super express train of Tohoku Shinkansen (Tohoku 
Bullet Train) to Sendai from Tokyo Station. The Yamabiko runs every 20 - 30
min. and takes about 2 hours from Tokyo to Sendai. Making reservation at 
Narita Station for the Yamabiko is recommended, since it will be the summer
tourist season. 
Those arriving at the new Osaka International Airport (Kansai Airport) can
fly to Sendai Airport, and take Limousine Bus service to Sendai Station. 
The bus takes about 30 min. to go from the Airport to Sendai Station. You 
can also take a shuttle bus service from Kansai Airport to the Osaka-Itami 
Airport to fly from there to Sendai Airport. Alternatively, you can take a 
local train from the Kansai Airport to JR Shin Osaka Station, then take the
Tokaido Shinkansen from Osaka to Tokyo Station and change at Tokyo Station 
to Tohoku Shinkansen. 
Some details on transportation will be available on the TCS2000 Web page, at
(1) In Japan, mid-August is the busiest tourist time during summer, 
    including domestic and international flights. 
(2) No flight service is available from Narita to Sendai Airport, since the
    train service is convenient. There is another train service from Narita
    Airport to downtown Tokyo (Ueno) by Skyliner of the Keisei-Narita Line.
    At Ueno you can take the Yamabiko super express of Tohoku Shinkansen to
    Sendai, but you have to walk about 10 min. from Keisei-Ueno Station to 
    JR Ueno Station to take Tohoku Shinkansen.
(3) If you are going to travel in Japan by JR lines before/after the IFIP 
    TCS2000 conference, it will be convenient and economical to get a JR 
    PASS before your departure. Contact your travel agent for more 
    information on JR PASS (Japan Rail Pass).


Two hotels are arranged to offer special discount rates to IFIP TCS2000 
participants: Sendai Tokyu Hotel and Sendai Washington Hotel. They are 
1.2 km west of Sendai Station and about 800 Yen by taxi from the station. 
These hotels are located within 5 min. walk from each other. The conference
welcome reception and banquet will be held at Sendai Tokyu Hotel.

Sendai and Climate

Sendai is the largest city in the northern part of the Honshu Island of 
Japan, with a population of about a million. The City is known in Japan 
as "City of Trees". Sendai is a modern, safe city with a temperate climate 
blessed by four distinct seasons; even in mid August it is quite seldom 
that the highest temperature exceeds 30 C (86 F). 
Usually, the weather in mid August would be mostly sunny with temperatures
ranging from 20 C (68 F) to 30 C (86 F), and rain, if any, would rarely be
Note: Average temperatures in August at Sendai, Tokyo and Osaka are about 
      23.5 C, 26.5 C and 27.5, respectively.


Registration fees cover attendance in all sessions, a copy of the proceedings, 
refreshments, the welcome reception and banquet, but not the Japanese dinner 
party on August 19. The reduced author rate applies to all authors of the 
accepted papers, and the reduced committee member rate applies to all TC1 
members and to all members of the Program Committee and the Organizing 
Committee. The student rate applies to full time students. Registrants paying
reduced rates have full privileges at the conference. The companion rate 
covers the reception and banquet only.

                      Through July 1st, 2000          From July 2nd, 2000 
   Regular                  40,000 Yen                    50,000 Yen
   Author                   30,000 Yen                    40,000 Yen
   Committee Member         30,000 Yen                    40,000 Yen
   Student                  25,000 Yen                    30,000 Yen
   Companion                 5,000 Yen                     7,000 Yen


Two convenient Western Style hotels offer special IFIP TCS2000 discount rates.
Rates are per person, per night, and include service charge and tax (not 
including breakfast).

                                    Single Room           Twin Room
   Sendai Tokyu Hotel               10,500 Yen            8,400 Yen
   Sendai Washington Hotel II        8,400 Yen            7,350 Yen
   Sendai Washington Hotel I         7,350 Yen            ---------

Note: Twin room reservations are available for two persons. No roommate 
      matching service is available, so that twin room reservations remain 
      the registrant's responsibility.

A Japanese dinner party for participants from abroad will be arranged at
SHOZANKAN in the evening of August 19. The invited speakers, some Steering
Committee members, PC members and conference organizers will attend. A 
limited number of reservations will be available for this dinner party. 
The rates are as follows.

   Conference registrant:   10,000 Yen
   Companion:                7,000 Yen

Cut here to send your registration form after filling in the required items.


Please register and make reservations by completing the form below and 
returning it by email to


Registrants are advised to email a copy of their completed form to


They are also encouraged to send a signed, printed copy of their completed 
form by fax to

        022-262-5002 (domestic)
     +81-22-262-5002 (from abroad)

which is the fax number of the following agent to take care of the conference
registration and reservation.

    JTB (Japan Travel Bureau) Tohoku Communications Inc.
    Kotsukosha Bldg 3F, 3-6-Chuo
    Aoba-Ku, Sendai 980-0021, Japan

    (Fax)   022-262-5002 (domestic)
            +81-22-262-5002 (from abroad)
    (Phone) 022-262-5055 (domestic)
            +81-22-262-5055 (from abroad)

Registration and reservations will be completed by your payment, whose method
is described below.

IMPORTANT NOTE: As described below, from the standpoint of the safety, 
    registrants are advised to pay fees by Bank Transfer. When the payment is
    made by a credit card, they are advised to send the required information 
    including Credit Card numbers by FAX; that is, do NOT send Credit Card 
    numbers by email.
  Last (Family) Name:

  First (Given) Name:



  Postal Address:






  Registration Status 
    <Regular, Author, Committee Member, Student>:

  Number of Companions:

  Companions' names (if applicable):

  (A) Total Registration Fee(s) in Yen:


  Hotel First Choice:

  Hotel Second Choice:

  Number of Single Room(s):

  Number of Twin Room(s):

  Roommate's Name(s) for Twin Room(s):

  Check-in Date:

  Check-out Date:

  Number of Nights:

  Special Room or other Request:


  A limited number of reservations are available for the Japanese dinner 
  party at SHOZANKAN on August 19 to be arranged for participants from 

  (B) 10,000 Yen x [   ] conference registrant(s):

  (C)  7,000 Yen x [   ] companion(s):


  (A) + (B) + (C):

Signature (not needed for email):


   From the standpoint of the safety and security, participants are encouraged
   to pay via Bank Transfer. When they pay via credit card, they are advised 
   to send the required information (in particular, Credit Card numbers) by 
   FAX; that is, do NOT send your Credit Card numbers by email. 
   In credit card payment Visa card, MasterCard, and Diners card will be 
   accepted. Personal checks cannot be accepted.
   All payments must be made in Japanese Yen.

Indicate method of payment below:

  [    ] Bank Transfer to

              Bank: Tokyo Mitsubishi Bank, Sendai Branch
              Account Name: IFIP TCS2000 Chair Takayasu Ito
              Account No. 1108671  

         From <bank name>:

         Date of transfer:

         Payer's name:

         Note: In Japan the bank number of Tokyo Mitsubishi Bank is 0005, and
               the number of its Sendai Branch is 320.

  [    ] Payment by Credit Card

         Credit Card Type <Visa, MasterCard, or Diners>:

         Card Number:

         Expiration Date:

         Signature (not needed for email):
  <Note>: When your payment is via Credit Card, send the above information
          by FAX to +81-22-262-5002, the fax no. of JTB Communications Inc. 
          Even when you send the above form by fax, send it by EMAIL 
          without  filling in Credit Card number for safety.
Registration and reservations will be confirmed upon receipt of payment.
Refunds will be made upon written request received through July 31st, 2000
by JTB Tohoku Communications Inc.

More information about the erlang-questions mailing list