Computer Science at the University of Helsinki 1996 Jorma Tarhio and Martti Tienari (editors) Department of Computer Science P.O. Box 26, FIN-00014 University of Helsinki, Finland Report A-1996-3 Helsinki, May 1996, 89 pages ISSN 1238-8645, ISBN 951-45-7411-7 Abstract Activities at the Department of Computer Science are presented. The research projects are described and the members of the faculty are introduced. Recent publications of the faculty are listed according to their classi|cation. The educa- tional program is described, and course descriptions, the titles of recent theses, and the abstracts of recent Ph.D. theses are given. Computing Reviews (1991) Categories: A.1, A.2, K.3.2 Key Words and Phrases: computer science education, research information 1 Chapter 1 Overview The Department of Computer Science was founded in 1967 when the |rst full professorship in computer science was established at the University of Helsinki. It is within the Faculty of Science, along with the departments of Mathematics, Physics, Chemistry, and others. Our current teaching faculty (January 1996) comprises 43 full time teach- ers. It can be categorized using American academic terminology: 4 full pro- fessors (Mannila, Tienari, Ukkonen, one vacant position), 5 associate pro- fessors (Makela, Orponen, Paakki, Sippu, one vacant position), 20 assistant professors (6 research oriented isenior assistantsj and 14 teaching oriented ilecturersj), 14 teaching assistants. We also employ approximately 25 of our students in teaching on a part-time basis. Nine senior experts are also asso- ciated with the department. These so-called idocentsj work mainly outside the university but occasionally give courses or supervise theses in the area of their speciality. Approximately 30 research positions are |nanced from outside sources. We also have a staoe of 10 persons. The department annually admits 200 students to major in computer sci- ence. The students are selected according to their standing in a national student examination. The number of completed M.Sc. degrees (5 year de- gree) was 37 in 1993, 46 in 1994, and 44 in 1995. The study time for a M.Sc. degree ranges from |ve to eight years. Many of our students work in industry, which slows down or stops the progress of their studies. Fairly frequently our students, after having acquired the basic skills in computer science, redirect their studies by transferring to the Helsinki University of Technology, the Helsinki School of Economics, Faculty of Social Sciences, or some other educational institution. Many students study computer science as a minor while pursuing a major in another subject, such as mathematics, physics, economics, psychology, or social sciences. We ooeer two curricula for students minoring in Computer Science. In 1995 our iapprobatur curriculum in Computer Sciencej (1525 credit units) was completed by 164 students 2 and our icum laude curriculum in Computer Sciencej (3560 credit units) was completed by 133 students. There are two graduate degrees in Finland: the Ph.Lic. (3 years) and Ph.D. degree (4 years). The latter has higher quality requirements. Both build upon the M.Sc. degree (5 years). The high demand for our M.Sc. gradu- ates to |ll well-paid jobs in industry is a fact which has hampered our Ph.D. education. Our department granted three Ph.D. degrees and ten Ph.Lic. degrees in the three year period 199395. In postgraduate education we co- operate with the Helsinki University of Technology within a framework called HeCSE (Helsinki Graduate School in Computer Science and Engineering). Two principal sources provide funds for computer science research in Fin- land. The most important one for us is the Academy of Finland under the Ministry of Education and Science. The other important research |nancier is the Technology Development Centre (TEKES) under the Ministry of Trade and Industry. Lately European ESPRIT, ACTS etc. |nancing has also be- come possible for us. The department maintains jointly with the University Computing Centre a good computer science library. It subscribes to most major international journals in computer science and related |elds and acquires a majority of the most important computer science books and conference publications. The library maintains publication exchange with approximately 130 other research institutes in various countries. The library is run by a librarian and a secretary. The University Computing Centre Maintains a communication backbone network and ooeers UNIX and PC services. In addition, the department maintains its own network of approximately 180 workstations (SPARCsta- tions and Linux PCs) and about 10 servers. Classrooms with workstations, X-terminals and PCs are available. Each oOEce of the department has a workstation or terminal. The department has three informal sections that are used in the planning of the curriculum and in administration. The division is not strict, and several research projects span two sections. The sections cover roughly the following subject areas: 1. General Computer Science (Prof. Esko Ukkonen, Assoc. prof. Matti Makela, Assoc. prof. Pekka Orponen): algorithms and data structures, computational complexity, computational geometry, machine learning, neural networks, computer graphics, numerical and symbolic computa- tion, computers in education 2. Computer Software (Prof. Martti Tienari, Assoc. prof. Jukka Paakki): programming languages, compilers, formal speci|cation and veri|ca- 3 tion, software engineering, distributed systems, computer networks, operating systems, performance evaluation 3. Information Systems (Prof. Heikki Mannila, Assoc. prof. Seppo Sippu): databases, human-computer interfaces, computer supported co-operative work, information system design methodology, design of databases, text databases, object-oriented databases, logic databases, database structures and algorithms The University of Helsinki has many diverse teaching and research ooeer- ings related to computer applications. At the Department of Mathematics there is an active group in mathematical logic, numerical analysis and sym- bolic computation as well as some interest in theoretical computer science. Our students also bene|t from the hardware-oriented teaching (e.g. electron- ics, digital electronics, microcomputers, interface electronics) given at the Department of Physics. In the Faculty of Social Sciences some teaching and research is devoted to computational statistics, administrative information systems, and the social eoeects of data processing. In the Faculty of Arts there is a research unit in computational linguistics and a degree program in linguistic theory and cognitive science. 4 Chapter 2 Research 2.1 Review The research at the department has evolved over the years similarly to the international research trends in computer science. Early work in numerical analysis in the 1960's made room for work in programming languages and compilers in the 1970's. Since then the research has diversi|ed and its volume has increased. In the following, the research activities of each section of the department are reviewed. The main research areas in the section of General Computer Science are algorithms and data structures, machine learning, probabilistic reasoning, and computations by complex dynamic systems (cellular automata and ge- netic algorithms). Algorithms and data structures is the area with the longest tradition. The work on string matching algorithms (Ukkonen, Tarhio) has been particularly successful. Theoretical work has often been conducted within the framework of systems research providing practical motivation for the problems studied. The motivations and applications of the algorithms developed have come e.g. from computational biology and from various ap- plications in the industry. Machine learning and probabilistic reasoning are active research direc- tions related to arti|cial intelligence. In probabilistic reasoning the main topic has been the design and implementation of dioeerent high-level knowl- edge representation schemes that are capable of performing Bayesian rea- soning (Myllymaki, Orponen, Tirri). The machine learning group (Elomaa, Kivinen, Mannila, Ukkonen) has studied dioeerent learning models and the complexity of learning tasks within these models. One of the results is the |rst MDL learning algorithm that has a proven performance guarantee. The more practice-oriented work has developed, for example, new Occam algo- rithms for learning decision trees and decision lists, and software tools for 5 testing and comparing various machine learning algorithms. Our computer software research can be subdivided in two main areas: distributed systems and telecommunication software (Raatikainen, Tienari) and programming languages and software engineering (Paakki). In some projects these two areas are intertwined. In telecommunication software we have both industrially and academi- cally oriented research projects. In the former category one could classify European ACTS-project DOLMEN (Service Machine Development for an Open Long-Term Mobile and Fixed Network Environment) (Raatikainen) as well as the project Mowgli (Tienari, Raatikainen, Alanko) concentrating on mobile computing in general and also in developing a software architecture for implementing mobile-aware applications. Also the new project RODAIN (Real-Time Object Based Database Architecture for Intelligent Networks) (Raatikainen) has strong ties to the Finnish telecommunication and software industries. The projects in distributed systems are DRYAD (Tienari, Alanko), in- vestigating open distributed processing, and MOCO (Modeling Concur- rency) (Tienari), concentrating on formal speci|cation and veri|cation of distributed systems. In the latter area, in particular, we have achieved no- table results well-received by the international research community. The department has long traditions in the research of programming lan- guages and compilers. This research still continues but is mainly directed now to object oriented languages and their implementation problems. From this work a new research line in software engineering (Paakki) has evolved. Below, under the titles iIntegrated Protocol Engineeringj and iComputer- Aided Software Maintenancej, an account of this work is given. In information systems the largest research project concentrates on data mining (Mannila, Verkamo), also known as knowledge discovery in databases. The work on data mining has several subprojects, and it includes industrial projects as well as an ESPRIT project. The research is done in cooperation with the machine learning group, with statisticians, and with the appliers of the work. Other research projects include relational database design (Mannila), evaluation of Datalog queries (Sippu), document management (Kilpelainen, Mannila), computer-supported cooperative work (Erkio), and knowledge rep- resentation (Grahne). The database design work has been published also as a monograph by Addison-Wesley. Recent research results include eOEcient data mining methods for database re-engineering, methods for |nding recurrent episodes within event sequences, new eOEciently evaluable query languages for text databases, and methods for automatically forming the grammar de- scribing the structure of a text document. 6 Active projects and research areas as well as individual research of some researchers and graduate students are presented in more detail in Section 2.2. Section 2.3 lists a selection of recent publications. More information on research projects can be found on the WWW pages of the department. 2.2 Projects a) General Computer Science Algorithms on Strings Research on strings algorithms, istringologyj started at the department quite early, in 1981. The initial impulse came from computer applications in molec- ular genetics where there is a lot of demand for eOEcient and sophisticated string-manipulation algorithms. The group is now one of the leaders in its special |eld in the world and has obtained several basic results that have been included in recent international text books. The group organized the 6th Annual Symposium on Combinatorial Pattern Matching in Helsinki in 1995. The reputation of the group is based on the work done in the 1980's on developing new algorithms for the following problems: edit distance, ap- proximate string matching, DNA sequence assembly, and shortest common superstring. In 1990's, various isublinearj approximate string-matching al- gorithms and new measures for string similarity have been developed. For the important problem of how a text should be preprocessed to speed-up subsequent approximate string searches, several solutions have been discov- ered based on the suOEx-tree of the text or the so-called iq-gramsj. For constructing suOEx-trees a natural ion-linej algorithm has been developed. The two-dimensional string matching problem has also been studied. We were able to obtain the |rst optimal expected time solutions using simple, practical algorithms. This is in contrast with the many worst-case optimal solutions proposed in the literature which are very complicated and have small practical value. Another new research direction is the study of special databases for strings. We have obtained initial results on reasoning about strings in databases and on extending the relational database model to allow for typical queries on strings. The on-going work deals with dioeerent feature-based schemes for approx- imate string matching, two and higher dimensional string matching, the in- dexing of strings, and string databases. Computational biology will get more emphasis in the future. Current members of the group are Prof. Esko Ukkonen (group leader), Doc. Gosta Grahne, Doc. Jorma Tarhio, Raul Hakli, M.Sc. Juha Karkkainen, 7 M.Sc. Kai Korpimies, Outi Lehtinen, M.Sc. Matti Nykanen, and M.Sc. Erkki Sutinen. The group gets support from the Academy of Finland. Publications: [9598, 100105, 110, 112123, 139]. Machine learning Being able to build computer systems that can learn in some sense is one of the very central problems in arti|cial intelligence. Inspired by certain theo- retical advances in the |eld such as Valiant's PAC model and Rissanen's MDL principle, the project generally aims, unlike traditionally in AI, to apply to machine learning the approach of theoretical computer science and algorith- mics. This international trend is called computational learning theory. Our theoretical work is supported by experimenting with the algorithms. Our results include generalizations and analyses of the RANK algorithm by Ehrenfeucht and Haussler, several theoretical results on the power of the so-called useful and reliable learnability (a variant of the PAC model), and in- troducing a new family of learning algorithms satisfying the Occam condition for learning decision lists and certain decision trees. The Occam algorithms are suitable for |nding common patterns in sets of strings. Two extensive tools for experimenting with learning algorithms have been produced: The TELA system for the study of learning algorithms that use traditional form of the data represented as attribute vectors, and the DALI system for the study of learning algorithms that use strings as the basic data. The current research themes of the group are: - Development of a decision tree learning algorithm that has a sound theoretical basis and performs well in practice. - Development of new MDL learning algorithms for various practical learning tasks as well as development of the complexity theory for MDL learning. Here some very promising results have been obtained recently including the |rst MDL learning algorithm that has a proven performance guarantee and its application to a clustering problem of biological sequences. - Further development of the Occam algorithms mentioned above and, in particular, their application to problems in computational biology. - Further development of the TELA and DALI systems. The group has good international reputation and is together with nine other European groups a member of the ESPRIT Working GroupiNeuroCOLTj and a site of European Machine Learning Network. 8 The group also works in close co-operation with Prof. Heikki Mannila's data mining group. The members of the group are Prof. Esko Ukkonen (group leader), Dr. Jyrki Kivinen, Dr. Tapio Elomaa, Timo Lamminjoki, M.Sc Janne Ravantti, Kimmo Valtonen, and M.Sc. Jaak Vilo. The group gets funding from the Academy of Finland and from the European ESPRIT Programme. Publications: [147, 148, 195205, 208215, 221]. Neural computing and complex systems (CoSCo) A complex system is a collection of simple interacting agents, elements or processes whose collective behavior exhibits interesting large scale phenom- ena. Such systems can be found in various disciplines, including economics, computer science, mathematical biology and physics. Formal models of such systems include e.g., Bayesian belief networks, arti|cial neural networks, cel- lular automata, genetic algorithms and autocatalytic networks. The Complex Systems Computation (CoSCo) research group studies com- putational issues related to complex systems focusing on learning, model selection, self-organizing behavior and computational complexity questions. The research areas addressed include neural networks, probabilistic and sta- tistical models, cased-based reasoning (CBR) and evolutionary programming (genetic algorithms). The results achieved include - techniques for mapping Bayesian belief networks to neural network architectures, thus allowing massively parallel implementations of Bayesian reasoning; - methods for learning probabilistic models from sample data; - complexity analyses of various problems related to the Hamming and Hop|eld neural network models, as well as results about the conver- gence of genetic algorithms. - a prototype for a probabilistic DeciSIon enDorsement Environment, D-SIDE; - an expert system shell (CAse-Based INferencE Tool, CABINET) for case-based reasoning with a probabilistic similarity metrics for case matching and adaptation; - fundamental studies on the computational power of dioeerent neural network models including synchronous, asynchronous, and continuous- time Hop|eld nets; on the eoeects of noise on discrete-time analog com- putation; and on the computational power of cellular automata -like models (speci|cally, so called coupled map lattices). 9 Basic research work by the group has been supported by grants from the Academy of Finland, the University of Helsinki, and various foundations. More applied work has been performed with support from TEKES and the domestic and foreign industrial partners which include, e.g., Kone, Nokia, ABB, and the AT&T and 3M corporations (USA). Some of the resulting software has been adopted in the industry. Current members of the CoSCo group are Prof. Pekka Orponen, Dr. Petri Myllymaki, M.Sc. Henry Tirri, M.Sc. Tomi Silander, Petri Kontkanen and Jussi Lahtinen. The group has also hosted several foreign graduate students, and participates in two EC-funded research networks (the NeuroCOLT work- ing group, and the Network of Excellence in Neural Computing, NEURO- NET). Publications: [41, 7286, 141146, 188, 189, 218225, 229231]. Animation Aided Problem Solving (AAPS) Animation is a standard technique in computer-aided instruction. The project aims at applying the methods of algorithm animation in problem solving. The idea is based on the internal similarity of algorithm design and problem solving. Traditionally animations were coded by hand demanding much time. We have developed a system for fast generation of animations for algorithms, and the generation speed is one of the key factors of the applicability of our approach. We see challenges at least in three areas: developing a descriptive lan- guage for problem solving, |nding a set of problems such that their solutions can be described using this language, and developing the visual counterparts for the language elements. Our research topic lies in the borderland of computer science and edu- cation and needs a true dialogue between these two disciplines. Therefore, the research will be carried out as a joint project with the Department of Teacher Education.. Current members of the AAPS group are Doc. Jorma Tarhio (group leader), Assoc. prof. Veijo Meisalo (Department of Teacher Education), M.Sc. Erkki Sutinen, Simo-Pekka Lahtinen, and Erkki Rautama. The group gets funding from the Ministry of Education in 199697. Publications: [245, 251254]. Individual Research Visualization in Science and Education (Assoc. prof. Matti Makela): Advanced computer graphics provides means of visualizing sci- 10 enti|c data and complicated formal structures and interactions which have earlier been diOEcult to manage and conceive by human brains. Scienti|c visualization ooeers a method to make pictures from the abstract material produced by scienti|c models and measurements. Thus, the natural human ability to see and think visually is utilized besides the traditional scienti|c thinking. The same applies in education, too. One essential problem is to select a proper type of pictures for representing the abstract data and to formalize the transformation from data to pictures. Another problem is the visual literacy, that is the ability to express thoughts by pictures, and the ability to interpret pictures. The scope of this research is to |nd out prac- tical recommendations to attack these problems. The present activities will include animation tools, corrosion simulation, and visualization and hyper- media applications for graphics education. As the problem area is highly interdisciplinary there are several contacts within the university, and with Helsinki University of Technology, Center for Scienti|c Computing, and Uni- versity of Industrial Arts (Helsinki), among others. Data Structures (Dr. Otto Nurmi) Problems arising from the use of data structures in a concurrent environment are studied. EOEciency consider- ations require that the search paths of a data structure should be short and that operations should not block too large a part of the structure for too long a time. These two requirements conAEict, since keeping the paths short after an update can, in a straightforward implementation, block too large a part of the structure. One would prefer that all operations reserve only a small, |xed-size part of a structure at all times. An elegant solution for these problems with dictionary operations was proposed in 1987. The solution was based on the notion of relaxed balance in AVL and B-trees and the decoupling of updates and rebalancing. In 1991 the idea of relaxing the balance condition was applied to red-black trees, the most promising data structures for implementing a data base in main memory. The newest results on the area concern augmenting the structures with further operations such as batch updating, and tightening the balance conditions. The research has been done in co-operation with Prof. D. Wood (Univer- sity of London, Canada), J. Eckerle (Universitat Freiburg, Germany), and a group at Helsinki University of Technology lead by Prof. E. Soisalon-Soininen. Publications: [68]. 11 b) Computer Software Modelling of Concurrency (MOCO) Distributed systems and parallel programs are notoriously prone to errors caused by subtle dioeerences in the relative execution orderings of the com- ponents of the system. In order to avoid such errors systems should be care- fully speci|ed and analyzed. The international research in this area, often called simplyiconcurrencyj, has been active in the 1980's and has resulted in numerous speci|cation methods and models for this purpose, e.g. state transition systems, Petri nets, process algebras and temporal logics. Elegant and rich theories supporting these models have made the models even more useful. Results in these theories can be employed in computer based analysis tools for checking and verifying concurrent real life software. An important class of distributed algorithms consists of computer com- munication protocols. We have worked with the problems of protocol anal- ysis since 1984. We begun by constructing a reachability analysis tool PROTAN88 designed for protocols speci|ed with an extended state tran- sition model (ESTELLE speci|cation language). In the 1980's this tool has been tried out by us in analyzing several well-known real-life protocols like X.25, FTAM and X.411/P1. Some of our improvement suggestions were included in the FTAM state tables published by CCITT and ISO. Lately our work has been more conceptual and theoretical. Various equiv- alence concepts have been studied in process algebra contexts (Milners CCS and ISO LOTOS) and the equivalence preserving minimization of labeled state transition systems has been studied. We have been especially inter- ested in divergence preserving behavioural equivalences and preorders. These equivalences allow neat comparisons between bisimulation and failures based equivalences and congruences. If an equivalence does not preserve diver- gences, it is diOEcult to analyze liveness properties after equivalence preserv- ing transformations of a transition system. Many aspects of temporal logic are closely related with equivalences and preorders. Research topics in this area include |xpoint calculi (mu-calculi) and automata on in|nite objects. A recurrent theme in our research is to make analysis and veri|cation feasible for concurrent systems of realistic size. That is why the dominant goal in our research is to understand and support compositional (or modular) speci|cation and veri|cation of concurrent systems. We have been e.g. ana- lyzing and applying the weakest equivalence (CFFD-equivalence) preserving deadlocks and linear next-timeless linear temporal formulae. Our research employs case analyses (often computer communication protocols) to ensure the practical usefulness of the theoretical concepts. At the university of Helsinki we have been developing a computer-based 12 veri|cation tool BIDMIN allowing us to minimize labeled transition systems with respect to divergence preserving bisimilarity and branching bisimilarity as well as the related congruences. We also often use a LOTOS oriented veri|cation tool ARA TOOLS developed at the Technical Research Centre of Finland. ARA TOOLS is a prototype aiming at industrial quality. Current members of the MOCO group are Prof. Martti Tienari (group leader), Dr. Jaana Eloranta, Dr. Roope Kaivola, M.Sc. Vesa Hellgren, Ph.Lic. Timo Karvi and M.Sc. Paivi Kuuppelomaki. As an associate member of the group we have professor Antti Valmari (Tampere University of Technology, Software Systems Laboratory) who is the chief designer of ARA TOOLS. Our concurrency group is participating (199496) in European COST247-project iVeri|cation and Validation Methods for Formal Descriptionsj. Publications: [124137]. Open Distributed Processing (DRYAD) The rapid advances in data communication networks have greatly increased the possibilities to make use of the various computational and information services available within reach of a computer network. These services may have dioeerent origins, they are implemented on dioeerent types of computa- tional platforms, and they can be located on sites far apart. As dioeerent services become reachable, interoperability of services must be considered. Distributed computation needs an enhanced functionality of the infrastruc- ture. Especially, emerging technologies around wireless communication open up ways for new AEexibility. The department started research activity in the area of open distributed processing at the end of 1980's. In our |rst project (AHTO) we designed a distributed software environment (imiddlewarej) ooeering for a user a ho- mogeneous interface to the computing services available in a heterogeneous computer network. Since that time the department has participated in the development of the Reference Model for Open Distributed Processing, under the auspices of ISO and ITU-T (former CCITT). The DRYAD project, started in 1992, studies open distributed systems, such as Open Distributed Processing reference model (ODP-RM). Especially we concentrate on heterogeneous environments that are created by integrat- ing autonomous computing systems. The technology solutions at each system can be heterogeneous at any level: hardware, operating system, middleware, languages, and applications. Basic problem in such an environment is the interoperability of systems: the objects should be able to communicate with each other reasonably re- gardless of the dioeerences in peer system technologies. We try to solve the interoperability problem by designing distributed middleware layer mecha- 13 nisms, that can themselves be heterogeneous. The project considers also open platforms, such as OMG/CORBA, and management aspects of open platforms. The DRYAD project has developed a prototype software package for some of the middleware services especially the trading function. The project has been also actively involved with international standardization work on ODP reference model. For example, one of the standardization meetings was held in Helsinki, in May 1995. The members of the DRYAD project group are Prof. Martti Tienari, M.Sc. Lea Kutvonen, Petri Kutvonen, M.Sc. Liisa Marttinen and Pekka Kahkipuro. The work has been partially funded by the Technology Devel- opment Centre TEKES, ICL Personal Systems, Telecom Finland, Helsinki Telephone Company, Finnish State Computing Centre, and Center for Sci- enti|c Computing. Publications: [2127]. Mobile Computing (MOWGLI) The goal of the MOWGLI project is to study, design and test a data com- munication architecture for a pan-European GSM-based mobile data service and to develop a prototype based on that architecture. The environment of an application consists of mobile PC's, which can be connected, through a mobile phone, to any part of a |xed data communication network. The work in the project is concentrated on the architectural aspects supporting mobility-aware computing. The main issues have been GSM-based wireless data transfer service, control of computing in weakly connected and dis- connected states, support for legacy software in a mobile environment, and design of mobility-aware applications for nomadic users (|le transfer, e-mail, WWW). The members of the MOWGLI project group are Prof. Martti Tien- ari, Dr. Timo Alanko, Doc. Kimmo Raatikainen, M.Sc. Heimo Laamanen, and M.Sc. Markku Kojo. The industrial partners of the project are Digital Equipment Corporation, Nokia Mobile Phones, Nokia Telecommunication Systems and Telecom Finland. Publications: [5, 6, 28, 29, 33]. Service Machine Development for an Open Long-term Mobile and Fixed Network Environment (DOLMEN) The EC/ACTS project DOLMEN (ACTS Ref. AC036), 199598, aims to de- velop, demonstrate, assess and promote a Service Architecture (called Open Service Architecture for a Mixed |xed and mobile environment OSAM) that meets the requirements of open provision of communication services 14 over both |xed and mobile heterogeneous and multi-provider telecommuni- cations networks. The project's approach will be based upon the RACE Open Service Archi- tecture (OSA) and will also progress results from RACE projects on mobility. The TINA-C current and future developments will be taken into account. In developing OSAM, the parallel work of related ACTS projects will be con- stantly monitored and utilized as appropriate. As in the case of OSA and TINA-C, the DOLMEN approach subscribes to a vision, beyond that cur- rently ooeered by IN and TMN, of a telecommunications service infrastructure as a large scale, distributed processing environment. Participants in DOLMEN are Fondazione Ugo Bordoni (Italy), University of Catania (Italy), INTRACOM S.A. (Greece), National Technical University of Athens (Greece), Personal Communications Services (UK), Research and Consultancy (UK), Telis (France), University of Helsinki (Finland), VTT In- formation Technology (Finland), Koniglijke PTT Nederland N.V. Research (The Netherlands), AT&T Network Systems Nederland B. V. (The Nether- lands), and Telecom Finland (Finland), The current members of the DOLMEN research group are Doc. Kimmo Raatikainen (group leader) and Mika Liljeberg. Real-Time Object-Based Database Architecture for Intelligent Networks (RODAIN) Database technologies will, already in the near future, have a dominant role in telecommunication and data communication networks. The information and knowledge needed in network operations and management will be organized as a logical entity. Due to the world-wide nature of communication the only way to achieve the logical uniformity is the interoperability of autonomous databases. The research project Dar|n, Database ARchitecture For Intelligent Net- works, 199395, examined database architectures that can ful|ll the require- ments of Intelligent Networks (IN) and Telecommunication Management Net- works (TMN). The current ITU-T Recommendations for TMN are based on object-oriented modelling. In addition, the long-term architecture of IN heavily advocates OO-modelling. Therefore, the project focused on object- oriented real-time databases. The research project RODAIN continues the work done in the Dar|n project. The ultimate objective of the RODAIN project is to design and to specify a real-time object-oriented database architecture for Intelligent Net- works and to implement a prototype based on that architecture. The design and speci|cation take place in 1996 while the prototype will be implemented in 1997. 15 Research topics: - real-time transaction processing, - main memory databases, - object models, - distributed object directory, - performance evaluation methodologies for real-time databases, and - OSI Directory and Management protocols (X.500 and X.700). The industrial partners and |nancial supporters of the project are Nokia Telecommunications, Solid Information Technology, Systems Software Part- ners and Telecom Finland. The RODAIN project is also funded by the Finnish Technology Development Centre (TEKES). Current members of the research group are Doc. Kimmo Raatikainen (group leader), M.Sc. Tiina Niklander, M.Sc. Juha Taina, and Petri Elovaara. Publications: [714, 32]. Integrated Protocol Engineering The constantly growing complexity of distributed and telecommunications applications has made it necessary to develop high-level application-oriented languages and tools. There exists a number of standardized languages and their implementations, but usually they focus just on some rather narrow aspect of the problem. This makes it necessary to use several unrelated languages and environments when implementing a nontrivial distributed ap- plication. This research project develops Kannel, an integrated language for the design and implementation of communications protocols. The main features of Kannel are high-level application support, object-orientation, and visual notations. In contrast to conventional languages in the area, Kannel and its programming environment provide facilities for all the main tasks in a typical protocol development eoeort. The |rst version of Kannel has been designed and implemented. The implementation entails a visual Kannel editor and a translator into C++. A graphical interpretive simulator and an integration with the protocol devel- opment environment CVOPS, developed at VTT in Finland, are currently under implementation. The main implementation language in the project is C++. The research has been constructive rather than theoretical, try- ing to achieve a practical tool set for protocol engineering. That is why 16 the project has been closely tied to an industrial steering group consist- ing of members from Nokia Research Center, Nokia Telecommunications, Nokia Mobile Phones, Nokia Cellular Systems, Telecom Finland, Technical Research Centre of Finland (VTT), and X-NET Ltd. The main funding has come from the Technology Development Centre (TEKES, 199295) and from the Academy of Finland (199596). The project is being carried out at two universities: Department of Com- puter Science, University of Helsinki (UH), and Department of Information Technology, Lappeenranta University of Technology (LUT). The research is organized roughly such that UH concentrates on the language issues, while the protocol side is taken care by LUT. The members of the research group are Assoc. prof. Jukka Paakki (UH), M.Sc. Kari Grano (UH), M.Sc. Antti- Pekka Tuovinen (UH), Prof. Jarmo Harju (LUT), and M.Sc.Eng. Jari Kuit- tinen (LUT). Publications: [3, 4, 15, 16, 5053]. Computer-Aided Software Maintenance Software maintenance is often the most expensive phase in a software sys- tem life-cycle, taking typically about 5080% of the total development costs. Therefore even modest improvements in the maintenance process may result in signi|cant bene|ts in the long run. The goal ot the research is to develop a tool supporting typical software maintenance tasks such as debugging, side-eoeect analysis, and regression testing. The tool, called HyperSoft is based on the combination of static program analysis and hypertext. First the target program is analyzed, and an internal (partial) representation is constructed for it. Then hypertextual access structures are generated on the basis of interactive speci|cations from the user. Finally the access structures are shown in a graphical user interface making it possible to systematically navigate in the program and to modify it. A prototype of HyperSoft has been implemented, mostly in C++. The prototype supports the maintenance of C programs, but the developed method and system architecture are rather independent of any particular target language. An extension into C-embedded SQL is currently under de- sign and implementation. The project is jointly carried out at the Department of Computer Science, University of Helsinki (UH), and at the Department of Computer Science and Information Systems, University of Jyvaskyla (UJ). The researchers are As- soc. prof. Jukka Paakki (UH), Prof. Airi Salminen (UJ), M.Sc. Jussi Koskinen (UJ), and M.Sc. Mika Nieminen (UJ). The project is |nanced during 199496 by Technology Development Centre (TEKES), Academy of Finland, Nokia 17 Research Center, KT-Tietokeskus, TT-Tieto, and TT-Kuntapalvelut. Publications: [4749]. Individual Research Language Design and Implementation for Multiple Paradigms (Ph.Lic. Juha Vihavainen): Multiparadigm programming integrates dif- ferent programming perspectives in order to simultaneously utilize concepts and mechanisms related to alternative programming paradigms. The dif- ferent programming paradigms (the main ones being procedural, object- oriented, functional, and logic) are considered to be complementary rather than conAEicting computational models. The constructive goals are to de- velop a general uniform implementation model for multiple paradigms and to produce software (a class library) to implement this model. The imple- mentation approach is based on meta-programming methodology in which a reAEective object-oriented architecture is extended by rede|ning and specializ- ing meta objects. This software addresses traditional translation issues (such as scanning, parsing, semantic analysis, and code generation) but also spe- cial problems related to class hierarchies (inheritance), dynamic and static polymorphism (generics), and higher-order values. The implementation is done in C++. Publications: [36]. Logic Programming (Assoc. prof. Jukka Paakki) Logic programming is a paradigm founded upon |rst order logic. Being mathematical in se- mantics, logic programming languages are harder to analyze and implement eOEciently than conventional imperative languages. The research develops analysis methods for logic programs, so as to improve their automated pro- cessing. Special emphasis is laid on data-AEow aspects that can be utilized in compilation and debugging of logic programs. The research is connected to similar work at the Hungarian Academy of Sciences, Szeged, and at Linkop- ing University, Sweden. Publications: [46, 54, 55, 6062, 140, 182]. c) Information Systems Data Mining Data mining (or knowledge discovery in databases) is a new research area developing methods and systems for extracting interesting and useful infor- mation from large sets of data. Data mining methods can be used in a va- riety of application areas, such as commercial databases, telecommunication 18 alarm sequences, epidemiological data, etc. The area combines techniques from databases, statistics, and machine learning. The Data Mining research group has developed data mining methods and studied the theory of data mining. The research started in late 1980's in the context of developing tools for inferring integrity constraints from databases. The recent focus of the research group has been in the analysis of event (sequence) data. We have considered methods for |nding recurrent episodes within event sequences, and using these to locate strong rules about the occurrences of the events. We also apply Markov chain Monte Carlo methods to examine the interdependence of events in more detail. Also clustering methods have been applied to locate regularities in the data. With large amounts of information produced by data mining, we are also looking at the problem of selection and visualization of the regularities, to help the user to make use of the data mining results. In connection with the Document Management group, we have also considered discovering document structures from marked documents. The group has also studied the theory of data mining, e.g., by looking at the relationship of the logical complexity of the discovered sentences and the sample size needed for discovery, and by investigating various frameworks for data mining. The research is done in several projects funded by the Academy of Fin- land, TEKES, and the EU ESPRIT research programme. The group has close cooperation with the Document Management and Machine Learning groups. The members of the Data Mining group are Prof. Heikki Mannila (group leader), Ph.Lic. Helena Ahonen, M.Sc. Oskari Heinonen, M.Sc. Mika Klemettinen, M.Sc. Pirjo Ronkainen, M.Th. Marko Salmenkivi, M.Sc. Riikka Suramo, M.Sc. Hannu Toivonen, and Dr. Inkeri Verkamo. Publications: [1820, 162, 163, 170178, 206, 216, 217, 227, 232, 241]. Document Management (DocMan) Text with a structure is quite common: dictionaries, reference manuals, and annual reports are typical examples. In recent years, research on systems for processing structured documents has AEourished. The SGML and ODA standards have further increased the interest in the area. The Document Management (DocMan) Research Group studies the theory and application of such structured documents. Structured and Intelligent Documents (SID) is an on-going project within the DocMan group that studies and develops methods for attaching intelli- gent features to structured documents. The purpose of these features is to make the manipulation (storage, retrieval, and assembly) of documents eas- 19 ier. The project started in 1995. SID is part of the new Electronic Printing and Publishing program started by the Technology Development Center of Finland (TEKES). Funding for SID is provided by TEKES and a group of supporting companies. One of the basic problems in document management is to provide on- demand generation of individualized documents through dynamic document assembly. Document assembly composes new documents from an existing collection of documents. Naturally, document markup and structure con- tribute to the retrieval and reuse of document fragments. An intelligent document contains knowledge about itself and its envi- ronment. It supports assembly of documents based on inputs given by the user. It is no longer a passive, linear representation of text, but is able to construct itself dynamically. Document assembly is intelligent when it uses application-domain-speci|c information about the document in addition to the contents and their structure. The goals of the SID project include (1) de|ning the information and the knowledge a structured document must contain so that it can work in an active and intelligent way, (2) developing prototype tools for intelligent assembly, and (3) de|ning a methodology for incorporating intelligence into document material. As a basis for the project we consider structured doc- uments marked up with SGML. The project combines methods and tools from, e.g., structured-document management, information retrieval, pattern matching, data mining, distributed systems, and machine learning. When dealing with documents in morphologically rich languages like Finnish, also natural language processing is vital to the success of document assembly. Other ongoing research within the DocMan group includes building gram- mars from pretagged text, and structured document transformations. Former research projects include the RATI project (198891) for building a prototype document manipulation system which provides multiple views of a document and the sgrep project (1995) which designed and implemented a search tool for structured documents. Also some results of the VITAL project (199095) are usable in this context: one of the tools built in the VITAL project was a general purpose text transformation generator suitable also for structured document transformations. Researchers of the group are Prof. Heikki Mannila, Ph.D. Pekka Kilpelainen, Ph.Lic. Helena Ahonen, Ph.Lic. Greger Lind#n, M.Sc. Barbara Heikkinen, M.Sc. Oskari Heinonen, and Jani Jaakkola. Publications: [57, 58, 64, 106, 107, 153, 154, 191194]. 20 Transaction Management Concepts such as transaction and a serializable history were introduced when only centralized database systems existed. As distributed systems developed, these concepts were extended to distributed systems. However, an important dioeerence between a distributed system and a centralized system are the rel- atively large communication delays between the sites and the autonomy of local systems. As a result, the traditional concepts of the transaction and the serializable history, though well suited for traditional centralized systems, may not be suitable in distributed systems. Moreover, as the database con- cepts have been applied to new areas such as computer-aided design, oOEce information systems and cooperative work, re|ned and generalized transac- tion models are needed. In this research area at our department new transaction models together with protocols for transaction management in heterogeneous distributed database systems have been developed. One approach exploits the infor- mation of distributed consistency constraints. This approach has resulted in the introduction of the notions of ipartial serializabilityj and icombined transactionsj. The transaction research at our department is partly per- formed in cooperation with INRIA (France) and Purdue University in the United States. This research has resulted in the notions of ivalue datesj and ifragmented composite objectsj. Researchers of the group are Ph.Lic. Juha Puustjarvi and M.Sc. Henry Tirri. Publications: [164166]. Transaction Management Support for Cooperative Applications (TRANS- COOP). Today`s software tools mostly aim at supporting a single user only. For example, consider text editors for writing documents, CAD-tools or soft- ware development environments. There are excellent text editors available, but they do not appropriately support multiple authors to work on the same document concurrently. A major conceptual problem in this framework is to ensure consistency criteria for the data concurrently processed by multiple users. Conventional database technology already provides mechanisms to absolutely guarantee consistency constraints by controlling the concurrent access of dioeerent users to shared data. Unfortunately, existing transaction management concepts are not suitable for supporting and controlling cooperation between users, because they are designed to fully isolate users from each other. The design of cooperative systems includes the description and formal speci|cation of cooperative activities. Such speci|cations have to be mapped to a cooperative transaction management model in order to enable appro- priate database management support at run time. Cooperative transactions 21 are thus intrinsically complex operations that are diOEcult to understand completely. A theory is needed for distinct notions of correctness and for correctness-preserving transformations that allow the designer to map spec- i|cations onto implementation platforms in a guided way. The partners of the project are GMD (D), University of Twente (NL) and Technical Research Centre of Finland (VTT) having University of Helsinki as a subcontractor. Current members of the research group are Doc. Jari Veijalainen Doc. Hannu Erki#, M.Sc. Henry Tirri, and Ph.Lic. Juha Puustjarvi. Individual research Knowledge Representation and Reasoning (Doc. Gosta Grahne) As soon as data becomes more complex than a collection of records, there is a need to address knowledge representation and reasoning issues. These issues require solving semantic, algorithmic, and complexity theoretic subproblems. The research has focused on problems stemming from incomplete information in relational databases, on recursion, on the relationship between updates to logical theories and counterfactual reasoning, and between updates and belief revision, on database updates and generalized datalog. Current research involves the reasoning about strings (such as DNA sequences) in databases. Publications: [155157, 159161, 183187]. 2.3 Publications Recent publications of the Department are listed below according to the ACM Computing Reviews (CR) classi|cation system. The list contains selected publications in 199193 and new publications since January 1994. Introductory and Survey (A.1) 1. H. Lokki, I. Haikala, S. Linnainmaa, K. Ronka, and O. Susiluoto: Intro- duction to Data Processing (in Finnish). 3rd ed, Tietotekniikan liitto, 1992. Computer-Communication Networks General (C.2.0) 2. M. Tienari and D. Khakhar (eds.): Information Network and Data Communication. IV. Proc. IFIP TC6 International Conference, North- Holland, 1992. 22 Network Architecture and Design (C.2.1) 3. K. Grano, J. Harju, T. Jarvinen, T. Karttunen, T. Larikka, and J. Paakki: Application of the protocol engineering language Kannel to IN service speci|cation. In: Proc. 3rd Summer School on Telecommu- nications, Vol. I: IFIP TC-6 International Workshop on Intelligent Networks (ed. O. Martikainen and J. Harju). Lecture Notes LN-18, Lappeenranta University of Technology, 1994, 7993. 4. K. Grano, J. Harju, T. Jarvinen, T. Karttunen, T. Larikka, and J. Paakki: IN service speci|cation using the Kannel language. In: Intel- ligent Networks (ed. J. Harju et al.), Chapman & Hall, 1995, 7796. 5. J. Kiiskinen, M. Kojo, M. Liljeberg, and K. Raatikainen: Data channel service for wireless telephone links. To appear in Proc. 2nd Interna- tional Mobile Computing Conference, Hsinchu, Taiwan, 1996. 6. M. Kojo, K. Raatikainen, and T. Alanko: Connecting mobile work- stations to the Internet over a digital cellular telephone network. In: Mobile Computing (ed. T. Imielinski and H. Korth), Kluwer Academic Publishers, 1996, 253270. 7. K. Raatikainen: Database Access in intelligent networks. In: Intelligent Networks (ed. J. Harju et al.), Chapman and Hall, 1995, 173193. 8. K. Raatikainen: Information aspects of services and service features in intelligent network capability set-1. Report C-1994-45, Department of Computer Science, University of Helsinki, 1994. 9. K. Raatikainen, T. Karttunen, O. Martikainen, and J. Taina: Eval- uation of database architectures for intelligent networks. In: Proc. TeleCom 95, ITU, 1995, Vol. 2, 549553. 10. K. Raatikainen and J. Taina: Design issues in database systems for telecommunication services. In: Proc. IFIP-TC6 Working Conference on Intelligent Networks, TeleDenmark, 1995, 7181. 11. J. Taina: Problem classes in intelligent network database design. In: Intelligent Networks (ed. J. Harju et al.), Chapman & Hall, 1995, 197 204. 12. J. Taina and K. Raatikainen: Design issues and experimental database architecture for telecommunications. To appear in Proc. IFIP IN '95, Intelligent Networks and New Services (ed. W. Iversen et al.), Chapman and Hall, 1996. 23 13. J. Taina, M. Rautila, and K. Raatikainen: An experimental database architecture for intelligent networks. In: Proc. IFIP TC6 Working Conference on Intelligent Networks, Copenhagen, 1995. 14. J. Taina and H. Tohonen: On implementing a prototype IN database architecture. Report C-1995-42, Department of Computer Science, University of Helsinki, 1995. Network Protocols (C.2.2) 15. K. Arvonen, K. Grano, J. Harju, and J. Paakki: Experiences with the integration of protocol software tools. To appear in Computer Com- munications. 16. T. Jarvinen, K. Grano, J. Harju, and J. Paakki: An integrated envi- ronment for protocol engineering. In: Proc. NWPER '94, 6th Nordic Workshop on Programming Environment Research (ed. B. Magnusson et al.), Report LU-CS-TR: 94-127, Department of Computer Science, Lund University, 1994, 177193. 17. J. Paakki, K. Grano, A. Ahtiainen, and S. Kesti: An implementation of ASN.1 (Abstract Syntax Notation One). In: Proc. 3rd Symposium on Programming Languages and Software Tools (ed. M. Tombak), Uni- versity of Tartu, Department of Computer Science, 1993, 95108. Network Operations (C.2.3) 18. K. Hatonen, M. Klemettinen, H. Mannila, P. Ronkainen, and H. Toivo- nen: Rule discovery in alarm databases. Report C-1996-7, Department of Computer Science, University of Helsinki, 1996. 19. K. Hatonen, M. Klemettinen, H. Mannila, P. Ronkainen, and H. Toivo- nen: TASA: Telecommunication alarm sequence analyzer, or iHow to enjoy faults in your networkj. In: Proc. NOMS '96, 1996 IEEE Net- work Operations and Management Symposium, Kyoto, Japan, IEEE, 1996, 520529. 20. K. Rossi and H. Toivonen: Q3E: Q3 emulator agent. In: Proc. NOMS '94, IEEE Network Operations and Management Symposium, Kissimmee, Florida, IEEE, 1994, 7080. 24 Distributed Systems (C.2.4) 21. L. Kutvonen: Achieving interoperability through ODP Trading func- tion. In: Proc. ISADS '95, Second International Symposium on Au- tonomous Decentralized systems, IEEE Computer Society, 1995, 6369. 22. L. Kutvonen: Comparison of the DRYAD trading system to ODP Trad- ing function draft. Report C-1994-51, Department of Computer Sci- ence, University of Helsinki, 1994. 23. L. Kutvonen: Federation transparency in ODP trading function. Report C-1994-32, Department of Computer Science, University of Helsinki, 1994. 24. L. Kutvonen: Overview of the DRYAD trading system implementa- tion. In: Proc. IFIP/IEEE International Conference on Distributed Platforms (ed. A. Schill et al.), Chapman & Hall, 1996, 314326. 25. L. Kutvonen: Supporting transition to open, heterogeneous comput- ing environment. In: TINA '95, Integrating Telecommunications and Distributed Computing from Concept to Reality, 1995, 5566. 26. L. Kutvonen and P. Kutvonen: Broadening the user environment with implicit trading. In: Proc. Second IFIP TC6/WG6.1 International Conference on Open Distributed Processing, Berlin, 1993, 157168. 27. P. Kutvonen and L. Kutvonen: Measured performance of a special- purpose database engine for distributed system software. In: Proc. First International Workshop on High Speed Networks and Open Dis- tributed Platforms (ed. V. Tschammer and M. Smirnov), St. Peters- burg, 1995. Also to appear in Computer Communications Journal. 28. M. Liljeberg, T. Alanko, M. Kojo, H. Laamanen, and K. Raatikainen: Optimizing World-Wide Web for weakly-connected mobile worksta- tions: an indirect approach. In: Proc. IEEE SDNE '95, 2nd Inter- national Workshop on Services in Distributed and Networked Environ- ments, IEEE Computer Society Press, 1995, 132139. 29. M. Liljeberg, H. Helin, M. Kojo, and K. Raatikainen: Enhanced ser- vices for World-Wide Web in mobile WAN environment. To appear in Proc. IMAGE'COM 96, 3rd International Conference Communicating by Image and Multimedia, Bordeaux, France, 1996. 30. K. Raatikainen: Experimental evaluation of a parallel spectral method for run length control in steady-state simulation. Report C-1994-55, Department of Computer Science, University of Helsinki, 1994. 25 31. J. Taina: Evaluation of OMG, ODMG, X.500, and X.700 Data Mod- els. Report C-1994-54, Department of Computer Science, University of Helsinki, 1994. Special-Purpose and Application-Based Systems (C.3) 32. J. Taina: Requirements analysis for database services in telecommuni- cations. Report C-1995-17, Department of Computer Science, Univer- sity of Helsinki, 1995. Performance of Systems (C.4) 33. T. Alanko, M. Kojo, H. Laamanen, M. Liljeberg, M. Moilanen, and K. Raatikainen: Measured performance of data transmission over cel- lular telephone networks. Computer Communications Review, 24, 5 (1994), 2444. 34. K. Raatikainen: Symptoms of self-similarity in measured arrival pro- cess of Ethernet packets to a |le server. In: Proc. NTS-12, Nordic TeletraOEc Seminar, VTT, 311324. Object-Oriented Programming (D.1.5) 35. K. Grano: Object-oriented implementation of communication proto- cols. In: Conceptual Modelling and Object-Oriented Programming (ed. A. Lehtola and J. Jokiniemi), Publications of the Finnish Arti|cial Intelligence Society, no. 11, 1993, 117131. 36. K. Koskimies and J. Vihavainen: The problem of unexpected sub- classes. Journal of Object-Oriented Programming 5, 6 (1992), 5359. Logic Programming (D.1.6) 37. T. Eiter, G. Gottlob, and H. Mannila: On the expressive power of disjunctive logic programming over |nite structures. Report CD-TR 96/90, Christian Doppler Laboratory for Expert Systems, TU Vienna, 1996. Software Engineering Tools and Techniques (D.2.2) 38. K. Arvonen, J. Harju, K. Grano, and J. Paakki: A Survey of software tools in protocol engineering. Technical Report TR-1, Lappeenranta University of Technology, 1993. 26 39. K. Grano: A Case Study on the Application of Protocol Software Tools. In: Proc. 2nd Summer School on Telecommunications (ed. Jarmo Harju), Lecture Notes LN-17, Lappeenranta University of Tech- nology, 1993, 117142. 40. G. Lind#n, J. Manuel Quesada, and A. I. Verkamo. OCML to FND CASE integration transformations, user's guide. Technical Report T444/DS/2, ESPRIT-II Project 5365 VITAL, April 1995. 41. G. Lind#n, L. Montero, J. Manuel Quesada, H. Tirri, and A. I. Verkamo. OCML to FND CASE integration transformations, technical descrip- tion. Technical Report T444/DS/1, ESPRIT-II Project 5365 VITAL, April 1995. 42. G. Lind#n and A. I. Verkamo. An interface between dioeerent software development environments. In: Proc. KBSE '95, Tenth Annual Knowl- edge Based Software Engineering Conference, IEEE Computer Society Press, 1995, 7987. 43. A. I. Verkamo: Cooperation of KBS development environments and CASE environments. In: Proc. SEKE '94, Sixth International Confer- ence on Software Engineering and Knowledge Engineering, Knowledge Systems Institute, 1994, 358365. 44. A. I. Verkamo and G. Lind#n: Case tool interface. Internal deliverable UH/T443/ID003, ESPRIT-II Project 5365 VITAL, May 1994. 45. A. I. Verkamo and G. Lind#n: Problems in interfacing tools of dioeerent development environments. In Proc. SEKE '95, Seventh International Conference on Software Engineering and Knowledge Engineering, 1995, 429437. Software Engineering Testing and Debugging (D.2.5) 46. T. Gyim#thy and J. Paakki: Static slicing of logic programs. In: Proc. AADEBUG '95, 2nd International Workshop on Automated and Algo- rithmic Debugging (ed. M. Ducass#), IRISA-CNRS, 1995. Software Engineering Distribution and Maintenance (D.2.7) 47. J. Koskinen, J. Paakki, and J. Salminen: Program text as hypertext using program dependences for transient linking. In: Proc. SEKE '94, Sixth International Conference on Software Engineering and Knowledge Engineering, Knowledge Systems Institute, 1994, 209216. 27 48. A. Salminen, J. Koskinen, and J. Paakki: HyperSoft: an environment for hypertextual software maintenance. In: Proc. NWPER '94, 6th Nordic Workshop on Programming Environment Research (ed. B. Mag- nusson et al.), Report LU-CS-TR: 94-127, Department of Computer Science, Lund University, 1994, 2537. 49. A. Salminen, J. Paakki, and J. Koskinen: Incorporating hypertext func- tionality into software maintenance environments. To appear in Proc. ECHT '94, Workshop on Incorporating Hypertext Functionality into Software Systems, New Jersey Institute of Technology. Software Engineering Design (D.2.10) 50. K. Grano, J. Harju, T. Jarvinen, T. Larikka, and J. Paakki: Object- oriented protocol design and reuse in Kannel. In Proc. 21st Euromicro Conference on Design of Hardware/Software Systems, IEEE Computer Society Press, 1995, 465472. Programming Languages Language Classi|cations (D.3.2) 51. K. Grano and J. Paakki: A language for specifying communication protocols. In: Proc. 7th Finnish Symposium on Computer Science (ed. M. Penttonen), Report A-1994-1, Department of Computer Science, University of Joensuu, 1994, 117. 52. K. Grano, J. Harju, J. Paakki, and T. Jarvinen: Proposal for a protocol engineering language. Technical Report TR-6, University of Jyvaskyla, 1994. 53. K. Grano, T. Jarvinen, J. Paakki, J. Harju, and T. Larikka: Kannel a language for tuning protocols. In: Proc. 4th Symposium on Pro- gramming Languages and Software Tools (ed. L. Varga). Department of General Computer Science, Eotvos Lor#nd University, 1995, 209222. 54. J. Paakki: PROFIT: a system integrating logic programming and at- tribute grammars. In: Proc. PLILP '91, Programming Language Im- plementation and Logic Programming. 3rd International Symp (ed. J. Maluszynski et al.) Lecture Notes in Computer Science 528, Springer- Verlag, Berlin, 1991, 243254. Processors Compilers (D.3.4) 55. J. Boye, J. Paakki, and J. Ma#uszynski: Synthesis of directionality information for functional logic programs. In: Proc. WSA '93, 3rd 28 International Workshop on Static Analysis, Lecture Notes in Computer Science 724, Springer-Verlag, 1993, 165177. 56. K. Koskimies and J. Paakki: High-level tools for language implemen- tation. Journal of Systems and Software 15, 2 (1991), 115131. 57. G. Lind#n and H. Tirri. ALCHEMIST the handbook. Version 1.08. Technical Report T416/DS/2, ESPRIT-II Project 5365 VITAL, April 1995. 58. G. Lind#n, H. Tirri, and A. I. Verkamo. ALCHEMIST: a general pur- pose transformation generator. To appear in Software Practice and Experience. 59. G. Lind#n, H. Tirri, and A. I. Verkamo. The VITAL transformation assistant. In: VITAL Project Final Report ( ed. Rouge) Deliverable SYSECA/DD71.5, ESPRIT Project P5365 VITAL, April 1995. 60. J. Paakki: Multi-pass execution of functional logic programs. In: POPL '94, Conference Record 21st ACM SIGPLAN-SIGACT Sym- posium on Principles of Programming Languages. ACM Press, 1994, 361374. 61. J. Paakki: Prolog in practical compiler writing. Computer Journal 34, 1 (1991), 6472. 62. J. Paakki, T. Gyim#thy, and T. Horv#th: Independent and-paralleliza- tion of logic programs using static slicing. In: Proc. 4th Symposium on Programming Languages and Software Tools (ed. L. Varga), Depart- ment of General Computer Science, Eotvos Lor#nd University, 1995, 302311. 63. M. Tienari: Compiler compilers. In: Concise Encyclopedia of Software Engineering (ed. D. Morris et al.), Pergamon Press, Oxford, 1992, 57 59. 64. H. Tirri and G. Lind#n: ALCHEMIST an object-oriented tool to build transformations between heterogenous data representations. In: Proc. HICSS '94, 27th Annual Hawaii International Conference on System Sciences, Vol. 2, 226235. 65. H. Tirri and G. Lind#n. VITAL transformation approach. Deliverable UH/DD415, ESPRIT-II Project 5365 VITAL, 1994. 29 File Systems Management (D.4.3) 66. T. Alanko and P. Kutvonen: The AHTO directory: a distributed di- rectory designed for distributed usage. IEEE Distributed Processing Technical Committee Newsletter 14, 1 (1992), 1320. Performance (D.4.8) 67. K. Raatikainen: Cluster analysis and workload classi|cation. Perfor- mance Evaluation Review 20, 4 (1993), 2430. Data Storage Representations (E.2) 68. O. Nurmi and E. Soisalon-Soininen: Uncoupling updating and rebal- ancing in chromatic binary search trees. In: Proc. 10th ACM SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems, Denver, CO, 1991, 192198. Coding and Information Theory (E.4) 69. H. Peltola and J. Tarhio: On syntactical data compression. In: Proc. 2nd Symposium on Programming Languages and Software Tools (ed. K. Koskimies et al.), Report A-1991-5, Department of Computer Science, University of Tampere, 205214. 70. J. Tarhio: Context coding of parse trees. Proc. DCC '95, Data Com- pression Conference (ed. J. Storer and M. Cohn), IEEE Computer So- ciety Press, Los Alamitos, California, 1995, p. 442. Theory of Computation General (F.0) 71. O. Nurmi and E. Ukkonen (eds.): Algorithm Theory SWAT '92, 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 621, Springer-Verlag, Berlin, 1992. Models of Computation (F.1.1) 72. P. Flor#en and P. Orponen: Attraction radii in binary Hop|eld nets are hard to compute. Neural Computation 5, 5 (1993), 812821. 73. P. Flor#en and P. Orponen: Complexity issues in discrete Hop|eld net- works. Report A-1994-4, Department of Computer Science, University of Helsinki. To appear in The Computational and Learning Complexity of Neural Networks: Advanced Topics. (ed. I. Parberry), MIT Press, Cambridge, MA. 30 74. P. Myllymaki: Mapping Bayesian networks to stochastic neural net- works: a foundation for hybrid Bayesian-neural systems. Ph.D. The- sis, Report A-1995-1, Department of Computer Science, University of Helsinki, December 1995. 75. P. Myllymaki: Mapping Bayesian networks to Boltzmann machines. In: Proc. Applied Decision Technologies 1995, London, 1995, 269280. 76. P. Myllymaki: Using Bayesian networks for incorporating probabilistic a priori knowledge into Boltzmann machines. In: Proc. SOUTHCON '94, Orlando, 1994, 97102. 77. P. Myllymaki and P. Orponen: Programming the Harmonium. In: Proc. IJCNN-91, International Joint Conference on Neural Networks, Singapore, 1991, Vol. 1, 671677. 78. P. Myllymaki and H. Tirri: Bayesian case-based reasoning with neural networks. In: Proc. IEEE International Conference on Neural Net- works, San Francisco, 1993, 422427. 79. P. Myllymaki and H. Tirri: Massively parallel case-based reasoning with probabilistic similarity metrics. In: Topics in Case-Based Rea- soning (ed. S. Wess et al.), Lecture Notes in Arti|cial Intelligence 837, Springer-Verlag, 1994, 144154. 80. P. Orponen: Computational complexity of neural networks: A survey. Nordic Journal of Computing 1, 1 (1994), 94110. 81. P. Orponen: On the computational power of continuous time neural networks. Project NeuroCOLT Report NC-TR-95-051, Royal Holloway College, Dept. of Computer Science, Univ. of London, 1995. 82. P. Orponen: On the computational power of discrete Hop|eld nets. In: Proc. 20th International Colloq. on Automata, Languages, and Programming (ed. A. Lingas et al.), Lecture Notes in Computer Science 700, Springer-Verlag, Berlin, 1993, 215226. 83. P. Orponen: The computational power of discrete Hop|eld nets with hidden units. Neural Computation 8, 2 (1996), 403415. 84. P. Orponen: Computing with truly asynchronous threshold logic net- works. To appear in Theoretical Computer Science 178 (1997). 85. P. Orponen: Neural networks and complexity theory. In: Proc. Math- ematical Foundations of Computer Science 1992, 17th International 31 Symposium (ed. I. Havel et al.), Lecture Notes in Computer Science 629, Springer-Verlag, Berlin, 1992, 5061. 86. H. Tirri: Implementing expert system rule conditions by neural net- works. New Generation Computing 10, 1 (1991), 5571. Complexity Classes (F.1.3) 87. H. Buhrman and P. Orponen: Random strings make hard instances. In: Proc. 9th Ann. Conference on Structure in Complexity Theory (ed. U. Schoning et al.), IEEE, New York, 1994, 217222. Also to appear in J. Comput. System Sciences. 88. P. Orponen, K. Ko, U. Schoning, and O. Watanabe: Instance complex- ity. J. Assoc. Comput. Mach. 41, 1 (1994), 96121. Nonnumerical Algorithms and Problems (F.2.2) 89. Z. Galil and E. Ukkonen (eds.): Combinatorial Pattern Matching CPM 95, Proceedings of the Sixth Annual Symposium, Lecture Notes in Computer Science 937, Springer, 1995. 90. T. Eiter and H. Mannila: Theory distance and similarity: measures and computation. To appear in Acta Informatica. 91. T. Eiter, G. Gottlob, and H. Mannila: Expressive power and com- plexity of disjunctive datalog under the stable model semantics. In: Management and Processing of Complex Data Structures, Proc. Third Workshop on Information Systems and Arti|cial Intelligence (ed. K. van Luck and H. Marburger), Springer-Verlag 1994, p. 83103. 92. T. Eiter, G. Gottlob, and H. Mannila: Expressive power and complex- ity of disjunctive datalog. In: Proc. PODS '94, 1994 ACM SIGACT- SIGMOD-SIGACT Symposium on Principles of Database Theory, Min- neapolis, MN, 1994, 267278. 93. T. Eiter, P. Kilpelainen, and H. Mannila: Recognizing renamable gen- eralized propositional Horn formulas is NP-complete. Discrete Applied Mathematics 59 (1995) 2331. 94. V. Estivill-Castro, H. Mannila, and D. Wood: Right invariant metrics and measures of presortedness. Discrete Applied Mathematics 42, 1 (1993), 116. 32 95. N. Holsti and E. Sutinen: Approximate string matching using q-gram places. In: Proc. Seventh Finnish Symposium on Computer Science (ed. M. Penttonen), Report A-1994-1, Department of Computer Sci- ence, University of Joensuu, 1994, 2332. 96. P. Jokinen, E. Sutinen, and E. Ukkonen: Approximate string matching (in Finnish). Tietojenkasittelytiede 3 (1992), 3539. 97. P. Jokinen, J. Tarhio, and E. Ukkonen: A comparison of approximate string matching algorithms. To appear in Software Practice and Ex- perience. 98. P. Jokinen and E. Ukkonen: Two algorithms for approximate string matching in static texts. In: Proc. Mathematical Foundations of Com- puter Science 1991, 16th International Symposium (ed. A. Tarlecki), Lecture Notes in Computer Science 520, Springer-Verlag, Berlin, 1991, 240248. 99. R. Khardon, H. Mannila, and D. Roth: Reasoning with Examples: Propositional Formulae and Database Dependencies, Technical Report TR-15-95, Aiken Computation Lab., Harvard University, 1995. 100. J. Karkkainen: SuOEx cactus: a cross between suOEx tree and suOEx ar- ray. In: Proc. CPM '95, Combinatorial Pattern Matching, 6th Annual Symposium (ed. Z. Galil and E. Ukkonen), Lecture Notes in Computer Science 937, Springer, 1995, 191204. 101. J. Karkkainen and E. Sutinen: Lempel-Ziv index for q-grams. To ap- pear in Proc. ESA '96, Fourth Annual European Symposium on Algo- rithms, Springer, 1996. 102. J. Karkkainen and E. Ukkonen: Lempel-Ziv parsing and sublinear-size index structures for string matching. To appear in Proc. WSP '96, Third South American Workshop on String Processing. 103. J. Karkkainen and E. Ukkonen: Sparse suOEx trees. To appear in Proc. COCOON '96, 2nd Annual International Computing and Combina- torics Conference, Springer, 1996. 104. J. Karkkainen and E. Ukkonen: Two dimensional pattern matching by static sampling. In: Proc. Seventh Finnish Symposium on Computer Science (ed. M. Penttonen), Report A-1994-1, Department of Computer Science, University of Joensuu, 1994, 7990. 33 105. J. Karkkainen and E. Ukkonen: Two and higher dimensional pattern matching in optimal expected time. In: Proc. SODA '94, 5th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 1994, 715723. 106. P. Kilpelainen and H. Mannila: Ordered and unordered tree inclusion. SIAM Journal on Computing 24, 2 (1995), 340-356. 107. P. Kilpelainen and H. Mannila: Query primitives for tree-structured data. In: Proc. CPM '94, 5th Annual Symposium on Combinato- rial Pattern Matching (ed. M. Crochemore and D. Gus|eld), Springer- Verlag, 1994, 213225. 108. P. Kilpelainen and H. Mannila: Grammatical tree matching. In: Proc. CPM '92, 3rd Annual Symposium on Combinatorial Pattern Matching (ed. A. Apostolico et al.), Lecture Notes in Computer Science 644, Springer-Verlag, Berlin, 1992, 162174. 109. P. Kilpelainen and H. Mannila: The tree inclusion problem. In: Proc. TAPSOFT '91, International Joint Conference on Theory and Practice of Software Development, Brighton, Vol. 1: Colloquium on Trees in Algebra and Programming, CAAP '91 (ed. S. Abramsky et al.), Lecture Notes in Computer Science 493, Springer-Verlag, Berlin, 1991, 202214. 110. O. Lehtinen, E. Sutinen and J. Tarhio: Experiments on block index- ing. To appear in Proc. WSP '96, Third South American Workshop on String Processing. 111. M. Nykanen and E. Ukkonen: Finding lowest common ancestors in arbitrarily directed trees. Information Processing Letters 50 (1994), 307310. 112. E. Sutinen: On average-case behaviour of the q-gram method. In: Proc. Seventh Finnish Symposium on Computer Science (ed. M. Pent- tonen), Report A-1994-1, Department of Computer Science, University of Joensuu, 1994, 133138. 113. E. Sutinen and J. Tarhio: Filtration with q-samples in approximate string matching. To appear in Proc. CPM '96, Seventh Symposium on Combinatorial Pattern Matching. 114. E. Sutinen and J. Tarhio: On using q-gram locations in approximate string matching. In: Proc. ESA '95, Third Annual European Sym- posium on Algorithms (ed. P. Spirakis), Lecture Notes in Computer Science 979, Springer, Berlin, 1995, 327340. 34 115. J. Tarhio: A sublinear algorithm for two-dimensional string matching. To appear in Pattern Recognition Letters. 116. J. Tarhio and H. Peltola: String matching in the DNA alphabet. Report C-1995-61, Department of Computer Science, University of Helsinki, 1995. 117. J. Tarhio and E. Ukkonen: Approximate Boyer-Moore string matching. SIAM Journal on Computing 22, 2 (1993), 243260. 118. E. Ukkonen: Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science 92, 1 (1992), 191211. 119. E. Ukkonen: Approximate string-matching and the q-gram distance. In: Sequences II. Methods in Communication, Security, and Computer Science (ed. R. Capocelli et al.) Springer-Verlag, New York, NY, 1993, 300312. 120. E. Ukkonen: Approximate string-matching over suOEx trees. In: Proc. CPM '93, 4th Annual Symposium on Combinatorial Pattern Matching (ed. A. Apostolico et al.), Lecture Notes in Computer Science 684, Springer-Verlag, Berlin, 1993, 228242. 121. E. Ukkonen: Constructing suOEx trees on-line in linear time. In: In- formation Processing 92, Proc. IFIP 12th World Computer Congress, Vol. 1: Algorithms, software, architecture (ed. J. van Leeuwen), North- Holland, 1992, 484492. 122. E. Ukkonen: On-line construction of suOEx-trees. Algorithmica 14 (1995), 249260. 123. E. Ukkonen and D. Wood: Approximate string matching with suOEx automata. Algorithmica 10, 5 (1993), 353364. Specifying and Verifying and Reasoning about Programs (F.3.1) 124. J. Eloranta: Minimal transition systems with respect to divergence preserving behavioural equivalences. Ph.D. Thesis, Report A-1994-1, Department of Computer Science, University of Helsinki, 1994. 125. J. Eloranta: Minimizing the number of transitions with respect to ob- servation equivalence. BIT 31, 4 (1991), 576590. 126. J. Eloranta, M. Tienari, and A. Valmari: Essential transitions to bisim- ulation equivalences. To appear in Theoretical Computer Science. 35 127. R. Kaivola: Axiomatising extended computation tree logic. In: Proc. CAAP '96, Colloquium on Trees in Algebra and Programming, Lecture Notes in Computer Science 1059, Springer, Berlin, 1996, pp. 87101. 128. R. Kaivola: Axiomatising linear time mu-calculus. In: Proc. CON- CUR '95, Concurrency theory, 6th International Conference (ed. I. Lee and S. Smolka), Lecture Notes in Computer Science 962, Springer- Verlag, Berlin, 1995, 423437. 129. R. Kaivola: Fixpoints for Rabin tree automata make complementation easy, To appear in Proc. ICALP '96, Springer, 1996. 130. R. Kaivola: Compositional model checking for linear-time temporal logic. In: Proc. CAV '92, Computer Aided Veri|cation, Fourth Inter- national Workshop, Lecture Notes in Computer Science 663, Springer- Verlag, Berlin, 1993, 248259. 131. R. Kaivola: Equivalences, preorders and compositional veri|cation for linear time temporal logic and concurrent systems. Ph.D. The- sis, Report A-1996-1, Department of Computer Science, University of Helsinki, 1996. 132. R. Kaivola: On modal mu-calculus and B#chi tree automata. Infor- mation Processing Letters 54 (1995), 1722. 133. R. Kaivola: A simple decision method for the linear time mu-calculus Proc. International Workshop on Structures in Concurrency Theory (STRICT) (ed. J. Desel), Springer-Verlag, Berlin 1995, 190204. 134. R. Kaivola and A. Valmari: Using truth-preserving reductions to im- prove the clarity of Kripke-models. In: Proc. CONCUR '91, 2nd In- ternational Conference on Concurrency Theory (ed. J. Baeten et al.), Lecture Notes in Computer Science 527, Springer-Verlag, Berlin, 1991, 361375. 135. R. Kaivola and A. Valmari: The weakest compositional semantic equiv- alence preserving nexttime-less linear temporal logic. In: Proc. CON- CUR '92, 3rd International Conference on Concurrency Theory (ed. W. Cleaveland), Lecture Notes in Computer Science 630, Springer-Verlag, Berlin, 1992, 207221. 136. A. Valmari and M. Tienari: Compositional failure-based semantic mod- els for Basic LOTOS. Formal Aspects of Computing 7 (1995), 440468. 36 137. A. Valmari and M. Tienari: An improved failures equivalence for |nite- state systems with a reduction algorithm. In: Protocol Speci|cation, Testing, and Veri|cation, XI. Proc. IFIP WG 6.1 11th International Symposium (ed. B. Jonsson et al.), North-Holland, Amsterdam, 1991, 118. Grammars and Other Rewriting Systems (F.4.2) 138. R. op den Akker, B. Melichar, and J. Tarhio: Attribute evaluation and parsing. In: Attribute Grammars, Applications and Systems, Interna- tional Summer School SAGA (ed. H. Alblas et al.), Lecture Notes in Computer Science 545, Springer-Verlag, Berlin, 1991, 187214. 139. E. Ohlebusch and E. Ukkonen: On the equivalence problem for E- pattern languages. To appear in Proc. MFCS '96, Mathematical Foun- dations of Computer Science 1996. 140. J. Paakki: Attribute grammar paradigms a high-level methodology in language implementation. ACM Computing Surveys 27, 2 (1995), 196255. Mathematics of Computing Probability and Statistics (G.3) 141. P. Kontkanen, P. Myllymaki, and H. Tirri: Comparing Bayesian model class selection criteria by discrete |nite mixtures. To appear in Proc. of the ISIS (Information, Statistics and Induction in Science) Conference, Melbourne, Australia, 1996. 142. P. Kontkanen, P. Myllymaki, and H. Tirri: Constructing Bayesian |nite mixture models by the EM algorithm. Report C-1996-9, Department of Computer Science, University of Helsinki, 1996. 143. P. Kontkanen, P. Myllymaki, and H. Tirri: Predictive data mining with |nite mixtures. To appear in Proc. KDD-96, Second International Con- ference on Knowledge Discovery and Data Mining, Portland, Oregon, 1996. 144. P. Kontkanen, P. Myllymaki, and H. Tirri: Some experimental results with |nite mixture models. To appear in Proc. First European Con- ference on Highly Structured Stochastic Systems, Denmark, 1996. 145. J. Lahtinen, P. Myllymaki, T. Silander, and H. Tirri: Empirical com- parison of stochastic algorithms in a graph optimization problem. To appear in Proc. Second Nordic Workshop on Genetic Algorithms, Vaasa, Finland, 1996. 37 146. P. Myllymaki and H. Tirri: Constructing computationally eOEcient Bayesian models via unsupervised clustering. In: Probabilistic Rea- soning and Bayesian Belief Networks, (ed. A. Gammerman). Alfred Waller Publishers, Suoeolk 1995, 237248 Database Management Logical Design (H.2.1) 147. J. Kivinen and H. Mannila: Approximate dependency inference from relations. Theoretical Computer Science 149, 1 (1995), 129149. 148. J. Kivinen and H. Mannila: The power of sampling in knowledge dis- covery. In: Proc. 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM Press, New York, 1994, 7785. 149. M. Kantola, H. Mannila, K.-J. Raiha, and H. Siirtola: Discovering func- tional and inclusion dependencies in relational databases. International Journal on Intelligent Systems 7 (1992), 591607. 150. H. Mannila and K.-J. Raiha: Algorithms for inferring functional de- pendencies. Data & Knowledge Engineering 12 (1994), 8399. 151. H. Mannila and K.-J. Raiha: The Design of Relational Databases. Addison-Wesley, 1992, Reprinted 1994. 152. H. Mannila and K.-J. Raiha: On the complexity of inferring functional dependencies. Discrete Applied Mathematics 40, 2 (1992), 237243. Database Management Languages (H.2.3) 153. G. E. Blake, M. P. Consens, I. J. Davis, P. Kilpelainen, E. Kuikka, P.-#. Larson, T. Snider, and F.W. Tompa: Text/relational database management systems: Overview and proposed SQL extensions. Report CS-95-25, UW Centre for the New OED and Text Research, Depart- ment of Computer Science, University of Waterloo, 1995. 154. G. E. Blake, M. P. Consens, P. Kilpelainen, P.-#. Larson, T. Snider, and F. W. Tompa: Text/relational database management systems: Harmo- nizing SQL and SGML. In: Proc. ADB-94, Applications of Databases, First International Conference (ed. W. Litwin and T. Risch), Springer- Verlag, 1994, 267280. 155. G. Grahne and A. O. Mendelzon. Updates and subjunctive queries. Information and Computation 116 (1995), 241252. 38 156. G. Grahne, A. O. Mendelzon, and P. Z. Revesz. Knowledgebase trans- formations. To appear in Journal of Computer and System Sciences. 157. G. Grahne, M. Nykanen and E. Ukkonen: Reasoning about Strings in Databases. In: Proc. PODS '94, 13th ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, ACM Press, 1994, 292300. 158. P. Kilpelainen and H. Mannila: Retrieval from hierarchical texts by partial patterns. In: Proc. SIGIR '93, 16th Annual International ACM SIGIR Conference on Research and Development in Information Re- trieval (ed. R. Korfhage et al.), ACM Press, 1993, 214222. Database Management - Systems (H.2.4) 159. S. Abiteboul, P. C. Kanellakis, and G. Grahne: On the representation and querying of sets of possible worlds. Theoretical Computer Science 78, 1 (1991), 159187. 160. G. Grahne: The problem of Incomplete Information in Relational Databases. Lecture Notes in Computer Science 554. Springer-Verlag, Berlin, 1991. 161. G. Grahne, S. Sippu, and E. Soisalon-Soininen: EOEcient evaluation for a subset of recursive queries. Journal of Logic Programming 10, 3/4 (1991), 301332. 162. M. Holsheimer, M. Kersten, H. Mannila, and H. Toivonen: A perspec- tive on databases and data mining. In: Proc. KDD '95, First Interna- tional Conference on Knowledge Discovery and Data Mining, (ed. U. M. Fayyad and R. Uthurusamy), Montreal, Canada, AAAI Press, 1995, 150155. 163. H. Mannila: Data mining: machine learning, statistics, and databases. To appear in Scienti|c and Statistical Database Management 1996. 164. J. Puustjarvi: Distributed management of transactions in heteroge- neous distributed database systems. BIT 31, 3 (1991), 406420. 165. J. Puustjarvi, H. Tirri, and J. Veijalainen: Concurrency Control for Overlapping and Cooperative workAEows. To appear in IEEE TCOS Bulletin. 166. J. Puustjarvi, H. Tirri, and J. Veijalainen: Managing Overlapping Transactional WorkAEows. To appear in CAiSE 96. 39 167. S. Sippu and E. Soisalon-Soininen: Avoiding redundant computations in evaluating linear queries. In: Proc. ADC '94, 5th Australasian Database Conference (ed. R. Sacks-Davis), 1994, 124135. 168. H. Tirri, J. Srinivasan and B. Bhargava: Integrating data sources using federated objects. In Distributed Object Management (ed. M. T. #zsu et al.), Morgan Kaufmann, 1994, 315328. Heterogeneous Databases (H.2.5) 169. A.-P. Tuovinen and J. Paakki: Translating SQL for database reengi- neering.ACM SIGPLAN Notices 31, 2 (1996), 2126. Content Analysis and Indexing (H.3.1) 170. R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo: Fast discovery of association rules. In: Advances in knowledge discovery and data mining, (ed. U.M. Fayyad et al.), AAAI Press, Menlo Park, California, 1996, 307328. 171. H. Mannila and H. Toivonen: Discovering generalized episodes using minimal occurrences. To appear in Proc. KDD '96, Second Interna- tional Conference on Knowledge Discovery and Data Mining, Portland, Oregon, AAAI, 1996. 172. H. Mannila, H. Toivonen, and A. I. Verkamo: Discovering frequent episodes in sequences. In: Proc. KDD '95, First International Confer- ence on Knowledge Discovery and Data Mining (ed. U. M. Fayyad and R. Uthurusamy), AAAI Press, 1995, 210215. 173. H. Mannila, H. Toivonen, and A. I. Verkamo: EOEcient algorithms for discovering association rules. In: Proc. KDD '94, Knowledge Discovery in Databases, (ed. U. M. Fayyad and R. Uthurusamy), AAAI Press, 1994, 181192. 174. H. Toivonen: Sampling large databases for |nding frequent sets. To appear in Proc. VLDB '96, 22nd International Conference on Very Large Data Bases, Bombay, India, 1996. Information Search and Retrieval (H.3.3) 175. K. Hatonen, M. Klemettinen, H. Mannila, P. Ronkainen, and H. Toivo- nen: Knowledge discovery from telecommunication network alarm databases. In: Proc. ICDE 96, 12th International Conference on Data Engineering, (ed. S. Su), IEEE Computer Society Press, 1996, 115122. 40 176. M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A. I. Verkamo: Finding interesting rules from large sets of discovered as- sociation rules. In: Proc. CIKM '94, Third International Conference on Information and Knowledge Management, (ed. N.R. Adam et al.), ACM Press, 1994, 401407. 177. M. Klemettinen, H. Mannila, and H. Toivonen: Interactive exploration of discovered knowledge: A methodology for interaction, and usability studies. Report C-1996-3, Department of Computer Science, University of Helsinki, 1996. 178. H. Toivonen, M. Klemettinen, P. Ronkainen, K. Hatonen, and H. Man- nila: Pruning and grouping discovered association rules. In: Proc. ECML-95 Workshop on Statistics, Machine Learning, and Knowledge Discovery in Databases, (ed. Y. Kodratooe et al.), Heraklion, Greece, 1995, 4752. User Interfaces (H.5.2) 179. H. Erkio: Model-based evaluation methods (in Finnish). In: Graa|sen kayttoliittyman suunnittelu (toim. A. Kalimo), Suomen Atk- Kustannus Oy, Helsinki, 1996, 113123. 180. H. Erkio: The purpose of evaluations, their bene|ts, and methods (in Finnish). In: Graa|sen kayttoliittyman suunnittelu (toim. A. Kalimo), Suomen Atk-Kustannus Oy, Helsinki, 1996, 8388. Group and Organization Interfaces (H.5.3) 181. S. Eherer, H. Erkio, H. Lewe, B. Ludwig, S. Myrseth, R. Popping, X. Tong: Information technology support for group knowledge devel- opment. Working document of COST 14 Co-Tech working group 1, 1992. Automatic Programming (I.2.2) 182. J. Paakki, T. Gyim#thy, and T. Horv#th: Eoeective algorithmic debug- ging for inductive logic programming. In: Proc. ILP-94, 4th Inter- national Workshop on Inductive Logic Programming (ed. S. Wrobel), GMD-Studien Nr. 237, Gesellschaft f#r Mathematik und Datenverar- beitung MbH, 1994, 175194. 41 Knowledge Representation Formalisms and Methods (I.2.4) 183. G. Grahne: Updates and counterfactuals. In: Proc. KR '91, Prin- ciples of Knowledge Representation and Reasoning, 2nd International Conference (ed. J. Allen et al.), Morgan Kaufmann, 1991, 269276. 184. G. Grahne, A. O. Mendelzon, and R. Reiter: On the semantics of belief revision systems. In: Theoretical Aspects of Reasoning About Knowledge, Proc. 4th Conference (TARK 1992) (ed. Y. Moses et al.), Morgan Kaufmann, San Mateo, CA, 1992, 132142. 185. G. Grahne, A. O. Mendelzon and R. Reiter. On the semantics of belief revision systems. Technical Reports on Knowledge Representation and Reasoning, KRR-TR-95-1. Department of Computer Science, Univer- sity of Toronto, 1995. Preliminary version also in Proc. 4th Conference on Theoretical Aspects of Reasoning about Knowledge. Asilomar, Ca. 1992, 132142. 186. G. Grahne. Updates and counterfactuals. To appear in Journal of Logic and Computation. 187. G. Grahne, A. O. Mendelzon, and P. Z. Revesz: Knowledgebase trans- formations. In: Proc. 11th ACM SIGACT-SIGMOD-SIGART Sympo- sium on Principles of Database Systems, ACM, San Diego, CA, 1992, 246260. 188. P. Flor#en, P. Myllymaki, P. Orponen, and H. Tirri: NEULA a hybrid neural-symbolic expert system shell. Tietojenkasittelytiede 3 (1992), 1118. 189. P. Myllymaki, P. Orponen, T. Silander: Integrating symbolic reason- ing with neurally represented background knowledge. In: Proc. of the Finnish AI Conference, Vol. 2., Finnish AI Society, Helsinki, 1992, 231240. 190. H. Toivonen: High level integration of rule-based and procedural pro- gramming through uni|cation of frames and classes. In: Proc. 5th Florida Arti|cial Intelligence Research Symposium (ed. M. Fishman), Florida AI Research Society, St. Petersburg, Florida, 1992, 129133. Learning (I.2.6) 191. H. Ahonen, Generating grammars for structured documents using grammatical inference methods. Ph.Lic. Thesis C-1994-65, Depart- ment of Computer Science, University of Helsinki, June 1994. 42 192. H. Ahonen, H. Mannila, and E. Nikunen: Forming grammars for struc- tured documents. In: Proc. AAAI-93 Workshop on Knowledge Discov- ery in Databases (ed. G. Piatetsky-Shapiro), AAAI, 1993, 314325. 193. H. Ahonen, H. Mannila, and E. Nikunen, Forming grammars for struc- tured documents: an application of grammatical interference. In: Proc. Second International Colloquium on Grammatical Inference and Appli- cations, (eds. R. S. Carrasco and J. Oncina), Lecture Notes in Arti|cial Intelligence 862, Springer-Verlag, 1994, 153167. 194. H. Ahonen, H. Mannila, and E. Nikunen: Generating grammars for SGML tagged texts lacking DTD. In: Proc. PODP '94, Workshop on Principles of Document Processing (eds. M. Murata and H. Gallaire), Darmstadt, 1994. To appear also in Mathematical and Computer Mod- elling. 195. A. Brazma, I. Jonassen, E. Ukkonen, and J. Vilo: Discovering patterns and subfamilies in biosequences. To appear in Proc. ISMB '96, Fourth International Conference on Intelligent Systems for Molecular Biology. 196. A. Brazma, E. Ukkonen, and J. Vilo: Finding a good collection of patterns covering a set of sequences. Report C-1995-60, Department of Computer Science, University of Helsinki, 1995. 197. T. Elomaa: Extending the learnability of decision trees. In: Proc. TAI '91, 3rd International Conference on Tools for Arti|cial Intelligence, San Jose, CA, 1991, 504505. 198. T. Elomaa: In defense of C4.5: notes on learning one-level decision trees. In: Machine Learning: Proc. Eleventh International Conference (ed. W. Cohen and H. Hirsh), Morgan Kaufmann, 1994, 6269. 199. T. Elomaa: Tools and techniques for decision tree learning. Ph.D. The- sis, Report A-1996-2, University of Helsinki, Department of Computer Science, 1996. 200. T. Elomaa, N. Holsti and I. Hyvarinen: TELA: a platform for ex- perimenting with attribute-based learning programs. In: Proc. Fifth Scandinavian Conference on Arti|cial Intelligence (ed. A. Aamodt and J. Komorowski), Frontiers in Arti|cial Intelligence and Applications 28, IOS Press & Ohmsha Ltd., 1995, 391395. 201. T. Elomaa and J. Rousu: Finding optimal multi-splits for numerical attributes in decision tree learning. NeuroCOLT Technical Report NC- TR-96-041, Department of Computer Science, Royal Holloway, Univer- sity of London, 1996. 43 202. T. Elomaa and E. Ukkonen: A geometric approach to feature selection. In: Machine Learning: Proc. ECML-94, Seventh European Conference on Machine Learning (ed. F. Bergadano and L. De Raedt), Lecture Notes in Arti|cial Intelligence 784, Springer-Verlag, 1994, 351354. 203. D. Haussler, J. Kivinen, and M. K. Warmuth: Tight worst-case loss bounds for predicting with expert advice. In: Proc. EuroCOLT '95, Computational Learning Theory. Second European Conference (ed. P. Vit#nyi), Lecture Notes in Arti|cial Intelligence 904, Springer, Berlin, 1995, 6983. 204. D. Haussler, J. Kivinen, and M. K. Warmuth: Tight worst-case loss bounds for predicting with expert advice. Technical Report UCSC- CRL-94-36, University of California, Santa Cruz, Santa Cruz, Califor- nia, 1994. 205. D. P. Helmbold, J. Kivinen, and M. K. Warmuth: Worst-case loss bounds for single neurons. To appear inAdvances in Neural Informa- tion Processing Systems 8 (ed. D. S. Touretzky et al.), MIT Press, Cambridge, MA, 1996. 206. M. Jaeger, H. Mannila, and E. Weydert: Data mining as selective theory extraction in probabilistic logic. To appear in SIGMOD '96 Data Mining Workshop 1996. 207. P. Kilpelainen, H. Mannila, and E. Ukkonen: MDL learning of unions of simple pattern languages from positive examples. Proc. EuroCOLT '95, Computational Learning Theory. Second European Conference (ed. P. Vit#nyi), Lecture Notes in Arti|cial Intelligence 904, Springer, 1995, 252260. 208. J. Kivinen: Learning reliably and with one-sided error. Mathematical Systems Theory 28, 2 (1995), 141172. 209. J. Kivinen, H. Mannila, and E. Ukkonen: Learning hierarchical rule sets. In: Proc. 5th ACM Workshop on Computational Learning Theory, 1992, 3744. 210. J. Kivinen, H. Mannila, and E. Ukkonen: Learning rules with local exceptions. In: Proc. EuroCOLT '93, Computational Learning Theory (ed. J. Shawe-Taylor and M. Anthony), Clarendon Press, Oxford, 1994, 3546. 44 211. J. Kivinen, H. Mannila, E. Ukkonen, and J. Vilo: An algorithm for learning hierarchical classi|ers. In: Proc. ECML '94, Machine Learning (ed. F. Bergadano and L. De Raed), Springer, Berlin, 1994, 375378. 212. J. Kivinen and M. K. Warmuth: Additive versus exponentiated gradi- ent updates for linear prediction. In: Proc. 27th Annual ACM Sympo- sium on Theory of Computing, ACM Press, New York, 1995, 209218. 213. J. Kivinen and M. K. Warmuth: Exponentiated gradient versus gradi- ent descent for linear predictors. Technical Report UCSC-CRL-94-16, University of California, Santa Cruz, Santa Cruz, California, 1994. 214. J. Kivinen and M. K. Warmuth: The Perceptron algorithm versus Win- now: Linear versus logarithmic mistake bounds when few input vari- ables are relevant. In: Proc. COLT '95, Eighth Annual Conference on Computational Learning Theory, ACM Press, New York, 1995, 289 296. 215. J. Kivinen and M. K. Warmuth: Using experts for predicting continu- ous outcomes. In: Proc. EuroCOLT '93, Computational Learning The- ory (ed. J. Shawe-Taylor and M. Anthony), Clarendon Press, Oxford, 1994, 109120. 216. H. Mannila: Data mining and machine learning. To appear in Inter- national Conference on Machine Learning 1996. 217. H. Mannila and H. Toivonen: Multiple uses of frequent sets and con- densed representations. To appear in Proc. KDD '96, Second Interna- tional Conference on Knowledge Discovery and Data Mining, Portland, Oregon, AAAI, 1996. 218. P. Myllymaki and H. Tirri: Bayesian case-based reasoning with neural networks. In: Proc. 1993 IEEE International Conference on Neural Networks, San Francisco, CA, 1993. Vol. 1, 422427. 219. P. Myllymaki and H. Tirri: Learning Bayesian prototype trees by sim- ulated annealing. In: Proc. Conference on Arti|cial Intelligence Re- search in Finland (ed. C. Carlsson, T. Jarvi and T. Reponen). Finnish Arti|cial Intelligence Society, Helsinki, 1994, 3237. 220. P. Myllymaki and H. Tirri: Learning in neural networks with Bayesian prototypes. In: Proc. SOUTHCON '94, Orlando, 1994, 6064. 221. I. Sillitoe and T. Elomaa: Learning decision trees for mapping the local environment in mobile robot navigation. In: Proc. MLC-COLT Workshop on Robot Learning, 1994, 119125. 45 222. H. Tirri: Concept randomness and neural networks. In: Proc. ICANN- 91, 1991 International Conference on Arti|cial Neural Networks (ed. T. Kohonen et al.), North-Holland, Amsterdam, 1991, Vol. 2, 13671370. 223. H. Tirri: Learning with instance based encodings. In Computational Learning Theory and Natural Learning Systems II: Constraints and Prospects (ed. Hanson et al.), The MIT Press, 1994, 205214. 224. H. Tirri, P. Kontkanen, and P. Myllymaki: Probabilistic Instance- Based Learning. To appear in Machine Learning: Proc. Thirteenth International Conference (ed. L. Saitta). Morgan Kaufmann Publish- ers, San Francisco, CA, 1996. 225. H. Tirri and P. Myllymaki: MDL learning of probabilistic neural net- works for discrete problem domains. In: Proc. IEEE World Congress on Computational Intelligence, Orlando, 1994, 14931497. Problem Solving, Control Methods, and Search (I.2.8) 226. R. Greiner and P. Orponen: Probably approximately optimal satis|cing strategies. Arti|cial Intelligence 83.1 (1996), 124. 227. H. Mannila and H. Toivonen: On an algorithm for |nding all interest- ing sentences. In: Proc EMCSR '96, Thirteenth European Meeting on Cybernetics and Systems Research, Vienna, Austria, Austrian Society for Cybernetic Studies, 1996, 973978. Image Processing Enchancement (I.4.3) 228. J. Tarhio, K. Lemstrom, and T. Takala: Color dithering with n-best al- gorithm. Proc. WSCG '96, Fourth International Conference in Central Europe on Computer Graphics and Visualization 96 (ed. N. Thalmann and V. Skala), University of West Bohemia, Department of Computer Science, 1996, 162170. Pattern Recognition Models (I.5.1) 229. X. M. Song, H. Tirri, O. Aaltonen and A. Hase: A discrete radial ba- sis function network for empirical modeling of soil extraction process. In: Proc. ECANN '95, International Conference on Engineering Ap- plications of Neural Networks (ed. A. Bulsari and S. Kallio), Finnish Arti|cial Intelligence Society, 1995, 1720. 46 230. H. Tirri and S. Mallenius: Optimizing the hard address distribution for sparse distributed memories. In: Proc. ICNN '95, IEEE Conference on Neural Networks, 1995, 19661970. 231. H. Tirri: Replacing the pattern matcher of an expert system with a neural network. In: Chapter 3: Intelligent Hybrid Systems (eds. S. Goonatilake and S. Khebbal), John Wiley & Sons, 1995, 4762. Pattern Recognition Clustering (I.5.3) 232. O. Heinonen and H. Mannila: Attribute-oriented induction and concep- tual clustering. Report C-1996-2, University of Helsinki, Department of Computer Science, 1996. Simulation and Modeling General (I.6.0) 233. T. Kerola: Qsolver a modular environment for solving queueing net- work models. In: Computer Performance Evaluation: Modelling Tech- niques and Tools, Proc. 5th International Conference (ed. G. Balbo), Elsevier, 1992, 427438. Model Validation and Analysis (I.6.4) 234. K. Raatikainen: Modeling service-time distributions for queueing net- work simulation. Communications in Statistics. B, Simulation and Computation 20, 1 (1991), 375390. 235. K. Raatikainen: Modeling service distributions in queueing network simulation. Simulation 59, 2 (1992), 116126. Simulation Output Analysis (I.6.6) 236. K. Raatikainen: A sequential procedure for simultaneous estimation of several means. ACM Transactions on Modeling and Computer Simu- lation 3, 2 (1993), 108133. 237. K. Raatikainen: Accuracy of estimates for dynamic properties of queue- ing systems in interactive simulation. International Journal in Com- puter Simulation 5, 3 (1995), 305326. 238. K. Raatikainen: Controlling the precisions of estimates in interactive simulations. Annals of Operations Research 53 (1994), 485505. 239. K. Raatikainen: Run length control using parallel spectral methods. In: Proc. 1992 Winter Simulation Conference IEEE, 1992, 594602. 47 240. K. Raatikainen: Simulation-based estimation of proportions. Manage- ment Science 41, 7 (1995), 12021223. Simulation Support Systems (I.6.7) 241. E. Arjas, H. Mannila, M. Salmenkivi, R. Suramo, and H. Toivo- nen: BASS: Bayesian analyzer of event sequences. To appear in Proc. COMPSTAT '96, XII Symposium on Computational Statistics, Barcelona, Spain, 1996. Life and Medical Sciences (J.3) 242. M. Huttunen, E. Ukkonen, and B. Vehvilainen: Neural networks as a part of watershed-model in ice-reduction of discharge observations. To appear in Nordic Hydrological Conference 1996. 243. J. Rinne, H. Lokki, and P. Saurola: Extensive parameterisation of sur- vival models for recovery data analysis. In: Marked Individuals in the Study of Bird Population (ed. J. Lebreton et al.), Birkhauser, 1993, 6575. History of Computing (K.2) 244. M. Tienari (ed.): The First Years of Computer Technology in Finland (in Finnish). Suomen atk-kustannus Oy, Espoo, 1993. Computer Uses in Education (K.3.1) 245. S.-P. Lahtinen, E. Sutinen, A.-P. Tuovinen, and J. Tarhio: Learning and problem solving assisted with animated objects. In Abstracts of the European Conference on Educational Research in 1995 (ECER '95), p. 153. University of Bath, 1995. 246. M. Makela: Information technology a tool and an obstacle in the future education. To appear in Proc. Second IFIP Working Conference on Information Techology in Educational Management, Hong Kong, 1996. 247. M. Makela: Experiences in computer uses in education (in Finnish). Peda-forum, Kevat 1/1996, 35. 248. E. Sutinen: Computers and change in mission. International Review of Mission (World Council of Churches) LXXXIII, 331 (1994), 585594. 48 249. E. Sutinen: From enthusiasm and doubt to searching for new pupils creating educational software (in Finnish). Opetushallituksen julkais- usarjat, Kehittamissarja 2/1992. 250. M. Parkkinen, P. Parkkinen, and E. Sutinen: On the feasibility of multimedia in a Tanzanian context. To appear in Matematiikan ja luonnontieteiden opetuksen tutkimuspaivien esitykset (ed. V. Meisalo), Report Tutkimuksia 162, Department of Teacher Education, University of Helsinki, 1996. Computer and Information Science Education (K.3.2) 251. S.-P. Lahtinen, T. Lamminjoki, V. Ollikainen, E. Sutinen, J. Tarhio, and A.-P. Tuovinen: Animation technology as a method of learning to write algorithms. To appear in Matematiikan ja luonnontieteiden opetuksen tutkimuspaivien esitykset (ed. V. Meisalo), Report Tutkimuk- sia 162, Department of Teacher Education, University of Helsinki, 1996. 252. S.-P. Lahtinen, T. Lamminjoki, E. Sutinen, J. Tarhio, and A.-P. Tuovi- nen: Towards automated animation of algorithms. In: Proc. WSCG '96, Fourth International Conference in Central Europe on Computer Graphics and Visualization 96 (ed. N. Thalmann and V. Skala), Depart- ment of Computer Science, University of West Bohemia, 1996, 150161. 253. S.-P. Lahtinen, V. Meisalo, E. Sutinen, and J. Tarhio: Uni|ed chal- lenges of algorithm design and problem solving. To appear in Mate- matiikan ja luonnontieteiden opetuksen tutkimuspaivien esitykset (ed. V. Meisalo), Report Tutkimuksia 162, Department of Teacher Educa- tion, University of Helsinki, 1996. 254. S.-P. Lahtinen, A. Porttikivi, E. Sutinen, and A.-P. Tuovinen: Algo- rithm animation as a method of learning. In: Uudet menetelmat ja mahdollisuudet matemaattis-luonnontieteellisten aineiden oppimisessa (ed. J. Enkenberg and K. Sormunen), University of Joensuu, 1994, 65 70. 255. E. Sutinen and J. Tarhio: String matching animator SALSA. In: Proc. Third Symposium on Programming Languages and Software Tools (ed. M. Tombak), University of Tartu, 1993, 120129. 49 Chapter 3 Faculty The members of the faculty are introduced by giving their position, E-mail address, research interests, a sample of recent publications, and recent aca- demic activities. The addresses of the personal WWW pages can be found in http://www.cs.helsinki.|/. All E-mail addresses are given in the Internet format. In the do- main "cs.helsinki.|" there is a general address format containing the |rst and the last name of a person separated with a period, for example hannu.erkio@cs.helsinki.| for Hannu Erkio (note the necessary translitera- tion #!e, a!a and o!o). The publication numbers refer to the classi|ed listing of publications in Section 2.3. AHONEN, Helena Ph.Lic., Research assistant - E-mail: helena.ahonen@cs.helsinki.| - Interests: document management, data mining, machine learning - Publications: [191194] ALANKO, Timo Ph.D., Assistant professor - E-mail: timo.alanko@cs.helsinki.| - Interests: distributed operating systems, mobile systems, performance analysis - Publications: [6, 28, 33, 66] ELOMAA, Tapio Ph.D., Research assistant - E-mail: tapio.elomaa@cs.helsinki.| - Interests: machine learning, robotics, arti|cial intelligence, algorithms 50 - Publications: [197202, 221] ELORANTA, Jaana Ph.D., Research assistant - E-mail: jaana.eloranta@cs.helsinki.| - Interests: speci|cation languages, modelling concurrency - Publications: [124126] ERKIo, Hannu Ph.D., Docent, Assistant professor - E-mail: hannu.erkio@cs.helsinki.| - Interests: user interfaces, computer-supported cooperative work - Publications: [179181] FLOR#EN, Patrik Ph.D., Docent, Secretary general (the Academy of Finland) - E-mail: patrik.AEoreen@aka.| - Interests: genetic algorithms, neural networks, computability theory GRAHNE, Gosta Ph.D., Docent, Assistant professor - E-mail: gosta.grahne@cs.helsinki.| - Interests: arti|cial intelligence, belief revision, data and knowledge bases, knowledge representation, sequence databases - Publications: [155157, 159161, 183187] - Memberships of program committees: Sixth Conference of Arti|cial Intelli- gence Research in Finland (STeP-94), Turku, Finland, 1994 - Other activities: Member of the Ph.D. examination committee for Mary- Anne Williams, University of Sydney, Australia, 1994 GRANo, Kari M.Sc., Research assistant - E-mail: kari.grano@cs.helsinki.| - Interests: distributed computing, programming languages, computer graphics - Publications: [3, 4, 1517, 35, 38, 39, 5052] HaKKINEN, Auvo M.Sc., Assistant professor (acting) - E-mail: auvo.hakkinen@cs.helsinki.| 51 - Interests: computer systems organization, operating systems, software en- gineering, JaRVINEN, Pertti Ph.D., Docent, Professor (University of Tampere) - E-mail: pj@cs.uta.| - Interests: information systems, research methodologies, human-computer interaction, social eoeects of computing systems KAIVOLA, Roope Ph.D., Assistant professor - E-mail: roope.kaivola@cs.helsinki.| - Interests: concurrency, temporal logic, process algebra, in|nitary automata - Publications: [127135] KaRKKaINEN, Juha M.Sc., Research assistant - E-mail: juha.karkkainen@cs.helsinki.| - Interests: string algorithms, algorithms and data structures - Publications: [100105] KARVI, Timo Ph.Lic., Assistant professor (acting) - E-mail: timo.karvi@cs.helsinki.| - Interests: formal speci|cation, process algebras, distributed computing KEROLA, Teemu Ph.D. (Purdue), Assistant professor - E-mail: teemu.kerola@cs.helsinki.| - Interests: performance evaluation, data visualization, operating systems - Publications: [233] - Memberships of program committees: Seventh International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, Vienna, Austria, 1994 KILPELaINEN, Pekka Ph.D., Assistant professor - E-mail: pekka.kilpelainen@cs.helsinki.| - Interests: document management, pattern matching - Publications: [93, 106109, 153, 154, 158, 207] 52 KIVINEN, Jyrki Ph.D., Assistant professor - E-mail: jyrki.kivinen@cs.helsinki.| - Interests: machine learning, neural networks - Publications: [147, 148, 203205, 208215] KLEMETTINEN, Mika M.Sc., Research assistant - E-mail: mika.klemettinen@cs.helsinki.| - Interests: data mining, user interfaces, usability - Publications: [18, 19, 175178] KOJO, Markku M.Sc., Assistant professor (acting) - E-mail: markku.kojo@cs.helsinki.| - Interests: mobile computing, distributed systems, data communication - Publications: [5, 6, 28, 29, 33] KOSKIMIES, Kai Ph.D., Docent, Professor (University of Tampere) - E-mail: koskimie@cs.uta.| - Interests: programming languages and environments, software engineering, object-oriented systems KUJALA, Teija M.Sc., Amanuensis - E-mail: teija.kujala@cs.helsinki.| - Interests: computer aided software engineering, database design KUTVONEN, Lea M.Sc., Amanuensis, Researcher - E-mail: lea.kutvonen@cs.helsinki.| - Interests: open distributed processing, heterogeneous system architectures - Publications: [2127] LAINE, Harri Ph.Lic., Assistant professor - E-mail: harri.laine@cs.helsinki.| - Interests: computer aided software engineering (CASE), database design 53 LIND#N, Greger Ph.Lic., Research assistant - E-mail: greger.linden@cs.helsinki.| - Interests: document management, database management - Publications: [4042, 44, 45, 5759, 64, 65] LINNAINMAA, Seppo Ph.D., Docent, Research professor (VTT Infor- mation Technology) - E-mail: seppo.linnainmaa@vtt.| - Interests: knowledge based systems, object oriented software, intelligent operations management LOKKI, Heikki Ph.Lic., Assistant professor - E-mail: heikki.lokki@cs.helsinki.| - Interests: numerical analysis, analytical methods for ringing recovery - Publications: [1, 243] MaKELa, Matti Dr. Techn., Associate professor - E-mail: matti.makela@cs.helsinki.| - Interests: numerical methods, mathematical software, computers in edu- cation, computer graphics, scienti|c visualization - Publications: [246, 247] - Activities: International coordinator of ACM SIGNUM Newsletter MANNILA, Heikki Ph.D., Professor - E-mail: heikki.mannila@cs.helsinki.| - Interests: data mining, databases, machine learning, algorithms - Publications: [18, 19, 37, 9094, 99, 106109, 147152, 158, 162, 163, 170 173, 175178, 192194, 206, 207, 209211, 216, 217, 227, 232, 241] - Memberships of program committees: International Conference on Database Theory (ICDT '95) ffi European Workshop on Statistics, Machine Learn- ing, and Knowledge Discovery, 1995 ffi First International Conference on Knowledge Discovery and Data Mining, 1995 ffi Thirteenth European Meet- ing on Cybernetics and Systems Research, 1996 ffi Fifteenth ACM SIGACT- SIGART-SIGMOD Symposium on Principles of Database and Knowledge- base Systems (PODS '96) ffi 22nd International Conference on Very Large 54 Data Bases (VLDB '96) ffi Second International Conference on Knowledge Discovery and Data Mining, 1996 ffi ACM SIGMOD Workshop on Knowl- edge Discovery and Data Mining, 1996 ffi Third International Conference on Knowledge Discovery and Data Mining (co-chairman) 1997 - Other activities: Journal of Data Mining and Knowledge Discovery, Editor- in-Chief, from 1996 ffi External evaluator for professorships at Hebrew Uni- versity (Jerusalem) and Technical University of Vienna ffi External reviewer for TFR (Sweden) from 1993 ffi OOEcial opponent for Ph.D. defense of Viggo Kann, KTH, 1994 ffi Chairman of the Finnish Society for Computer Science 199495 MARTTINEN, Liisa M.Sc., Assistant professor (acting) - E-mail: liisa.marttinen@cs.helsinki.| - Interests: computer communication, computer networks, network manage- ment, open distributed processing MYLLYMaKI, Petri Ph.D., Research scientist - E-mail: petri.myllymaki@cs.helsinki.| - Interests: probabilistic modeling, uncertain reasoning, machine learning, neural computing - Publications: [7479, 141146, 188, 189, 218220, 224, 225] NURMI, Otto Dr.rer.pol., Assistant professor - E-mail: otto.nurmi@cs.helsinki.| - Interests: databases, algorithms, data structures, computational geometry - Publications: [68, 71] NYKaNEN, Matti M.Sc., Research assistant - E-mail: matti.nykanen@cs.helsinki.| - Interests: query languages for sequence databases, bioinformatics, theory of computation - Publications: [111, 157] ORPONEN, Pekka Ph.D., Associate professor - E-mail: pekka.orponen@cs.helsinki.| - Interests: computational complexity, neural networks, genetic algorithms, 55 cellular automata - Publications: [72, 73, 77, 8085, 87, 88, 188, 189, 226] - Memberships of program committees: 21st Internat. Colloquium on Au- tomata, Languages and Programming, Jerusalem, 1994 ffi Fifth Scandinavian Workshop on Algorithm Theory, Reykjav# k, 1996 - Other activities: OOEcial opponent in the thesis defense of Magnus Stensmo, Kungliga Tekniska Hogskolan, Stockholm, 1995 PAAKKI, Jukka Ph.D., Associate professor - E-mail: jukka.paakki@cs.helsinki.| - Interests: software engineering, programming languages: design and im- plementation, communications protocol engineering - Publications: [3, 4, 1517, 38, 4656, 6062, 140, 169, 182] - Memberships of program committees: Sixth International Symposium on Programming Language Implementation and Logic Programming (PLILP '94), Madrid, Spain, 1994 ffi Sixth Nordic Workshop on Programming Envi- ronment Research (NWPER '94), Lund, Sweden, 1994 ffi Second International Workshop on Automated and Algorithmic Debugging (AADEBUG '95), St. Malo, France, 1995 ffi Fourth Symposium on Programming Languages and Software Tools, Vis# grad, Hungary, 1995 ffi Seventh Nordic Workshop on Pro- gramming Environment Research (NWPER '96), Aalborg, Denmark, 1996 - Other activities: Editor of Tietojenkasittelytiede (Finnish Journal of Com- puter Science) ffi External reviewer for the Academy of Finland from 1995 PELTOLA, Eero Ph.D., Docent, Chairman of the Board (Mintax Ltd, Helsinki, Finland) - E-mail: eero.peltola@mintax.pp.| - Interests: software business management, information processing manage- ment, information systems, database management, analysis and design of algorithms, searching and sorting PUUSTJaRVI, Juha Ph.Lic., Research assistant - E-mail: juha.puustjarvi@cs.helsinki.| - Interests: concurrency control, multidatabases, workAEows - Publications: [164166] 56 RAATIKAINEN, Kimmo Ph.D., Docent, Assistant professor - E-mail: kimmo.raatikainen@cs.helsinki.| - Interests: distributed systems, mobile computing, telecommunications, in- telligent networks, performance evaluation, real-time databases - Publications: [510, 12, 13, 2830, 33, 34, 67, 234240] - Memberships of program committees: IFIP 1995 Working Conference on Intelligent Networks ffi IFIP 1996 Conference on Intelligent Networks - Other activities: Member of IFIP TC6 Special Interest Group of Intelligent Networks ffi Editor of Tietojenkasittelytiede (Finnish Journal of Computer Science) RaIHa, Kari-Jouko Ph.D., Docent, Professor (University of Tampere) - E-mail: kjr@cs.uta.| - Interests: human-computer interaction, databases RONKAINEN, Pirjo M.Sc., Research assistant - E-mail: pirjo.ronkainen@cs.helsinki.| - Interests: data mining, databases, knowledge bases, hypertext - Publications: [18, 19, 175, 176, 178] SIPPU, Seppo Ph.D., Associate professor - E-mail: seppo.sippu@cs.helsinki.| - Interests: logic databases, query processing, parsing - Publications: [161, 167] SUTINEN, Erkki M.Sc., Research assistant - E-mail: erkki.sutinen@cs.helsinki.| - Interests: algorithms and data structures, string algorithms, algorithm animation, computer aided learning - Publications: [95, 96, 101, 110, 112114, 245, 248255] TAINA, Juha M.Sc. Research assistant - E-mail: juha.taina@cs.helsinki.| - Interests: intelligent networks, real-time databases, object orientation, 57 main memory databases - Publications: [914, 31, 32] TAKALA, Tapio Dr.Tech., Docent, Professor (Helsinki University of Technology) - E-mail: tapio.takala@hut.| - Interests: computer graphics, animation, multimedia, virtual reality, digital sound, user interfaces, CAD, modeling, design theory TARHIO, Jorma Ph.D., Docent, Assistant professor - E-mail: jorma.tarhio@cs.helsinki.| - Interests: string algorithms, animation, computational biology, data com- pression, attribute grammars - Publications: [69, 70, 97, 110, 113117, 138, 228, 245, 251253, 255] TIENARI, Martti Ph.D., Professor, Chairman of the Department - E-mail: martti.tienari@cs.helsinki.| - Interests: modeling concurrency, computer networks and distributed sys- tems, programming languages and compilers, management of computing - Publications: [2, 63, 126, 136, 137, 244] - Memberships of program committees: PSTV '95 The 15th International Symposium on Protocol Speci|cation, Testing and Veri|cation, Warsaw, Poland, June 1995 - Other activities: Activities in IFIP (International Federation of Informa- tion Processing): General Assembly since 1987, IFIP Trustee 198995, Cog- nizant OOEcer of TC2 (Software: Theory and Practice) and TC12 (Arti|cial Intelligence), Member of Publication Committee, Chairman of the Activity Management Board 199296, Chairman of the Technical Assembly 1996 ffi Ex- ternal reviewer of computer science professorships at the University of Oslo, University of Linkoping, Technical University of Stockholm and Columbia University, New York, 199495 ffi External reviewer of docent competence at the University of Linkoping 1995 ffi Member of the Finnish Academy of Science and Letters ffi Member of the Finnish Academy of Technical Sciences TIRRI, Henry M.Sc., Research scientist - E-mail: henry.tirri@cs.helsinki.| 58 - Interests: computational intelligence (neural networks, evolutionary al- gorithms, arti|cial life), probabilistic modeling and reasoning, transaction processing, foundations of machine learning - Publications: [41, 5759, 64, 65, 78, 79, 86, 141146, 165, 166, 168, 188, 218220, 222225, 229231] - Memberships of program committees: Applications of Databases (ADP-94), Vadstena, Sweden, 1994 ffi Second European Conference on Case-Based Rea- soning (EWCBR '94), Chambery, France, 1994 ffi Research Issues in Data En- gineering '95 (RIDE '95) ffi Scandinavian Conference on Arti|cial Intelligence (SCAI '95) ffi International Conference on Case-Based Reasoning (ICCBR- 95) ffi 3rd European Conference on Case-Based Reasoning (EWCBR-96) - Other activities: Member of the Editorial Board: Computer Journal (Ox- ford University Press) ffi Associate node coordinator: European Community ESPRIT III Network of Excellence in Neural Networks (NEURONET) ffi Member of 1993 European Community Cost 14 Project: Computer Sup- ported Cooperative Work, WG 7: Communication and Distributed System Support for CSCW TOIVONEN, Hannu M.Sc., Research assistant - E-mail: hannu.toivonen@cs.helsinki.| - Interests: data mining, information systems, machine learning, arti|cial intelligence - Publications: [1820, 162, 170178, 190, 217, 227, 241] UKKONEN, Esko Ph.D., Professor - E-mail: esko.ukkonen@cs.helsinki.| - Interests: algorithms and data structures, string algorithms, machine learn- ing, computational biology - Publications: [71, 89, 9698, 102105, 111, 117123, 139, 157, 195, 196, 202, 207, 209211, 242] - Memberships of program committees: Fifth Annual Symposium on Combi- natorial Pattern Matching (CPM '94), Asilomar, California, U.S.A., 1994 ffi Fourth Scandinavian Workshop on Algorithm Theory (SWAT '94), Aarhus, Denmark, 1994 ffi Fifth International Workshop on Algorithmic Learning The- ory (ALT '94), Leipzig, Germany, 1994 ffi Sixth Annual Symposium on Com- binatorial Pattern Matching (CPM '95), Hanasaari, Espoo, 1995 (chair) ffi 24th International Colloquium on Automata, Languages, and Programming (ICALP '97), Bologna, Italy, 1997 59 - Other activities: Editor-in-Chief of the Nordic Journal of Computing, from 1994 ffi Member of the Steering Committee of the Scandinavian Workshop on Algorithm Theory (SWAT), from 1991 ffi Member of the Finnish-Estonian Joint Committee on Informatics, 198894 ffi External reviewer for professor- ships at Lule#University, Sweden, 1994, and at University of California at San Diego, University of California at Davis, University of Colorado at Boulder, and the University of Utah, 1996 ffi External reviewer for NSF (Washington D.C., U.S.A.) from 1991, and for TFR (Sweden) from 1993 ffi Member of the Ph.D. examination committee for Carsten Helgesen, University of Bergen, Norway, 1994, and for Stefan Kurtz, University of Bielefeld, Germany, 1995 ffi Biotechnology Prize of 1996 awarded by the Alko-Group Ltd. VALMARI, Antti Dr.Techn., Docent, Associate professor (Tampere Uni- versity of Technology) - E-mail: antti.valmari@tut.| - Interests: computer-aided veri|cation and validation of concurrent and distributed systems VEIJALAINEN, Jari Dr.-Ing., Docent, Senior research scientist, (VTT Information Technology, Multimedia Systems) - E-mail: jari.veijalainen@vtt.| - Interests: heterogeneous autonomous distributed systems, heterogeneous transaction processing, transactional workAEow systems, mobile computing, veri|cation and validation of concurrent and distributed systems VERKAMO, A. Inkeri Ph.D., Assistant professor - E-mail: inkeri.verkamo@cs.helsinki.| - Interests: software performance evaluation, software engineering, data min- ing - Publications: [4045, 58, 59, 170, 172, 173, 176] - Memberships of program committees: Sixth International Conference on Software Engineering and Knowledge Engineering (SEKE '94), Jurmala, Latvia, 1994 ffi Seventh International Conference on Software Engineering and Knowledge Engineering (SEKE '95), Rockville, Maryland, 1995 VIHAVAINEN, Juha Ph.Lic., Assistant professor - E-mail: juha.vihavainen@cs.helsinki.| 60 - Interests: principles and implementation of programming languages, lan- guage processors, programming paradigms, multi-paradigm programming, object-oriented programming - Publications: [36] VILO, Jaak M.Sc. (University of Tartu), Research assistant - E-mail: jaak.vilo@cs.helsinki.| - Interests: algorithms and data structures, machine learning, bioinformatics, stringology and text databases - Publications: [195, 196, 211] WIKLA, Arto M.Sc., Assistant professor (acting) - E-mail: arto.wikla@cs.helsinki.| - Interests: computer science education, WWW, programming languages, Java 61 Chapter 4 Education 4.1 Educational Program The students of the department normally start their university studies at the age of 19. Their goal is to receive a B.Sc. (Bachelor of Science) or M.Sc. (Mas- ter of Science) degree in computer science requiring three to four or |ve years of full time study. Beyond the |rst degree there are two alternative gradu- ate degrees: Ph.Lic. (Licentiate of Philosophy) degree and Ph.D. (Doctor of Philosophy). The academic year has two semesters: the fall semester lasts from September 1 to December 20 (classes from September 11 to December 10), while the spring semester lasts from January 16 to May 31 (classes from January 16 to May 10, excluding one week of Easter vacation). It is also possible to study in summer. Intensive courses of 45 weeks covering intro- ductory topics are ooeered in June and August. Graduate courses are also organized in cooperation with other Finnish universities during the summer. These courses typically last for one week and are intended for Ph.Lic. and Ph.D. students. These are often given in English by foreign visitors. In order to obtain a B.Sc. degree a student must earn 120 units of aca- demic credit. For M.Sc. degree 160 units of credit as well as a thesis is required. One credit should normally correspond to roughly one week (40 hours) of study. Our students typically register for 12 credits (istudy weeksj) in the fall semester and 15 credits in the spring semester. During the sum- mer sessions a student can earn an additional 810 credits. Most students, however, work in industry during the summer to gain practical experience in data processing and earn money. This is actually what the department recommends. Thus, a normal student should earn 27 credits a year, an exceptionally diligent full-year student 40 credits. Nevertheless, there is a considerable variation in study eOEciency among students. Our typical course consists of from 50 to 60 lectures (a lecture lasts 45 62 minutes) and of from 20 to 30 hours of problem solving, discussion and rep- etition sessions in small groups of from 10 to 20 students. Each course is examined individually with grades: 3/3 = excellent, 2/3 = good, 1/3 = sat- isfactory. A typical course is worth 4 or 5 credits. The computer laboratory is supervised in small groups of 6 to 12 students. Students also attend seminar courses, the enrollment of which ranges from 5 to 15 students. In these sem- inars current literature is read, essays are written and oral presentations are given. A seminar group normally meets 2 hours per week yielding 2 credits per a semester. In order to receive a M.Sc. degree in computer science, students are re- quired to earn their credits as follows: Computer science _ 95 c Mathematics __ 26 c Physics __ 15 c General studies __ 9 c total 160 c In mathematics the obligatory courses are calculus (11 c), algebra (5 c), logic (5 c), and probability (5 c). Physics can be replaced with almost any other subject, such as economics, administration, statistics, or psychology. For a B.Sc. degree 55 credit units of computer science is suOEcient. The computer science studies for a M.Sc. degree can be subdivided as follows: Obligatory courses and laboratories 35 c Elective courses 28 c Seminars __ 4 c Project work __ 8 c M.Sc. Thesis, Scienti|c writing __ 20 c total 95 c The obligatory computer science courses and laboratory work currently cover (academic year 199697) the following areas: Introductory programming (Pascal) 6 c Data structures 6 c Operating systems and hardware architecture 8 c Information systems and databases _10_c Theory of computation __ 5 c total 35 c 63 In principle, students are fairly free to choose any elective courses. They normally follow the recommendation of the department by building up a spe- cialized background knowledge for a successful thesis in one of our research groups. Thus, a student might orient himself according to his study goals, interests and talents towards, e.g., theoretical computer science, informa- tion systems, telecommunications software, distributed systems, operating systems, arti|cial intelligence, or programming languages. To start studies for the graduate degrees Ph.Lic. (Licentiate of Philos- ophy) and Ph.D. (Doctor of Philosophy) in Computer Science, a student having shown good academic standing in his M.Sc. studies contacts a pro- fessor of the department. At |rst, a personal study program is designed for the student. It outlines the |eld of specialization of the studies, the topic for the thesis, and the content and the schedule of the coursework. Each student is assigned a personal advisor. See Section 4.2 (Graduate School) for more details. The requirements for the Ph.Lic. degree can be summarized as follows: Elective courses and seminars in computer science 20 c in mathematics __20 c Ph.Lic. thesis __50 c total 90 c The elective courses in mathematics can be replaced with coursework in other subjects such as physics, economy, psychology etc. The Ph.Lic. thesis can be written in Finnish, Swedish (the two oOEcial languages of our university) or English. The allocation of credits for thesis research indicates that after the required coursework it should take 12 years to prepare a Ph.Lic. thesis. It is important that the student takes the courses and the seminars early enough to obtain suOEcient background for writing the thesis. Active partic- ipation in seminar courses is particularly useful as is attending international schools and specialized research courses. Such courses are also regularly given at the department. The requirements for the Ph.D. degree are otherwise the same as for the Ph.Lic. degree, but a Ph.D. thesis demands more work, from 2 to 3 years, roughly one year more than a Ph.Lic. thesis. The Ph.D. degree can be achieved directly, although we often recommend that our students take the Ph.Lic. degree |rst, and then by improving and extending their Ph.Lic. research, achieve the Ph.D. level. The Ph.D. theses are written in English. A thesis should include a scien- ti|c contribution which is signi|cant enough to be publishable internation- ally. A Ph.D. thesis (as well as a Ph.Lic. thesis) can also be assembled from a 64 number of published articles or congress papers, possibly written jointly with other authors. A dissertation of this type, which is actually fairly common, consists of an introductory survey written by the candidate alone, with the individual articles as appendices. Preparing the thesis is clearly the most demanding part of the Ph.D. and Ph.Lic. studies. To succeed with the thesis it is recommendable that a student works within a research group at the department. The support and the criticism given by the group is often essential for making progress in the work. 4.2 Graduate School Helsinki Graduate School in Computer Science and Engineering (HeCSE) is a post-graduate program in computer science and computer engineering jointly ooeered by the Helsinki University of Technology and the University of Helsinki. In addition to the Department of Computer Science at the Uni- versity of Helsinki, the following laboratories of the University of Technology participate in HeCSE: - Laboratory of Information Processing Science (Prof. Martti Mantyla) - Laboratory of Telecommunications Software and Multimedia (Prof. Arto Karila) - Digital Systems Laboratory (Prof. Leo Ojala) - Laboratory of Signal Processing and Computer Technology (Prof. Iiro Hartimo) - Laboratory of Computer and Information Science (Prof. Erkki Oja) - Neural Networks Research Centre (Prof. Teuvo Kohonen) The main areas of HeCSE are: - Software Systems (information technology for production, multimedia, database systems, data structures) - Software Engineering (embedded systems, speci|cation methods) - Telecommunication Software and Distributed Systems (formal meth- ods, data communication software, signal processing) - Learning and Intelligent Systems (pattern recognition, neural networks, machine learning, knowledge based systems) 65 HeCSE provides a program aiming at a doctoral degree in four years on the basis of a Master's degree in computer science or a related |eld. The student is appointed a supervising professor, with whom a study plan is made. The study plan contains an individual timetable. The student participates in the work of a research group. The progress of the student is followed by his/her supervisor and at seminars. Additionally, the student must report on his/her work twice a year. The student is formally enrolled at the university of his/her supervising professor. The studies consist of courses and seminars (2025%) and research work ending in a thesis (7580%). There is a compulsory course on Writing Sci- enti|c English and |ve courses on the main areas of HeCSE, three of which are to be taken by the student. The other courses are chosen individually. The student takes the courses and most of the seminars during the |rst two years. At the end of the second year, the student presents a thesis proposal to the Board of HeCSE. The doctoral thesis is expected to be |nished by the end of the fourth year. The studies end with a public doctoral dissertation. About half of the students in HeCSE are funded by graduate assis- tantships, others are employed in research projects as research assistants or in the participating laboratories as part time teachers. The Finnish graduate schools in computer science (Helsinki, Turku, Tam- pere and Eastern Finland) co-operate. Joint courses are arranged and stu- dents of one graduate school can participate in the courses arranged by another graduate school. Also participation in some courses arranged by industry is possible. 4.3 Course Descriptions Undergraduate Courses Introduction to Computing (2 cu) Introduction to computers and data processing. Algorithm. Computer hardware. Operating systems. Applica- tions software. Programming languages. Database systems. Communication networks. System analysis and design. Programming (Pascal) (4 cu) The course provides the student with the knowledge of the principles of an algorithmic language. The student will be able to program in Pascal and implement those programs in a microcomputer environment. Computer Systems Organization (3 cu) Introduction. Data presen- tation, error detection and correction. Computer organization. Conven- 66 tional machine level. Assembly language. Compilation, linking, loading. Input/Output. Secondary storage. Operating system. Data communication equipment and software. Information Systems (4 cu) Data systems and systems development. Data AEow techniques. Conceptual Modelling. Transaction Analysis. Data base design. Relational data model. SQL. User Interfaces. CASE tools. Programming Project (2 cu) The student designs, documents and pro- grams a complete, nearly realistic program. In the course of the development she/he also gives small lectures and demonstrations about the project. Data Structures (4 cu) Basic data structures. Applications to algo- rithms. Analysis of algorithms. Implementations of data structures and algorithms in Pascal. Memory management. Concurrent Systems (4 cu) Basic concepts and problems in concur- rent systems. Operating system concepts. Device, memory, |le and process management. Single concurrent actions. Synchronization. Process commu- nication. Deadlock and deadlock avoidance. Database Systems I (4 cu) File structures. Databases and database management systems. Relational data bases. Relational algebra, calculus and query languages. Relational database processing. Database application development. Database design. Functional dependencies and normalization. Network database principles. Theory of Computation (5 cu) Finite automata and regular languages. Context-free grammars and languages. Rudiments of parsing theory and attribute grammars. Context-sensitive and type-0 grammars. Turing ma- chines. Recursive and recursively enumerable sets. Computability and com- putational complexity. Data Structures Project (3 cu) A simulator or some other fairly large program is designed, programmed, tested and documented. Information Systems Project (2 cu) A small ADP-system is designed and programmed. 67 Computing Methodologies (3 cu) A characterization of computer sci- ence, its problems, methods and applications by selected examples and dis- cussions. Models as tools. A learning model. Human and scienti|c informa- tion processing: Perspectives on data, information, coding and computing, perception and thinking. Algorithm, why and how. L-systems as models. It- erated function systems. Discrete numerical computing. Pictures and graph- ics. Individual work. Languages for Arti|cial Intelligence (3 cu) Fundamentals of declar- ative and symbolic programming. LISP and PROLOG basics. Hands-on experimentations and implementations. Arti|cial Intelligence (4 cu) General owerview of the potential of AI in various kinds of problem solving is given. Main results in AI research and applications are presented. Also basic readiness to construct AI based soft- ware is provided. The course consists of overview, search and game playing, knowledge representation and reasoning, planning, probabilistic reasoning, rational decisions. Prerequisites: Basic ability to program in LISP. Computer Graphics (4 cu) Overview of graphics systems. Output prim- itives and their attributes. Two-dimensional transformations. Windowing and clipping. Segments. Interactive input methods. Three-dimensional con- cepts, representations, transformations, viewing. Hidden-surface and hidden- line removal. Shading and color models. Modeling methods. Design of the user interface. Individual practical work. Computer Uses in Education (4 cu) Fundamentals of computer ap- plications in education. Computer as a tutor, tool, and tutee. Computer assisted instruction (CAI) systems. Courseware design, development, and evaluation. Authoring systems and languages. Multimedia CAI. Intelligent CAI. Applications and research. Practical courseware designing in small groups. Principles of Programming Languages (4 cu) History. Basic con- cepts of Ada. Type systems (Algol68, Pascal, Ada). Blocks, subroutines and parameter passing. Modules (Clu, Modula-2, Euclid, Ada). Classes and objects (Simula, C++, Smalltalk, Oberon). Exception handling (PL/I, Clu, Ada). Concurrency (Concurrent Pascal, Ada). Generics. Programming environments. 68 Semantics of Programs (3 cu) Axiomatic semantics of programs. Weak- est precondition calculus for the guarded command language of Dijkstra. Development of small programs based on the programming logic. Data Communications (4 cu) The electrical interface. Data transmis- sion. Data link control protocols. Local area networks. High-speed and bridged local area networks. Wide area networks. Internetworking. Trans- port protocols. Programming in C (3 cu) Language de|nition. Programming tools. General programming principles. Software Engineering (8 cu) Introduction to software engineering as a professional discipline. Models of software engineering. Team work. Project planning and organization. Requirements analysis and engineering. Software design. Implementation techniques. Testing. Debugging and maintenance. Software con|guration management. Software quality assurance. Each stu- dent takes part in a project where a group of students analyzes the require- ments of a software product, designs, implements, and tests the product, using systematic software engineering methods and tools. The group assign- ment may also be focused on some sub-phase of the software life-cycle, such as evolution or maintenance of an existing software system. UNIX Principles (1 cu) Principles of UNIX environment for end users. Includes principles of |le system, shell, wildcards, protection, I/O, text edit- ing, regular expressions, sorting and searching, awk, program development, project maintenance, and networking commands. Unix Platform (3 cu) Programming interface to Unix system: system calls and library functions for process control, memory management, |le systems and peripherals, tools for interprocess communication. UNIX Networking (4 cu) Data communication protocols typically used in a UNIX environment are discussed including networking services provided to application programs, as well as design and implementation principles of these protocols. The focus is in the practical aspects of designing and implementing distributed applications using these protocols. Social Role of Automatic Data Processing (2 cu) Information soci- ety. Information technology policy of Finland. Economic eoeects. Eoeects on 69 employment. Quality of work. Educational impacts. Privacy legislation and other juridical issues. Eoeects of new telecommunication services. Scienti|c Writing (4 cu) Sources of scienti|c information. Use of li- braries and scienti|c data bases. The structure and details of a scienti|c publication. Examples of scienti|c Finnish. Three individual survey writing exercises. Graduate Courses a) General Computer Science Design and Analysis of Algorithms (5 cu) Analysis techniques. De- sign techniques. Models of computation and lower bounds. Algorithms on sets. Graph algorithms. Approximation algorithms for NP-complete prob- lems. Probabilistic algorithms. Parallel algorithms. String Processing Algorithms (5 cu) Exact string matching. Approx- imate string matching. Pattern matching in static strings. Text databases and hypertext. Algorithm implementation and comparison project. Machine Learning (5 cu) History. Inductive learning: Learning in the blocks world, identi|cation in the limit, version spaces. Learning classi|ers: Finite automata, case-based, rules, decision trees, neural networks, genetic algorithms. PAC-learning: basics, Occams Razor, Vapnik-Chervonenkis di- mension, learning by queries, PAC and noise, relation of dioeerent models. PAC and classi|er learning. Inductive logic programming. Real-world appli- cations. Parallel Algorithms (3 cu) Parallel processors and computers. Arrays and trees: elementary sorting and counting, integer arithmetic, matrix com- putations, retiming and systolic conversion, graph algorithms, sorting re- visited, packet routing, higher dimensional arrays. Meshes of trees: two- dimensional mesh of trees, O(log N )-step algorithms. Hypercubes and re- lated networks: hypercubes, variations with bounded branching degree (but- terAEies, cube-connected-cycles). Computational Complexity Theory (3 cu) Review of Turing machines and complexity classes. Space complexity. Alternating Turing machines and the polynomial time hierarchy. Oracle Turing machines and relativization. Structure theorems for NP-complete sets. Structure within NP. Probabilistic 70 Turing machines and complexity. Nonuniform complexity measures. Kol- mogorov complexity. Complex Computational Systems (4 cu) Cellular automata. Simu- lated annealing. Recurrent neural networks. Genetic algorithms. Molecular computation. Thermodynamics of computation. Arti|cial life. Advanced Computer Graphics (4 cu) Selection of advanced topics such as tray tracing, radiosity, solid modeling, illumination and color, sci- enti|c visualization, etc. are taken as a theme of the course. Individual and group work, report writing and oral presentations by the participants. Robotics (4 cu) Types and applications of robots. Components of a robot. Architectures. Autonomous mobile robots: Navigation and motion planning. Robot learning: Reinforcement learning, Q learning. b) Computer Software Compiler Construction (5 cu) Examples of industrial compiler projects. Introduction to compiling. Lexical analysis: regular expressions, scanning. Syntax analysis: context-free grammars, recursive descent parsing, parsing conAEicts and their solving. Semantic analysis: symbol tables, attribute gram- mars. Code generation: intermediate languages, optimization. Distributed Operating Systems (4 cu) Kernel functionality. File ser- vice. Name Service. Time and coordination. Replication. Distributed trans- actions. Recovery and fault tolerance. Performance Evaluation (2 cu) General performance modeling con- cepts. Queueing network models and their solutions. Workload modeling. Emphasis on applications. Foundations in Software Engineering (3 cu) Software engineering as a scienti|c discipline. Software production vs. engineering. Software product quality. Software process maturity. Testing techniques. Modelling and Simulation of Data Communication Systems (2 cu) Recent advances in modelling and simulation techniques for communication systems are examined. The focus is on traOEc modelling and on simulation of rare events. 71 Performance Evaluation of Data Communication Systems (2 cu) The course focuses on speci|c aspects of performance evaluation applied to data communication systems. The main topics include modelling commu- nication systems, analysis of measurement data, modelling protocol stacks, and speci|c features in high-speed networks. Computer Networks (4 cu) Formal speci|cation and analysis of commu- nication protocols, speci|cation case studies. Security in computer networks: encryption, authentication, digital signatures etc. Simulation Methods (2 cu) General simulation methodology concepts. Model veri|cation and validation. Statistical analysis of simulations results. Generating, testing and using random numbers. Emphasis on applications. Project. Principles of Concurrent Programming (4 cu) Basic abstractions in concurrent programming, analysis and veri|cation of algorithms and syn- chronization primitives for shared-memory parallel programs. Computer Architecture (4 cu) Basics of computer architecture from instruction set design to I/O subsystems. The emphasis is on uniprocessor systems but parallel and distributed architectures are also discussed. Object-Oriented Programming (4 cu) Introduction to object-oriented thinking. Pure object-oriented languages. Object-oriented analysis and de- sign. Hybrid object-oriented languages. Design patterns. Mobile (Wireless) Data Communications (2+1 cu) Overview of wireless data communications. Wireless data communications systems: cel- lular telephone networks, packet radio networks, wireless LANs, and satel- lites. Challenges of integration of wireless and wireline networks. Dioeerent solutions: MIP, Indirect TCP, Snoop, Mowgli, Barwan, etc. Software Performance Engineering (2 cu) Principles for creating re- sponsive software. Data gathering. Execution models. Software performance evaluation. Memory management. Real-Time Databases (2 cu) Integrating concurrency control with real- time scheduling is the most challenging part of providing a real-time trans- action processing system. Various solutions proposed in the literature and their merits are examined. 72 Performance Evaluation of Database Systems (2 cu) The course focuses on speci|c aspects of performance evaluation applied to database systems. The main topics include benchmarking, modelling concurrency in queueing network models, and evaluation of concurrency control algorithms. c) Information Systems Database Systems II (5 cu) Physical data organization in databases. Sequential, hashed and indexed |le structures. Query processing and op- timization for relational database systems. Join algorithms. Query opti- mization for distributed databases. Crash recovery. Concurrency control. Transaction management. Relational Database Design (3 cu) ER model and relational model. Object-oriented models. Integrity constraints and dependencies. Goals of database design. Axiomatizations of functional and inclusion dependen- cies. Algorithms for manipulating integrity constraints. Transformations between models. Database design by using examples. Generation of exam- ple databases. Dependency inference. Performance issues. Object-Oriented Databases (4 cu) Basic concepts of object data man- agement. Advanced database applications. Extended relational database systems. Objects and types, composite objects, relationships, inheritance. Associative object access. Object calculus. Views. Object storage. Single- level store. Storage of large objects. Indexing. Clustering. Workstation- server architectures. Transaction management. Performance. Transaction Processing (4 cu) Serializability theory. Locking and non- locking schedulers. Multiversion concurrency control. Centralized and dis- tributed recovery. Management of replicated data. Multidatabase trans- action management. Cooperative transaction management. Prototype sys- tems. User Interfaces (4 cu) Psychological foundations. Types of users, user modelling. Design guidelines. Basic interaction styles and techniques. For- mal description of interaction. Special issues: user support, error handling, screen design. Interfaces to some application systems: database systems, hypertext, information exploration. The course includes a laboratory work where a prototype interface is designed and implemented. 73 Computer-Supported Cooperative Work (3 cu) Concepts and his- tory of CSCW. Advanced electronic mail and news systems. Meeting sup- port systems. Collaborative writing and hypertext. Shared data. Structural properties behind groupware solutions. WorkAEow principles. Social and or- ganizational aspects. Knowledge Bases (3 cu) Knowledge representation. Advanced data models and new database systems, including rule-based, object-oriented, and structured text databases. Knowledge-base systems. Information Retrieval Methods (3 cu) Traditional information re- trieval methods. Information |ltering. Digital libraries. Information Systems Development Methodologies (4 cu) Informa- tion system life-cycle models. Comparison of methods. Research on devel- opment methodologies. SA, SSADM, JSD, IE, OMT, OOSE, OOA and new object oriented methods. Principles of Computer Aided Software Engineer- ing (CASE). Meta CASE, CASE repositories and processing of CASE data. Seminar Courses in 199496 a) General Computer Science Advanced Computer Graphics Analogic Computation Arti|cial Intelligence Bioinformatics Computation in Complex Systems Computer Graphics Computer Uses in Education Data Compression Techniques Dynamic Data Structures Evolutionary Algorithms: Foundations and Applications Genetic Algorithms History and Philosophy of Computing History of Computing Machine Learning Models and Algorithms for Parallel Computation Multimedia Technology, Especially Sound Processing Probabilistic Analysis of Algorithms on Words Research Seminar on Machine Learning and Data Mining Scienti|c Visualization 74 Training Stochastic Grammars and Their Applications to Modelling Biolog- ical Sequences b) Computer Software Computer Network Architectures Data Communications Technology De|nition and Implementation of Object-Oriented Languages Design of Distributed Applications Fault-Tolerant Systems Functional Programming Information super highway, implementation problems Mobile Workstations Object-Oriented Programming Real Time Databases Research Seminar on Computer Networks Research Seminar on Formal Speci|cation and Veri|cation Research Seminar on Mobile Workstations Research Seminar on Performance Analysis of Data Communications Security of Distributed Systems Software Engineering Software Maintenance and Version Management Software Reliability Analysis Speci|cation of Distributed Systems Supercomputers with Distributed Memory Telecommunication Software Architectures Thesis Seminar (Mobile Workstations) c) Information Systems Algorithms for Structured Text Computer-Supported System Work Database Structures Groupware Information Retrieval Logic Databases Object-Oriented Databases Research on User Interfaces Research Seminar on Databases Text Database Systems Thesis Seminar (Information Systems) Transaction Management in Cooperative Environments 75 4.4 Accepted Theses Theses for Doctor of Philosophy Seppo Linnainmaa: Analysis of some known methods of improving the ac- curacy of AEoating-point sums. BIT 14 (1974), 167202. Eljas Soisalon-Soininen: Characterization of LL(k) languages by restricted LR(k) grammars. A-1977-3. Esko Ukkonen: On the eoeect of rounding errors on the AEow of control in numerical processes. A-1977-7. Ralph-Johan Back: On the correctness of re|nement steps in program devel- opment. A-1978-4. V.-E. Juhani Virkkunen: A uni|ed approach to AEoating-point rounding with applications to multiple-precision summation. A-1980-1. Hannu Erkio: Studies on the eOEciency of certain internal sort algorithms. A-1980-4. Seppo Sippu: Syntax error handling in compilers. A-1981-1. Kari-Jouko Raiha: A space management technique for multi-pass attribute evaluators. A-1981-4. Timo Alanko: Empirical studies of program behaviour in virtual memory. A-1983-3. Kai Koskimies: Extensions of one-pass attribute grammars. A-1983-4. Heikki Mannila: Instance complexity for sorting and NP-complete problems. A-1985-1. Ilkka Haikala: Program behaviour in memory hierarchies. A-1986-2. Pekka Orponen: The structure of polynomial complexity cores. A-1986-3. A. Inkeri Verkamo: Sorting in hierarchical memories. A-1988-1. Jorma Tarhio: Attribute grammars for one-pass compilation. A-1988-11. Gosta Grahne: The problem of incomplete information in relational databases. A-1989-1. Niklas Holsti: Script editing for recovery and reversal in textual user inter- faces. A-1989-5. Kimmo Raatikainen: Modelling and analysis techniques for capacity plan- ning. A-1989-6. 76 Jukka Paakki: Paradigms for attribute-grammar-based language implemen- tation. A-1991-1. Jyrki Kivinen: Problems in computational learning theory. A-1992-1. Patrik Flor#en: Computational complexity problems in neural associative memories. A-1992-5. Pekka Kilpelainen: Tree matching problems with applications to structured text databases. A-1992-6. Jaana Eloranta: Minimal transition systems with respect to divergence pre- serving behavioural equivalences. A-1994-1. Petri Myllymaki: Mapping Bayesian networks to stochastic neural networks: a foundation for hybrid Bayesian-neural systems. A-1995-1. Roope Kaivola: Equivalences, preorders and compositional veri|cation for linear time temporal logic and concurrent systems. A-1996-1. Tapio Elomaa: Tools and techniques for decision tree learning. A-1996-2. Selection of Theses for Licentiate of Philosophy Kari-Jouko Raiha: On attribute grammars and their use in compiler writing systems. A-1977-4. Kai Koskimies: A study on the programming language Euclid. A-1980-2. Harri Laine: Semantic integrity and data base update in the grammatical data base model. C-1981-48. Jorma Tarhio: Attribute evaluation during LR parsing. A-1982-4. Juha Vihavainen: Design of the simulation language Mode (in Finnish). C-1987-42. Jukka Paakki: Generating one-pass semantic analysis for a compiler. A-1988-8. Eeva Hartikainen: Speci|cation and design of distributed programs that use broadcasting. A-1988-13. Jukka Mutikainen: An experimental study of attribute selection criteria in decision tree induction. C-1989-67. Erja Nikunen: Views in structured text databases. C-1990-60. Liisa Raiha: Sequence comparison: computation of the edit distance. C-1991-59. 77 Juha Puustjarvi: Management of transactions in heterogeneous distributed database system. C-1992-31. Pasi Tapanainen: Finite-state parsing for natural languages (in Finnish). C-1993-7. Greger Lind#n: Incremental updates in structured documents. C-1993-19. Helena Ahonen: Generating grammars for structured documents using gram- matical inference models. C-1994-65. Paivikki Parpola: Object-oriented knowledge acquisition (in Finnish). C-1995-11. Pekka Siltanen: Free form modeling using cubic Bezier curves and surfaces. C-1995-19. Selection of Master Theses in 199419961 a) General Computer Science Juha Nurmonen: Kolmogorov complexity of strings. C-1994-6. Janne Nappi: Compression of weather radar data. C-1994-10. Serge Santos: Phase transitions in sparsely connected Bolzmann machines. C-1994-15. Jarmo Pensola: Determinations and functional dependencies. C-1994-18. Tommi Timonen: Pattern matching in three-dimensional space. C-1994-35. Satu Nahkuri: Inference of genetic structures with case-based methods. C-1994-36. Pekka Haara: Modeling group-behaviour in computer animation. C-1994-69. Marko_Tuominen:_Use and development of hypermedia systems in education. C-1995-1.__ _ Juha_Karkkainen:_SuOEx cactus suOEx tree in small space. C-1995-6. _ Kaisa_Kaunonen: Reconstructing 3-D models from parallel data. C-1995-21. _ Kjell_Lemstrom:_Quantization and dithering of a digitized image. C-1995-22. _ Marko_Nyman:_A system for optimizing liquid chromatography experiments. C-1995-28.__ _ Seppo_Mallenius: Optimizing the hard address distribution for Kanerva's _ distributed_memories. C-1995-56. _ 1Written mostly in Finnish. 78 Mika Panhelainen: Public key cryptography. C-1995-57. Antti Alestalo: Applicability of parallel genetic algorithms to the graph par- tition problem. C-1995-75. b) Computer Software Taira Hiili: Software quality assurance. C-1994-19. Marko Moilanen: Performance analysis of NMT-based wireless data commu- nication. C-1994-23. Tero Venetjoki: Trader federation and its implementation in the DRYAD system. C-1994-25. Olli Nousia: Synchronous speci|cation languages for reactive sys- tems: STATECHARTS formalism and ESTEREL programming language. C-1994-30. Pertti Pellonpoika: Empirical performance analysis of a PC. C-1994-38. Kaarlo Hirvi: Fault-tolerant computing based on process groups. C-1994-46. Olli Vertanen: Protection in distributed systems. C-1994-60. Anna Sillanpaa: The Cleanroom method. C-1994-62. Antti-Pekka Tuovinen: Conversions between relational query languages. C-1994-70. Juha-Antti Sorsa: Object-oriented interpreting and code generation. C-1995-3. Vesa Hellgren: Multimedia synchronization with Audio|le examples. C-1995-20. Markku Kojo: Remote procedure call in heterogeneous systems. C-1995-24. Timo Leppanen: Parallel compilation. C-1995-25. Jarkko Lapinlampi: Space-eOEcient minimization of transition systems. C-1995-35. Lea Viljanen: International directory services for electronic mail. C-1995-45. Seppo Nuutinen: Software con|guration management in distributed environ- ments. C-1995-54. Lauri Glad: Process migration in distributed systems. C-1995-59. Tommi Kokkola: Analysis and measurements of the performance character- istics of GSM data services. C-1995-62. Tapani Ojaluoma. Clustering algorithms for call-detailed records in telecom- munications. C-1995-69. 79 c) Information Systems Sarianne Mykra: The containment model for structured text. C-1994-5. Sari Huvinen: Interaction objects and their constraints. C-1994-48. Kati Vilkki: Structured presentation of knowledge in computer supported cooperative work. C-1994-49. Olli Hamalainen: Estimation of work load in application development by function point methods. C-1994-52. Synnove Kekkonen: On the expressive power of query languages. C-1994-58. Mika Klemettinen: Selection and visualization of interesting associative rules. C-1994-59. Jaakko Suoninen: On implication of EDP in public health service. C-1994-68. Satu Eloranta: Knowledge base revision and update. C-1995-5. Jari Manninen: Analysis of user requirements in object-oriented systems development. C-1995-23. Riitta Kahelin: An eOEcient similarity search method in sequence databases. C-1995-27. Jarkko Koivula: On negative and set operations in logic databases. C-1995-44. Eeva Jauhiainen: A query method for structured text |les. C-1995-46. Oskari Heinonen: Knowledge discovery in databases by generalizing relations. C-1995-47. Mika Laurila: Concept hierarchies in knowledge discovery. C-1995-50. Jarmo Kannisto: Customizing of user interfaces. C-1995-53. Jarkko Majuri: On knowledge-based methods in designing the computation of a tablet and its manufacturing process. C-1995-71. T. Anton Puolakka: Composite event implementation in active databases. C-1995-72. 80 4.5 Abstracts of Recent Ph.D. Theses Jaana Eloranta: Minimal transition systems with respect to divergence pre- serving behavioural equivalences. A-1994-1. Three divergence preserving behavioural equivalences for labelled transition systems (lts), namely D-bisimilarity, branching D-bisimilarity and CFFD- equivalence, are analyzed and compared. For an image-|nite lts, which does not contain an in|nite sequence of distinct | -connected states, it is possible to |nd the unique lts which is state- and transition-minimal with respect to D-bisimilarity or branching D-bisimilarity. It is well known how to |nd an equivalent state-minimal lts. We show how the state and transition-minimal lts can be found, and moreover give a transition minimization algorithm in a |nite case. In the case of CFFD-equivalence, which is a modi|cation of failures-equivalence, a unique state- and transition-minimal lts cannot always be found. For rooted versions of D-bisimilarity and branching D-bisimilarity the uniqueness result holds only for root-unwound lts's. Related equivalences, D-congruence and branching D-congruence, handle the |rst transitions from a root, rather than a root itself, in a special way. The relation between rooted equivalences and corresponding congruences is fully analyzed. For D-congruence and branching D-congruence a unique root-unwound minimal lts is found, for an image-|nite (without an in|nite sequence of distinct t- connected states). Moreover, D-congruence and branching D-congruence are compositional with respect to Basic LOTOS operations. Since the same result holds for CFFD-equivalence, D-congruence, branching D-congruence and CFFD-equivalence are compatible with compositional reduction. In order to apply and demonstrate the theoretical results, we specify and verify several concurrent systems. The speci|cations are reduced with respect to several equivalences, including D-congruence, branching D-congruence and CFFD-equivalence. The analysis shows that it is possible to |nd errors, as well as reasons for divergences by studying reduced lts's. Moreover, these case studies are used to test the eoeect of the transition-minimization algorithm, to compare divergence preserving and divergence ignoring equivalences, and to compare branching and weak versions of equivalences. In some studies compositional reduction is used and the results are analyzed. Furthermore, based on the results of these applications, we propose some modi|cations to the reduction algorithm with respect to CFFD-equivalence. Petri Myllymaki: Mapping Bayesian networks to stochastic neural net- works: a foundation for hybrid Bayesian-neural systems. A-1995-1. In this work, we are interested in the problem of |nding maximum a pos- 81 teriori probability (MAP) value assignments for a set of discrete attributes, given the constraint that some of the attributes are permanently |xed to some values a priori. For building a system capable of this type of uncertain reasoning in practice, we need |rst to construct an accurate abstract rep- resentation of the problem domain, and then to establish an eOEcient search mechanism for |nding MAP con|gurations within the constructed model. We propose a hybrid Bayesian network-neural network system for solving these two subtasks. The Bayesian network component can be used for construct- ing a compact, high-level representation for the problem domain probability distribution quickly and reliably, assuming that suitable expert knowledge is available. The neural network component provides then a computationally eOEcient, massively parallel platform for searching the model state space. The main application areas for these kinds of systems include con|guration and design problems, medical diagnosing and pattern recognition. For implementing a hybrid Bayesian-neural system as suggested above, we present here methods for mapping a given Bayesian network to a stochas- tic neural network architecture, in the sense that the resulting neural net- work updating process provably converges to a state which can be projected to a MAP state on the probability distribution corresponding to the origi- nal Bayesian network. From the neural network point of view, these map- pings can be seen as a method for incorporating high-level, probabilistic a priori information directly into neural networks, without recourse to a time- consuming and unreliable learning process. From the Bayesian network point of view, the mappings ooeer a massively parallel implementation of simulated annealing where all the variables can be updated at the same time. Our empirical simulations suggest that this type of massively parallel simulated annealing outperforms the traditional sequential Gibbs sampling/simulated annealing process, provided that suitable hardware is available. Roope Kaivola: Equivalences, preorders and compositional veri|cation for linear time temporal logic and concurrent systems. A-1996-1. A promising approach to formal speci|cation and veri|cation of |nite-state concurrent systems is using propositional temporal logic as a speci|cation language and applying automated model-checking algorithms for the veri|- cation task. However, the so-called state explosion-problem caused by rep- resenting concurrency by interleaving makes model-checking in many cases practically intractable. One way of attacking this problem is replacing the modules of a system by smaller ones so that the visible properties of the system are not aoeected. This approach leads to notions of compositional property-preserving equivalences and preorders between modules. This work examines the uses of equivalences and preorders in verifying 82 nexttime-less linear temporal logic properties. Concurrent systems are mod- elled here by labelled transition systems augmented with state information, and both synchronisation and read-shared variables are considered as meth- ods of communication. We examine a novel equivalence notion, called the non-divergent failures divergences or NDFD-equivalence. It is shown that NDFD preserves all nexttime-less linear temporal logic properties, and that it is compositional with respect to parallel composition and abstraction by hiding and encapsulation. Conversely, it is shown that NDFD is the weak- est such equivalence, i.e. that it is fully abstract with respect to preserving nexttime-less linear temporal logic properties in an arbitrary context. The computational complexity of determining NDFD-equivalence is also exam- ined and the problem is shown to be PSPACE-complete. Analogous to NDFD-equivalence, the theory of NDFD-preorder is de- veloped and the compositionality, full abstractness and computational com- plexity results extended to it. Moreover, it is shown that the veri|cation technique of modular validity introduced by Manna and Pnueli corresponds to an extremal case of NDFD-preorder. As a larger case study illustrating the practical applications of the results, we use the NDFD-preorder to verify semi-automatically both safety and liveness properties of the sliding window communication protocol for arbitrary channel lengths and realistic parame- ter values. In this process we locate a previously undiscovered fault leading to lack of liveness in a version of the protocol. Tapio Elomaa: Tools and techniques for decision tree learning. A-1996-2. Decision tree learning is an important |eld of machine learning. In this study we examine both formal and practical aspects of decision tree learning. We aim at answering to two important needs: The need for better motivated decision tree learners and an environment facilitating experimentation with inductive learning algorithms. As results we obtain new practical tools and useful techniques for decision tree learning. First, we derive the practical decision tree learner Rank based on the Find- min protocol of Ehrenfeucht and Haussler. The motivation for the changes introduced to the method comes from empirical experience, but we prove the correctness of the modi|cations in the probably approximately correct learn- ing framework. The algorithm is enhanced by extending it to operate in the multiclass situations, making it capable of working within the incremental setting, and providing noise tolerance into it. Together these modi|cations entail practicability through a formal development process, which constitutes an important technique for decision tree learner design. The other tool that comes out of this work is TELA, a general testbed for all inductive learners using attribute representation of data, not only for 83 decision tree learners. This system guides and assists its user in taking new algorithms to his disposal, operating them in an easy fashion, designing and executing useful tests with the algorithms, and in interpreting the outcome of the tests. We present the design rationale, current composition, and future development directions of TELA. Moreover, we reAEect on the experiences that have been gathered in the initial usage of the system. The tools that come about are evaluated and validated in empirical tests over many real-world application domains. Several successful inductive al- gorithms are contrasted with the Rank algorithm in experiments that are carried out using TELA. These experiments let us evaluate the success of the new decision tree learner with respect to its established equivalents and validate the utility of the developed testbed. The tests prove successful in both respects: Rank attains the same overall level of prediction accuracy as C4.5, which is generally considered to be one of the best empirical decision tree learners, and TELA eases the execution of the experiments substantially. 84 Chapter 5 Library The department maintains a library with large collections of literature in Computer Science. The library is managed jointly with the University Com- puting Centre and is mainly used by the staoe and advanced students of the department. Established in 1967, the library now holds nearly 50,000 volumes of lit- erature. The annual cumulation is about 2,000 monographic titles (books, reports) and 300 journal subscriptions. In Finland, the collections of this library are probably the best in the |eld of computer science. The AEoor area of the library is 408 sq. meters including a reading room of 60 seats. Admission to the premises is free and collections are freely available to all visitors. Home loans, however, are restricted to the faculty and advanced students. The library subscribes to most major international journals in computer science and acquires a majority of the most important computer science books and conference publications. An important part of the collections consists of technical reports that are acquired as exchanges. The department maintains mutual exchange ar- rangements with about 130 research centers and university departments, in Europe and North America. To help users search and locate the required literature, the library main- tains an on-line database of its holdings. The database includes material acquired since 1982, classi|ed according to the CR Classi|cation System of the ACM. The database now contains nearly 30,000 bibliographic records, representing approximately 75% of the total holdings. The library staoe includes two full-time employees, one librarian and one secretary, who are assisted in their work by a library committee comprising of several members of the faculty. 85 Chapter 6 Computing Facilities The department ooeers a wide range of services to support computing activ- ities of the academic staoe and students. The policy is to provide access to advanced hardware and software systems. The computing facilities include three general purpose computers, |le servers, a farm of dedicated servers (e.g. for mail, WWW and FTP) and a network of workstations and microcomputers. The departmental general purpose computers are an Alpha based Citum Power System (a repackaged Aspen server), a SPARCserver 670MP and a SPARCserver 10. Some SPARC- servers are used as |le servers but the main |le server is a Pentium based system running Linux and utilizing RAID technology. The total disk space is currently approximately 40 Gbytes. All the Alpha and Pentium based ma- chines use Linux, but the SPARC computers run SunOS/Solaris. Together these systems support a wide variety of services, languages and software tools including electronic mail and news, graphics and visualization tools, several typesetting systems, and relational database systems. The workstation network consists of about 40 SPARCstations and about 140 PCs (mostly Pentiums with high resolution monitor) running Linux. MS- Windows can be used as an alternative for Linux. About 20 of the Linux workstations are mobile laptops which can join and leave the network dy- namically. The department also has about 70 other PCs and a number of X-terminals. Networking is based on Ethernet and ATM. CDDI (Copper Distributed Data Interface) technology is currently being phased out. On the UNIX side (Linux, SunOS/Solaris) NFS is used to share common re- sources. On the MS-Windows side Samba (a UNIX hosted Lan Manager Server) is used. Both Sun OpenWindows and MIT X11R6 with dioeerent window managers are in active use. The workstations are used as tools for software development, in research and all levels of teaching. The network of the department is connected to the university backbone network, giving access to computers at the University Computing Centre as 86 well as to the FUNET wide area network that links Finnish universities and research establishments. The computers operated by the Computing Cen- tre include SPARC (Sun, Solbourne, Axil), Digital Alpha and HP machines running under UNIX. Services provided by the Computing Centre include Oracle and Ingres database management systems, SAS statistical analysis package, NAG numerical library, and Pascal, Ada, and Prolog programming environments. In addition, the department has access to Cray C94, Cray T3E, two SGI Power Challenge, IBM SP2/24, and other supercomputers at the Center for Scienti|c Computing. The national FUNET network is further connected to the Nordic Uni- versity Network, Nordunet with a dedicated G.703(E3) 34 Mbps line. The Nordunet has also a 34 Mbps terrestrial connection to NAP Pennsauken in the United States as well as many connections to the European infrastruc- ture. This means that the department is very well connected to the Internet. 87 Chapter 7 International Relations Student exchange The department of Computer Science accepts annually some |ve new foreign students to start their undergraduate studies. These students are either beginning their computer science studies or complementing their studies. The department ooeers only occasionally courses lectured in English and thus a knowledge of Finnish is helpful for successful completion of undergraduate studies. Each year usually |ve to ten Finnish students from the department com- plement their studies at other European universities. The department is involved in the ERASMUS Inter-University Coordination Program, |nanced by the Commission of the European Communities. Through this program it is possible for students of the department to study at several European universities, including the Technical Universities of Darmstadt and of Graz, the University of Kent at Canterbury, and the University of Catalonia in Barcelona. The department also accepts visiting students from these and other partner institutions. Exchange of students within the Nordic countries is also easy with the |nancial support of NORDPLUS, a program coordinated by the Nordic Council of Ministers. Post-graduate studies at the department can usually be accomplished in English. The department may admit foreign post-graduate students, who want to study for either the M.Sc. or Ph.D. degree, or visiting students. The Academy of Finland and the Ministry of Education and Science ooeer grants for foreign post-graduate students within the international exchange programs. 88 Research cooperation The department has active contacts with many European and American Computer Science Departments. Faculty members have joint research eoeorts with individual researchers from abroad. The results of this international cooperation are partly presented in the publication list. Many faculty mem- bers have spent long periods of time abroad as visiting researchers or guest professors. In turn, apart from more than 20 short term visitors every year, the department has hosted several visiting foreign scholars. A list of long term visitors in 199496 is given below. The department has actively taken part in the European research coop- eration. The department is participating in the COST 247 project iFormal methods in Communication Protocol Designj. The department also takes part in the ESPRIT Programme in sev- eral projects. The largest of these are iKESO Knowledge Extraction for Statistical OOEces (ESPRIT III 20596)j (Heikki Mannila, 199698) and iTransCoop Transaction Management Support for Cooperative Applica- tions (ESPRIT III P8012)j (Henry Tirri, 199497). The department is a member institution in the working group iNEUROCOLT Neural and Com- putational Learning (ESPRIT III P8556)j (Esko Ukkonen, 199497) and in a networks of excellence iML-net Network of excellence in Machine Learning (ESPRIT III P7115)## (Esko Ukkonen, 1994) and iNEURONET - Net- work of excellence in Neural Networks (ESPRIT III P8961)j (Henry Tirri, 199496). In addition the department is a member institution of EC ACTS-project DOLMEN (AC036) iService Machine Development for an Open Long-Term Mobile and Fixed Network Environmentj (Kimmo Raatikainen). Project iObject-oriented programming and compiler constructionj (Jukka Paakki, 199597) is funded jointly by the Academy of Finland and Deutscher Akademischer Austauschdienst. Faculty members abroad in 199496 Gosta Grahne, Universite de Paris Sud, Centre d'Orsay, 5/96 Roope Kaivola, University of Edinburgh, 10/9212/95 Pekka Kilpelainen, University of Waterloo, Canada, 8/938/94 Jyrki Kivinen, University of California at Santa Cruz, U.S.A., 1/9312/94 and 5/957/95 Heikki Lokki, University of Missouri, St. Louis, and Webster University, St. Louis, Missouri, U.S.A., 7/935/95 89 Heikki Mannila, Max Planck Institut f#r Informatik, Saarbr#cken, Germany, 9/957/96 Petri Myllymaki, Royal Holloway and Bedford New College, University of London, UK, 3/957/95. Pekka Orponen, Technische Universitat Graz, Austria, 9/947/95 Jukka Paakki, Technical University of Munich, Germany 2/963/96 Jorma Tarhio, University of California at Berkeley, U.S.A., 7/937/94 Martti Tienari, University of British Columbia, Vancouver, Canada, 5/94 7/94 Esko Ukkonen, University of Bielefeld, Germany, 10/9411/94 Foreign Visitors in 199496 Dr. Hiroki Arimura, Kyushu University, 5/9610/96 Dr. Alvis Brazma, University of Latvia, 7/9512/95 B.Sc. Renato Busato, University of Edinburgh, 10/945/95 M.Sc. Riitta H#llerer, Technical University of Munich, 9/9512/95 B.Sc. Lorin Jurow, U.S.A., 1/957/95 B.Sc. David Nespoli, U.S.A., 1/9612/96 Mag. Fr#d#ric Prost, ENS Lyon, 6/948/94 M.Sc. Cheng Qi, China, 10/93 Mr. Serge Santos, ETH Z#rich, 11/934/94 Mr. Hannes Wettig, Univ. Koln, 4/96 M.Sc. Wentao Ye, Taiyuan Univ. of Technology, 3/96 Other Activities Faculty members regularly serve as referees for international computer sci- ence journals and conferences. Some faculty members are also reviewers for various review publications, such as Computing Reviews and Mathematical Reviews. Many faculty members have served in the program committees of various conferences, see Section 3. Prof. Esko Ukkonen is the editor-in-chief of the Nordic Journal of Computing. Prof. Heikki Mannila is the editor-in- chief of the Journal of Data Mining and Knowledge Discovery. Assoc. prof. Matti Makela is an international coordinator of ACM SIGNUM Newsletter. 90 The department organized the 6th Annual Symposium on Combinatorial Pattern Matching in Helsinki in July 1995. The conference proceedings was edited by Zvi Galil and Esko Ukkonen and it was published by Springer in the Lecture Notes in Computer Science Series. 91