3 Oct 1994 12:57

Chair in Computer Science


Dear Colleague,

Computer Science or Software Engineering at the University of
Birmingham.  I would appreciate it if you could distribute it
to those who might be interested.  The deadline is 14th October 1994.

With regards,

Marta Kwiatkowska
_________________

\documentstyle[10pt]{article}
% \pagestyle{empty}
\setlength{\oddsidemargin}{-0.5cm}
\setlength{\evensidemargin}{-0.5cm}
\setlength{\textwidth}{6.75in}
\setlength{\topmargin}{-0.5cm}
\setlength{\textheight}{9.9in}
\def\sp{\\[0.1cm]}
\def\Sp{\\[0.2cm]}
\def\SP{\\[0.45cm]}
\def\ps{\vspace{-0.2 cm}}
\def\Ps{\vspace{-0.4 cm}}
\def\PS{\vspace{-0.6 cm}}
\def\hs{\newline\hspace*{2.0cm}}
% indent next line


3 Oct 1994 14:32

BRICS positions


Postdoctoral positions at BRICS

There are to be several postdoctoral positions at BRICS for a period
of one to two years starting in 1995.  Applications by researchers are
welcome in the areas of logic, semantics and algorithmics.
Applications for positions should preferably be sent by e-mail and
include curriculum vitae and two or three names of referees for
recommendations as well as the referees' regular mail addresses and,

BRICS, a Centre for Basic Research in Computer Science, is funded by
the Danish National Research Foundation for the period 1994-1999.  Its
aim is to establish in Denmark important areas of basic research in
the mathematical foundations of Computer Science, notably Algorithmics
and Mathematical Logic.  The Centre is to develop these areas as a
joint effort between the theoretical-computer-science groups at Aarhus
University and Aalborg University.  The research plan is based on a
committment to develop Algorithmics and Logic integrated with existing
strong activities in Semantics of Computation, using a combination of
long-term efforts and a number of short-term, intensive programmes,
within carefully chosen scientific themes.  Organizationally, BRICS is
an autonomous centre with its own management, and yet with its
activities strongly integrated in the existing infrastructure and
student environments at the two universities.

The scientific planning is the responsibility of the following committee:

Glynn Winskel, Professor (Aarhus), Director
Mogens Nielsen, Associate Professor (Aarhus), Codirector


7 Oct 1994 13:58

Request for Subscription to types list



Kindly include the following address to the types list.

tcs@...

Sincerely,

Anil Seth

(For TCS group,
The Institute of Mathematical Sciences,


24 Oct 1994 15:40

Please publicize this in the types list

 To: Potential Contributors to Computing Surveys
Subject: Invitation to discuss the article "On Computational Complexity and the Nature of Computer
Science", by Juris Hartmanis
From: Peter Wegner, Incoming Editor in Chief, Computing Surveys

You are invited to submit a discussion piece to Computing Surveys on topics arising from the recent Turing
Award article by Juris Hartmanis in the October CACM. The overall topic of his article, "On Computational
Complexity and the Nature of Computer Science," lends itself to both technical discussion of questions
in theoretical computer science and broader discussion of policy issues relating to "Computing the
Future". I hope you will be able to participate so that we can start a meaningful discussion on the research
directions and goals of computer science in the pages of Computing Surveys. Juris has agreed to comment on
accepted discussion items. Potential topics for discussion, all of them related to questions raised in
the paper, are listed below:

1. What is the role of theory, and especially of complexity theory, in computer science? How does
complexity relate to other theoretical areas of computer science like semantics?
2. What are the critical research questions for the next decade? How is the change from algorithmic to
network and distributed computing technology affecting the paradigm of computer science research?
3. What distinguishes CS from the other sciences? Is it the wide range of scales, its concrete and
general-purpose conceptual models, or something else.
4. What is the status of automata theory and what are its current challenges?
5. What is the status of complexity theory and what are its current challenges?
6. What is the status of the P = NP problem and what is its relevance to
7. What is the role of nondeterminism in algorithms research, are there connections to concurrency
research?
8. What is the role of randomness, information theory, and Kolmogoroff complexity in theoretical research?
9. What is the role of algorithms in scalability and programming in the large?
10. What is the relation of theoretical and experimental computer science? Is the role of experiments


10 Oct 1994 10:57

Programs for Proof-nets


The following programs:

mll.c      a program for testing whether a
proof-structure in multiplicative
fragment of linear logic is logically sound, i.e.
is a proof-net

fmll.c     a program for testing whether a  proof
structure with units (1s and \bots) is
logically sound, i.e. represent (at least)
one proof of sequent calculus

are now available by ftp.

Both programs are   highly portable,
they are written in ANSI C, and can be compiled
in ANY computer where ANY C compiler is installed.

FTP instructions:

ftp gloxinia.cs.cuhk.hk
cd itnt
get mll.c
get fmll.c
bye


11 Oct 1994 17:50

Paper announcement


The following paper is obtainable by anonymous ftp from

boole.logique.jussieu.fr

It can be found in the directory pub/scratch/DJS, under the name

decostringopolaro.ps.Z

The directory DJS contains several related papers (read the

---------------------------------------------------
|      V. Danos, J.-B. Joinet & H. Schellinx        |
|                                                   |
|    "A NEW DECONSTRUCTIVE LOGIC: LINEAR LOGIC"     |
---------------------------------------------------

Abstract:

and quantifiers during the last four, five years.
Our approach to the problem is to understand this first of all as the
quest for a classical second order calculus equipped with a strong
(and, as much as possible, confluent) normalization, and a
denotational semantics.

Considering that there are many, seemingly unrelated, solutions, we


11 Oct 1994 23:02

Lambda Definability in Categorical Models


A Characterization of Lambda Definability
in Categorical Models of Implicit Polymorphism

Moez Alimohamed

University of Pennsylvania

This paper contains the work of Moez Alimohamed, a mathematics graduate
student at the University of Pennsylvania who died tragically on August 29th.
Lambda definability is characterized in categorical models of simply typed
lambda calculus with type variables.  A category-theoretic framework known
as glueing or sconing is used to extend the Jung-Tiuryn characterization of
lambda definability in Henkin models for the simply typed lambda calculus
first to ccc models, and then to categorical models of the calculus with
type variables.

WWW access is http://www.cis.upenn.edu/~andre/moez.html. The paper is also
available by anonymous ftp from the host ftp.cis.upenn.edu as the file
pub/papers/scedrov/def.ps.Z.


12 Oct 1994 14:09

LLL


An extended abstract of a forthcoming paper
LIGHT LINEAR LOGIC
is available by anonymous ftp
lmd.univ-mrs.fr
dir : pub/girard
name : LLLo.ps.Z

Abstract : The abuse of structural rules can have damaging complexity
effects.

---

Jean-Yves GIRARD
Directeur de Recherche

CNRS, Laboratoire de Mathematiques Discretes
163 Avenue de Luminy, case 930
13288 Marseille cedex 9

<girard@...>
(33) 91 82 70 25
(33) 91 82 70 26 (Mme Bodin, secretariat)
(33) 91 82 70 15 (Fax)


13 Oct 1994 19:40

LLW is decidable


The paper by A.Kopylov

\title{Decidability of Linear Affine Logic}
\author{Alexei P. Kopylov \\
Department of Mathematics and Mechanics \\
Moscow State University \\
119899, Moscow, Russia}
\date{September, 1994}

\begin{abstract}
The propositional Linear Logic is known to be undecidable.
In the current paper we prove that the full propositional Linear Affine
Logic containing all the multiplicatives, additives, exponentials,
and constants is decidable. The proof is based on a
reduction of the Linear Affine Logic to sequents of
specific normal forms'', and
on vector games interpretation adapted to these normal forms''.
\end{abstract}

is now issued as the preprint

CNRS, Laboratoire de Math\'{e}matiques Discr\{e}tes,
Pr\'{e}tirage n$^\circ$ 94-32, ~1994, 30~p.\\
Available by anonymous ftp from host lmd.univ-mrs.fr
and the file pub/kopylov/fin.dvi

Best regards,
Sergei Artemov



17 Oct 1994 20:59

DIMACS Special Year on Logic and Complexity


>From vardi@... Mon Oct 17 14:14 EDT 1994
>From: vardi@... (Moshe Vardi)

DIMACS 1995-96 Special Year on Logic and Algorithms
Call for Visitor & PostDoctoral Fellowship Applications

The DIMACS Center for Discrete Mathematics and Theoretical Computer
Science announces its 1995-6 Special Year on Logic and Algorithms.

DIMACS is a Science and Technology Center funded by the NSF,
whose participating institutions are Rutgers University, Princeton
University, AT&T Bell Laboratories, and Bellcore.  Research and
education activities at DIMACS focus on such areas as analysis of
algorithms, combinatorics, complexity, computational algebra, discrete
and computational geometry, discrete optimization and graph theory.
A primary activity of the Center is to sponsor year-long research
programs on specific topics of current interest, and one such program
is this Special Year on Logic and Algorithms.

A dichotomy in theoretical computer science is best demonstrated by
looking at the 1994 Handbook of Theoretical Computer Science.  Volume A
discusses algorithms and complexity, while Volume B treats formal models
and semantics.  Theoretical computer science in the United States is
largely "Vol. A"-ish, while European theoretical computer science is
largely "Vol. B"-ish.  The goal of this Special Year is to bridge the gap
between the two branches, focusing on three bridge areas: Computer-Aided
Verification, Finite-Model Theory, and Proof Complexity.  All three are
emerging research areas that fit naturally between Vol. A and Vol. B.

`