Posted to comp.theory February 21, 1996:
THEORIEDAG 96
Nederlandse Vereniging voor Theoretische Informatica (NVTI)
vrijdag 1 maart 1996
Jaarbeurs Congrescentrum Utrecht
Het is ons een genoegen u uit te nodigen tot het bijwonen van de
Theoriedag 96 van de NVTI, de Nederlandse Vereniging voor Theoretische
Informatica, die zich ten doel stelt de theoretische informatica te
bevorderen en haar beoefening en toepassingen aan te moedigen.
De Theoriedag 96 zal gehouden worden op vrijdag 1 maart 1996 in het
Jaarbeurs Congrescentrum te Utrecht, en is een voortzetting van de
reeks jaarlijkse bijeenkomsten van de NVTI die een jaar geleden met
de oprichtingsbijeenkomst begon.
Evenals vorig jaar hebben wij een aantal prominente sprekers uit
binnen- en buitenland bereid gevonden deze dag gestalte te geven
door voordrachten over recente en belangrijke stromingen in de
theoretische informatica. Naast deze wetenschappelijke inhoud heeft
de dag ook een informatief gedeelte, in de vorm van een algemene
vergadering waarin de meest relevante informatie over de NVTI gegeven
zal worden, alsmede presentaties van de onderzoekscholen OZL, IPA en SIKS.
--------------------------------------------------------------------------
Lidmaatschap NVTI
Alle leden van de voormalige WTI (Werkgemeenschap Theoretische
Informatica) zijn automatisch lid van de NVTI geworden.
Aan het lidmaatschap zijn geen kosten verbonden; u krijgt de
aankondigingen van de NVTI per email of anderszins toegestuurd.
Was u geen lid van de WTI en wilt u lid van de NVTI worden:
u kunt zich aanmelden bij het contactadres beneden (M. Brune, CWI),
met vermelding van de relevante gegevens, naam, voorletters, affiliatie
indien van toepassing, correspondentieadres, email, telefoonnummer.
---------------------------------------------------------------------------
Programma
09.30 Ontvangst en koffie
10.00 - 10.10 Opening door G. Rozenberg
10.10 - 11.00 Voordracht Emo Welzl
11.00 - 11.30 Koffie
11.30 - 12.20 Voordracht Henk Barendregt
12.20 - 13.00 Informatie over Onderzoekscholen OZL, IPA, SIKS
13.00 - 14.20 Lunch
14.20 - 14.50 Algemene Vergadering
14.50 - 15.40 Voordracht Wolfgang Thomas
15.40 - 16.00 Thee
16.00 - 16.50 Voordracht Joost Kok
---------------------------------------------------------------------------
Lunchdeelname
Het is mogelijk aan een georganiseerde lunch in het Jaarbeurs
Congrescentrum deel te nemen; hiervoor is aanmelding verplicht.
Dit kan per email of telefonisch bij Mieke Brune (mieke@cwi.nl,
020-592 4249), tot een week tevoren (23 februari).
De (niet geringe) kosten kunnen ter plaatse voldaan worden;
deze bedragen f 25,95.
Wij wijzen erop dat in de onmiddellijke nabijheid van de vergaderzaal
ook uitstekende lunchfaciliteiten gevonden kunnen worden, voor wie niet
aan de georganiseerde lunch wenst deel te nemen.
---------------------------------------------------------------------------
Abstracts van voordrachten
Abstractions of Linear and Convex Programming --
Quest for Lower Bounds
Emo Welzl, Freie Universitaet Berlin
Recent progress in the knowledge of the combinatorial complexity of
linear and convex programming problems came along with general abstract
frameworks. On the one hand these frameworks extend the applicability
of the randomized techniques to many problems. On the other hand,
they reveal that very little of the preconditions supplied by the
"original" problems (like LP) are exploited for the derivation of
the subexponential upper bounds.
One way towards a better understanding of the structure of the problems
at hand is the attempt to derive lower bounds in these frameworks.
In this talk we present AOP's (abstract optimization problems) by Gaertner,
and LP-type systems. We briefly indicate how the upper bounds are obtained,
state their implications for natural problems, and discuss aspects of lower
bound proofs (although we are not able to provide even modest results).
Here is the AOP setting. We are given a set $H$ with
a linear ordering $\prec$ on its power set $2^H$. The goal is
to determine the maximum element in this ordering.
There are no assumptions whatsoever on the ordering.
The only information we can retrieve is the following:
For $F$, $G$, $F \subsetqe G \subseteq H$ an oracle tells
us whether $F$ is maximum (w.r.t. $\prec$) in $2^G$, and
if not, provides an $F' \subseteq G$ with $F \prec F'$.
Clearly, the oracle suffices to determine the solution in
at most $2^{|H|}-1$ queries, and this is already optimal
for any deterministic algorithm. However, there is a
randomized procedure which determines the solution with
expected at most $e^{2 \sqrt{|H|} + o(\sqrt{|H|}) }$ oracle
queries. No lower bounds for randomized methods are known,
while any improvement on the upper bound has immediate
implications on the combinatorial complexity of
Linear Programming (and many other problems).
--------------------------------------------------------------------------
The impact of the lambda calculus
Henk Barendregt, Katholieke Universiteit, Nijmegen
On three levels the lambda calculus has had considerable impact.
1. Foundations: 1a computability; 1b provability.
2. Functional programming.
3. Proof verification.
As to 1, the notions of computability and of provability can be
described via the lambda calculus.
As to 2, as a consequence of 1a, lambda calculus can be used as the
kernel of a programming language. This so called functional programming
even can be done interactively.
As to 3, as a consequence of 1b, lambda calculus can be used to
formally describe proofs. A technological spin-off is the interactive
development and automated verification of proofs.
---------------------------------------------------------------------------
Finite-state recognizability and logic: from words to graphs
W. Thomas, Universitaet Kiel
A fundamental theorem of Buechi says that finite automata over
(finite or infinite) words have the same expressive power as monadic
second-order logic (MSO). Today, applications of this result are visible
in several areas: decidability of mathematical theories, the structure
theory of regular languages, circuit complexity and descriptive complexity,
and last but not least verification and synthesis of finite-state programs.
In this lecture we report on recent progress in establishing a
correspondence between automata and logic formulas over the more
general domain of labelled graphs (instead of labelled linear
orderings, i.e. words). An interesting case is supplied by the
"grid-graphs" or "two-dimensional words". We review some versions
of automata over graphs which have been considered and show that a
natural class of finite-state acceptors, called "finite tiling systems",
characterizes existential monadic second-order logic. (The proof relies
on a model theoretic technique, the Ehrenfeucht-Fraisse game.)
We verify the failure of a complementation theorem for tiling systems,
which shows that in the logical characterization the restriction to
existential MSO cannot be avoided. This gives also a simple argument
that the monadic version of the polynomial time hierarchy does not collapse.
Finally, we discuss over which special classes of graphs a
complementation result can be regained. This is of interest especially
in the case of labelled acyclic graphs (or partial orders),
as used for modelling computations of concurrent programs.
We outline some preliminary results in this direction, however
leaving open an exact description of those graph classes
where Buechi's theorem holds.
--------------------------------------------------------------------------
Theory of Genetic Algorithms
Joost N. Kok, Universiteit Leiden
Biocomputation studies biologically inspired computation models
like neural networks, evolutionary computation and DNA-computing.
Biocomputation for learning semi-optimal solutions to ill-defined
problems is widely used by software developers in commercial appli-
cations. The reason that these methods are used often in practice
is that they are relatively easy to program while empirical evidence
shows that the resulting systems perform well.
Evolutionary computation encompasses algorithms based on the
biological process of natural selection and their use for search and
optimization. Evolutionary computation searches for good solutions by
means of an evolution proces. In this process a set of candidate
solutions is improved with respect to an optimisation criterion by
selection, and by genetic operations like mutation and cross-over.
Their main areas of application are to problems of optimisation,
design, routing and scheduling.
There are three broadly similar avenues of investigation within
evolutionary computation: genetic algorithms, evolution strategies
and evolutionary programming.
In this presentation we give an overview of methods for examining
fundamental properties of genetic algorithms. The presentation will
be of a tutorial nature. We do not assume knowledge about genetic
algorithms.