pdm@daimi (Peter Mosses) (06/08/89)
N.B. The deadline for registration is June 20!
----------------------------------------------------------------------
The International Symposium on
Mathematical Foundations of Computer Science
MFCS 89
is the fourteenth in the series of MFCS symposia organized
alternatively in Czechoslovakia and Poland. This symposium is
organized by the Institute of Informatics of Warsaw University and
The Polish Information Processing Society.
The purpose of the meeting is to encourage research in theoretical
computer science and to bring together specialists from various
countries.
Principal areas of interest include:
logics of programs, parallel and distributed computing,
deductive data bases, automata and formal languages,
algorithms and data structures, software specification and validity,
complexity and computability theory.
In accordance with the tradition, the scientific program will include
8 invited talks and 43 short communications selected from a total 102
submitted papers by the Program Committee on the basis of originality
and relevance to the topic of the Symposium.
PROGRAM COMMITTEE
A. Arnold Bordeaux
J. de Bakker Amsterdam
A. Blikle Warszawa
M. Chytil Praha
P. van Emde Boas Amsterdam
A.P. Ershov
R. Freivalds Riga
H. Genrich St. Augustin
J. Gruska Bratislava
H. Langmaack Kiel
A. Maggiolo-Schettini Pisa
G. Mirkowska Warszawa (Chairperson)
B. Monien Paderborn
P. Mosses Aarhus
M. Protasi Roma
A. Salwicki Warszawa
W. Wechler Dresden
ORGANIZING COMMITTEE
K. Diks
M. Grabowski
A. Kreczmar
G. Mirkowska
A. Szalas
CONFERENCE BUREAU
Institute of Informatics
Warsaw University
00-901 Warszawa, PKiN room 850
POLAND
Telephone: +48-22- 26 82 58
Telex: 81 55 91 infuw pl
Telefax: +48-22- 26 82 58
and
Sports Tourist
Telephone: +48-22- 21 62 20 or 21 72 91
----------------------------------------------------------------------
SCIENTIFIC PROGRAM
MONDAY
August 28
Opening of the Symposium
INVITED LECTURES
Chairman: B. Monien
J. Hartmanis, D. Ranjan :
Tape bounded computations: review and new separation results.
D. Harel: A thesis for bounded concurrency
CONTRIBUTIONS - SESSION A: Chairman: M. Chytil
L.A. Hemachandra, A. Hoene, D. Siefkes:
Polynomial-time functions generate SAT: On P-splinters
D.A. Mix Barrington, P. McKenzie:
Oracle branching programs and Logspace versus P
V.A. Stetsenko:
One more method for proving lower bounds on the formula complexity of
boolean functions
K. Diks, T. Hagerup, W. Rytter:
Optimal parallel algorithms for the recognition and coloring
outerplanar graphs
J. Dassow, J. Hromkovic, J. Karhumaki, B. Rovan, A. Slobodova:
On the power of synchronization in parallel computations
CONTRIBUTIONS - SESSION B: Chairman: P. Mosses
B. Steffen:
Optimal data flow analysis via observational equivalence
J.N. Kok:
An iterative metric semantics for nondeterministic dataflow
F.S. de Boer, J.N. Kok, C. Palamidessi, J. Rutten:
Control flow versus logic: a denotational and declarative model for Guarded Horn Clauses
E.M. Schmidt, M.I. Schwartzbach:
An imperative type hierarhy with partial products
J. Farres-Casals:
Proving correctness of constructor implementations
TUESDAY
August 29
INVITED LECTURES
Chairman: J. Hartmanis
K. Mehlhorn, S. Naher:
Reusable efficient software(RES)
B. Trakhtenbrot:
Understanding nets
CONTRIBUTIONS -- SESSION A: Chairman: H. Langmaack
B. Just:
Integer relations among algebraic numbers
A. Saoudi:
Pushdown automta on infinite trees and Omega-Kleene closure of
context-free tree sets
C. Calude:
Ehrenfeucht's theorem and Hilbert basis theorem: a constructive glimpse
U. Heuter:
Generalized definite tree languages
M. Zaionc:
How to define functionals on free structures in typed lambda calculus
A. Weber:
On the lengths of values in a finite transducer
CONTRIBUTIONS - SESSION B: Chairman: D. Harel
M.G. Gouda, R.R. Howel, L.E. Rosier:
System simulation and the sensitivity of self-stabilization
R. van Glabbeek, U. Goltz:
Equivalence notions for concurrent systems and refinement of actions
J. Ch. Meyer, E.P. de Vink:
Pomset semantics for true concurrency with synchronization and
recursion
E. Badouel:
Algebraically closed theories
J. Knoep, B. Steffen:
Finite constants: characterizations of a new decidable set of
constants
C. Josselin, P-P. Moskowitz:
Memory and algebra
WEDNESDAY
August 30
CONTRIBUTIONS - SESSION A: Chairman: K. Mehlhorn
R. Holte, L. Rosier, I. Tulchinsky, D. Varvel:
Pinwheel scheduling with two distinct numbers
M. Slusarek:
A coloring algorithm for interval graphs
J. Wiedermann:
On the computational power of symmetric neural networks
B. Chlebus, K. Diks, W. Rytter, T. Szymacha:
Parallel complexity of lexicographically first problems for
tree-structured graps
V. Palko, O. Sykora, I. Vrto;
Area complexity of merging
CONTRIBUTIONS - SESSION B: Chairman: M. Protasi
Ch. Elkan:
A rational reconstruction of nonmonotonic TMSs
J.H. Andrews:
Proof-theoretic characterizations of logic programming
D. Szczepanska:
The Hoare-like verification system for a language with exception
handling mechanism
U. Petermann:
An extended Herbrand theorem for first-order theories with equality
interpreted in partial algebras
THURSDAY
August 31
INVITED LECTURES
Chairman: W. Wechler
V.N. Agafonov:
From specification languages to specification knowledge bases
B. Courcelle:
Monadic second-order logic and context free graph grammar
CONTRIBUTIONS - SESSION A: Chairman: P. van Emde Boas
M. Regnier:
Knuth-Morris-Pratt algorithm: an analysis
Ch. Meinel:
Switching graphs and their complexity
S. Iwanowski:
Testing approximate symmetry in the plane is NP-hard
W. Kowalczyk:
Complexity of decision problems under incomplete information
D.T.H. Ng, B.J. Oommen:
On doubly linked list reorganizing heuristics
F.M. Ablayev:
On comparing probabilistic and deterministic automata complexity of
languages
CONTRIBUTIONS - SESSION B: Chairman: A. Arnold
H. Andreka, I. Nemeti, I. Sain:
On the strength of temporal proofs
V. Manca, A. Salibra, G. Scollo:
On the nature of TELLUS
S. Yoccoz:
Recursive omega-rule for proof systems
P. Peladeau:
Logically defined subsets of N^k
P. Weil:
On varietes of languages closed under products with counter
A. Petit:
Characterization of recognizable trace languages by distributed automata
FRIDAY
September 1
INVITED LECTURES
Chairman: A. Salwicki
E.R. Olderog:
Correctness of concurrent processes
A. Mazurkiewicz:
Synchronization and compositionality (tentative title)
V. Kotov:
Adequacy of structure and behaviour
OPEN SESSION
----------------------------------------------------------------------
INFORMATION
LOCATION
The symposium will be held at Porabka-Kozubnik HPR Center (about 22 km
from Bielsko-Biala). (Attention! In the first announcement it was
another place proposed for the conference site.)
CONFERENCE OFFICE
The conference office will be located in the lobby of the main HPR
Center building and will be open from 9.00 a.m. to 11.00 p.m. on
Sunday, August 27 and from 8.00 a.m. to 5.00 p.m. on Monday till
Friday (August 28 - September 1).
TRANSPORTATION
The nearest international airports are Warszawa (Warsaw) and Krakow
(Cracow). The distance from Warszawa to Porabka is about 350 km and
from Krakow to Porabka about 80 km.
There are two convenient trains going directly from Warszawa to
Bielsko-Biala. The first one starts from Warszawa-Centralna Station at
2.20 p.m. reaching Bielsko-Biala at 8.03 p.m. on the same day. The
second is an express train starting from Warszawa-Centralna Station at
5.50 p.m. and reaching Bielsko-Biala at 9.52 p.m. There is a bus
service from Krakow to Bielsko-Biala. Buses start from Krakow PKS bus
station situated near Krakow Glowny train station.
From Bielsko-Biala you can reach Porabka by bus from the PKS Station.
HPR center is situated about 1.5 km from the bus stop in Porabka. A
taxi to the HPR Center costs approximately 2$.
We arrange special conference buses on Sunday August 27 from Warszawa
to Porabka HPR at 3.30 p.m. (they will be waiting for the participants
in the front of the Palace of Culture and Science, the sky-scraper
situated in the city center nearby Warszawa-Centralna Train Station
and will bear an MFCS sign). The same day conference buses will
transport participants from Bielsko-Biala trian station to Porabka HPR
Center at 22.00 p.m.
ACCOMMODATION AND MEALS
All participants will be accommodated at the HPR Center in a single or
double rooms. There is a limited number of single rooms. Lodging is
reserved since Sunday, August 28 till Saturday, September 2. Daily
rates of full pension (lodging and meals) are 50$ for single rooms and
40$ for double rooms (per person). The first meal will be supper
served on Sunday August 28, the last meal will be breakfast on
Saturday, September 2.
REGISTRATION FEE
The registration fee is 80$. It covers all materials, an excursion,
refreshments in breaks between sessions, a welcome party and the
conference dinner.
REGISTRATION
Those who wish to participate in the MFCS' 89 symposium should
complete the enclosed registration card and mail it together with a
copy of your receipt confirming payment of the registration fee and
accommodation to the secretarial office. It should reach the
conference bureau not later than June 20, 1989. Please preserve one
copy of the receipt for presentation at the border. Registration will
be confirmed by the organizers.
The number of participants is limited and the Organizing Committee
reserves the right of replacing anyone who does not return his
registration card by June 20 by another person on the waiting list.
PAYMENTS
Checks should be made payable to:
PBK
Panstwowy Bank Kredytowy I Oddz.
Warszawa, Poland
Nr 370002-1515
(for MFCS'89 conference)
Participants from the countries with convertible currency are required
to pay the fees in US dollars or in an equivalent currency.
VISA AND EXCHANGE
A valid passport (and for citizens of most countries also a visa) is
required for entering Poland. Visas are issued by Polish embassies and
consulates throughout the world. No Polish visas are issued at the
Polish border crossings.
In order to be exempted from the obligatory money exchange, present a
photocopy documenting your payment of the registration fee when
applying for Polish entry visa, and when crossing the Polish border.
PROCEEDINGS
The proceedings of the symposium will be published by Springer Verlag
as a volume of the Lecture Notes in Computer Science. Each registered
participant will receive a copy. Additional copies may be ordered
directly from Springer-Verlag.
PRESENTATION
For oral presentations an overhead projector 25 x 25 cm and a
blackboard will be available. The language of the symposium is
English.
SOCIAL PROGRAM
All participants and accompanying persons are invited to take part in
the following activities:
Welcome Party, on Monday, August 29, from 7 p.m.
Excursion, on Wednesday afternoon, August 30.
Conference Dinner, on Thursday, August 31, from 7 p.m.
MFCS' 89
It is necessary to attach a photocopy of a remittance of the
registration card. Only registration cards with attached
certifications will be accepted.
There is a possiblity to visit Cracow on Saturday, September 2. Anyone
who wishes to take part in this trip please contact directly
Tourist Agency
Sports-Tourist
84/92, Marszalkowska Stree
00-514 Warszawa
Poland
Tel: +48-22- 21 62 20 or 21 72 91
----------------------------------------------------------------------
REGISTRATION CARD
Fourteenth International Symposium
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
Porabka-Kozubnik, POLAND
August 28 - September 1, 1989
Please complete and return this card with a certification of
remittance to reach us no later than June 20, 1989 to the following
address:
MFCS'89
Institute of Informatics
Warsaw University
00-901 Warsaw, PKiN room 850
Poland
Tel./Telefax: +48-22- 26 82 58
Telex: 815591 infuw pl
FAMILY NAME ....................
FIRST NAME ....................
MAILING ADDRESS ....................
....................................
....................................
Telephone: ....................
Telex: ....................
Telefax: ....................
NAMES OF ACCOMPANYING PERSONS
1. .................... Mr/Ms
2. .................... Mr/Ms
DATE OF ARRIVAL ....................
Are you going to take the conference bus?
[ ] YES [ ] NOT
Payments for the symposium:
Registration fee
participants 80$
accompanying persons 30$
Accomodation
[ ] single room 300$ (6*50$)
[ ] double room 240$ (6*40$)
Checks should be made payable to:
PBK
Panstwowy Bank Kredytowy
I Oddz. Warszawa, Poland
Nr 370002-1515
(for MFCS'89 conference)
Name of prefered roommate:
Date: .....................
Signature: .....................