Report on TC 1 - Foundations of Computer Science

Giorgio Ausiello

Part I. Council

1 Introductory remarks

The main efforts in the first two years of activity of TC1 have been devoted to starting new working groups and to promote further initiatives.
It is worth noting that such efforts successfully led to the promotion of two new working groups in two hot areas of theoretical computer science: term rewriting and formal methods in security. The TC has activated a web site containing general information on the TC, links to WGs, links to scientific events organized within the TC.The address is   and is also accessible from the IFIP web site.

2. Meetings

The last meeting of the TC has been held last August in Brno, Czech Republic in the occasion of MFCS 98. A meeting in Atlanta (USA) on May 5, 1999 is planned. It will be hosted by the ACM representative in TC1, David Johnson, on the occasion of the Federated Computing Research Conference.

3. Changes in Membership and Officers

Until now only the representatives of ten countries have been formally appointed (China, Denmark, Germany, Hungary, Japan, Poland, Portugal, Slovakia, Thailand, United States). The membership of TC 1 is therefore still essentially the same as it was defined when SG 14 was established.
This is the major problem we are encountering for becoming fully operative and proceeding in appointing experts and officers.

4. Working Group activities

TC 1 has now six working groups. The proposal for a seventh WG is ready for approval. All of them are formed by the leading experts in the various fields and in most cases the groups have a widely recognized role in their respective scientific communities. TC1 has started an action to renovate the membership of the Working Groups and to encrease the attendance of young researchers to WG meetings.

WG 1.1 on Continuous Algorithms and Complexity has 36 members. The Group is chaired by Joe Traub. It has an electronic newsletter sent to 220 people. There were two week-long meetings in 1998

Two meetings are planned for 1999.

A new annual prize for achievement in information-based complexity has been created. It will consist of three thousand dollars (coming from institutions different from TC1) and a certificate. The deadline for nominations is March 31, 1999. The 1999 prize will be awarded during the FoCM Conference in Oxford. Between meetings WG 1.1 members communicate through CAC-NET.

WG1.2 on Descriptional Complexity has been chaired by Detlef Wotschke since October 1996. The revival of IFIP WG 1.2 on Descriptional Complexity, which was started since then, is making significant progress.
WG 1.2 has more than 50 members from many countries and is chaired by Detlef Wotschke. Since descriptional complexity has many facets and appears in different forms in various areas, the activities of WG 1.2 are subdivided into several subareas: Kolmogorov Complexity; Descriptional Complexity for Grammars, Automata and Related Structures; Program Complexity and Reliability of Software; Descriptional Complexity and Mathematical Linguistics.
A few more subareas are being planned. To underscore the multi-disciplinary aspect of descriptional complexity, the possibility of cooperating with other IFIP working groups (especially in applied areas) will be explored.

Since last September the following meetings have taken place:

All workshops held in 1998 turned out to be very successful!

The following events are planned:

WG1.3 on Algebraic Specification of Languages is chaired by Peter Mosses.
The group has promoted the Common Framework Initiative for algebraic specification and development (CoFI, coordinated by Peter Mosses 1995-98, and by Don Sannella since August 1998). In October 1998, CoFI completed its design of CASL, the Common Algebraic Specification Language, which is based as much as possible on a critical selection of features that had previously been explored in various contexts; CoFI WG also became established as an ESPRIT working group. All the coordinators of CoFI WG task groups are WG1.3 members. CoFI WG is now working on sub-languages and extensions of CASL, translations between CASL and other languages, tools, methodology, and applications to reactive system specification.

The survey book on Algebraic Foundations of Systems Specification (edited by E. Astesiano, H.-J. Kreowski and B. Krieg-Bruckner) is due to appear in the second quarter of 1999. The book will be printed by Springer as an IFIP State-of-the-Art report. It is expected that the work on CASL will also result in IFIP publications.

WG 1.4 on Computational Learning Theory is chaired by Carl Smith. The main activity of WG 1.4 has been to promote computational learning theory by giving best student paper awards at each of the three primary learning theory conferences.

TC1 anticipated another $1500 to continue this program in 1998. A scholarship will be given to Andras Antos from Budapest for his paper ``Lower Bounds on the Rate of Convergence of Nonparametric Pattern Recognition'' at the EuroCOLT meeting in Dormund next month. The committee had several discussion on how to continue this program without further financial contributions from IFIP. They concluded that it would have been best to set up a separate mechanism from each of the three conferences. For the COLT conference, an award has being set up in memorial to "Mark Fulk", a researcher in the field who died unexpectedly in 1997. The ALT meeting, being organized in Japan, has a long tradition of corporate and other funding of the meeting. Consequently, a best student paper award will become part of the obligation of the local organizer for the meeting. The ALT award was named for "E. Mark Gold" and will be given for the first time at the ALT meeting in Tokyo in 2000. WG 1.4 committee members are actively trying to find a mechanism to independently fund a best student paper award also for the EuroCOLT conference in the future.
At the last meeting, the WG decided to gain more acceptance in the research community by trying to reformulate itself as a truely representative body along the lines of asking for representatives from various conference steeing committees and electronically electing some members at large but progress has been slow on this side.

WG 1.5 on Cellular Automata and Machines is chaired by Giancarlo Mauri, who succeeded to Roland Vollmar. On december 10-12, 1998, Eric Goles and Martin Matamala organized the annual workshop of the WG in Santiago (Chile). There were about 45 participants, and 24 papers were presented, on different aspects of CA's.
The meeting of the WG members took place in this occasion. It was decided to propose a new president, Giancarlo Mauri, and a new secretary, Thomas Worsch, in substitution of Roland Vollmar and Bruno Durand, respectively.
New members have been added to the WG: Stefania Bandini, Nino Boccara and Kenichi Morita. Stefania Bandini and Thomas Worsch have been charged to prepare a report on industrial applications of Cellular Automata. Finally, it was decided that the next meetings will be in Lyon in 1999 and in Japan in 2000.

Part II - TA

1. Promotion of new WGs

Feeling that WGs are one of the most prominent forms of activity of a Technical Committee, in actions for the creation of new WGs have been undertaken by TC1 during 1998. A new working group in the area of Term Rewriting (promoted by Jeh Hsiang) has been approved at the last IFIP GA.
At the same time Roberto Gorrieri has prepared the proposal for a WG on Theoretical Foundations of Security Analysis. Security is a fast growing area of Informatics, with increasing relevance to real life applications such as internet transactions and electronic commerce. Theoretical foundations for the analysis (or the design) of security aspects of these applications are badly needed in order to validate and prove (or guarantee) their correctness. The new group will have the aim of investigating the theoretical foundations of security as an independent discipline with firm grounds in logic, semantics and complexity; promoting new areas of application of theoretical techniques in computer security; providing a platform for presenting and discussing emerging ideas and trends; making formal methods amenable to the security practicioners, hence increasing awareness of formal verification techniques for security in the computer science community at large. The main research topics relevant for the Working Group include: formal definition and verification of the various aspects of security: confidentiality, integrity, authentication and availability; new theoretically-based techniques for the formal analysis and design of cryptographic protocols and their manifold applications (e.g., electronic commerce); formal techniques for the analysis and verification of mobile code etc.

In advanced state but still underway is the proposal for a working Group in the area of Two dimensional combinatorial structures and languages (promoted by Maurice Nivat). Also in the area of Computational Logic the involved scientist are showing new interest in having a WG in TC1 as an 'umbrella' organization for the several initiatives yearly held in the field. This opportunity will be further explored.

2. Other Initiatives

In the year 2000 TC1 will organize its first conference on Theoretical Computer Science. The conference will be held in Sendai (Japan) from August 17 to August 19, just before the IFIP World Computing Congress in Beijing.
General Chairman of the Conference will be Takayasu Ito. A Steering Committee including Wilfred Brauer, Michel Rabin, John Staples, Joe Traub, besides Takayasu Ito and Giorgio Ausiello, has been formed with the aim of defining the general outline of the conference. It is in the intention of the organizers to give large space in the conference to young bright scientists that should give their view on the development of TCS in the next century. Particular attention will be devoted not to overlap with the theoretical aspects involved in the Congress on Software that is part of the IFIP WCC.

Prof. Giorgio Ausiello