============================= VOLUME 18 NUMBER 1 APRIL 1994 ============================= 1. PROFILES: R. TRAPPL ----------------------- 2. EDITORIAL: CYBERNETICS AND SYSTEMS RESEARCH ON THEIR WAY TO THE 21ST CENTURY ----------------------- 3. PARALLEL ALGORITHMS FOR THE COMPLETE AND RESTRICTED TRANSITIVE CLOSURE OF A DATABASE RELATION A.A. Toptsis, Dept. of Computer Science and Mathematics, York University, Atkinson College, Toronto, Ontario, M3J 1P3, Canada, Phone: (416) 736-5232; Fax: (416) 736-5773; Email: anestis@cs.yorku.ca pp. 7-25 keywords: transitive closure, parallel processing, relational database, load balancing, scalability abstract: Integration of data and knowledge bases presents a major challenge of efficient processing linear recursive queries on very large data volumes. A notable example is the computation of the transitive closure. Although a plethora of sequential transitive closure algorithms have been developed, parallel transitive closure algorithms are rather scarce. In this paper we present, analyze, and compare six parallel algorithms for the computation of the transitive closure of a database relation. Three of the algorithms compute the complete closure, while the other three are modifications tailored for the computation of the restricted closure. The algorithms make no assumptions about data organization and do not require any preset indices or preprocessed data. A share-nothing parallel architecture is assumed for all algorithms. The analysis and performance evaluation shows that the restricted closure algorithms outperform the complete closure ones by a significant factor. Moreover, four of the six presented algorithms possess load balancing and scalability properties that make them far superior to the conventional transitive closure parallel methods. ----------------------- 4. MFM BASED DIAGNOSIS OF TECHNICAL SYSTEMS A. Znidarsic, V.J. Terpstra, H.B. Verbruggen, Jozef Stefan Institute, Department of Computer Automation and Control, Jamova39, 61111 Ljubljana, Slovenia, Phone: +386 61 1259 199 (int. 606); Fax: +386 61 1219 385, E-mail: alenka.znidarsic@ijs.si, Delft University of Technology, Department of Electrical Engineering, Control Laboratory, P.O. Box 5031, 2600 GA Delft, The Netherlands pp. 27-36 keywords: fault detection, fault diagnosis, system modelling, expert systems abstract: Detection and diagnosis of faults (FDD) in technical systems represent an important segment of intelligent and fault-tolerant systems. In the article we present the qualitative FDD approach proposed by Larsson and based on Multilevel Flow Modelling representation of the process. The contribution of this article regards evaluation of this method on a simulated water-level process controlled by feedback. The MFM diagnostic expert system, together with the continuous simulation of the process, is implemented in a real-time expert system tool G2. Based on results perspectives for further work will also be given. ----------------------- 5. ADAPTIVE FILE ALLOCATION IN DISTRIBUTED INFORMATION SYSTEMS A. Mahmood, H.U. Khan, H.A. Fatmi, Dept. of Electronic and Electrical Engineering, King's College London, The Strand, London WC2R 2LS, U.K., a.mahmood@bay.cc.kcl.ac.uk keywords: file allocation, distributed data management, computer networks, heuristics pp. 37-46 abstract: The problem of adaptive data allocation in distributed information systems to minimize the overall communication and storage costs is discussed. A key problem of economical estimation of future file utilization pattern is described and an algorithm based on the Gabor-Kolmogorov learning process is presented to estimate the future access and the update patterns. An adaptive algorithm to reallocate data in a computer network is proposed. The reallocation algorithm chooses the optimal allocation using two objective functions and the best fit strategy. Also, a distributed candidate selection algorithm is presented to reduce the number of files and nodes in the reallocation process. The simulation results are presented to demonstrate the accuracy and the efficiency of the proposed algorithms. ----------------------- 6. CONCEPT REPRESENTATION OF THE SOFTWARE TOOL PIDMASTER FOR SYSTEMS MODELING AND CONTROLLERS TUNING M. Ostroversnik, Z. Sehic, B. Zupancic, M. Sega, Jozef Stefan Institute, Jamova 39, 61 000 Ljubljana, Slovenia, Faculty of Electrical and Computer Engineering, 61 000 Ljubljana, Trzaska 25, Slovenia, Metronik d.o.o., Stegne 21, 61 000 Ljubljana, Slovenia. keywords: OOP, Software Engineering, Control System Design, PID Control pp. 47-53 abstract: The work deals with the representation of the concepts of program package PIDMaster for on-site signal analysis, system modeling and controller's synthesis. A user-friendly interface is introduced which enables comfortable work also for less experienced users. The required user-friendliness has been achieved by the use of window interface completed with some elements of the object oriented user interface management system. Central points of the new interface are the so-called movable graphical objects. Their usage in the phase of system parameter estimation is explained thoroughly. ----------------------- 7. EVALUATION OF SOFTWARE QUALITY ATTRIBUTES DURING SOFTWARE DESIGN C. Wohlin, Dept. of Communication Systems, Lund Institute of Technology, Lund University, Box 118, S-221 00 Lund, Sweden keywords: quality evaluation, performance, functional analysis, software reliability, simulation, software metrics, Cleanroom pp. 55-70 abstract: This article presents an evaluation method of software quality attributes during software design with a high-level design technique. The attributes considered are real time functional behaviour, performance (in terms of capacity) and reliability. The method is based on transformation of the software design documents and simulation models of hardware architecture in terms of processors, communication channels etc. and the environment in terms of usage of the system. The method provides an opportunity to concentrate on software, architecture and usage of the system one by one and facilitates analysis of the software system long before it is taken into operation, which is particularly valuable for safety-critical software and other complex software systems. This implies that important information concerning both functionality, performance and reliability can be studied early in the development, so that re-design can be performed instead of implementing a poor solution. ----------------------- 8. SCHEDULING STRATEGIES IN HIGH-LEVEL SYNTHESIS Jurij Silc, Jozef Stefan Institute, Laboratory for Computer Architectures, Jamova 39, Ljubljana, Slovenia, E-mail: jurij.silc@ijs.si keywords: high-level synthesis, scheduling, allocation pp. 71-79 abstract: The paper describes objectives of high-level synthesis. It concentrates on operation scheduling strategies and the interaction with the resource allocation. Some transformational and iterative/constructive scheduling algorithms are described. Moreover, a new scheduling/allocation approach is presented and compared with other known algorithms. Finally, some open problems of the high-level synthesis are given. ----------------------- 9. FORCE CONTROL OF AN INDUSTRIAL ROBOT WITH ADAPTIVE COMPENSATION OF THE ENVIRONMENT STIFFNESS B. Nemec, L. Zlajpah, Jozef Stefan Institute, University of Ljubljana, Ljubljana, Jamova 39, Slovenia, bojan.nemec@ijs.si keywords: force control, robot control, adaptive control pp. 81-91 abstract: The paper describes the implementation of the adaptive force control of an industrial robot. The implemented algorithm is a position based hybrid control scheme with adaptation to the environment stiffness. Control scheme is sensitive to the changes in environment stiffness. We solved this problem by the adaptive controller. Implementation problems on the robot controller are also discussed. The proposed control method is easy to implement and can be applied to existing industrial robots fitted with a conventional position controller. The performance of the force controlled manipulator with the proposed control law was tested with the computer simulation and by using the real robot. ----------------------- 10. CURRENT STATUS OF THE EDR ELECTRONIC DICTIONARY PROJECT H. Suematsu, Japan Electronic Dictionary Research Institute, Ltd. (EDR), Mita-Kokusai Bldg. Annex, 4--28, Mita 1-chome, Minato-ku, Tokyo, Japan, suematsu@edr.co.jp keywords: beta test, bilingual dictionary concept dictionary, cooccurrence dictionary, current status, EDR, EDR corpus, electronic dictionary, project, structure, text base, word dictionary pp. 93-96 abstract: The current status of the EDR electronic dictionary project and its future plan is reported in this paper. The electronic dictionary is not a mere electronic version of a book-form dictionary (i.e. machine-readable dictionary, MRD). It is a dictionary for computer processing of natural languages, e.g. machine translation. It captures lexical information, such as lemmas, parts of speech, and word senses, in a machine-tractable way, to support various natural language processing (NLP) approaches on the level of morphology, syntax, semantics, and pragmatics. A considerable vocabulary size needs to be covered in a consistent way, and implicit information left to the human reader in the case of a book-form dictionary, has to be explicitly stated in a computer-processible manner. In constructing such a large-scale electronic dictionary, a very large-scale corpus is needed to extract linguistic information, and to verify data described in the electronic dictionary. The corpus is gaining more importance along with the recent advocation of example-based machine translation. The EDR electronic dictionary project is one of the earliest efforts of this kind, and has one more year before it ends. EDR is now in the process of compiling and producing the final result of 8 years' work. The EDR Electronic Dictionary, or for short, EDR Dictionary, has reached a level competent enough to be used for R&D, provision of it has started as the beta test. There is a concern, however, about the slow progress in the English section of the Dictionary. Various views and opinions are currently under discussion on the future plan for the EDR Electronic Dictionary. ----------------------- 11. IJCAI'93 - A CRITICAL REVIEW M. Gams, Jozef Stefan Institute, Jamova 39, 61000 Ljubljana, Slovenia, matjaz.gams@ijs.si The purpose of this report is to highlight critical points of the IJCAI'93 event. It is not that the author does not deeply appreciate AI or thinks that IJCAI'93 was not a great event -- on the contrary. The main reason for the ``critical-advocate approach'' is to avoid writing just another favourable report regarding IJCAI. International Joint Conference on Artificial Intelligence (IJCAI) is the major world-wide AI-related event. Every second time it is held in USA and every second time elsewhere, e.g., in Europe or Australia. Typically, there are a couple of thousands of participants. In 1993, there were more than 2000. Conference chair was Wolfgang Wahlster, program chair Ruzena Bajcsy, and local arrangements chair Jean-Pierre Laurent. Technical program started on Tuesday 31st of August and ended on Friday 3rd of September. There were 16 tutorials and 28 workshops, several panels, exhibitions, invited papers, awards. The IJCAI distinguished service award for honouring senior scientists in AI was given to Daniel G. Bobrow, editor of Artificial intelligence. The IJCAI award for research excellence of consistently high quality was given to Raymond Reiter. The Computers and Thought Award for outstanding young scientists (below 35 years) was given to Hiroaki Kitano. Now, to the critical remarks. First, there were two papers with the same first author. Regardless of the fact that the author of both papers is one of brilliant scientists and editors of Informatica, this seems quite extraordinary. Namely, the IJCAI'93 acceptance rate was around 25%, and several very good papers were rejected because of limited quota. It is a common practice that conferences and magazines limit the number of appearances of the same author. For example, Informatica does not accept scientific papers of the same (co)author in two neighbouring issues. Second, there were typing mistakes and inconsistencies in the proceedings. For example, in a superb paper by Hiroaki Kitano we find (page 814, top paragraph) ``... to it.[Waltz, 1988] and ...'', later (page 814, third paragraph from top) ``... direction[Brooks, 1991] and ...''. Most other references in the text -- unlike above -- have one blank before and a delimiter behind. Another example - Figure 11 and Figure 13 both contain the misspelled word ``Accracy''. Text in figures is too small and in some cases practically unreadable, e.g., in Figure 4. One can hardly imagine that the invited paper is not carefully read and corrected. Talking about one of the best papers and presentations at IJCAI'93, it seems really strange that at the end of the presentation participants started leaving in great numbers. Probably the reason for this was the announced dinner event and prolonged lecture - partially due to technical troubles and partially due to extended presentation. Why not postpone the buses? Overall, organisation was quite well. The influence of French charm was clearly observable, and local arrangements by Jean-Pierre Laurent (one of best-known AI researchers in France and also an editor of Informatica) were very exciting from scientific and social point of view. If the purpose of this paper is to present critical points about the event, then the refereeing process is clearly a matter of discussion. There were several matters of substance the author of this paper finds debatable. Consider for example, the problem of finding cut-points, i.e. points where to cut continuous-valued attributes into intervals to satisfy a sort of minimal-entropy function. In the proceedings, p.1023, theorem 1 basically states that it is worth to look for cut points only in intervals where examples change classes and not between examples of the same class. It is claimed that the proof of theorem 1 is rather lengthy and thus omitted, while we think that the proof is rather trivial. Three such cases are presented at the top of next page. The first row indicates indexes of examples sorted by an attribute A. The examples are presented in the second row and belong to classes ``+'' or ``-''. In the third row there is a function calculated at cut points between examples. The function is calculated as the relative sum of Gini index functions (1 - p_+^2 - p_-^2) for left and right set of examples regarding the cut point. Weights represent relative frequencies of examples. For example, consider the case with six examples. If we cut between 1 and 2, we obtain 1/6 [(1 - 1/1)^2 - (0/1)^2]+ 5/6 [(1 - 2/5)^2 - (3/5)^2] = 0.4 The proof we have discussed in our laboratory about 5 years ago is as follows: In the book by Breiman, Friedman, Olshen and Stone (1984) Classification and Regression Trees it has been shown that ``reasonable'' functions such as Gini index or informativity are convex functions (Figure 4.3, 4.4, around p. 100). If functions such as Gini index are indeed convex then the weighted sum of two convex functions is again a convex function. Therefore, the only possibility for minimal cuts is in the intervals where classes of examples change. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + + - - - - - - - - + + - - - 0.31 0.23 0.31 0.35 0.37 0.39 0.39 0.39 0.39 0.37 0.39 0.36 0.37 0.38 1 2 3 4 5 6 7 8 9 10 - - + + + + - - + - 0.44 0.38 0.48 0.50 0.48 0.42 0.48 0.50 0.44 1 2 3 4 5 6 + + - - - + 0.40 0.25 0.44 0.50 0.40 Fair to say, although the basic proof for two-class problems seems trivial and can be extended to many classes as well, in the discussed paper there are several extensions and additions. Furthermore, we might have overlooked something. In that case I will be happy to publish a correction. On the other hand, it is hard to believe that the misses we have observed were all results of our misunderstandings or ``bugs'' that inevitable do happen. The position of a ``critical advocate'' allows me to raise questions whether the refereeing process is really done as good as it could be. >From the point of critical research directions, two phenomena can be highlighted. First - there is an unhealthy gap between research and applications in AI. During several occasions a question was raised: Can anybody report really successful applications of AI? Typically, majority or participants remained silent. Since there are thousands of AI applications all over the world, it is hard to believe that researchers do not have contacts with developers. We were one of those quite happy to report around fifty small-scale applications in Slovenia, all related to the Bratko's laboratories. In particular, we have presented an application of novel integration methods at the ML and KA workshop organised by George Tecuci (Gams, Karba, Drobnic, Average-case improvements when integrating ML and KA). The major AI application in Slovenia was in use for 2 years at the Acroni Iron and Steel Works Jesenice. There might be several reasons why most of the papers were seemingly unrelated to real world. Since IJCAI's motto is search for excellence, it is hard to find methods mature enough to be tested in real-life environments and at the same time so intellectually new and attractive to pass the refereeing procedure. The second reason might be the ``Publish or perish'' frenzy. It seems that certain circles in modern science have accepted that all that counts is the number of publications. In return, this criterion has forced scientists to devote most of their energy to publications, and not to essential scientific research. Remarks of participants working on real-life problems often indicated that one of the key assumptions enabling an original (although not verified) idea was related to the absence of real-life circumstances. Another critical remark: most prominent presentations, especially the winners of Computers and Thought Awards in recent years (e.g. Brooks in 1991, Kitano in 1993) have presented substantially novel approaches while many or even most of the ``normal'' papers belonged to the ``classical'' AI. In that sense and from my personal point of view Hiroaki Kitano's presentation was a truly excellent way to promote new directions in AI and thus avoid the possibility of saturation. Kitano earned his PhD in 1991. At present, he is a researcher at the Sony Computer Science Laboratory in Japan and the Center for Machine Translation at Carnegie Mellon University. According to the reviewers, Kitano won the prize for novel translation work on a massively parallel computer. Previous approach to translation used explicit rules of knowledge and was guided by rigid rules. Kitano says that for domains such as translation between two natural languages it is almost impossible to obtain a complete set of knowledge for a given problem. His approach builds on memory as the foundation of intelligence. Each of computer's 32,000 processors contains a few sentences and determines the best match for an input sentence in natural language. Translation is based on extensive use of memory. Statements are parsed into basic parts, translated, and sensibly combined to the translated language. All reasoning is by analogy. The program achieves around 75-percent accuracy by one reports and around 90-percent in others. This puzzle was answeared by prof. Kitano's reply e-mail. He poited our that the accuracy figure 75% - 90% depends on the task, memory-based size etc. But all demonstrates superior performance than traditional methods. His presentation at IJCAI'93 was even better, more profound, overviewing, observing very important changes and providing new directions. One of the major Kitano's remark is related to AI research directions regarding problem domains. He categorises complete, correct and consistent problem domains as toy domains. Real-world domains are denoted as incomplete, incorrect, inconsistent, and are in addition characterised by human bias, tractability and economics. Real-world domains are by definition very difficult to explain because no simple ideas work well in such circumstances. According to Kitano, a great part of AI research is devoted to toy problems which are unscalable not only to real-world problems but also to intelligent systems. He proposes designing useful systems (p. 817) which are from start devoted to real-world problems. Another major Kitano's suggestion is that AI as well as computer science and engineering in general are much more dependent on the development of computer hardware that generally recognised. Bare computer power will son beat the best human chess player. Future computer projects can be characterised by massive computing, massive parallelism, massive data. The progress is still exponential. In a couple of years, a single-wafer chip will achieve the performance of best-today supercomputers. One of the reasons for my overwhelming support for Kitano's approach lies in the fact that we have been working on similar problems for the last couple of years. In 1991, Gams and Krizman have published in Informatica a paper ``The Principle of Multiple Knowledge'' describing a cybernetical principle which leads to a conclusion that single systems (similar to Kitano's toy problems/systems) can not achieve good performance in real-life domains nor can they achieve intelligence on digital computers. This seems similar to Kitano's `collaborative learning'. Enthusiastic about Kitano's ideas B. Hribovsek and I have implemented two versions of an intelligent interface for VAX/VMS. One was classical and the other based on memory. Both work similarly, e.g., solve similar problems similarly, yet the memory-based program is a couple of times smaller, and therefore, a couple of times easier and faster to write. In addition, substantially more flexible, transportable and adaptable. The success of memory-based approach is based on dramatic changes in memory capacities in recent years. While translation between natural languages demands special supercomputers, most of every-day human communication can be solved in this way on existing computers. Today, most of ``normal'' human-computer communication, e.g., communication with an application package or operating system, can easily be captured in the primary memory of personal computers with response time well below one second. In many computer and AI-related literature one observes a diagram showing that problems can be solved using programs (processing) or data (memory). For example, using only memory enables better and better performance with more and more memory, yet eventually gets unproportionally more expensive. Therefore, optimal solutions consist of proportional amount of data and proportional amount of program code. However, in the last 20 years human programmers produce basically the same amount or program lines per hour while the memory capacity of PC grew from 4 KB in 1980 to 8 MB in 1990 and are expected to approach 100 MB in 2000. This progress has already substantially moved the optimal approach towards using more memory and less code. At the end, being critical or not, IJCAI'93 might be one of those rare events that substantially influence the way humans use computers.