Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2001
EATTK 2001

6th Estonian Winter School in Computer Science (EWSCS)
VI Eesti Arvutiteaduse Talvekool (EATTK)

Park Hotel Palmse, Lahemaa, Estonia
March 4 - 9, 2001

List of Talks and Abstracts

Fuzzy Logic Controlers

Vytautas Barzdaitis
Vytautas Magnus University (Kaunas), Lithuania
Dept. of Applied Informatics

Fuzzy logic and artifitial inteligence have at least one common objective: to develop computational methods that can perform reasoning and problem solving tasks that require human intelligence. Fuzzy set theory provides the basis for fuzzy modeling and fuzzy inference. Fundamental to fuzzy set theory is the use of fuzzy sets. In fuzzy sets, objects have a grade of membership ranging from 0 to 1. Fuzzy inference provides the means by which to perform fuzzy reasoning. Key to a fuzzy inference system is the fuzzy rule base, which contains information relating the input conditions to the output conditions. A fuzzy model is created when the fuzzy rule base dafines the relationship between the inputs ant the outputs of the system. Fuzzy set theory provides the formal framework for fuzzy modeling (representing) and fuzzy inference (reasoning) with uncertain or imprecise information. In my talk the basics of the theory of fuzzy logic will be observed. The comparison of the control by means of PI controlers and Fuzzy logic controllers of the same object will be presented.

Building Location Privacy in MobileIP networking

Alberto Escudero
KTH (Stockholm), Sweden
Microelectronics and Information Technology

The protection of privacy is considered as one of the most important issues on the Internet today. Internet users are concerned about privacy protection. More Internet sites are collecting personal information from users through forms, cookies, online registrations, or surveys than never before.

With the new wireless technologies mobility will be available and with it "location information" will be used to provide also new "location aware services".

The Big Flying Brother is a monitor and tracking system that records the movements and activities of the wireless users of the FlyingLinux.NET. Every minute "Big Flying Brother" updates the status of each of the mobile nodes. The location of each of the user in the network is stored in private database in which personal data is protected by providing a Nym to each user in the network. The aim of the project is to study "location privacy" related issues in new wireless environments and include "unlinkability" technologies as one more of the available services.

The information collected by "Big Brother" will help us in the design of wireless networks focused on the protection of privacy.

Key Establishment in Ad-hoc Networks

Maarit Hietalahti
Helsinki University of Technology, Finland
Dept. of Computer Science and Engineering

We overview protocols for contributory group key agreement in the context of ad-hoc networks. The efficiency and operating requirements of the protocols are compared and we find that the protocols from the literature are not efficient in ad-hoc networks with arbitrary topology.

Efficient search by the Simple Genetic Algorithm

Roger Jonsson
Mälärdalen University (Västerås), Sweden
Dept. of Computer Engineering

Results obtained by different researchers in the genetic algorithm community are often hard to compare and it is often difficult to draw general conclusions from these results. This means that non-experienced users of genetic algorithms have little help in constructing their own effective solutions for a particular problem. This presentation contains a suggestion about possible ways of investigating features of search in genetic algorithms as well as some theoretical ideas.

SSP for Java programming language

Vahur Kotkas
Institute of Cybernetics at TTU, Estonia
Software Department

During several years SSP (Structural Synthesis of Programs) has been studied in Institute of Cybernetics. This time we are aiming to apply SSP to Java programming language. In my presentation I would briefly describe how and what kind of declarative specifications we are going to introduce into Java classes. I would also give an overview of the CORBA based synthesizer that would perform the automatic program construction.

Verification of Parameterised Networks by Abstraction

Marcel Kyas
University of Kiel, Germany
Inst. of Computer Science and Applied Mathematics

I have computed a network invariant for all single bus configurations of the Futurebus+ Cache Coherence Protocol (Kyas, 2000) using PAX (Baukus et. al., 1999). Using this invariant I am able to prove a specification of cache coherence correct. This specification includes a progress property not discussed in literature yet.

I describe the basic principles of PAX, i.e., the formalisation of a parameterised network in the weak second order theory of one successor (WS1S), a decidable second order logic, and how to compute an abstract, finite state system from the parameterised network. This finite state system serves as input for a model checker.

The method I have used is, except for the formulation of the system's description and the abstraction relation, fully automated.


Baukus et. al., 2000
K. Baukus, S. Bensalem, Y. Lakhnech, and K. Stahl. "Abstracting WS1S Systems to Verify Parameterized Networks." In: S. Graf and M. Schwartzbach (eds.), "Proc. TACAS'00", volume 1785 of LNCS, Springer-Verlag, 2000.

Kyas, 2000
Marcel Kyas. "Verifikation parameteriserter Netzwerke durch Abstraktion." Master's thesis. Christian Albrechts Universitaet zu Kiel, Institute for Computer Science and Applied Mathematics, 2000.

Computationally Secure Information Flow

Peeter Laud
Universität des Saarlandes, Germany
FR Informatik

Suppose that the variables of a program are divided into high- and low-security (or secrecy) variables. Intuitively, we say, that a program has secure information flow, if an observer, who knows the final values of low-security variables, can deduce nothing about the initial values of high-security variables.

We propose a definition of secure information flow in programs. Our definition is not based on noninterference, but on computational indistinguishability, i.e. we do not require that the low security outputs of the program do not depend in any way from the high security inputs, but only require that the dependency is such, that no computationally bounded attacker can make use of it. In this sense our definition is somewhat similar to the definition of semantic security. This definition allows us to handle cryptographic primitives, whose security is usually defined in similar terms --- only security against computationally bounded adversaries is required.

We also give a data flow analysis which allows us to certify programs for secure information flow in our sense.

On Long-Lived Public-Key Traitor Tracing. First steps.

Silja Mäki
Helsinki University of Technology, Finland
Dept. of Computer Science and Engineering

Broadcast encryption can be used to address the contents of a digital transmission to, e.g., registered and paying receivers only. An efficient public-key broadcast encryption scheme was presented by Boneh and Franklin in Crypto '99. The scheme enables so-called traitor tracing, which discourages the users from replicating their decryption keys.

We present general attempts to make the scheme long-lived, so that the server can adapt its encryption procedure to the presence of pirate decryption keys, and modify the transmissions to reach the legitimate users only. We also present attacks against our own proposition and discuss the properties of the scheme.

A Theory of Replacement

Härmel Nestra
University of Tartu, Estonia
Institute of Computer Science

The phenomenon of subterm replacement is often used in theoretical computer science, for instance, within reasoning about term rewriting systems. However, it appears to be almost never investigated in itself.

The presentation introduces a mathematical theory of subterm replacement. In this theory, the definition of replacement operation is not inductive and corresponds closely to the human's intuitive preconception about subterm replacing. As a result, proofs of facts about replacement turn out to be easily readable for humans and interesting to compose.

The theory is developed uniformly for a large class of term calculi.

Measures of Quantum Entanglement

Reimo Palm
University of Tartu, Estonia
Institute of Computer Science

The power of quantum computing relies on the so-called entangled states that have no counterpart in classical world. It is important to find a measure for information that can be encoded in such states. We propose and analyse some possibilities doing this.

Compiler for Logic formulae

Ahti Peder
University of Tartu, Estonia
Institute of Computer Science


Problems of specialization of models and usage of reference models in analysis and design process

Alar Raabe
Tallinn Technical University, Estonia
Department of Computer Engineering

To make the analysis and design process more effective and guide the analysis in specific domain, there is a need to provide reference models which are results of partial analyze of given domain as starting point for analysis and design processes. These reference models must be specialized to create concrete analysis and design models for given problem. As a result of nested problem domains and need for interoperability between the specific reference models there will be need to create specialization hierarchies of reference models. To be able to further specialize the model, there are certain aspects during the construction of model, that have to be taken into account: modeling should be based on roles and variable parts of model should be isolated and clearly identified. Presentation describes new proposed mechanisms applicable during the specialization and inheritance of models -- overriding or substituting the model elements and removing unused elements.

Learning to recognize music

Gailius Raskinis
Vytautas Magnus University (Kaunas), Lithuania
Dept. of Applied Informatics

The problem of automatic transcription of monodic folk songs requires complex solutions in comparison to the transcription of instrumental music. Folk songs carry the spoken component. They are often ill-tempered as well. We assume that the problem of folk song transcription may be decomposed into the set of independent sub-problems such as feature extraction, segmentation, rhythm and pitch recognition. The existing solutions for these sub-problems were examined and appeared to be insufficiently accurate. We suggested methods that better suits for folk song transcription. These methods were incorporated into a new transcription algorithm called ATRAMA. ATRAMA extracts fundamental frequency, energy and a few spectral features from the song signal. The extraction of fundamental frequency is performed by means of cross-correlation and cepstrum techniques. The smoothness of the fundamental frequency curve and "octave error" reduction are achieved by the newly proposed heuristic search method. Segmentation is based on machine learning techniques. The features describing note's onset and its context are proposed. New method for pitch recognition is developed. It uses search techniques and heuristics inspired by music theory. The formal criterion of transcription accuracy is proposed. ATRAMA was tested on a large corpus of Lithuanian folk songs and appeared to be more accurate than existing commercial transcription software.

Long-term validation of digital signatures

Meelis Roos
University of Tartu, Estonia
Institute of Computer Science

The use of digital documents is increasing rapidly. With the the help of digital signatures, digital documents start having legal meanings. However, legally binding digital documents are a new area and contain new types of risks like short-lasting validity. This presentation analyzes some existing solutions to long-term signature validation technologies and offers a new and efficient solution.

Artificial Neural Networks for Sudden Cardiac Death Prediction

Ausra Saudargiene
Institute of Mathematics and Informatics, Lithuania
Data Analysis Dept.

Artificial neural networks have been used to assess the discriminative power of the risk markers of sudden cardiac death. Two groups of patients, 38 of whom overcame a myocardial infarction with cardiac ventricular fibrillation, and 115 of whom suffered myocardial infarction without cardiac ventricular fibrillation, have been investigated. As the number of the characteristic features extracted from the electrocardiograms is large, and the amount of the patients is limited, a design of the reliable classification system for the feature assessment is very problematic. A method to build a classification algorithm in the small design set case is presented. This method allows to retain all the features extracted, and it is based on the simplest artificial neural network, single-layer perceptron, used together with Radial basic function features and data whitening transformation. It is demonstrated that the method proposed shows the same generalization performance as much more complex artificial neural network, multilayer perceptron, applied together with the feature selection procedure.

Black or White Box Modeling? Biological Applications.

Minija Tamosiunaite
Vytautas Magnus University (Kaunas), Lithuania
Dept. of Applied Informatics

The presentation is motivated by the enormous popularity of the black-box modeling, including linear regressive models, neural networks, etc., and is grounded on the experience of application of various types of models for electrocardiogram analysis. They range from the dipole model of a heart, which has good electrophysiological basis, up to neural network based models having very little cardiological insight. The models with better insight into the subject field proved to be more successful (though not all of them) and the models taken to cardiology from other areas (physics, speech analysis) did not perform as well as expected. Some models based on neural networks, if correctly applied, have given good results.

Finite-State Methods for Computational Morphology

Heli Uibo
University of Tartu, Estonia
Institute of Computer Science

During the past twenty years the use of finite-state methods in various language engineering applications has grown steadily. Finite-state automata-based implementations are known as fast and effective, thus it is worth to study, how to apply the finite-state methods to any language. In the current talk, the finite-state methods for the primary stage of NLP - morphology - are discussed. The main question is: are regular expressions powerful enough to handle the morphology of various languages, in particular, Estonian language? Possible operations used in regular expressions and corresponding morphological phenomena are examined. The phenomena that can be handled using regular expressions are illustrated with examples from different languages. New methods by L. Karttunen for the handling of non-concatenative morphotactics - "compile-replace" and "merge" - are introduced.

Outlines of two finite-state models for computational morphology - two-level model (K. Koskenniemi) and replace-operator (L. Karttunen) are drawn.

The results of the development of experimental two-level morphology of Estonian are discussed. The list of other languages, for which the two-level morphological analysers have been developed, is given.

Cryptanalysis of the Self-Shrinking Generator

Erik Zenner
Universität Mannheim, Germany
Inst. für Informatik

A very common design for stream cipher systems is the concept of the running key generator. A relatively small "seed" is expanded by a deterministic algorithm into a long bit sequence that is not easily distinguished from a truly random sequence. Encryption is done by adding this bit sequence (called the key stream) modulo 2 to the message stream.

The presentation will introduce the self-shrinking generator, a running key generator that has been proposed in 1994 by Meier and Staffelbach. We will give some consideration to the most efficient attacks on the generator previously known. Finally, we will demonstrate how to break the cipher in a more efficient way, introducing some previously unknown results from our own research activities.

04/03/2001 16:20 EET    webmaster