[Apologies for multiple copies]
IFIP TCS2000 PRELIMINARY 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
[EMAIL PROTECTED]
--------------------------------------------------------------------------
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
Martin Abadi (Bell Labs, Lucent)
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, 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
16:15 Task Distributions on Multiprocessor Systems
Evgeny V. Shchepin, Nodari Vakhania
16:40 Fast Interpolation using Kohonen Self-Organizing Neural Networks
Olivier Sarzeaud, Yann Stephan
17:05 Steganography Using Modern Arts
Galdi Clemente, Blundo Carlo
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
Vladimiro Sassone
16:40 Fibred Models of Processes: Discrete, Continuous, and Hybrid Systems
Marcelo 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
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
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 CA
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
A Compositional Model of Time and Uncertainty
Thomas 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)
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
[EMAIL PROTECTED]
Registrants are advised to email a copy of their completed form to
[EMAIL PROTECTED]
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) [EMAIL PROTECTED]
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.
