*Abstract:*
We focused on the question - what kind of collision-finding attacks have
influence on the security of time-stamping schemes? In our analysis, we
distinguish between client-side hash functions used to shorten the
documents before sending them to time-stamping servers and server-side hash
functions used for establishing one way causal relations between time stamp
requests. We derive necessary and sufficient conditions for client side
hash functions and show by using explicit separation techniques that
neither collision-resistance nor 2nd preimage resistance is necessary for
secure time-stamping. Moreover, we show that server side hash functions can
even be not one-way. This shows that no generic collision-finders to
black-box hash functions can be turned into wrappers that break the
corresponding time-stamping schemes. Each such wrapper should analyze the
structure of the hash function. However, these separations do not
necessarily hold for more specific classes of hash functions. Considering
this, we take a more detailed look at the structure of practical hash
functions by studying the Merkle-Damgaard (MD) hash functions. We show that
attacks, which are able to find collisions for MD hash functions with
respect to randomly chosen initial states, also violate the necessary
security conditions for client-side hash functions. This does not
contradict the black-box separations results because the MD structure is
already a deviation from the black-box setting. As a practical consequence,
MD5, Sha-0, and RIPEMD are no more recommended to use as a client-side hash
function in time-stamping schemes. However, as we show, there is still no
evidence against using MD5 (or even MD4) as a server-side hash
function. (Joint work with Sven Laur).

Ettekande kiled. [pdf]

*Abstract:*
Hash functions are widely used for distributing data pseudorandomly accross
hash tables for fast access. Bit-state hashing is a well known method in
model checking for reducing memory consumption of the whole state space
search by storing only a single bit for each seen state at the address
calculated by the hash function. The drawback of the method is the
possibility of hash collisions that will result in unexplored parts of the
search space. We look at how changing the behaviour of a hash function by
changing the size of the hash table influences the performance of bit-state
hashing and compare it to the approach of replacing the hash function with
an abstraction function for the sake of utilizing the previously referred
collisions for abstraction.

Ettekande kiled. [pdf]

*Abstract:*
Planted motif problem is a benchmark problem for evaluating string motif
discovery programs, which are extensively used in bioinformatics.
A set of long strings is generated randomly and a short string motif is
planted into a random position in each of the long strings. The planting
process is not exact and some "mutations" may occur. The task is to find
the short string motif, given the set of long strings.
We will interactively solve the task and discuss the probability of having
a solution in random strings without the planted motif.

*Abstract:*
The issue of security of the information flow in a system arises if the
inputs and outputs of the system have been partitioned into different
security classes. In this case we want the high-security (private) inputs
to not influence the low-security (public) outputs in a way that is useful
for an adversary trying to gain some new information about these inputs.
In this tutorial we give an overview of possible definitions of secure
information flow for different classes of systems, as well as means to
check the security of information flow.

Ettekande kiled. [pdf]

*Abstract:*
One of the most common aspects of (programming) languages, logics and
semantics is the concept of *name* and the action of
*naming*. These aspects are so buried in our habits that we hardly
ever talk about them. In fact, the action of naming can be seen as the
archetypal mechanism of *abstraction*, in the sense that it allows
to isolate and crystallize into names specific aspects of more complex
concepts, which are thus easier to deal with. A closer look will reveal
that there are several, and quite different, abstractions paradigms which
names can be used for. Different paradigms yield different behaviors of
names, and sometimes these differences have been source of confusion in the
past. In this talk, we will analyze some prominent abstraction paradigms
in the theory of programming languages, of process calculi, of logics and
semantics; we will see the different roles played by names in these
situations. Then we discuss some recent developments in the theory of
these situations, with particular care to semantic models and general
logical systems for reasoning about them.

Ettekande kiled. [pdf]

*Abstract:*
Recently, it has turned out that transfinite semantics is useful for
constructing a sound mathematical framework of some program transformation
techniques like program slicing. On the other hand, transfinite semantics
may seem a bit artificial solution; moreover, using them for recursive
imperative programs involves serious problems.

We introduce trace semantics where trace components are indexed with rational numbers. Call these semantics rational. Rational semantics turns out to be a uniform framework to both recursive and non-recursive imperative programs. Thereby, rational semantics can be naturally given so that, for non-recursive programs, it in principle coincides with transfinite semantics (the difference is only in indexing of components).

Ettekande kiled. [pdf]

*Abstract:*
A finite array is a set with "lookup" and "update" maps on it subject to
the axiomatics of global state of Plotkin and Power. Finite arrays model a
memory on which one admits the two operations above. In this paper we study
potentially infinite arrays, with a collection of maps representing
"allocation" of fresh portions of memory. These arrays are defined on
omega-chains, where each set in a chain determines the finite array of the
corresponding dimension. Power and Shkaravska have shown that finite
arrays are comonadic over Set. Here we show that the category of
potentially infinite arrays is comonadic over omega-chains. Plotkin and
Power have studied a "local state" monad for fresh memory allocation. The
result presented here is not a dual for their result, but rather it is its
simplified version. The monad of Plotkin and Power is given over the
presheaves, which map the category of finite sets and injections onto
Set.

*Abstract:*
Position Weight Matrices (PWMs) can not describe polymorphisms in the
TFBS that are derived from evolutionary events as insertions or deletions.
In this work we extend the use of PWMs for the description of varied
length TFBS (for the same TF). We combine the PWMs with the Levenshtein
Distance (edit distance) and allow the introduction of insertions and
deletions. We apply our method in the promoter region of genes with a
similar expression profile, in order to discover 'undetected' TFBS that
are possible to explain the similarities in the expression profiles.
(Joint work with Pavlos Pavlidis).

Ettekande kiled. [pdf]

*Abstract:*
We present a method for size reduction of two-way multitape automata. Our
algorithm applies local transformations that change the order in which
transitions concerning different tapes occur in the automaton graph, and
merge suitable states into a single state. Our work is motivated by
implementation of a language for string manipulation in database systems
where string predicates are compiled into two-way multitape automata.
Additionally, we present a (one-tape) NFA reduction algorithm that is
based on a method proposed for DFA minimization by Kameda and Weiner, and
apply this algorithm, combined with the multitape automata reduction
algorithm, on our multitape automata.
(Joint work with Matti Nykänen and Esko Ukkonen, presented at CIAA 2005,
LNCS 3845, pp 307-318).

*Kokkuvõte:*
Lineaarne regressioon on levinud statistiline mudel, mis kirjeldab
valjundi `Y` sõltuvust sisenditest `X1, X2, ..., Xn`
lineaarteisendusega `Y = a1 X1 + a2 X2 + ... + an Xn`. Reeglina
valitakse mudeli koefitsendid nii, et need minimiseeriks mudeli viga
valimil. Sellise meetodiga saadavad tulemused pole paljude masinõppimisega
seotud rakendustes rahuldavad. Väikeste valimite korral võib koefitsentide
väärtuste variatsioon olla suur, põhjustades mudeli ennustustäpsuse olulise
languse. Teiseks on raske interpreteerida lineaarset mudeli poolt
kirjeldatud sõltuvusi, kui nullist erinevaid koefitsente on piisavalt
palju.

Mitmete alternatiivsete lineaarse regressiooni algoritmide eesmärgiks on leida parim väheste nullist erinevate koefitsentidega mudel. Ettekandes käsitleme lineaarse regresiooni algoritmide peret LARS. Peaeesmärgiks on näidata, et LARS-i saab dualiseerida - esitada dimensioonist sõltumatute lineaarsete operatsioonide abil. See annab võimaluse kombineerida LARS-i tuumateisendustega, mis omakorda võimaldab kasutada LARS-i oluliste tunnuste automaatsel valikul. (Ühistöö Sven Lauriga).

Ettekande kiled. [pdf]

*Abstract:*
Huet's zipper datatype provides a way for representing trees with a focus
and for refocussing. Attribute evaluation is a form of computation on trees
where a tree is taken into a tree of the same shape where the values at the
nodes are computed uniformly for every node. We show that while the zipper
operations are a tool for describing the computations for each individual
node, the computation on the whole is organized by a comonad structure that
is present in the zipper. (Joint work with Varmo Vene.)

*Abstract:*
We are giving a brief overview of Domain Decomposition methods,
their parallel implementation and performance. We discuss a class
of such methods based on aggregation algorithms for parallel
solution of highly heterogeneous PDEs with strong coefficient
variations. We will outline implementation of the methods in the
DOUG (Domain Decomposition on Unstructured Grids) package. At the
same time we discuss some ideas about implementation of the
methods on computational GRIDs.

Ettekande kiled. [pdf]

*Abstract:*
We show that cyclic structures, i.e., finite or possibly infinite
structures with back-pointers, unrollable into possibly infinite
structures, can be elegantly represented as nested datatypes. This
representation is free of the various deficiencies characterizing the
more naive representation as mixed-variant datatypes. It is inspired
by the representation of lambda-terms as a nested datatype via the de
Bruijn notation.

*Abstract:*
We will show how to study inner structure of the graphs (cliques, minimal
feedback edges aso) and tournaments best ranking problems using some
simple ideas about monotone systems.

Peeter Laud

Helger Lipmaa

Tarmo Uustalu

Varmo Vene

Viimane uuendus 6.02.2006