IFIP General Assembly
Kuala Lumpur, September 5-9, 1999
Giorgio Ausiello
Part I. General Assembly
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 other initiatives. It is worth noting that such efforts successfully led to the creation of two new working groups in two hot areas of theoretical computer science: term rewriting and formal methods in security. Also, the first World Conference in Theoretical Computer Science is being organized in the year 2000 in Japan.
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 http://hermes.dis.uniroma1.it/Ifip-Tc1/ and is also accessible from the IFIP web site.
2. Meetings.
The last meeting of the TC has been held in Atlanta (USA) on May 5. The meeting in the year 2000 will be organized either in Geneva in the occasion of ICALP 2000 or in Sendai in the occasion of TCS 2000.
3. Changes in Membership and Officers.
Until now the representatives of fifteen national societies and organizations have been formally appointed (Austria, Bulgaria, China, Denmark, Germany, Greece, Hungary, Italy, Japan, Poland, Portugal, Slovakia, 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, France, Great Britain, India, Russia, Spain, The Netherlands have not yet nominated their representatives.
4. Working Group activities.
TC 1 has now seven working groups. The proposal for the seventh WG on Theoretical Foundations of Security Analysis has been approved at the last IFIP Council. 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. All the Working Groups have a considerable acivity and are involved in the organization of several meetings every year. Unfortunately, due to the informality of such events, only few of them are indeed registered as IFIP events. Further effort will be done toward having a more visible IFIP-labeled activity and there are strong hopes that the creation of the figure of "event facilitator" will help in this respect.
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 differnt from TC1) and a certificate. 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. 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. The community that meets under the label of WG 1.2 is very lively, even if this is the most relevant case in which only a small part of the activity of the WG goes through the official procedure for IFIP event organization.
Since last September the following meetings have taken place:
All workshops held in 1998 turned out to be very successful!
The following events have been held or are planned in 1999:
WG1.3 on Algebraic Specification of Languages is chaired by Peter Mosses. In 1999 the Group is sponsoring WADT'99, the Workshop on Algebraic Development Techniques, which is taking place adjacent to the next WG1.3 meeting in September 1999, and which will attract more than 90 participants. The mini-track on Foundations of System Specification at FM'99, the World Congress on Formal Methods, also sponsored by WG1.3, has attracted 18 submissions, of which 4 have been accepted for presentation in the Technical Symposium.
One of the major intiatives sponsored by the Group is the Common Framework Initiative for algebraic specification and development (CoFI, coordinated by Peter Mosses 1995-98, and by Don Sannella since August 1998). All the coordinators of CoFI task groups are WG1.3 members. 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 is now working on sub-languages and extensions of CASL, translations between CASL and other languages, tools, methodology, and applications to reactive system specification. CoFI, is to present CASL, its Common Algebraic Specification Language, in a 1-day workshop at FM'99; and the CASL Summary and Formal Semantics are included on the FM'99 CD-ROM, together with various tools for CASL. A book and a user's manual for CASL are in preparation, with a view to eventual publication.
The survey book on Algebraic Foundations of Systems Specification (edited by E. Astesiano, H.-J. Kreowski and B. Krieg-Bruckner, and with contributions by many other WG1.3 Members) has now been published 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 formerly chaired by Carl Smith has recently elected a new chirman, Arun Sharma. The main activity of WG 1.4 until now has been to promote computational learning theory by giving best student paper awards at the three primary learning theory conferences. 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 for each of the three conferences.
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.
WG1.6 on Term Rewriting has been created at the last IFIP General Assembly. Chairman pro-tempore is Prof. Jieh Hsiang. On 1 April, 1998, the WG1.6 had a pre-meeting held in conjunction with the 7th International Conference on Rewriting Techniques and Applications at Tsukuba, Japan. About twenty people attended. In the meeting Jieh Hsiang reported on the progress of the founding of the working group which was followed by a lively discussion of future directions. The discussion was summarized by Leo Bachmair of the SUNY at Stony Brook and distributed to all the potential members of the WG. After the WG was approved in September, the initial list of members was finalized, and Claude Kirchner of INRIA-Lorraine was invited as the vice-chair and Leo Bachmair the secretary. The first official WG meeting has been held on 1 July, 1999 at Trento, Italy, in conjunction with FLoC (Federated Logic Conferences). At the meeting it was decided to meet again in the year 2000 in Japan.
WG1.7 on Theoretical Foundations of Security Analysis has been created at the last IFIP Council in Goa. 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 first meeting of the WG will take place in November (the location has not been decided yet). During the meeting there will be elections for chairman, vice-chairman and secretary. Currently, the pro-tempore chair is Roberto Gorrieri and the pro-tempore secretary is Riccardo Focardi. The next meeting will be in Geneva, as a satellite event of ICALP '00. A school on Security will be organised in September'00 by the WG chair in Italy. The lecturers will be mainly members of the WG.
Part II - Technical Assembly
1. Promotion of new WGs
Feeling that WGs are one of the most prominent forms of activity of a Technical Committee, actions for the creation of new WGs have been undertaken by TC1 during 1998 and 1999. Beside the newly created working groups in the areas of Term Rewriting and of Theoretical Foundations of Security Analysis also initiatives in the area of Computational Logic have been undertaken where the involved scientists have been showing new interest in having a WG in TC1 for coordinating the several initiatives yearly held in the field. Actually the recent creation of IFCoLog (International Federation for Computational Logic, a sort of IFIP entirely dedicated to applications of logics in computer science and in artificial intelligence) shows that such community, with strong connections with both TC1 and TC12, is reluctant to join under the IFIP 'umbrella'. The creation of IFCoLog is an alarming issue that the IFIP General Assembly should take into serious consideration.
2. World Congress in Theoretical Computer Science (TCS 2000)
In the year 2000 TC1 will organize the first world 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. The conference will be organized in two tracks, one dedicated to Algorithms and Complexity (chaired by Jan van Leuwen), one dedicated to Logics and semantics (chaired by Peter Mosses). 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. The list of outstanding of the nine Invited Speakers that have accepted to deliver lectures at the conference shows the interest of the Theory community in the initiative. Professor Michael Rabin has accepted to deliver the banquet speach.
In order to increase the interaction between the TC1 community and the more traditional IFIP community, TC1 is strongly advocating that at the next IFIP WCC in Montreal a theory track (or a theory subconference) be organized.