[Apologies for multiple copies] IFIP TCS2000 PROGRAM AND REGISTRATION INFORMATION ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -------------------------------------------------------------------------- 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 http://tcs2000.ito.ecei.tohoku.ac.jp/tcs2000/ Any inquiry on IFIP TCS2000 Program and Registration may be directed to TCS2000@ito.ecei.tohoku.ac.jp -------------------------------------------------------------------------- PRELIMINARY PROGRAM ^^^^^^^^^^^^^^^^^^^ [Outline] 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 ----------------------------------------- AUGUST 16 WEDNESDAY ^^^^^^^^^^^^^^^^^^^ 15:00 REGISTRATION at Sendai Tokyu Hotel till 20:00 18:00 WELCOME with light snack at Sendai Tokyu Hotel till 19:00 AUGUST 17 THURSDAY ^^^^^^^^^^^^^^^^^^ 9:30 OPENING SESSION Giorgio Ausiello (TC1 Chair and IFIP TCS2000 Co-Chair) Takayasu Ito (IFIP TCS2000 Co-Chair) 10:00 KEYNOTE PLENARY TALK 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 14:40 TRACK (1) INVITED TALK It is on the Boundary: Complexity Considerations for Polynomial Ideals Ernst Mayr (TU Muenchen) 15:30 Break SESSION (1.3), 15:50 - 17:30 15:50 An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks 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 13:30 TRACK (2) INVITED TALK 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 AUGUST 18 FRIDAY ^^^^^^^^^^^^^^^^ 9:10 KEYNOTE PLENARY TALK 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 Graphs 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 14:40 TRACK (1) INVITED TALK 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 13:30 TRACK (2) INVITED TALK 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 Conjugates 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 BANQUET SPEECH Non-Random Thoughts about Randomization Michael O. Rabin (Harvard U.) AUGUST 19 SATURDAY ^^^^^^^^^^^^^^^^^^ 9:10 KEYNOTE PLENARY TALK 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 13:30 TRACK (1) INVITED TALK Hierarchical State Machines Mihalis Yannakakis (Bell Labs, Lucent) 14:20 Break -----------// [TRACK (2)] 10:20 TRACK (2) INVITED TALK 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) ------------------------ [OPEN LECTURES] 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 ========================================================================== GENERAL INFORMATION ^^^^^^^^^^^^^^^^^^^ 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. Transportation 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 http://tcs2000.ito.ecei.tohoku.ac.jp/tcs2000/ Note: (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). Hotels 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 heavy. Note: Average temperatures in August at Sendai, Tokyo and Osaka are about 23.5 C, 26.5 C and 27.5, respectively. REGISTRATION AND RESERVATION INFORMATION ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ REGISTRATION FEES 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 HOTELS 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. JAPANESE DINNER PARTY 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. ============================================================================= IFIP TCS2000 REGISTRATION AND RESERVATION FORM ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Please register and make reservations by completing the form below and returning it by email to tcs02@thk.jtb.co.jp Registrants are advised to email a copy of their completed form to TCS2000@ito.ecei.tohoku.ac.jp 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) (Email) tcs02@thk.jtb.co.jp 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. REGISTRATION FOR IFIP TCS2000 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Last (Family) Name: First (Given) Name: Middle: Affiliation: Postal Address: City/State/Zip: Country: Phone: Fax: Email: Registration Status <Regular, Author, Committee Member, Student>: Number of Companions: Companions' names (if applicable): (A) Total Registration Fee(s) in Yen: HOTEL RESERVATION 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: JAPANESE DINNER PARTY A limited number of reservations are available for the Japanese dinner party at SHOZANKAN on August 19 to be arranged for participants from abroad. (B) 10,000 Yen x [ ] conference registrant(s): (C) 7,000 Yen x [ ] companion(s): TOTAL FEE IN YEN (A) + (B) + (C): Signature (not needed for email): METHOD OF PAYMENT FOR IFIP TCS2000 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.