IFIP General Assembly
Natal, September 4-5, 2001

Report on TC 1
Foundations of Computer Science

 Giorgio Ausiello

Part I. General Assembly

1. Introductory remarks.

During the first triennium of life of TC1 the main activity of the TC has been devoted to the creation of new working groups. To our view, in fact, working groups are the main expression of the scientific role of a TC. It is worth noting that such efforts successfully led to the creation of two new working groups in hot areas of theoretical computer science: term rewriting and formal methods in security. New initiatives for the creation of working groups are on their way.

The second line of activity is directed to guaranteing the presence of theoretical issues in the main IFIP sponsored international events. In the IFIP World Congress 2000 a meaningful presence has been guaranteed through the involvement of WG1.3. In the IFIP World Congress 2002 TC1 is organizing a full subconference, TCS 2002. The conference is Chaired by Nicola Santoro and consists of two tracks, one dedicated to Algorithms and Complexity (chaired by Ricardo Baeza - Yates) and one dedicated to Logics and Semantics (chaired by Ugo Montanari).

Such issue were debated at the last TC1 Meeting that was held in Crete on July 10, 2001, during the SIGACT-EATCS co-sponsored event consisting of the three conferences ICALP, STOC and SPAA. In particular the organization of TCS 2002 has been discussed and the decision has been to give more emphasis to the focus of the Conference: IT Foundations in the Era of Network and Mobile Computing in order to encourage the submission of papers that can attract a larger audience among the IFIP WCC attendees. The second issue that has been discussed is the possible creation of a WG in Quantum Computing.

More information on the activity of TC1 can be accessed through the TC1 web site. The site contains general information on the TC, links to WGs, links to scientific events organized within the TC and to events of interest for the TC1 community. The address is http://www.dis.uniroma1.it/~ifip-tc1/  and is also accessible from the IFIP web site.

2. Changes in Membership and Officers.

TC1 has now twenty-two official members from national societies and organizations: Argentina, Australia, Austria, Bulgaria, China, Denmark, Germany, Great Britain, Greece, Hungary, Italy, Japan, Poland, Portugal, Slovakia, Slovenia, South Africa, Spain, The Netherlands, Thailand, ACM and IEEE). All preceding members are still invited to attend TC1 meetings and will be invited until the full new membership will be achieved. Note that several countries with an extremely active theory community, such as Czech Republic, India, Russia, have not yet nominated their representatives. France has announced the nomination of a representative but no formal communication has been received yet. All members of the previous SGFCS are still invited to the meetings.

Still pending is the problem of electing one (or two) vice-chairman. In Geneva a panel consisting of Gruska, Ito and Ausiello has been set up for selecting possible candidates but no viable proposal has yet been formulated.

4. Working Group activities.

TC 1 has now seven working groups. All the Working Groups have a considerable acivity and are involved in the organization of several meetings every year.

WG 1.1 on Continuous Algorithms and Complexity is chaired by Joseph F. Traub; the Secretary is Arthur G. Werschulz. WG 1.1 continues its very active program of international meetings. In 2001 there will be a meeting in Oberwohlfach (Germany). In 2002 there will be meetings in Minneapolis (USA) and Schloss Dagstuhl (Germany). The members of WG 1.1 stay in touch via CAC-NET, an electronic newsletter which is sent to over 250 people.

WG1.2 on Descriptional Complexity is chaired by Detlef Wotschke with Helmut Juergensen and Chandra Kintala both serving as vice-chairmen. Descriptional Complexity has many facets and appears in different forms in various areas. Therefore the activities of WG 1.2 are subdivided into several subareas: Kolmogorov Complexity; Descriptional Complexity for Grammars, Automata and Related Structures; Descriptional Complexity and Software Reliability; Descriptional Complexity and Mathematical Linguistics. Because of the interdisciplinary aspects of Descriptional Complexity, WG 1.2 is currently exploring closer cooperation with IFIP WG 10.4 (Dependable Computing and Fault Tolerance). Chandra Kintala, one of the vice-chairmen of WG 1.2, is also a member of WG 10.4 and has held and is holding official functions with the International Conference on Dependable Systems and Networks which is sponsored on a regular basis by IFIP WG 10.4.

Since the date of the last report WG 1.2 has held or has jointly held the following meetings:

The following meetings will be held in 2001 and are being planned for 2002:

DCAGRS'2001 - Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Vienna, Austria, July 20 - 22, 2001, in cooperation with DLT'2001, July 16 - 20, 2001.

Workshop on Descriptional Complexity and Mathematical Linguistics, date and location to be determined.

DCAGRS'2002 - Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, possibly in connection with TCS 2002 in Montreal/Canada.

FDSR'2002 - Workshop on Formal Descriptions and Software Reliability, possibly in cooperation with IFIP WG 10.4 and in connection with TCS 2002 in Montreal/Canada.

Workshop on Kolmogorov Complexity and its Applications, possibly in connection with TCS 2002 in Montreal/Canada.

These last three workshops could also be organized as one workshop with three different sections. For the organization of these workshops in Montreal we would need the local organizing support of the TCS 2002 organizing committee. Another option would be to have

these last three workshops take place at the University of Western Ontario in London/Ontario. Helmut Juergensen has offered to host these workshops there. In order to underscore the connection with TCS 2002 and IFIP, these workshops would in this case be scheduled to take place directly before or after TCS 2002.

WG1.3 on Foundations of System Specification is chaired by Peter Mosses. CoFI, the Common Framework Initiative for algebraic specification and development of software, continues to be a major focus of activity. ESPRIT funding for a CoFI WG ended in April 2001, and CoFI has returned to its original status as an initiative relying primarily on the unfunded efforts of its participants. Don Sannella is continuing as overall coordinator.

As predicted in last year's report, the WG1.3 meeting held in California, summer 2000, turned out to be a relatively small one, with only 15 participants, and it was cut down to 3 days duration.  The meeting was nevertheless a particularly useful and productive one, with plenty of time for discussions. The meeting included a special session on "observability", organized by Rolf Hennicker (currently a WG1.3 Observer), as well as a presentation of the final design for CASL, the Common Algebraic Specification Language.

In contrast, the 2-day WG1.3 meeting that was held in Genova at the end of March 2001, adjacent to the joint WADT/CoFI WG workshop and ETAPS conferences, was attended by 20 Members, 7 Observers, and 2 accompanying young researchers. One major item was the report of the expert reviewers provided by WG1.3 to assess the final design of CASL: the report recommended approval of the design, and this was granted by a unanimous vote by the Members present at the meeting.

The next WG1.3 meeting is intended to take place in January 2002, for 4 days in the French Alps. The details are still being finalized, but it is hoped that altogether at least 15 Members and Observers will attend.  The next WG1.3 meeting after that is to be a 2-day meeting held on Chiemsee, near Munich, in September 2002, co-located with WADT: Workshop on Algebraic Development Techniques, which is sponsored and organized by WG1.3.

WG1.3 is sponsoring also ICGT'02: International Conference on Graph Transformation, Barcelona, October 2002, which is organized by, and of considerable interest to, WG1.3 Members.

The WG1.3 activities connected with CASL have been making slower progress than had been hoped: the formal semantics of CASL has been updated to the final design of CASL, but still needs editorial work to get it into an appropriate form for publication; the CASL User's Guide has been severely delayed due to unanticipated obligations imposed on one of the authors - a draft is now not expected until the end of the summer (2001); the libraries of CASL specifications are being polished, and a stable version is expected in autumn 2001.  The submission of a publishing proposal for an IFIP book on CASL (to include samples of all the above) has therefore been deferred yet again. The increasing pressure on the intended contributors, and the current activities, should however lead to the completion and submission of the proposal this autumn.

WG 1.4 on Computational Learning Theory is chaired by Arun Sharma. The last main event supported by the IFIP WG1.4 was the Eleventh International Conference on Algorithmic Learning Theory (ALT,00) during December 11-13, 2000 in Sydney, Australia. This was the first ALT conference outside the umbrella of JSAI (Japanese Society for Artificial Intelligence). The conference was collocated with the Pacific Knowledge Acquisition Workshop, and the two events shared invited speakers. The combined participation of the two events was over 100.  During the conference Mark Gold Award for the Best  Student Paper was awarded to Gunter Grieser.

The venue for this year's ALT conference was decided to be Washington, DC. This is the first time that the ALT series travels to North America, and it will be colocated with the Discovery Science Conference during November 26-29, 2001 in Washington, DC.

The next meeting of the IFIP Working Group 1.4 will be held during the combined COLT (Annual Conference on Computational Learning Theory) and EuroCOLT (European Conference on Computational Learning Theory) conferences in Amsterdam during 16-19 July 2001.  At this combined event, there will be a proposal for the merger of these two conferences. At this meeting, the composition of the IFIP Working Group 1.4 and the subject the next chair will be discussed, as the two year term of the current chair will be over.

WG 1.5 on Cellular Automata and Machines is chaired by Giancarlo Mauri. The last WG meeting was held in Osaka, August 21, 2000. 6 members attended. The WG chair proposed to admit three new members: Marianne Delorme (F), Kojiro Kobayashi (JP) and Maurice Margenstern (F). The proposal was accepted.

It was decided to accept the offer of Bruno Durand to organize the next workshop in Marseille, if possible in September 2001. As usual, collisions with other conferences relevant for the CA community should be avoided. During the meeting Jozef Gruska suggested to establish an electronic archive for preprints on CA. At the moment some preprints can be found in the electronic archive which was well-known as {xxx.lanl.gov} and which is now also to be found at {www.arxiv.org}. In fact there is a ``Nonlinear Sciences'' group that has a section on ``Cellular Automata and Lattice Gases''. Furthermore some papers are spread in some of the physics  groups. Nevertheless it seems worthwhile to try to organize a centralized CA archive, at least to Kathrin Paschen and Thomas Worsch who agreed to work on it.

WG1.6 on term rewriting was created in 1999 and it currently has 43 members from 11 countries. Professor Jieh Hsiang who was the initiator and first chairman of the working group resigned in March and Claude Kirchner has been the acting chair until the annual meeting that was held on May 24, where he has been proposed to be the new chairmen.

This third working group meeting was held in Utrecht (The Netherlands), in conjunction with the 12th International Conference on Rewriting Theory and Applications (RTA2001).  There were 15 members attending and 3 invited persons. The agenda of the meeting can be found on the web page ( http://rewriting.loria.fr/IFIP-WG1.6 ). In addition to technical contributions, there were very interesting presentations of rewriting activities in Japan, Austria and in Valencia (Spain). The goal that was set last year to collaborate on an electronic book on term rewriting was deepened. It was also explored various ways to get

Web repository of problems, software systems, examples and counter-examples, and benchmarks.

The next meeting will held during the next RTA Conference that will be part of the next FLOC event, in Copenhagen, Denmark (July, 2002).

WG1.7 on Theoretical Foundations of Security Analysis and Design is chaired by Roberto Gorrieri, with Cathy Meadows and Riccardo Focardi serving as vice-chairwoman and secretary, respectively. Since the date of the last report, WG 1.7 has promoted (or is promoting) the following events:

The volume 2171 of the Springer series LNCS-Tutorials will be published in September, with a collection of tutorial papers covering all the main courses of the FOSAD 2000 school.

A special issue of the journal TCS, edited by R.Gorrieri, on "Foundations of Security Analysis and Design" has been completed recently. It will probably appear by early 2002.

We are debating the issues of extending the WG to other geographical areas not yet represented, e.g., Japan.

5 IFIP World congresses.

5.1 IFIP World Congress in Montreal

The conference TCS 2002 will be held in Montreal in the framework of the IFIP World Computer Conference (August 25-30, 2002). The Call for papers has been issued. We are aiming at having from four to six invited speakers, divided in the two streams. We are also planning to contribute to the overall organization of WCC by selecting an invited speaker from theory with a strong appeal for participants from industry or anyway with applied interest.

Part II Technical Assembly

Nothing to be reported.