IFIP General Assembly Budapest, September 7-8, 1998
Giorgio Ausiello
1 Introductory remarks
TC 1 started its activity on January 1st, 1997. The main efforts in the first eighteen month have been devoted to starting new working groups and to promote further initiatives (prizes, special sessions in conferences atc.). 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
TC1 met for the first time in Bologna on July 6, 1997 in the occasion of the ICALP conference and the Silver Jubilee of the European Association for Theoretical Computer Science. The second meeting was held in Lisbon on March 29, 1998. The third meeting was organized in Brno, Czech Republic in the occasion of MFCS 98. A meeting in US in May 1999 in the occasion of FCRC is being planned.
3. Changes in Membership and Officers
Until now only the representatives of nine countries have been formally appointed (China, 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. The General Assembly is the proper occasion to remind Member Organizations to nominate their representatives. During the meeting in Bologna the Secretary of the TC has been appointed in the person of Prof. Roberto Gorrieri (gorrieri@cs.unibo.it). The appointment of two Vice Chairmen is planned and actions for identifying possible candidates have been started.
4. Working Group activities
TC 1 has five working groups. 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. It is chaired by Joe Traub. The Working Group continues its very active program of international meetings. In May 1998 there will be a workshop at Schloss Dagstuhl. Participating will be 45 experts from a dozen countries. In November 1998 there will be a one-week workshop at the University of California, Berkeley. This workshop is still in the planning stage. We are currently planning a number of future meetings. There will be a meeting at Oxford, U.K., in July 1999 and a meeting in Hong Kong, China, in October, 1999. Between meetings WG 1.1 members communicate through CAC-NET, and operate an electronic newsletter (CAC/FoCM Digest) which is sent to 220 people. WG1.2 on Descriptional Complexity has been chaired by Detlef Wotschke since October 1996 and has begun a major reorganization and revival of its activities. It currently has more than 50 members from 14 countries. In order to account for the increasing influence and widening scope of descriptional complexity, an advisory board to the chairman with members representing the various disciplines is being established. Already several leading scientists have agreed to serve on this advisory board. Recently the subarea "Program Complexity and Reliability of Software" has been added to the scope of activities of WG1.2. Since the last report of a year ago, WG 1.2 has - as part of its revival program - organized two regional workshops and a workshop on "Descriptional Complexity for Automata and Formal Languages" at Darmstadt, Germany, held in May 1998. It has also coorganized (in collaboration with MFCS' 98) a Workshop on "Grammar Systems" in Brno, Czech Republic, on August 22 - 23, 1998. In addition, it is organizing in collaboration with Bell Laboratories (Murray Hill) and IEEE-ISSRE and in connection with the ISSRE-Conference a workshop on "Automata and Formal Language-Based Frameworks for Software Reliability Analysis" in Paderborn, Germany, on November 3, 1998.
WG1.3 on Foundations of System Specification is a particularly active group. It has 32 members from 12 countries, and is now chaired by Peter D. Mosses (Hans-Jõrg Kreowski was chairman until January 1998). Most of the prominent researchers in the field belong to the group, or regularly attend its meetings as observers. The activity of the group is well established. Beside the WG Meetings (the last one in Lisbon, Portugal, in April 1998), the group participates in the organization of several events. In particular it co-sponsors the Workshop on Algebraic Design Techniques (WADT, formerly Workshop on Abstract Data Types) held in Lisbon in April 1998, and it will co-sponsor the World Congress on Software Design Calculi planned for October 1999 in Toulouse, France.
WG1.3 has promoted the Common Framework Initiative for algebraic specification and development (CoFI, coordinated by Peter Mosses). The aim of CoFI is to come up with a widely-agreed algebraic framework, based as much as possible on a critical selection of features that have already been explored in various contexts. The proposed design for the main CoFI language (named CASL) was tentatively approved at the WG meeting in June 1997 - subject to reconsideration of a few points. The language design has since been revised accordingly, and work on the formal semantics, tools, methodology, and applications to reactive system specification is proceeding.
The work on a survey book on Algebraic Foundations of Systems Specification (edited by E. Astesiano, H.-J. Kreowski and B. Krieg-Brückner) is in the final editing. The book will be printed by Springer as an IFIP State-of-the-Art report.
Recently WG1.3 has proposed to appoint four Honorary Members and two more Ordinary Members.
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 out best student paper awards at each of the three primary learning theory conferences. The first award went to Juris Smortrovs from the Institute of Mathematics and Computer Science of the University of Latvia, for his paper "Closedness Properties in Team Learning of Recursive Functions." It was presented that EuroCOLT meeting in Jerusalem, Israel. The next award went to N. V. Vinodchandran of Institute of Mathematical Sciences, India, for his paper with V. Arvind "Exact Learning via Teaching Assistants." It was presented at the ALT meeting in Sendai, Japan.
TC1 anticipated another $1500 to continue this program in 1998. The committee had several discussion on how to continue this program without further financial contributions from IFIP. We concluded that it would be best to set up a separate mechanism from each of the three conferences. That way, an international fund raising effort becomes a regional one.
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. There is considerable overlap (two thirds) between the Fulk Award Association and WG 1.4 membership. Tax exempt (USA residents) contributions will be solicited as part of the conference registration. The funds will be invested conservatively and the half of the proceeds of the investment will make the award. With this algorithm, the award will start out financially small, but grow with time. Since no IFIP award was made at the 1997 COLT due to lack of a suitable candidate from an economically disadvantaged country, the committee decided to use the $500 allocated for that award to initiate the Fulk Award. The first award has been given in Madison, Wisconsin in 1998.
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. This was accomplished as a direct result of the lobbying efforts of members of WG 1.4. The ALT award will be named for E. Mark Gold and will be given for the first time at the ALT meeting in Tokyo in 2000.
Arrangements for an award at the EuroCOLT meeting are more problematic. WG 1.4 committee members are actively trying to find a mechanism to independently fund a best student paper award.
WG 1.5 on Cellular Automata and Machines is chaired by Roland Vollmar. Since its foundation in 1995 the WG has organized workshops on a regularly basis: 1995 Schloss Dagstuhl (IBFI) (Germany), 1996 Schloss Rauischholzhausen (Germany), 1997 Gargnano (Italy). This last workshop (Sept. 25-27, 1997) was organized by G. Mauri as chairman. About 30 persons from 7 countries have attended. Selected papers from it will appear in "Fundamenta Informaticae". This is also by "tradition": Following the habits of all IBFI workshops a seminar report has been produced in 1995. A collection of papers of the 1996 workshop has been published as a special issue of volume 23 of "Parallel Computing". The next workshop focused on "Modeling with Cellular Automata" took place on March 5-6, 1998 at the University of Karlsruhe (Germany); it was organized by T. Worsch.
In December 1998 a general workshop on the theme of WG 1.5 with E. Goles as host is planned in Chile.
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. In particular the following areas have been considered during the Bologna TC1 meeting and further discussed in the Lisbon and Brno meetings: computational logic, term rewriting, approximation algorithms, two dimensional languages, and the names of the persons to whom assign the exploratory tasks have been decided. With regard to the area of Approximation Algorithms it appeared that the scientific communitiy considers such domain sufficiently covered by the existing conferences and they do not perceive the need for establishing new bodies. More promising situations appear in other domains. Roberto Gorrieri is carrying on an exploration for starting a WG on Formal Methods in Security. Another area that needs being explored is the area of Algorithmic Issues in Communications. The most advanced state has been reached by the proposal for starting a new working group in the area of Term Rewriting (promoted by Jeh Hsiang). 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.
The Working Group on Term Rewriting (WG 1.6) has been formally approved in the Lisbon meeting and is under discussion at the Budapest Technical Assembly. The membership list is being examined in the TC1 Brno meeting so that the WG can become operative if it meets the consensus of the IFIP Technical Assembly.
2. Other Initiatives
TC1 is actively exploring directions for information dissemination on the role of theory in Information Technology, both through relationships with other TCs and through the presence of theory tracks in the forthcoming World Congresses. Also, an initiative for promoting the analysis of the main open research directions in the area of Foundations of Computer Science has been activated and is expected to produce some visible results for the year 2000.