A-1992-4 Pertti Järvinen, On research into the individual and computing systems. September 1992.
Abstract. In order to improve quality of information systems research we must try to select an adequate research approach. When an information system consists of hardware, software and users, we have to consider every component as research objects. Their behaviour is then important. Hardware and software normally behave deterministicly. We can therefore predict their behaviour. But users do not always behave deterministicly. They have their own will and we cannot predict their behaviour. This may recommend different research approaches for computing systems on one hand and for individuals for the other hand. This fact will be demonstrated by taking two studies: a controlled experiment and a survey, and by considering them from different points of view: a) view of human being, b) horizon, c) dynamic system and d) paradigm. In two studies evaluated here the deterministic view were applied, although the voluntaristic view is considered to be more adequate. The causal models (horizon) were applied, although teleological explanations, hermeneutics and phenomenology seem to be more adequate. The human beings were also considered to behave as nilpotent systems, although the theory of dynamic systems supports such a view that they should be considered as self-steering systems. The meaning paradigm should be preferred instead of the behavioristic paradigm applied in those two studies.
Compressed Postscript
pdf-file.
A-1992-5 Kai Koskimies and Juha Vihavainen, Incremental parser construction with metaobjects. November 1992.
Abstract. The construction of an object-oriented recursive descent parser is studied. A program is modelled by representing each nonterminal symbol as a class. To support interactive, incremental parser construction, it is required that a modification in the definition of a nonterminal has minimal effects on the classes of other nonterminal symbols. An object-oriented parsing method based on metaobjects and lazy recursive descent technique is developed. It is shown that Eiffel allows a pseudo-incremental solution in which the changes propagate only to the next superclass level, while C++ allows fully incremental solution.
Compressed Postscript.
pdf-file
A-1993-1 Esa Järnvall and Kai Koskimies, Language implementation model in TaLE. February 1993.
Abstract.TaLE (Tampere Language Editor) is a specialized program editor for developing implementations of textual languages. The system assumes an object-oriented programming language (currently Eiffel), and supports the development of language implementations following a particular model. The basic object-oriented language implementation model, including integrated methods for lexical analysis, syntactic analysis, name analysis, error recovery, and the construction of an internal (object) representation is discussed. A central requirement implied by the incremental character of the system is that the information concerning the language is distributed among the classes representing structural units of the language (like nonterminals), so that changes in the definition of a particular unit have minimal effects on the classes representing other units. A general method for solving LL(1) parsing conflicts using semantic information is included in the model.
Compressed Postscript.
pdf-file
A-1993-2 Pertti Järvinen, Notes on assumptions of user modelling. March 1993.
Abstract. Conversation, co-operation and mutual understanding are considered in human discourse valuable and important. It is desirable for the flexible, interactive computer dialogue system to exhibit these various features of human discourse. For this, it is crucial that the system contains a user modelling component. Such a component will be used to collect and represent relevant aspects of knowledge about the user. This knowledge normally consists of goals, plans, beliefs and background understanding.
In this paper basic assumptions of goals, plans and beliefs are presented and evaluated. It seems that the system collecting a user's goals, plans and beliefs considers a user as a regularly behaving unit like a machine. Our contribution is to present some alternative views on human being. They may provide a more adequate model of a user. In the same context some means for collecting knowledge of a user are considered to be ethically questionable. Similarly, some warnings to use user models are also presented.
Compressed Postscript.
pdf-file
A-1993-3 Kai Koskimies and Erkki Mäkinen, Inferring state machines from trace diagrams. July 1993.
Abstract. The automatic synthesis of state machines describing the behavior of a class of objects in object-oriented software modeling is studied. It is shown that the synthesis can be carried out on the basis of trace diagrams giving possible sequences of events during the execution of the system. An algorithm originally developed for the automatic construction of programs on the basis of their execution traces is applied to the problem, and an experimental state machine synthesizer is implemented. It is demonstrated that such a synthesizer is a highly useful component in a practical object-oriented CASE system.
Compressed Postscript.
pdf-file
A-1993-4 Esa Järnvall and Kai Koskimies Computer-aided language implementation with TaLE. July 1993.
Abstract. TaLE is a specialized editor for developing language implementations in an object-oriented programming environment. In contrast to conventional language implementation systems, there is no formal metalanguage for specifying a language; instead, the user edits the classes taking part in the implementation under the control of a specialized editor. This editor provides a high-level, partly graphical view of the classes representing language structures. The system supports the reuse and refinement of the language implementation classes, incremental implementation development, integration of syntactic and name analysis, and special views for classes representing standard language features. The expected main advantages of the metalanguageless approach and the graphical user interface are high usability and fast development cycle.
Compressed Postscript.
pdf-file
A-1993-5 Timo Niemi and Kalervo Järvelin, A form-based user interface for NF2 relations and its implementation strategy. November 1993.
Abstract. It has been widely recognized that query formulation in a SQL-like query language extended to the NF2 relational model requires large nested expressions in the context of complex queries. This means that query formulation, from the view point of the user, resembles rather the design of an algorithm than a nonprocedural specification. In this paper we propose a truly declarative user interface which minimizes the user effort in query formulation. In our approach the user describes the form or the structure of the result of the query in a straightforward way without specifying, as usually, those restructuring operations on the basis of which the result is derived from the source NF2 relation. We show that query formulation based on our interface is simple and compact - also in the context of complex queries. In this paper we define a query processing strategy based on this interface. Because our interface has been intended to simplify formulation of complex queries the starting point of our query processing strategy is that existing relationships among data have to be restructred considerably when producing the query result. Our query processing strategy is based on such a calculus which is able to construct an NF2 relation from the representations of atomic-valued attributes or the smallest data units in the NF2 relational model. The data structures allowed by the calculus, called nf2-structures, describe both the schema and instance levels explicitly and bind them together by an indexing mechanism. Therefore our calculus has the pleasant feature that it performs all processing on the schema and instance levels at the same time. We can characterize our approach as an object-based processing strategy because all data processed by the calculus are modelled structurally as objects of type tuple, set, map or tree. We pay also attention to a variety of features in our query processing strategy which support its main memory implementation. A-1993-5 is available as a paper copy only.
A-1993-6 Kari Nieminen, A bi-directional model from an equation to mathematical word problems. December 1993.
Abstract. The aim of this study was to develop a model for the mathematical word problem-solving from logical point of view. Word problems and the underlying equations were shown to be isomorphic.
We studied the relevant theories related to word problem-solving model. First a survey of the history of word problems and corresponding computer programs was conducted. The properties of logic programming as a modelling language was then investigated. The model was developed on the basis of that theoretical groundwork.
The model is relational, and has several abstraction levels. The model is called the TEACHER, because we want to emphasise the similarity of the model and Polya's strategy to teach problem-solving. Questions concerning natural language understanding are not covered. The TEACHER is able to generate exactly those word problems that it is can analyse. Text analysis and text generation of the word problem is done with logic grammars.
The result of this study, a logic based model of mathematical word problem-solving, could be used in different ways. First, the model is a confirmation of Polya's way to teach problem-solving. Second, the model may be used as a starting point for further theoretical development and as a framework for empirical studies of word problem-solving. Third, the TEACHER is a computer program that can be used a basis of an Intelligent Tutoring System.
Compressed Postscript.
pdf-file
A-1993-7 Matti Pettersson, Analysis in analysis. December 1993.
Abstract. Research in cognitive psychology suggest that the concepts human beings use vary across individuals, time and contexts. In this paper we stplications of these findings for system analysis methodologies. These methodologies seem to assume stability and generalizability of mental terrelations of concepts, operations and technology are poorly understood. Based on studies in cognitive psychology, twoclusions are made: First, a theory view of system development is proposed. Seconcepts and the technoopment should be understood as a creativing process.
Compressed Postscript.
pdf-file
A-1994-1 Erkki Mäkinen and Mika Sieranta, Genetic algorithms for drawing bipartite graphs. January 1994.
Abstract. This paper introduces genetic algorithms for the level permutation problem (LPP). The problem is to minimize the number of edge crossings in a bipartite graph when the order of vertices in one of the two vertex subsets is fixed. We show that genetic algorithms outperform the previously known heuristics especially when applied to low density graphs. Values for various parameters of genetic LPP algorithms are tested.
Compressed Postscript.
pdf-file
A-1994-2 Juha Lehikoinen and Erkki Mäkinen, Notes on distance-based coding methods for binary trees. February 1994.
Abstract. This note introduces a new coding method for binary trees in which the code item corresponding to a node equals node's distance from the left arm of the tree according to the metrics defined by the tree. The new coding method is compared with previously known methods. Moreover, we establish a connection between distance-based methods and a recently introduced method by Johnsen.
Compressed Postscript.
pdf-file
A-1994-3 Harri Klemetti, Ismo Lapileimu, Erkki Mäkinen and Mika Sieranta, Trimming the spring algorithm for drawing hypergraphs. February 1994.
Abstract. This paper introduces a practical method for drawing hypergraphs. The method is based on the spring algorithm, a well-known method for drawing normal graphs.
A-1994-3 is available as a paper copy only.
A-1994-4 Maarit Niittymäki, Implementing a PL/M-to-C converter with TaLE. February 1994.
Abstract. A source-to-source converter translating programs from PL/M to C is described. The converter has been implemented with the language implementation system TaLE. Various problems specific to this converter are discussed. The problems are related partly with the particular language pair and partly with the object-oriented implementation tool.
Compressed Postscript.
pdf-file
A-1994-5 Tatu Männistö, Tarja Systä and Jyrki Tuomi, SCED report and user manual. February 1994.
Abstract. This document describes the implementation of an environment - called SCED - to support the dynamic modeling of object-oriented applications. With the SCED system, the user will model an application by specifying scenarios, which are sequences of events occurring during a particular execution of a system. Scenarios are usually given for "normal" cases and for different kinds of "exceptional" cases. SCED can automatically synthesize state diagrams for the participating objects from the event trace information of one or several scenarios.
Creating of scenarios - interaction diagrams, use-cases, event traces as they are called in various object-oriented analysis/design methodologies - is supported by many CASE tools, but few, if any, support automatic generation of state diagrams from a set of scenarios.
The document also describes future research directions where SCED is planned to be extended.
Compressed Postscript.
pdf-file
A-1994-6 Ari Juutistenaho, Linear time algorithms for layout of generalized trees. March 1994.
Abstract. Many layout problems involve n-ary trees with variable-sized vertices. This paper includes linear time algorithms for the layout of such trees. Two algorithms are presented: the first one creates a layout in a simple way, and the second one makes it narrower.
Compressed Postscript.
pdf-file
A-1994-7 Ari Juutistenaho, Linear time algorithm for layout of acyclic digraphs with variable-sized vertices. July 1994.
Abstract. We investigate the problem of representing acyclic digraphs in the plane so that all edges flow from the bottom to the top and the vertices can have variable sizes. This paper includes a linear time algorithm for such a layout.
Compressed Postscript.
pdf-file
A-1994-8 Carl-Erik Wikström, An investigation of factors influencing the success of customer-oriented marketing information systems. November 1994.
Abstract. This research investigates factors influencing the success of marketing information systems. First the utilization of information systems (IS) in marketing is analyzed. In the investigation we use the framework of IS research by Ives, Hamilton and Davis. As a result, major problems and challenges of utilizing ISs in marketing are explicated. We then review research into the measuring of IS success and develop a framework based on both earlier IS success literature and the results of our own investigation into the utilization of ISs in marketing. The extended success framework is used to construct nine research hypotheses, which are then tested in an empirical multiple-case study comprising three cases. Our research findings indicate that researchers should consider including environmental factors in a success model, too. We have also shown how important it is to include the time perspective into the research of IS success. Our observations of the time value of information, the importance of a champion, and the importance of an evolution of Database Marketing culture within the marketing organization, are examples of this. Our research results indicate that practitioners should consider focusing on end-user participation in implementation as well as analyzing the job factors of salespeople first, and then proceed on developing the functions of an IS product so that they better service the needs of the individual marketing and sales professionals. In this way the organizational benefits are easier to achieve, too.
A-1994-8 is available as a paper copy only.
A-1994-9 Erkki Mäkinen, A note on the grammatical inference problem for even linear languages. November 1994.
Abstract. This note introduces subclasses of even linear languages for which there exist inference algorithms using positive samples only.
Compressed Postscript.
pdf-file
A-1994-10 Timo Niemi and Kalervo Järvelin, Prolog-based implementation of a straightforward NF2 relational query interface. November 1994.
Abstract. It has been widely recognized that the proposed user-oriented NF2 (Non-First-Normal-Form) relational query languages such as different SQL extensions are cumbersome to use from view point of an ordinary end-user. This is because the user usually has to formulate large nested expressions in order to specify how the result NF2 relation is derived from the source NF2 relation(s). The NF2 relational query interface in this paper is based on a different approach. In it the user describes only the structure of the result NF2 relation in a straightforward and intuitive way. This starting point of our interface affords the possibility of formulating queries in a compact and truly declarative manner - also in those cases which require considerable restructuring among data. In this paper we consider the Prolog-based implementation of the query processing strategy of our interface. Special attention is paid to those principles and techniques in terms of which the representation and manipulation of complex structural relationships of NF2 relations can be managed in Prolog. The representation of NF2 relations and the query processing strategy have been designed to support main memory oriented implementation.
A-1994-10 is available as a paper copy only.
A-1994-11 Tatu Männisto, Tarja Systä and Jyrki Tuomi, Design of state diagram facilities in SCED. December 1994.
Abstract. Various possibilities to support the automated construction of state diagrams of the OMT method are considered. The proposed facilities are planned to be included in a prototype environment whose basic components are editors for scenarios and state diagrams. The considered support covers automatic means for synthesizing a state diagram on the basis of scenarios, for making the state diagram as compact as possible, for determining a satisfactory layout for the state diagram, and for maintaining consistency between scenarios and state diagrams. The propotype environment - called SCED - currently supports editing of scenarios and automatic synthesis of state diagrams.
Compressed Postscript.
pdf-file
A-1995-1 Jyrki Nummenmaa Designing desirable database schemes. April 1995.
Ph. D. Thesis. Abstract not available.
A-1995-1 is available as
a paper copy only.
A-1995-2 Eija Kujansuu, Tuukka Lindberg and Erkki Mäkinen, The stable roommates problem and chess tournament pairings. April 1995.
Abstract. In many chess tournaments the number of players is much larger than the number of rounds to be played. In such tournaments the Swiss pairing system is usually used. This means that players with equal or almost equal scores so far are played against each others. Moreover, each player should alternately have, if possible, white and black pieces, and every pair of two players is allowed to play at most once against each others. This paper shows how the well-known stable roommates algorithm can be used to determine the pairs in a pairing system similar to the Swiss system.
Compressed Postscript.
pdf-file
A-1995-3 Aulikki Hyrskykari, Development of program visualization. April 1995.
Abstract. The last decade has been a very active period of designing systems for program visualization. Without proper means for describing and evaluating both existing and new systems further development may be delayed. Recently, several researchers have been working for creating
taxonomies for program visualization systems. During the active period of system development benefits of visualization were often praised without criticism, and scientific references were rarely presented. What do we really know about the usefulness of program visualization?
We first present the terminology and the state of the work for developing a taxonomy for the discipline. Moreover, we review the existing empirical studies on the benefits of graphical presentation of programs. We also give a reference list to the existing program visualization systems.
Compressed Postscript.
pdf-file
A-1995-4 Liisa Räihä, Note on approximate comparison of sequences with normalization. July 1995.
Abstract. The edit distance is a measure e.g., to classify a sequence to a correct word or concept. Often, particularly with editing errors, the edit distance measures are linearly dependent on the lengths of their parameter sequences. The normalized distances are an attempt to remove this dependency. In this work we show adjustments to the algorithms of Marzal and Vidal for the computation of the normalized distances.
Compressed Postscript.
pdf-file
A-1996-1 Kai Koskimies, Tatu Männistö, Tarja Systä, and
Jyrki Tuomi,
On the role of scenarios in object-oriented software design.
January 1996.
Abstract.
Scenario diagrams are a graphical notation for
describing the interaction of a set of collaborating
objects. We study the relationships between scenarios
and other models used in object-oriented software development,
in particular dynamic model and static object model. These
relationships are significant for improving various
consistency checks between the different models and for
developing automated support for model synthesis.
Compressed Postscript.
pdf-file
A-1996-2 Isto Aho, Erkki Mäkinen and Tarja Systä,
Remarks on the thickness of a graph. March 1996. Revised March 1997.
Abstract.
The thickness of a graph is the minimum number of planar subgraphs
into which the graph can be decomposed. This note discusses on
some recent attempts to determine upper bounds for the thickness
of a graph as a function of number of edges or as a function
of maximum degree.
Compressed Postscript.
pdf-file
A-1996-3 Maarit Harsu, Automated construction of
source-to-source translators. March 1996.
Abstract.
In this work, source-to-source translation and automated construction
of source-to-source translators are considered. Various general
problems related to source-to-source translation are discussed, e.g.
conflicting requirements of a source-to-source translator. An
experimental translator converting PL/M programs into C has been
developed using the language implementation framework TaLE. The
problems associated with the mapping of PL/M constructs into C are
discussed, and a technique for reducing the space requirements of
converting large PL/M programs is presented. A-1996-3 is available
as a paper copy only.
A-1996-4 Kai Koskimies, Tatu Männistö, Tarja Systä, and
Jyrki Tuomi, SCED: A tool for dynamic modelling of object systems.
July 1996.
Abstract. Dynamic modeling of object-oriented software makes use of
scenario diagrams, i.e. descriptions of particular uses of a system
in terms of message flow between the objects belonging to the system.
Such diagrams help the designer the specify the general behavior of
objects as state machines or as collections of methods. Several
techniques are discussed for building automated tool support for the
dynamic modeling aspects of object-oriented software development.
The discussed techniques include synthesis of state machines and
method descriptions on the basis of scenario diagrams, constructing
scenario diagrams with the support of existing state machines,
visualizing the run-time behavior of an object system, extracting
state machines of objects from running systems, consistency checking
between scenario diagrams and state machines, automated simplification
of state machines using OTM notation, and automated layout for state
machines.
Compressed Postscript.
pdf-file
A-1996-5 Roope Raisamo and Kari-Jouko Räihä,
Techniques for Aligning Objects in Drawing Programs. August 1996.
Abstract. Object alignment is one of the basic operations
in drawing programs. Current solutions provide mainly three ways for
carrying out this
operation: either by issuing an alignment command, or by using direct
positioning with the help of gravity active points, or by making use of
constraints. The first technique has limited functionality, and the other
two may be mysterious for a novice. We describe here a new direct
manipulation tool for alignment. We show that while direct manipulation
helps to make the tool intuitive, it has through iterative design evolved
into a tool that also offers functionality not found in current commercial
products.
Compressed Postscript.
pdf-file
A-1996-6 Erkki Mäkinen and Ferucio Laurentiu Tiplea,
Pattern ambiguities for pure context-free grammars. August 1996.
Abstract. We consider here some special forms of ambiguity for pure
context-free grammars, namely pattern avoiding ambiguity, pattern
preserving ambiguity,pattern ambiguity, and grammar avoiding ambiguity.
The first two properties are undecidable for arbitrary pure context-free
grammars, and in a particular but general enough case we can effectively
decide whether or not a pure context-free grammar is pattern preserving
ambiguous.
Compressed Postscript.
pdf-file
A-1996-7 Isto Aho, Harri Klapuri, Jukka Saarinen and Erkki Mäkinen,
Optimal load clipping with time of use rates. October 1996.
Abstract. We present four heuristical algorithms and one
suboptimal method based on dynamical programming for cutting the
overload in electricity consumption. The dynamic successive programming
method were developed to work with "time of use rates" (i.e., to work
with hourly buying and selling rates of electricity). Our dynamic
programming method optimizes one load at a time and uses states
sparingly. Gained time savings are 50-90\%, depending on the
difficulty of the clipping situation, compared to methods not using
state saving. The heuristic methods are still very much faster than
the methods based on dynamical programming. Tests show that these
algorithms are well suited for their purpose. A-1996-7 is available
as a paper copy only.
A-1996-8 Ferucio Laurentiu Tiplea and Erkki Mäkinen,
Jumping Petri nets. Specific properties. October 1996.
Abstract.
A Jumping Petri Net [Tiplea and Jucan, Jumping Petri nets, Foundations
of Computing and Decision Science 19 (1994); Jucan, Masalagiu and
Tiplea, Relation based controlled Petri nets, Scientific Annals of the
"Al. I. Cuza" University], JPTN for short,
is defined as a classical net which can spontaneously jump from a marking to
another one. In [Tiplea and Jucan] it has been shown that the
reachability problem for
JPTN's is undecidable, but it is decidable for finite JPTN's (FJPTN).
In this paper we establish some specific properties and
investigate the computational power of such nets, via the
interleaving semantics. Thus, we show that
the non-labelled JPTN's have the same computational power as the
labelled or \lambda-labelled JPTN's.
When final markings are considered, the power of JPTN's equals the power
of Turing machines.
The family of regular languages and the family of languages generated by
JPTN's with finite state space are shown to be equal.
Languages generated by FJPTN's can be represented in
terms of regular languages and substitutions with classical Petri
net languages. This characterization result leads to many important
consequences, e.g. the recursiveness (context-sensitiveness, resp.)
of languages generated by arbitrarily labelled (labelled, resp.)
FJPTN's.
A pumping lemma for nonterminal jumping net languages is also
established. Finally, some comparisons between families of
languages are given, and a connection between FJPTN's and
a subclass of inhibitor nets is presented.
Compressed Postscript.
pdf-file
A-1996-9 Erkki Mäkinen, Inferring uniquely terminating
regular languages from positive data. November 1996.
Abstract.We define a new subclass of regular languages,
called uniquely terminating regular languages, which can be inferred
from positive data. The class of uniquely terminating regular
languages and the previously known subclasses of regular languages
inferable from positive data are incomparable.
Compressed Postscript.
pdf-file
A-1996-10 Timo Eloranta and Erkki Mäkinen,
TimGA - A genetic algorithm for drawing undirected graphs.
December 1996.
Abstract.
The problem of drawing graphs nicely contains several computationally
intractable subproblems. Hence, it is natural to apply genetic
algorithms to graph drawing. This paper introduces a genetic
algorithm (TimGA) which nicely draws undirected graphs of moderate
size. The aesthetic criteria used are the number of edge crossings,
even distribution of nodes, and edge length deviation. Although TimGA
usually works well, there are some unsolved problems related to the
genetic crossover operation of graphs. Namely, our tests indicate
that TimGA's search is mainly guided by the mutation operations.
Compressed Postscript.
pdf-file
A-1997-1 Marja Vehviläinen, Gender, expertise and
information technology. March 1997.
Ph. D. Thesis.
Abstract
This book explores the interwoven construction of gender, expertise, and information technology by starting from three positions of information systems development in Finland -- male computing pioneers' autobiographical accounts, women developers' oral histories, and an office workers' study circle with related interviews -- and, fourthly, from the codes of ethics of international computing professionals' associations ACM and IFIP. By applying Dorothy Smith's theory of conceptual practices of power, information technology is understood as textuality in which texts, e.g. programs, professional journals and electronic messages, are produced and interpreted through people's particular practices and by using particular knowledges of information technology. Both practices and knowledges -- the expertise of information technology -- are organized within materially-based social relations. Gender intertwines with information technology through social practices. Gender is studied on the level of social -- often textually mediated -- relations, in terms of gendering hierarchies and divisions of labour, but also -- inspired by Donna Haraway -- at the level of subjectivity, in terms of definitions of information technology made by subjects. The second major aim of this work is to participate in the development of methodologies on gender and technology research.
The study pays attention to persistently male tendencies of information technology but it looks for spaces available for women as well. The computing professions inherited strict gender hierarchies from the punched card systems of the 1950s, and those were strengthened by fraternities of former army acquaintances, in everyday practices of systems development, in public worlds of professional journals and associations, as well as within images of identity. In this setting, the view of male experts and managers gained a status of objective truth. In the 1970s and 1980s, the ideas of flexible management and work design made space for participatory approaches towards systems design. At the same time, large numbers of women entered information technology professions in Finland. Yet, that view of objective truth has not been thoroughly challenged, and there has been little room for textualities developed from women's or any other particular groups' standpoints within information technology expertise. People such as office workers can develop technologies based on their everyday life situations, and this is a real opportunity for challenging both the gendering and the expertise of technology. However, the work done in particular settings does not translate to publicly available textuality.
A-1997-1 is available as a paper copy only.
A-1997-2 Erkki Mäkinen, Ranking and unranking left Szilard
languages. January 1997.
Abstract. We give efficient ranking and unranking algorithms
for left Szilard languages of context-free grammars. If O(n^2) time and
space preprocessing is allowed then each ranking operation is possible
in linear time. Unranking takes time O(n log n). These algorithms imply
similar algorithms for context-free languages generated by arbitrary
unambiguous context-free grammars.
Compressed Postscript.
pdf-file
A-1997-3 Juha Hautamäki, A survey of frameworks.
March 1997.
Abstract. A framework is tool to improve the software developing
process. It is a reusable design expressed as a set of abstract classes
and the way their instances collaborate. With frameworks, application
developers don't have to start from scratch each time they write an
application. Instead they specialize framework's behavior to suit
the current problem by extending and refining its classes and operations.
The purpose of this paper is to give an overview of frameworks as well as
tools and methods supporting their use and design.
Compressed Postscript.
pdf-file
A-1997-4 Erkki Mäkinen, On lexicographic enumeration of
regular and context-free languages. March 1997.
Abstract. We show that it is possible to efficiently
enumerate the words of
a regular language in lexicographic order. The time needed for
generating the next word is O(n) when enumerating words of
length n. We also define a class of context-free languages
for which efficient enumeration is possible.
Compressed Postscript.
pdf-file
A-1997-5 Isto Aho, Properties of dynamic programming used
in load clipping. April 1997.
Abstract.
We analyze a dynamic programming solution for cutting the overload in
electricity consumption. We are able to considerably improve the earlier
algorithms presented in the literature. Our improment makes the method
practical so that it can be used more often or, alternatively, new state
variables can be added into the state space to make the results more accurate.
We also propose a way to add a new state variable to the system.
A-1997-5 is available as a paper copy only.
A-1997-6 Erkki Mäkinen, Inferring regular languages
by merging nonterminals. May 1997.
Abstract.
Several subclasses of regular languages are known to be inferable
from positive data only. This paper surveys classes of languages
originating from the class of reversible languages. We define
the classes by using a uniform grammatical notation.
Compressed Postscript.
pdf-file
A-1997-7 Maarit Harsu, Automated conversion of PL/M to C.
July 1997.
Abstract.
This paper describes an implementation of a converter translating PL/M
programs into C. The purpose of the document is to help possible
modifications to the converter. Thus, the implementation of the converter is
tried to describe as exactly as possible.
Some basic concepts used in this paper are defined as follows. The term
compiling means translation from a high-level language to a low-level
language. The term conversion means translation from a high-level language
to another high-level language. The term translation covers all the cases
such that both the source and target languages can be of any level.
Source-to-source translation is a synonym for conversion.
Conversion between high-level languages is different from compiling into a
low-level language. In some cases conversion is easier than compiling and in
some other cases the situation is the opposite. The difficulties in
implementing the translation of some language structures are associated with
the difference between compiling and converting. This document basically
concentrates on the difficult parts in translation, and the most obvious
parts have not even been mentioned.
The converter consists of two parts: the preprocessor and the actual
converter implemented with TaLE (Tampere Language Editor). TaLE is a language
implementation tool for object-oriented environments. Because of the
implementation tool, the translation code of the converter is written in an
object-oriented language, C++. The input programs of the converter are
assumed to be correct PL/M programs. However, TaLE gives error messages
about syntax errors.
A-1997-7 is available as a paper copy only.
A-1997-8 Tarja Systä, Automated support for constructing OMT
scenarios and state diagrams in SCED. August 1997.
Abstract.
Dynamic modeling of object-oriented software using OMT notation
is considered. The modeling starts by constructing scenarios,
i.e. descriptions of the interactions of a set of objects and actors
during a particular usage of a system.
The spesification of the dynamic behavior is defined using state diagrams,
which are composed on the basis of information given by scenarios.
Notations used for dynamic modeling in OMT, UML, and SCED are introduced.
Various techniques are discussed for building automated tool support
for the dynamic modeling aspects of object-oriented software development.
The discussed techniques include synthesis of a state diagram using
information given in scenarios, optimization of a synthesized
state diagram by generating OMT state diagram notation for it, and generation
of scenarios by animation communication between state diagrams.
Concurrency and aggregation in OMT state diagram notation is considered,
as well as possibilities to include it also to SCED. Consistency between
scenarios and state diagrams in SCED is discussed. A-1997-8 is
available as a paper copy only.
A-1997-9 Timo Niemi and Kalervo Järvelin,
Constructor-oriented query processing strategy for NF2 relational
queries: Part I. Implementation on top of a relational database.
August 1997.
Abstract.
It has been widely recognized that in the context of relational databases
the user often wants to see the result of his query as an NF2 relation
instead of a 1NF relation. However, user-oriented, mainly SQL-like query
languages developed so far are cumbersome to use. This is due to the
fact in the context of the NF2 relational model the user has to specify
large nested expressions containing restructuring operations. Likewise,
several query languages developed for object-oriented databases support
the construction of NF2 relations. However, in these languages the user
has to specify and nest complicated constructor expressions. We have
developed an NF2 relational query interface, called the FRC-interface,
which is both expressive and at a very high abstraction level. In this
paper we study how the FRC-interface can be implemented by applying
constructors automatically so that the user need not to be aware of the
existence of constructors at all.
The core of the implementation is the so-called NF2 object calculus
in terms of which an NF2 relation (an NF2 object) can be constructed from
atomic-valued attributes (NF2 objects). In the representations of NF2
objects we use only constructors of type tuple, set, tree and map. Both
the schema and instance levels are represented on the basis of them. Our
query processing strategy is implemented on top of an existing relational
dbms (database management system). In it the underlying relational dbms
need not be modified in any way. A-1997-9 is
available as a paper copy only.
A-1997-10 Timo Niemi and Kalervo Järvelin,
Constructor-oriented query processing strategy for NF2 relational
queries: Part II. Implementation based on constructor-oriented
representations of NF2 relations. August 1997.
Abstract.
In many applications it is appropriate to store an NF2 relation as a
whole. We show that the constructor types of our constructor-oriented
approach afford the possibility of storing an NF2 relation as a whole
in a natural and systematic way. On the basis of the constructor-
oriented representation developed for NF2 relations the implementation
of the FRC-interface is given. Here query processing is considerably
more demanding than in Part I. This is because the query processing
strategy must have the capability for complex data restructuring
including compressions, expansions, mergings and inversions of
hierarchical levels. Further, unlike in Part I, query processing must
be totally performed without the query evaluation mechanism of a
relational dbms. The query processing strategy is defined purely in
terms of constructor expressions and in this context we introduce
a.o. a constructor-oriented way to evaluate conditions. In the paper
the query processing strategies for manipulating both a single and
several NF2 relations are given. A-1997-10 is
available as a paper copy only.
A-1997-11 Kalervo Järvelin and Timo Niemi, Integration of
complex objects and transitive relationships for information
retrieval. November 1997.
Abstract.
In this paper we show that in advanced information retrieval (IR)
applications capabilities for data aggregation, transitive computation and
NF2 (non-first normal form)relational computation are often necessary. We
demonstrate that complex objects are naturally modeled as NF2 relations
whereas structures like hierarchical thesauri and citation networks must be
modeled for transitive computation. Transitive processing cannot be
supported by structurally static structures like NF2 relations. We present
a truly declarative query interface which integrates data aggregation,
transitive computation and NF2 relational computation. Thus the interface
supports the retrieval and structural manipulation of complex objects
(e.g., documents, bibliographic references), their retrieval through
transitive relationships (e.g., thesauri, citations) and data aggregation
based on their components (e.g., ci-tation counts, author productivity).
Most importantly, users can formulate queries on a high abstraction level
without mastering actual programming or database techniques. A-1997-11 is
available as a paper copy only.
A-1997-12 Markku Hakala, Juha Hautamäki, Jyrki Tuomi,
Antti Viljamaa and Jukka Viljamaa, Design of a Java Framework Engineering
Tool. November 1997.
Abstract.
Frameworks are reusable designs used to improve the software development
process. This report presents a plan to implement the FRED (Framework Editor
for Java - Support for Framework Development and Use) tool set for designing
and using frameworks. FRED is a joint project between the departments of
Computer Science at the University of Helsinki and at the University
of Tampere,
supported by TEKES and several Finnish industrial partners.
Keywords: Frameworks, Design patterns, CASE Tools.
Compressed Postscript.
pdf-file
A-1997-13 Maarit Harsu, Translation of conditional compilation.
November 1997.
Abstract.
This paper describes how to translate the compiler directives for conditional
compilation in automated source-to-source translation between high-level
programming languages. The directives for conditional compilation of the
source language are translated into the corresponding directives of the
target language, and the source program text of each branch of conditional
compilation is translated into the corresponding target program text. Such
translation raises a problem in conventional parsing because the source text
is not a continuous stream of tokens of a legal program but rather a
sequence of fragments that must be combined in certain ways to obtain one
of several possible alternative programs. As a solution to this problem, a
parsing technique is introduced which is able to cope with such input if
certain reasonable conditions are satisfied.
Compressed Postscript.
pdf-file
A-1997-14 Takeshi Koshiba, Erkki Mäkinen, and
Yuji Takada, Inferring pure context-free languages from positive data.
December 1997.
Abstract.
We study the possibilities to infer pure context-free langauges from
positive data. We can show that while the whole class of pure
context-free languages is not inferable from positive data, it has
interesting subclasses which have the desired inference property.
We study uniform pure languages, i.e., languages generated by pure
grammars obeying restrictions on the length of the right hand sides
of their productions, and pure languages generated by deterministic
pure grammars.
Compressed Postscript.
pdf-file
A-1997-15 Isto Aho, Harri Kemppainen, Kai Koskimies, Erkki
Mäkinen and Tapio Niemi, Searching neural network structures
with L systems and genetic algorithms.
December 1997.
Abstract.
We present a new method for using genetic algorithms
and L systems to grow up efficient neural network structures.
Our L rules operate directly on 2-dimensional cell matrix.
L rules are produced automatically by genetic algorithm
and they have ``age'' that controls the number of firing times,
i.e. times we can apply each rule.
We have modified the conventional neural model so that it is easy to
present the knowledge by birth (axon weights) and the
learning by experience (dendrite weights).
A connection is shown to exist between the axon weights and
learning parameters used e.g. in back propagation.
This system enables us to find special structures that
are very fast for both to train and to operate comparing to
conventional, layered methods.
Compressed Postscript.
pdf-file
A-1998-1 Marko Junkkari and Marko Niinimäki,
An algebraic approach to Kauppi's concept theory. January 1998.
Abstract. The aim of this paper is to represent concept
systems algebraically.
We discuss concepts and their intensions, a formal concept system and
its operations, and a description of how the operations and some basic
notions can be represented in algebra. This approach enables us to
handle the formal conceptual level of a representation system in an
established and well-known formalism.
A-1998-1 is available as paper copy only.
A-1998-2 Erkki Mäkinen,
Binary tree code words as context-free languages. January 1998.
Abstract.
Given a binary tree coding system, the set of valid
code words of all binary trees can be considered as a
context-free language over the alphabet used in the
coding system. The complexity of the language obtained
varies from a coding system to another.
Xiang, Tang and Ushijima have recently proved some
properties of such languages. We show that their
results can be more easily proved by noticing the
form of the generating grammar in question. Namely, in the
most simplest cases the language obtained is a left
Szilard language, a very simple deterministic
language. Moreover, we prove some new results
concerning the ``binary tree languages''.
Compressed Postscript.
pdf-file
A-1998-3 Erkki Mäkinen,
Generating random binary trees - A survey. March 1998.
Abstract.
This paper surveys algorithms for generating unbiased random binary trees.
There exist several linear time algorithms. The best algorithms use
only integers of size O(n) to generate binary trees on n nodes.
Compressed Postscript.
pdf-file
A-1998-4 Marko Junkkari and Marko Niinimäki,
A Path-Oriented Approach to Hierarchical Concept Structures. April 1998.
Abstract.
There are many principles to present a hierarchy of knowledge units
i.e. concepts. A concept hierarchy exists on a set of concepts and it
is based on a partial order relation. The set of concepts and the
relation among these form a concept system. The purpose of this paper
is to present a method and functions for inspecting the structure of a
concept system and to provide a classification of typical structures.
Understanding the structure of a concept system is vital when one
considers the utilisation of a concept system. The most common concept
structures include trees, different lattices and semilattices. In order
to utilise the operations for any type of a structure, it is important
to recognise the structure. Our contribution here is to present a set
of functions to recognise typical structures and to form a principle for
classification of hierarchical concept structures. Here, the concept
structures are represented on the basis of set theory, which is a
well-known and established formalism. We introduce a path-oriented
method that enables accurate and clear consideration of different structures.
Compressed Postscript.
pdf-file
A-1998-5 Erkki Mäkinen,
Constructing a binary tree efficiently from its traversals. April 1998.
Abstract.
In this note we streamline an earlier algorithm for constructing
a binary tree from its inorder and preorder traversals. The new
algorithm is conceptually simpler than the earlier algorithms
and its time complexity has a smaller constant factor.
Compressed Postscript.
pdf-file
A-1998-6 Maarit Harsu,
A survey of object identification in software re-engineering. April 1998.
Abstract.
In order to translate a non-object-oriented (procedural) program into an
object-oriented one, objects
must be identified from the procedural program. Object-oriented programs
(compared with procedural ones) are considered to be easier to reuse and
maintain. Thus, object identification followed by translation from a
non-object-oriented language into an object-oriented language is one way to
re-engineer legacy
programs. This paper gives an overview of re-engineering in general and
of object identification especially. Associated with object-orientation,
identification of (design) patterns is discussed, too.
Compressed Postscript.
pdf-file
A-1998-7 Erkki Mäkinen,
On inferring zero-reversible languages. August 1998. Revised October 1998.
Abstract.
We use a language-theoretic result for zero-reversible
languages to show that
there exists a linear time inference method for this class of
languages using positive data only.
Compressed Postscript.
pdf-file
A-1998-8 Maire Heikkinen and Saila Ovaska,
Lotus Notes in a software house: a case study of experiences and
change impacts. October 1998.
Abstract.
We present a case study of the experiences gained of in-house
Lotus Notes application development in a software house which
is also involved in Notes application development for customers.
The software house SF (a pseudonym) is one of the first Notes
application developers in Finland. The time range of data
collection for this report is 1992-1994, and we describe findings
of early adopters of groupware technology. In SF almost all
internal operational applications are implemented as Lotus Notes
applications, deliberately testing the limits of the software as
application generation platform.
The findings of this study base on a log analysis of actual use
activity, and questionnaires filled in by the workers of SF.
The gains of deploying Notes in SF seem to resemble those of any
other organisation: better communication, easier information sharing,
reduced output on paper. The change impacts of Notes applications
are discussed in three main areas: customer relations, groupwork,
and organisational relations.
A finding of the study not brought up in previous literature is that
the company has used Notes also in application development areas
where it is found not fit well by some informants. Some of the
applications developed are too complex for the task at hand, or
prematurely taken into production use. The problems seem to relate
to the Notes infrastructure enabling fast application development.
Still, some problems are due to the lack of a corporate policy in
developing and using the applications, which was also noted by the
informants.
A-1998-8 is available as paper copy only.
A-1998-9 Lauri Forsman and Markku J. Penttinen,
Investment and risk management analysis of proactive as against
reactive network maintenance. October 1998.
Abstract.
This study analyses the factors affecting investment decisions concerning end-user support (EUS), which is even more complex than that of centralised data processing (DP). The alternatives of proactive and reactive end-user support (EUS) in a modern LAN environment are compared by analysing the failure risk of one specific component (HUB) of the LAN. The additional preventive actions and management costs are considered as well. Both proactive and reactive EUS are analysed in terms of investment and risk management. Arguments for and against enhanced support capability and a fault tolerant system structure are sought for optimising risk/spending levels. The reliability theory with its demand patterns demonstrated by electronic components has been used in the spirit of inventory-production theory in order to quantify the risk both with deterministic and random failure intensity parameters.
Exact Bayesian tests have been developed in order to evaluate the two vendor MTBF figures, only the first of which turns out to match the observation. Bayesian posterior failure distribu-tions have been estimated both in the deterministic and random failure intensity cases, the last of which results in a binomial distribution with an annual mean of 16 HUBs and a standard deviation of 4 HUBs. The cost parameters estimated by NOKIA from the field have been used, and the costs of alternative policies have been assessed.
The annual expected reactive cost, with a lower hourly developer cost option of kFIM 563, exceeds the annual proactive cost of kFIM 552. An additional investment, i.e. systems for network monitoring equipment of kFIM 210 with a three-year pay-back period can be recommended. However, the expected reactive cost would not carry the investment where proactive policy would require an additional management effort compared with the reactive one. The additional preventive actions, costing kFIM 672 annually, could be covered only by assuming that developer capacity is a sales-limiting facxtor.
Recommendations and sensitivity considerations can easily be provided for the day-to-day decision-making of IT and SBU management, using the developed calculation models with updated cost and failure statistics data. A key notion of the study is to develop a management tool for NOKIA's DP management.
Keywords: Investment planning, reliability, fault tolerance, DP management, management policy.
Compressed Postscript.
pdf-file
A-1998-10 Hannu Kangassalo,
Are global understanding, communication, and information management
in information systems possible? A conceptual modelling view - Problems
and proposals for solutions. November 1998.
A-1998-10 is available as paper copy only.
A-1998-11 Erkki Mäkinen,
On inferring linear single-tree languages. November 1998.
Abstract.
We consider the inferability of linear single-tree languages.
We are able to show that if the terminal productions of the
corresponding grammars obey a simple restriction, then the
languages generated are inferable from positive samples only.
Moreover, we solve an open problem posed by Greibach, Shi, and
Simonson concerning the unambiguity of certain ultralinear STG's.
Compressed Postscript.
pdf-file
A-1998-12 Marko Junkkari and Marko Niinimäki,
Functional representation of Kauppi's concept operations and concept
associations.
November 1998.
Abstract.
In conceptual modelling we need exact and systematic methods and
equipment to find a relevant and an accurate model of the Universe
of Discourse. To manage concepts we need relations and operations
that associate them. In this paper, we present the covering set of
associate relations and concept operations. By using these we can
search concepts that are in some way in association with one or
several concepts in a concept system. The main associations with
two or several concepts are compatibility and comparability.
The operations and relations that we present here are based on Kauppi's
concept theory. There is only one two-placed basic relation in
Kauppi's theory, the relation of intensional containment.
We use set theory as the meta-language for concept theory,
since set theory is an established and well-known manner for
formal representation in computer science. Using set theory,
we build functions, some of which utilise paths in sets of
concepts. By using this approach we also create a system for an
explicit representation of Kauppi's theory.
Compressed Postscript.
pdf-file
A-1998-13 Marko Junkkari,
The modeling primitives for component relationships and a `design by
examples' method. December 1998.
Abstract.
In this paper we present essential primitives for abstraction of
relationships among composed objects and their components. We start
out from modality and then present whether an object, by nature,
occurs only in some specific construct or whether it is an independent
one. These approaches are well-known in many areas of computer science,
but the integrated and exact systematic presentation of these is
generally lacking, especially in modeling approaches for component
based systems. We represent a 'design by example' method for modeling
and designing an abstraction from single component structures of objects.
This approach enables us to modify the object type structure during
the designing process. Primitives of modeling methods are generally
defined only on graphical level, but more accurate presentation is
needed because the result of this modeling analysis gives input for
detailed design and implementation. For this reason, our definitions
are based on an exact and implementation-independent presentation
language, that is, set theory.
Compressed Postscript.
pdf-file
A-1998-14 Jyrki Nummenmaa,
Functional dependencies in a hierarchical conceptual model. December 1998.
Abstract.
The database design often gets its input from a
conceptual design process. The outcome of the process should somehow
be used as the input for database design. For this, it is necessary to
use methods to produce the necessary data for database
design for the particular database model being used. We will define a
hierarchical conceptual modelling language which has two types of relationships
between concepts (aggregation and generalisation) and other constructs
(cardinalities, concept primary keys and concept functional dependencies)
to describe the conceptual schema. We show how functional dependencies
for relational database design can be produced from a conceptual
schema, assuming the conceptual schema meets certain conditions.
The conceptual modelling language is based on the use of
graph theory. Care is taken to ensure compatibility between the
conceptual model and relational dependency theory. We also use relational
dependency theory to operate with the conceptual model.
A-1998-14 is available as paper copy only.
A-1998-15 Timo Niemi, Marko Junkkari and Kalervo Järvelin,
Deductive object-oriented approach to systems analysis and its
representation with the set theory. December 1998.
Abstract.
In next generation information systems it is necessary to combine
data-oriented, behavioral and deductive aspects. In this paper we introduce
a deductive object-oriented modeling method (DOOM) which takes into account
these aspects and integrates them seamlessly with each other.
Object-orientation in itself is a powerful tool for organizing both
relationships and behavior among related data. Therefore our approach is
based on the incorporation of deductive aspects to object-orientation.
Unlike the existing object-oriented modeling methods, we develop a way
based on set theory to represent the result of systems analysis precisely.
Set theory affords the possibility of representing the application domain
of interest without any reference to implementation issues. It is obvious
that in next generation information systems complex (often deductive) and
large specifications have to be to embedded in application specific
structures and concepts which are available to the user for facilitating
query formulation. The detection and specification of this kind of
information means a new challenge for analysis methods. In the paper we
show that the modeling primitives of our modeling method can represent this
kind of information in a natural way.
A-1998-15 is available as paper copy only.
A-1999-1 Roope Raisamo and Kari-Jouo Räihä,
Design and evaluation of the alignment stick. January 1999.
Abstract.
Object alignment is one of the basic operations in drawing programs. Current
solutions provide mainly three ways for carrying out this operation: either
by issuing an alignment command, or by using direct positioning with the
help of gravity active points, or by making use of constraints. The first
technique has limited functionality, and the other two may be mysterious for
a novice. We describe here a new direct manipulation tool for alignment. We
show that while direct manipulation helps to make the tool intuitive, it has
through iterative design evolved into a tool that also offers functionality
not found in current commercial products. We also report on an experiment in
which we compared the ease of use, intuitiveness, learnability, and
efficiency of alignment menus, palettes and the alignment stick. Finally, we
discuss our experiences in the two-handed control of the alignment stick and
report on other interesting findings in our experiment.
Compressed Postscript.
pdf-file.
A-1999-2 Yrjö Auramo,
Construction of an expert system to support otoneurological vertigo
diagnosis. February 1999.
Abstract.
Otoneurology is a diverse and difficult medical field in respect
to decision making and diagnostics. The cause of many diseases
involving vertigo is unknown, and the decision-making has to be
based on case history, signs, and results of otoneurologic,
audiologic, imaging and serologic tests. Three expert systems
for vertigo have been described so far.
Typical rule-based expert systems have some difficulties when
applied to medical expert systems. These facts are discussed in
the introduction and they are the basis of the reasons why a
novel method was introduced. The method used is described in
detail in the following six papers.
In this thesis the construction of an otoneurological expert
system ONE examined. The results of the classification are
compared with another expert system and with a group of mainly
junior physicians of otolaryngology.
Minor weak points of ONE are discussed and some enhancement
ideas are presented for future improvement. Ph.D. Dissertation.
A-1999-2 is available as paper copy only.
A-1999-3 Erkki Mäkinen,
Inferring finite transducers. February 1999.
Abstract.
We consider the inference problem for finite transducers using different
kinds of samples (positive and negative samples, positive samples only,
and structural samples). Given pairs of input and output words, our task is to
infer the finite transducer consistent with the given pairs. We
show that this problem can be solved in certain special cases by
using known results on the inference problem for linear languages.
Compressed Postscript
pdf-file.
A-1999-4 Marko Niinimäki,
Understanding the semantics of conceptual graphs. March 1999.
Abstract.
In this paper, we propose a simple and well established semantics for
conceptual graphs. This model theoretic semantics
is an alternative to previous approaches, where
a game theoretical semantics has been suggested. In addition to that,
we thoroughly compare conceptual graphs with First Order Predicate
Logic (FOPL). The comparison is based on semantics. Based on
this comparison, we present some clarifying remarks on the
semantics of conceptual graphs.
The comparison of the expressive power of FOPL and conceptual
graphs is carried out by a consideration of translation algorithms.
John Sowa's algorithm
translates an arbitrary conceptual graph into a
FOPL formula. The algorithm that we shall outline in this paper
translates an arbitrary closed FOPL formula
into a conceptual graph. On the basis of the algorithms,
it can be claimed that
the expressive power of conceptual graphs (with limited syntax)
equals to that of a slightly limited FOPL.
Without the syntactic limitations, the
expressive power of conceptual graphs would probably exceed the expressive
power of FOPL.
We also provide a set of knowledge representation examples using
both FOPL and conceptual graphs.
The examples indicate that in some cases conceptual graph formalism
is harder to read than FOPL.
Compressed Postscript
pdf-file.
A-1999-5 Isto Aho, Interactive knapsacks. March 1999.
Abstract.
The interactive knapsack problems are generalizations of the
classical knapsack problem. Three different new NP-complete problems,
IKHD, IKD and MDCS, are presented for the interactive knapsack models,
which are also new. IKD and MDCS are shown to be strongly NP-complete.
By using interactive knapsacks we model many planning and scheduling
problems in an innovative way. We show Interactive
knapsacks to have several applications, for example, in electricity
management, single and multiprocessor scheduling and packing of
two, three and n dimensional items to different containers. Many
natural problems related to interactive knapsacks are NP-complete.
We apply interactive knapsacks to load clipping used in electricity
management in detail.
Specifically, we implement several heuristic methods, dynamic
programming, enumerative and genetic algorithms for solving
the load clipping problem. The enumerative method and dynamic programming
are slow while heuristics and genetic algorithms are faster.
The dynamic programming gives best results in reasonable time and
genetic algorithms often outperform heuristics. Heuristics, however,
are several times faster than the other methods.
Compressed Postscript
A-1999-6 Jouni Mykkänen, Martti Juhola and Ulla Ruotsalainen,
Three-dimensional ROIs in Brain PET.
Abstract.
A semi-automatic system for determining volumes of interest (VOI)
from positron emission tomography (PET) scans of brain is described.
The VOIs surface extraction is based on user selectable threshold
and three-dimensional target flood-fill. Contrast to anatomical
volume detection approaches, volumes are determined from functional
PET images and the obtained objects are checked against anatomical
images. The developed VOI program was evaluated with brain FDOPA-PET
studies where the striatum was the object. The results were
comparable to entirely manual method and the target extraction time
is reduced to about one third of manual method.
Compressed Postscript
pdf-file.
A-1999-7 Erkki Mäkinen,
On the longest upsequence problem for permutations. April 1999.
Abstract.
Given a permutation of n numbers, its longest upsequence
can be found in time O(n log log n). Finding the
longest upsequence (resp. longest downsequence) of a permutation solves the
maximum independent set problem (resp. the clique problem) for
the corresponding permutation graph.
Moreover, we discuss the problem of effeciently constructing the
Young tableau for a given permutation.
Compressed Postscript
pdf-file.
A-1999-8 Erkki Mäkinen,
On the inclusion problem for very
simple deterministic pushdown automata. June 1999.
Abstract.
We present a new algorithm for checking the inclusion of
very simple deterministic pushdown automata. The inclusion
``L(M1) \subseteq L(M2)?'' is checked by first constructing
a finite characteristic set R of M1, and then checking whether
or not the inclusion R \subseteq L(M2) holds.
Compressed Postscript
pdf-file.
A-1999-9 Tarja Systä and Ping Yu,
Using OO Metrics and Rigi to Evaluate Java Software. July 1999.
Abstract.
A prototype reverse engineering environment has been built to support
understanding an existing Java
software. The static software artifacts and their dependencies are
extracted
from Java byte code and viewed with Rigi reverse engineering environment
as a
nested graph. Several software metric values can be calculated from the
byte code and analyzed
with Rigi. The metric values can be used to study and structure the
static dependency graph
and hence support program comprehension. Rigi can be used to examine
the
metric values and to find software artifacts that have exceptional or
extreme values.
Compressed Postscript
pdf-file.
A-1999-10 Tapio Niemi and Jyrki Nummenmaa,
A query method based on intensional concept definition. October 1999.
Abstract.
We present a query language which is based on intensional
concept definition. In traditional conceptual query systems the user
generally defines the query using the existing concepts without actually
forming new concept definitions in the conceptual schema. In our approach
the query construction is equal to defining new concepts. This way, the
query formulations also increase the amount of conceptual information.
The intensional concept operations are applied in query formulation. A
user can choose an existing concept or form new concepts by using the
concept operations and then it is possible to generate the extension set
for the new concept, i.e. to execute the query. These new concepts can be
further used to construct new queries, namely new concepts. Consequently,
the user can form a conceptual schema, which serves best his/her own
purposes.
The approach is very strongly user oriented and produces declarative
queries. In the respective database perspective, the expressive power of
the approach is that of the project-join queries, which cover a large
amount of typical everyday queries. Moreover, the queries can be evaluated
efficiently under certain conditions.
A-1999-10 is available as paper copy only.
A-1999-11 Roope Raisamo,
Evaluating different touched-based interaction techniques in a
public information kiosk. October 1999.
Abstract.
Public information kiosks are becoming more and more common. However, their
user interfaces are still based on simple button interfaces, which may be
implemented with physical buttons or with virtual buttons drawn on a
touchscreen. We have implemented a multimodal kiosk prototype that is based
on touch and speech input. This paper describes an evaluation in which 23
users compared five area selection techniques for touchscreens. These
techniques are based on selection time, touch pressure and direct
manipulation. The results show that pressure-sensitive techniques offer a
possible alternative to the other selection techniques, but require careful
designing. Our time-based technique was the most intuitive and the direct
manipulation technique was understood well after an initial learning phase.
Compressed Postscript.
pdf-file.
A-1999-12 Timo Niemi, Maria Christensen and Kalervo Järvelin,
Query language based approach based on application specific concepts.
November 1999.
Abstract.
The integration of data-oriented (structural), behavioral and
deductive aspects is necessary in next generation information systems.
Therefore the deductive object-oriented database paradigm offers a very
promising starting point for the implementation of these kinds of
information systems. So far in the context of this paradigm a big problem
has been the lack of a query language suitable to an ordinary end user.
Typically in existing proposals for deductive object-oriented databases the
user has to master well both logic-based rule formulation and
object-oriented programming. It is clear that the end user need a
declarative query language at a high abstraction level. We argue that in
next generation information systems it is necessary to embed complex (often
deductive) and large specifications in application-specific structures and
concepts which the user can use as such in query formulation. This means
that a query language has to provide such primitives in which these
concepts can be embedded. In this paper we introduce this kind of a query
language which is based on a collection of high-level primitives which the
user combines with each other in ad hoc query formulation. The idea of our
query language approach is based on the incorporation of deductive aspects
to object-orientation. Among others this means that deductive aspects are
inherited in the specialization/generalization hierarchy like any other
property of an object.
A-1999-12 is available as paper copy only.
A-1999-13 Roope Raisamo,
Multimodal human-computer interaction: a constructive and
empirical study,
November 1999.
Abstract.
Multimodal interaction is a way to make user interfaces natural and efficient with parallel and synergistic use of two or more input or output modalities. Two-handed interaction is a special case of multimodal interaction that makes use of both hands in a combined and coordinated manner. This dissertation gives a comprehensive survey on issues that are related to multimodal and two-handed interaction. Earlier work in human-computer interaction and related psychology is introduced within both these fields.
The constructive part of this dissertation consists of designing and building a group of multimodal interaction techniques that were implemented in two research prototypes. The first prototype is an object-oriented drawing program that implements new tools that are controlled with two-handed input. The second prototype is a multimodal information kiosk that responds to both touch and speech input, and makes use of touch pressure sensing.
In order to evaluate the success of constructive research, four empirical studies were conducted to compare the new interaction techniques to the conventional methods and to evaluate how the users react on them. The first of the studies compared a new direct manipulation tool to conventional menu and palette commands. The second evaluation was more informal and determined how an alternative way of drawing would be used by normal users. The third study was aimed at determining what is the best input device configuration to control the new tools. The last study evaluated different touch-based selection techniques in a multimodal touch and speech based information kiosk.
The need for extensive interdisciplinary research is pointed out with a group of research questions that need to be answered to better understand multimodal human-computer interaction. The current knowledge only applies to a few special cases, and there is no unified modality theory of multimodal interaction that covers both input and output modalities. Ph.D. Dissertation.
A-1999-13 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 5.
A-1999-14 Poika Isokoski,
A minimal device-independent text input method,
November 1999.
Abstract.
Recently the need to write text on paper with a pen has diminished. One
reason for this development is the emergence of various portable computing
and communications devices. Each device typically has its own method for
text input. Some rely on miniature keyboards while others are used with a
stylus. This means that a person owning several of these gadgets needs to
learn many writing methods. In an attempt to alleviate the user's learning
burden we have constructed a minimal device-independent
text input method which can be used with a variety of input devices.
In our experiment with five volunteers we found the method to be rather
slow at 7.6 words per minute after five hours of practice. A handheld
touchpad was used for the practice period. After the practice we measured
the writing speed and error rate for mouse, trackball, joystick and
keyboard without device specific training. We found that the writing speed
is only slightly slower with unpracticed devices. The error rate varied
more between the devices. Keyboard and joystick had the best error rates
of roughly 3 %. Trackball was the worst with 7 % of characters requiring
corrections.
Compressed Postscript
pdf-file.
A-2000-1 Ferucio Laurentiu Tiplea, Erkki Mäkinen,
Corina Apachite, Synchronized Extension Systems. January 2000
(Revised December 2000).
Abstract.
Synchronized extension systems (SE-systems, for short) are 4-tuples
G=(V,L1,L2,S), where V is an alphabet
and L1, L2 and S are languages over V.
They generate languages extending L1 by
L2 to the left or to the right, and synchronizing
on words in S.
Such systems appear naturally when considering stacks,
queues, grammar-like generative devices, splicing
systems, zigzag-codes etc.
This paper introduces the concept of an SE-system,
and studies some basic properties of them.
Compressed Postscript
pdf-file.
A-2000-2 Erkki Mäkinen and Jarmo Siltaneva,
A note on Remy's algorithm for generating random binary trees. January 2000.
Abstract.
This note discusses the implementation of Remy's algorithm
for generating unbiased random binary trees.
We point out an error in a published implementation of the algorithm.
The error is found by using the chi-square test.
Moreover, a correct implementation of
the algorithm is presented.
Compressed Postscript
pdf-file.
A-2000-3 Timo Poranen and Jyrki Nummenmaa,
Efficient algorithms for MC games. February 2000.
Abstract.
In this paper we provide efficient algorithms for two classes
of MC games.
For tree-like MC games, where a game graph doesn't have any other
cycles than self-loops, we can use a dfs-based
algorithm to find the winner in O(E) time. For cycle-connected
MC games, where all cycles in each
strongly connected component of the game graph have at least
one common vertex, we can find the
winner in polynomial time.
The class of tree-like MC games is a subclass of cycle-connected
MC games. The class of cycle-connected MC games are equivalent to
a subclass of
model checking games G(E,P), where E is finite
state process and
P is an alternation
free formula.
It is known in the literature that
model checking for alternation-free mu-calculus can be done in
linear time. It follows that
cycle-connected MC games are solvable in polynomial time, but
no explicit algorithms are given in the literature for MC games.
Our treatment is based on
standard graph-theoretical concepts, rather than the concepts
of model checking, which is usually used in the literature.
A-2000-4 Tarja Systä,
Static and dynamic reserve engineering techniques for
Java software systems.
Ph.D. Dissertation.
A-2000-4 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 30.
A-2000-5 Erkki Mäkinen, Timo Poranen and Petri Vuorenmaa,
A genetic algorithm for determining the thickness of a graph. March 2000.
Abstract.
The thickness of a graph is the minimum number of planar subgraphs
into which the graph can be decomposed. Determining the thickness of
a given graph is known to be a NP-complete problem. This paper discusses
the possibility of determining the thickness of a graph by a genetic
algorithm.
Our tests show that the genetic approach outperforms the earlier
heuristic algorithms reported in the literature.
Compressed Postscript
pdf-file.
A-2000-6 Juha-Matti Heimonen and Mikko Ruohonen (eds.),
Pertti Järvinen 60 years - Work for science.
pdf-file.
A-2000-7 Erkki Mäkinen and Tarja Systä,
Minimally adequate teacher designs software. April 2000.
Abstract.
We consider the problem of synthesizing UML statechart diagrams from
sequence diagrams as a language inference problem, and we solve it in
Angluin's framework of minimally adequate teacher. The designer has the
role of teacher who answers membership and equivalence queries made by the
algorithm. It turns out that there are several natural restrictions
concerning the form of languages accepted by state machines. These
restrictions can be used to decrease the number of membership queries
needed, and thus, to make the method practically applicable.
Compressed Postscript
pdf-file.
A-2000-8 Maarit Harsu, Re-engineering legacy software through
language conversion.
Abstract.
Software industry has a huge amount of legacy programs needing
re-engineering and modernization.
We are especially interested in re-engineering legacy programs via
language conversion. In language conversion,
the source and target languages can be either from the same programming
paradigm or from different ones.
Thus, we consider program modernization from two aspects.
If the source and target languages share the same programming paradigm,
we can modernize programs via source-to-source
translation. If the languages are from different paradigms,
for example
procedural and object-oriented, we need re-engineering means in
modernization, particularly in identifying objects from procedural code.
After finding objects and their operations, we need again source-to-source
translation methods in the actual conversion.
As a constructive part of
this thesis, we have implemented a converter translating PL/M
programs into C.
As an implementation tool of that converter, we have used TaLE
(Tampere Language Editor). Because of the nature of the legacy
software and PL/M language, we have been forced
to extend TaLE.
Since legacy systems are typically
large, we have developed a technique to reduce the space requirements
of the converter.
In addition, conditional compilation
of the source language may cause parsing problems in source-to-source
translation. As a solution for
this problem, we introduce multi-branch parsing. Both of these
techniques are implemented in TaLE.
We also show how to exploit the existing features of TaLE in information
passing.
We have extended the PL/M-to-C converter
with object identification methods as a first step to enable
translation from a procedural language into an object-oriented one
(for example, C++).
We introduce new methods to identify object-oriented
features, such as subclass relationships and polymorphism, from legacy
programs.
The converter developed in this work is currently being used for
modernizing PL/M systems in telecommunication industry.
The experiences in using the converter are briefly summarized.
Keywords: re-engineering, software maintenance,
language conversion, object identification,
source-to-source translation, parsing,
conditional compilation, piecewise translation.
Ph.D. Dissertation.
A-2000-8 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 56.
A-2000-9 Erkki Mäkinen and Tarja Systä,
Implementing Minimally Adequate Synthesizer. June 2000.
Abstract.
Minimally Adequate Synthesizer (MAS) is an algorithm that synthesizes
UML statechart diagrams from sequence diagrams. It follows Angluin's
framework of minimally
adequate teacher to infer the desired statechart diagram with the help of
membership and equivalence queries.
The purpose of this paper is to discuss problems related to
an practical implementation of MAS.
In order to be able to handle
most membership queries without consulting the user,
MAS maintains a structure of strings already known to belong to
the unknown language. User's erroneous answers and mind
changes require an implementation of the structure
that is capable of handling backtracking. We sketch a trie based
implementation to allow this.
Moreover, we discuss the interaction between the user and the algorithm
as a medium of improving the algorithm and further decreasing the
number of membership queries needed. Furthermore, we show how MAS
can be used to synthesize sequence diagrams into an edited or
manually constructed statechart diagram.
Finally, we extend MAS to handle UML sequence diagrams containing also
other concepts than objects and message calls.
Compressed Postscript
pdf-file.
A-2000-10 Pirkko Nykänen, Decision Support Systems
in Health Informatics Perspective.
Abstract.
Our theme in this study is decision support systems in a health informatics context. A decision support system can be approached from two major disciplinary perspectives, those of information systems science and artificial intelligence, which offer different conceptualisations of a decision support system. From an information systems science perspective, the approaches taken have been functionalist and development- and implementation-oriented, resulting in systems being developed mostly to support managerial decision making. In artificial intelligence-based approaches, on the other hand, the focus has been on modelling of an expert task and on implementation of that model as a knowledge-based system. Under these latter approaches, the focus has been on the design of systems to support individual decision making in tasks that are considered to require intelligence. In neither of these perspectives has the social and organisational contexts of decision support systems been given much attention.
We present in this study an extended ontology for a decision support system in health informatics. The ontology emphasises the need to cover environmental and contextual variables as an integral part of a decision support systems development methodology. With the addition of these variables, the focus in decision support systems development shifts from a task ontology towards a domain ontology. The variables presented have been further connected to a development and evaluation framework, which applies incremental development using evolutionary prototyping. The presented ontology and framework help the system developers to take the system's context into account through the set of defined variables which are linked to the application domain. This results in systems that support decision making in the health care organisational context and in the user's domain, application and knowledge contexts.
The presented ontology is founded on experience from related research fields, those of information systems science and artificial intelligence, as well as being informed by analysed five case studies. The result of this sudy is demonstration of a pragmatic approach for decision support systems development in health informatics domain. Further research is needed with the operationalisation of the developed ontology.
Ph.D. Dissertation
A-2000-10 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 55.
A-2000-11 Ferucio Laurentiu Tiplea and Erkki Mäkinen,
A note on synchronized extension systems. July 2000.
Abstract.
The concept of a synchronized extension system (SE-system,
for short) has been introduced by Tiplea, Mäkinen and
Apachite as a 4-tuple G=(V,L1,L2,S), where V is an alphabet
and L1, L2 and S are languages over V.
Such systems generate languages extending L1 by
L2 to the left or to the right, and synchronizing on
words in S. In [Tiplea, Mäkinen and Apachite] it has been
shown that the language of type r- generated by an SE-system
of type (r,r,f) is regular. As a particular case,
the stack language of a pushdown automaton is regular.
In this note we prove the converse. That is, using the
fact that the stack language of a pushdown automaton is
regular, we obtain that the language of type r- generated
by an SE-system of type (r,r,f) is regular.
Compressed Postscript
pdf-file.
A-2000-12 Isto Aho,
Notes on the properties of dynamic programming used in direct load
control scheduling. August 2000.
Abstract.
We analyze a dynamic programming (DP) solution for cutting the
overload in electricity consumption. We are able to considerably
improve the earlier DP algorithms presented in the literature. Our
improvements make the method practical so that it can be used more
often or, alternatively, new state variables can be added into the
state space to make the results more accurate. We also propose a way
to add a new state variable to the state space. By using different
numbers of state variables we can build up a hierarchy of solutions,
in which we can trade between rapidity and accuracy. A similar
trade-off situation occurs also between low and high number of
states a variable is allowed to have.
Compressed Postscript
pdf-file.
A-2000-13 Markku Siermala, Martti Juhola and Mauno Vihinen,
On preprosessing of protein sequences for neural network prediction
of polyproline type II secondary structure. August 2000.
Abstract.
Motivation: Polyproline type II stretches are rather rare among
proteins, and, therefore, it is a very challenging task to try to
find them computationally. In the present study our aim was to
consider especially the preprocessing phase, which is important for
any machine learning method. Preprocessing includes selection of
relevant data from Protein Data Bank and investigation of
learnability properties. These properties show whether the material
is suitable for neural network computing. In addition, algorithms in
connection with data selection and other preprocessing steps were
considered.
Results: We found that feedforward perceptron neural networks were
appropriate for the prediction of polyproline type II as well as
relatively effective in this task. The problem is very difficult
because of high similarity of the two classes present in the
classification. Still neural networks were able to recognize and
predict about 75 % of secondary structures.
pdf-file.
A-2000-14 Ferucio Laurentiu Tiplea and Erkki Mäkinen,
A note on SE-systems and regular canonical systems. October 2000.
Abstract.
A synchronized extension system is a 4-tuple
G=(V,L1,L2,S), where V is an alphabet
and L1, L2 and S are languages over V.
Such systems generate languages extending L1 by
L2 to the left or to the right, and synchronizing
on words in S.
In this note we consider the relationship between
synchronized extension systems and regular canonical
systems. We are able to give a simplified and
generalized proof for the classical result concerning
the regularity of the languages defined by regular
canonical systems.
Compressed Postscript
pdf-file.
A-2000-15 Ferucio Laurentiu Tiplea and Erkki Mäkinen,
On SE-systems and monadic string rewriting systems. November 2000.
Abstract.
A synchronized extension system
is a powerful and elegant rewriting formalism.
In this paper we show how it can be used to improve
a well-known result concerning monadic string
rewriting systems. We give a new proof for the fact
that if the rewriting rules of a monadic string
rewriting system are applied to the strings of a
regular set L, the set so obtained is also regular.
We obtain the result with better time and space bounds
than the earlier proofs.
Compressed Postscript
pdf-file.
A-2000-16 Timo Poranen, A new algorithm for drawing series-parallel
digraphs in 3D. December 2000.
Abstract.
This paper proposes a new algorithm for drawing
series-parallel digraphs in three dimensions.
Our algorithm produces a three dimensional strictly upward Fary grid drawing
with volume O(n^3) for an arbitrary series-parallel digraph. We also prove
that if series-parallel digraph is regular, it can be drawn with volume
O(n^2) and further, if a series-parallel digraph is regular and its
structure tree fulfils a simple condition, the graph can be drawn inside
a box having volume O(n).
Compressed Postscript
pdf-file.
A-2000-17 Ferucio Laurentiu Tiplea, Erkki Mäkinen
and Constantin Enea,
SE-systems, timing mechanisms, time-varying codes. December 2000.
Abstract.
We show that synchronize extension
systems [Tiplea, Mäkinen, Apachite] can be succesfully used to
simulate timing mechanisms incorporated into grammars
and automata
[Baer & Spanier, Salomaa, Krithivasan & Das, Krithivasan & Srinivasan,
Matei].
Further, we introduce the concept of a time-varying code as
a natural generalization of L-codes, and the relationship
with classical codes, gsm codes and SE-codes is established.
Finally, a decision algorithm for periodically time-varying
codes is given.
Compressed Postscript
pdf-file.
A-2000-18 Jyrki Nummenmaa and Peter Thanisch,
Practical distributed Commit in modern environments. December 2000.
Abstract.
A characteristic difficulty in formulating distributed
protocols is that the problem definition is, perforce,
architecture-dependent. In the case of atomic commit protocols,
this difficulty manifests itself in the description of the circumstances
under which faults (real or suspected) can cause the participants
to decide to abort a transaction, despite unanimity that it could be
committed.
We show that textbook definitions of the atomic commit problem
can be misleading, especially in today's distributed transactions which
use
the Internet and mobile computing technologies.
Depending on the environment, a protocol which would be
traditionally considered efficient might actually make the overall
system peformance worse. We reformulate
the atomic distributed commit problem and give practical
protocols, based on existing well-known protocols, which can be used
to take into account the overall efficiency considerations
in distributed transaction processing. The solutions are especially
applicable in situations where the data contention varies
between transactions or it is difficult to estimate
message delivery delay and the duration of the commit protocol.
A-2000-18 is available as paper copy only.
A-2000-19 Markku Siermala, Mikko Kankainen and Jyrki Nummenmaa,
Tracing footballers' movements from video. December 2000.
Abstract.
In this paper we will explain our methods and experiments in
detecting footballers' movements from a single VHS videotape.
We have developed methods for detecting indivdual
players' movement along the pitch during the game.
Such movement is needed e.g. for tactical analysis software
developed in Research Institute for Olympic Sports (KIHU)
at the University of Jyväskylä.
As the video quality and coverage imposes difficulties,
there is no basis to aim for analysis which would require
no user assistance. However, we tried to minimize the need
for such assistance.
We implemented several methods, which broadly fall into two
categories. The first category is based on analysing
difference images and it was found to be not practical for this
particular type
of application, although we outline some ways to improve it.
The second is based on detecting pixel clusters and tabulating
them based on colour analysis and computing the paths of
the players from such a table. The second method was found much
more suitable for the task at hand.
A-2000-19 is available as paper copy only.
A-2001-1 Kati Viikki, A variable grouping method based on graph
theoretic techniques. February 2001.
Abstract.
This paper presents a variable grouping method that is based on
techniques of graph theory. An association matrix is calculated and
the properties of the graph induced by the
matrix are employed in variable grouping. The method gives a deeper
insight into data. Furthermore, it can be utilised in feature subset
selection for machine learning and statistical methods.
Compressed Postscript
pdf-file
A-2001-2 Jorma Laurikkala, Improving identification of
difficult small classes by balancing class distribution. April 2001.
Abstract.
We studied three different methods to improve identification of small
classes, which are also difficult to classify, by balancing imbalanced
class distribution with data reduction. The new method, neighborhood
cleaning rule (NCL), outperformed simple random selection within classes
and one-sided selection method in experiments with ten real-world data
sets. All reduction methods improved clearly identification of small
classes (20-30%), but differences between the methods were insignificant.
However, the significant differences in accuracies, true-positive rates
and true-negative rates that were obtained with the three-nearest
neighbor method and C4.5 decision tree generator from the reduced
data were in favor of NCL. The results suggest that NCL is a useful
method for improving modeling of difficult small classes, as well as
for building classifiers that identify these classes from the real-world
data which often have an imbalanced class distribution.
pdf-file
A-2001-3 Tapio Niemi, Jyrki Nummenmaa, and Peter Thanisch,
Constructing OLAP cubes based on queries. May 2001.
Abstract.
An OLAP user often follows a train of thought, posing a sequence
of related queries against the data in the data warehouse. Although their
details are not known in advance, the general form of those queries, and
in particular the relevant portion of the data, is apparent beforehand.
We present a technique that automates cube logical design given the data
warehouse, stored as a relational database, functional dependency
information, and sample OLAP queries expressed in the general form alluded
to above. Using this knowledge, we can construct complete but minimal
cubes and reduce risks related to sparsity and incorrect aggregations. The
process is iterative and interactive. After the user has given queries,
the system will suggest a cube. The user accepts it or gives more queries
to include more information or to improve the structure of the cube. The
method is also suitable to improve existing cubes using respective real
queries.
A-2001-3 is available as paper copy only.
A-2001-4 Ferucio Laurentiu Tiplea and Erkki Mäkinen,
On the complexity of a problem on monadic string rewriting systems.
June 2001.
Abstract.
Computing the set of descendants of a regular
language L with respect to a monadic string rewriting
system has proved to be very useful in developing
decision algorithms for various problems on
finitely-presented monoids and context-free grammars.
Recently, Esparza et al. [Bull. EATCS 72 (2000), 169-177] proved
O(ps^3) time and O(ps^2) space bounds
for this problem,
where p is the number of rules in the monadic
string rewriting system and s is the number of
states in the automaton accepting L.
Using synchronized extension systems
we provide a new insight to the problem and allow
an O(pr) time and space solution, where p is
as above and r is the number of the rules in the
grammar generating L.
Compressed Postscript
pdf-file
A-2001-5 Marko Junkkari, The systematic object-oriented representation
for managing intensional and extensional aspects in modeling of part-of
relationships. June 2001.
Abstract.
It is typical of the existing approaches proposed for manipulating part-of
relationships that the user is responsible for controlling manipulation of
part-of relationships. In order to make query formulation possible at a
higher abstraction level it is necessary to create such a representation of
part-of relationships which contains both the explicit description for
intensional (schema) and extensional (instance) levels and the exact
mechanism for their interaction. Here we develop an object-oriented,
constructor-oriented and formal representation, called PSE (Part-of
Structure Element) representation, for this purpose. We show that it is a
systematic, precise and powerful tool for advanced structural analysis
both at the intensional and extensional levels. Further we demonstrate how
truly declarative querying primitives for part-of structures can be
realized on the basis of PSE representation.
A-2001-5 is available as paper copy only.
A-2001-6 Jorma Laurikkala,
Knowledge Discovery for Female Urinary Incontinence Expert System.
October 2001.
Abstract.
This study addresses the construction of an expert system for the differential diagnosis of female urinary incontinence by using data mining techniques. The motivation for the work was the problematic diagnostic task, and the need for an alternative to the slow and expensive manual knowledge acquisition process in which a knowledge engineer interviews an expert repeatedly to acquire the expert's knowledge. Therefore, the main aims were to develop a decision support tool for the physicians, and to investigate whether data mining techniques could be used to discover diagnostic knowledge automatically from the patient data for the expert system. In this context, special attention was paid to pre-processing of the data and the machine learning methods were researched. This work produced a new machine learning program, Galactica, which is based on genetic algorithms, and the neighbourhood cleaning rule (NCL) that balances the imbalanced class distribution by using an instance-based approach. Comparison of Galactica with different classification methods showed that genetic algorithms were a competitive method for constructing classifiers from medical data. NCL enabled improved identification of difficult small classes, while keeping the classification ability of the other classes at an acceptable level. Galactica, NCL, and other data mining techniques were applied to overcome difficulties with real world data, and to build ability for classification and critique for the incontinence expert system. The study showed that it is possible to develop an expert system with data mining techniques. In 'laboratory conditions' the first version of the system (IES1) correctly classified 94% and 91% of the two batches of the test data, and the medians of the true positive and true negative rates were 97% and 94% in the first test set, and 96% and 90% in the second test set. The expert system was implemented as an Internet-based application that a physician can use with a World Wide Web browser. IES1 seems to be a useful aid for the physicians, but only real world diagnostic work-up will prove its utility in the diagnosis of incontinent women.
Keywords: artificial intelligence, decision support systems,
expert systems, medical diagnostic computing, patient diagnosis, data mining, machine learning, genetic algorithms, data pre-processing
Ph.D. Dissertation.
A-2001-6 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 137.
A-2001-7 Isto Aho, Erkki Mäkinen, and Jyrki Nummenmaa (eds.),
IOI'01. July 2001.
Abstract.
The International Olympiad in Informatics is one of the six international
science Olympiads. It is an algorithmic programming competition for
students from secondary schools. In IOI the competition contestants
compete individually in solving a set of algorithmic problems using a
computer. The problems involve programming and efficient computations.
IOI 2001 took place in Tampere, Finland on July 14 - 21, 2001.
This book explains the competition material of IOI 2001: the tasks,
their solutions, and the theory behind them. The computing environment -
compilers, hardware, and program development tools are also shortly
described.
pdf-file
A-2001-8 Jarmo Siltaneva and Erkki Mäkinen,
A comparison of random binary tree generators.
November 2001.
Abstract.
This paper empirically compares five linear-time algorithms for generating
unbiased random binary trees. We count the numbers of various types of
operations executed by
the algorithms. It turns out that there hardly exists a definite overall
ranking order among the algorithms but the order varies depending
on the criteria applied.
pdf-file
A-2001-9 Tapio Niemi,
Methods for Logical OLAP Design.
December 2001.
Abstract.
As the amount of information is increasing all the time, information
modelling and analysis have become essential areas in information
management. Storing and retrieving data have earlier been the main
functions in databases but the importance of deeper understanding of data
has increased during the recent years. The nature of data has also become
more complex. Therefore, powerful modelling methods are needed for the
data. In addition, the methods have to be user-friendly since the users of
data oriented applications are not often database-professionals. The
general aim of this work is to develop methods to make database design and
management easier and more efficient for all users, both database
professionals and people with no prior experience with databases.
We have studied methods to support logical design of OLAP
(On-Line-Analytical Processing) cubes. The methods give a good basis for
implementing software tools that partly automate the logical design
process. These methods are needed since it is commonly noticed that
logical design of OLAP cubes is a complex process that requires good
knowledge on both application area and databases. Good logical structure
of an OLAP cube is important, because a bad design can, for example, lead
to an extremely sparse cube and to such a need for storage space that is
not possible to achieve in practice. As a solution, we give a method for
estimating the structural sparsity of OLAP cubes and a normal form to
reduce sparsity risks. Moreover, synthesis and decomposition algorithms
for producing normalised OLAP cubes are developed. Hierarchical
dimensions, which enable the user to analyse data on different levels of
aggregation, are essential for OLAP. Hierarchies can arise from the
attribute hierarchy (e.g. day, month, year), or from the relationship
between the instances of two attributes (e.g. employee, manager). We study
what kinds of hierarchy structures are desirable with respect to correct
aggregations and efficient calculations. To represent logical OLAP
schemata, a dependency-based modelling method has been developed. This
method enables the user to describe concepts and their relationship to
each other explicitly. The OLAP cube should be complete and minimal with
respect to the user's queries. To define what data should be taken into
account when constructing an OLAP cube, we give two methods based on query
information. One applies the intensional concept theory and a query method
based on it. The other uses MDX queries that the user poses against a base
cube representing the contents of the data warehouse. If real queries are
available, they can be used as input.
Ph.D. Dissertation.
A-2001-9 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 153.
A-2001-10 Heikki Hyyrö, Explaining and extending the bit-parallel algorithm
of Myers. December 2001.
Abstract.
The O(mn / w), where m is pattern length, n is text length and w is the
computer word size, bit-parallel algorithm of Myers is one of the best
current algorithms in the case of approximate string matching allowing
insertions, deletions and substitutions. We begin this paper by deriving a
practically equivalent version of the algorithm of Myers. This is done in
a way, which we believe makes the logic behind the algorithm easier to
understand than the original presentation. Then we show how to extend the
algorithm to allow also a fourth kind of error, which is transposition of
two adjacent characters. This is a very common type of error for example
in typed text, but has typically been omitted from approximate string
matching algorithms. Finally we present experimental results to show, what
kind of effect adding transposition has on the performance of the
algorithm.
pdf-file
Errata
A-2002-1 Tarja Tiainen, Information System Specialist Predispositions.
March 2002.
Abstract.
This dissertation discusses predispositions on two levels: First, three
main types of predispositions are outlined and discussed on a broad level.
Second, predispositions among information system (IS) specialists, in
particular, are made explicit and some dominant types are clarified.
Predispositions are unquestionable assumptions, beliefs that are taken for
granted, common sense and normal ways of behaviour. The central theme on
which this dissertation concentrates is IS specialists' predispositions. IS
specialists are persons who design, create and mediate IS and ICT
(information and communication technology) and so influence the working
environment of others in significant ways.
IS development is group activity in which people from several occupational
groups work together - IS specialists comprise one of those groups. IS
specialists not only work with other occupational groups in IS
development; some of them work with users in their everyday IS use; for
example, when users encounter problems in using an IS or ICT. There are
challenges in multi-occupational groups working together, as several
studies confirm. Predispositions have effects on group activity; it is
easier to work with people who share the same predispositions.
Predispositions have effects on what problems are noticed and on what
possible development paths are identified. Furthermore, predispositions
influence which issues can be negotiated and the negotiation process,
i.e., determining which arguments are relevant.
In this dissertation IS specialists' predispositions are studied by using
an interpretative approach applied to two text sets. Both text sets have
been produced by IS specialists and their topic was envisioning the future.
The first text set includes 31 essays, which were written by computing
pioneers, industry observers, and technical leaders in the IS and ICT
fields. The essays were published in the Communications of the ACM in 1997.
The second text set consists of 24 interviews of Finnish IS specialists.
They describe their visions of the future from several perspectives. The
analysis of the text sets focuses on cultural aspects by using discourse
analysis.
The text sets portray the future from a technology-centred perspective; for
example, technology is presented as the most important - or even the only -
driving force of development. Furthermore, the text sets include a
masculine world view, in which women are presented as problems. In any
case, the text sets portray a one-sided view of people. They do not wholly
ignore people but their view of people is reductionist, underrating
people's knowledge and possibilities. The results not only describe the
individuals' predispositions but also the predispositions of the community
of IS specialists and the IS field, as well.
Key words and phrases: information system, technology shaping, views of technology,
technology-centricity, future visions, predisposition, IS specialists,
computing professionals, masculinity, gender studies, interpretive IS
research.
Ph.D. Dissertation.
A-2002-1 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 163.
A-2002-2 Juha Lehikoinen, Interacting with Wearable
Computers: Techniques and Their Application in Wayfinding Using Digital Maps.
September 2002.
Abstract.
Wearable computers are a special case of mobile computers. They are either
embedded in clothing, or they may even be the clothing. They are very personal
in nature, being always with the user, always on and always ready. The aim in
developing wearable computers is to provide the user with instant and
easy-to-use access to digital information sources anytime, anywhere.
Wearable computers are a potential platform for several location-aware
software applications. One such application is a personal navigation assistant
that is aware of the user's current geographical location, and has access to a
database that contains maps of the current surroundings. Equipped this way, the
assistant can provide the user with easy to understand and real-time
instructions on how to reach a specific destination, and assist in exploring the
environment without getting lost.
This dissertation addresses the issues that arise when personal navigation
assistants for wearable computers are developed. The research comprises eight
studies in the areas of human-map interaction, wearable computing, and
human-computer interaction. Two research methods have been applied: in the
constructive research part, a navigation application, including several
interaction techniques suitable for wearable use, has been developed. In the
empirical research part, the methods and techniques developed have been
evaluated to assess their usability. As a result - in addition to the navigation
application itself - a set of user interaction techniques and interface
components that support the various tasks needed in wayfinding has been
proposed. These include a finger-based interaction technique, an efficient list
searching technique, and a novel pocket-based user interface metaphor. The
results also include guidelines for designing the map behavior while navigating.
Ph.D. Dissertation.
A-2002-2 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 207.
A-2002-3 Markku Siermala, Local Prediction of Secondary Structures of Protein
from Viewpoints of Rare Structure.
May 2002.
Abstract.
This dissertation deals with the local prediction of protein secondary
structure from the viewpoint of rare secondary structures. Protein
three-dimensional structures are needed in the biomedical field because
structures indicate something about the functions of proteins, and
functions are almost everything that happens in a living cell.
Unfortunately, it is difficult to ascertain the structure of a protein,
because the details of the structure are located at the level of atoms.
However, an amino acid sequence is fairly easy to solve and can also be
produced from a DNA sequence. This could be a shortcut to the structure
and function of proteins. We searched for ways to better understand the
prediction challenge of secondary structures. Our research started with
polyproline type II secondary structure prediction. The results showed
that a neural network behaved well when the learning and test sets had a
uniform class distribution. However, the identification of amino acid
sequences that represent a rare class was difficult with class
distribution of the real world. In this context, prediction was hampered
by imbalanced class distribution. We developed spectrum and response
analysis for the neural network which reveal the reasons for a certain
decision. The frequencies of prolines affected a major part of decisions
and this was almost all that a neural network could learn from the data.
Apparently input sequences can take the evolutionary pre-information to
the learning process. With the polyproline II structure this was a
promosing idea and aroused interest in using the method with other
structures and other pre-information types. With hyperspheres we developed
a learning algorithm that achieved excellent prediction accuracy with all
known secondary structure types. Unfortunately, the method leaves cases
unclassified - if uncertain generalization is reduced, hyperspheres can
achieve better prediction accuracies. Finally, for all secondary structure
types we analyzed the space used and found explanations for how the
structure types behave in the sequence space. The results showed that
polyproline II is an exception among other types because of its
sensitivity to the amino acid proline. We were able to show that for half
of sequences the nearest case seek its one's way to the distance as cases
were randomly generated. Therefore, in the sequence space there are no
large clusters. Rather, around the individual case (sequence) there is a
sphere with high probability of achieving the same secondary structure
type.
Key words and phrases: secondary structure prediction, neural network, machine learning
Ph.D. Dissertation.
A-2002-3 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 180.
A-2002-4 Isto Aho, New polynomial time instances to various knapsack type problems.
April 2002.
Abstract.
We describe a special case of the interactive knapsack optimization
problem (motivated by the load clipping problem) solvable in
polynomial time. Given an instance parameterized by k, the
solution can be found in the polynomial time, where the polynomial
has degree k. In the interactive knapsack problem k is connected
to the length induced by an item. A similar construction solves a
special case of the 0-1 multi-dimensional knapsack and the 0-1
linear integer programming problems in polynomial time. In these
problems the parameter determines the width of the restriction
matrix, which is a band matrix. We extend the 0-1
multi-dimensional knapsack solution to 0-n multi-dimensional
knapsack problems (and to 0-n IP problems).
Our algorithms are based on the (resource bounded) shortest
path search: we represent restrictions efficiently in a form of a
graph such that each feasible solution has a path between given
source and target vertices.
Compressed Postscript
A-2002-5 Pekka Ketola, Integrating Usability with Concurrent Engineering in
Mobile Phone Development. June 2002.
Abstract.
The technical complexity of mobile phones is continually increasing due to the introduction
of new functions and technologies. The development organisations face an increasing challenge
in making the products usable and useful. If for any reason an organisation does not apply
user-centred design during the product development phase, the usability engineers may
encounter problems in doing their daily work efficiently and effectively. A practical
solution is to adapt usability engineering to the specific product development process
by applying standard project practices, planning and risk management. The problem studied
is how usability engineering can be integrated with the Concurrent Engineering development
process. The main research activity was to perform usability engineering in a product
development lifecycle during the period 1998-2002. A secondary activity was to assess
how successful the same usability engineering approach was in other development projects
during the same time period.
The main result of this case study is to amend and supplement Concurrent Engineering with
usability engineering activities, reported in the form of Usability Engineering Guidelines.
They enable effective and efficient usability engineering in a complex product development
setting. For this we must understand the limitations and opportunities that Concurrent
Engineering set for usability engineering especially in the context of mobile phone
development, and to provide well-defined tools for improving the effectiveness and
efficiency of usability engineering. The particular activities and products of this
study are Usability Assessment, Usability Plan, and Usability Risk Management. Usability
Assessment is the activity that verifies that the development team has a common
understanding in a very early phase about the challenges for product usability. On a
practical level the Usability Plan identifies what factors are important for the success
of the developed product and by what coordination and execution activities the success
(meeting user requirements) can be verified. Usability Risk Management is a method for
managing and communicating the emerging usability problem areas during the development process.
This dissertation presents Usability Engineering Guidelines for avoiding and minimising the
basic usability engineering problems, namely lack of management support and usability activities
undertaken too late. From the product development perspective this dissertation shows that
usability engineering has an important role in minimizing uncertainties in product design,
building and communicating the overall understanding of the product to be developed, and
in connecting development teams of parallel design areas. The long-term planning of usability
work is a powerful tool especially in organizing and integrating usability work in a complex
organisational setting.
Keywords and phrases: user-centred design, usability engineering, Concurrent Engineering,
smart product, information appliance, mobile phone, product development, action research, innovation.
Ph.D. Dissertation.
A-2002-5 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 185.
A-2002-6 Hannakaisa Isomäki, The Prevailing Conceptions of the Human Being in Information
Systems Development: Systems Designers’ Reflections.
May 2002.
Abstract.
The goal of human-centred information systems development (ISD) is to adjust information systems
(IS) to meet human characteristics and action. This perspective is
in this study referred to as the humanisation of IS. Traditionally, the prevailing argument has
been that the humanisation of IS can be best achieved by utilising human-centred ISD methodologies.
In this study it is argued that it is the prevailing conceptions of IS designers of the user that
are more fundamental. Even if the designers are to use a human-centred methodology the designers’
intentions and design activity will be directed by their conceptions about the nature of those
people that will interact
with the system.
This dissertation investigates the nature and comprehensiveness of information systems (IS) designers’
conceptions of the human being as a user of an IS. Two particular standpoints are taken in the
study. First, the user is defined as a human being. This means that users are conceptualised
according to their fundamental constituents as humans rather than in terms of different
instrumental tasks and purposes which people accomplish with the aid of IS. Second, IS designers’
conceptions of humans as users of an IS are seen as knowledge that reflects IS designers’
competence in humanising IS. Competence is here seen as constituted by the meaning that users
take on for the designers in their experience, which, in turn, reflect partial or more comprehensive
notions of people indicating qualitatively different levels of competence.
An interpretatively oriented approach referred to as phenomenography was adopted in this study. By
drawing on in-depth interviews with 20 Finnish IS designers, 18 qualitatively different conceptions
of the human being were categorised from the IS designers’ descriptions. These conceptions are not
only varied in their conceptualisations of the different human qualities, but also constitute a
hierarchy of competence. This hierarchy can be drawn up in terms of three forms of thought: the
separatist, functional, and holistic forms of thought. The separatist form of thought provides
designers predominantly with technical perspectives and a capacity to objectify matters. The
functional form of thought focuses on external task information and task productivity, nevertheless,
with the help of positive emotions. The holistic form of thought provides designers with competence
in human-centred ISD, although without revealing all aspects of the richness of the human condition.
The study rethinks the conception of the human being in ISD. The empirical results suggest that only
few of the Finnish IS designers have the ability to contribute to the humanisation of IS.
Keywords and phrases: human-centred ISD, information system, conception of the human
being, IS designers, competence, forms of thought, interpretive IS research, phenomenography
Ph.D. Dissertation.
A-2002-6 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 188.
A-2002-7 Marko Helenius, A System to Support the Analysis of Antivirus Products' Virus Detection
Capabilities. June 2002.
Abstract.
Computer viruses have become a threat to computer users and computer antivirus products have been developed to facilitate the
prevention of computer viruses. Unfortunately, computer antivirus products are not perfect solutions and therefore antivirus product
evaluation is needed. One important aspect of computer antivirus product evaluation is analysis of products' virus detection and
prevention capabilities. First an introduction to computer viruses and antivirus products' virus detection analysis is presented.
We will conclude that analysis of computer antivirus products' virus detection capabilities is a difficult task because of the large
number of computer viruses, complex tasks involved with test bed preparation and multiple operations of antivirus products.
The author shows that many tasks supporting the analysis of computer antivirus product's virus detection capabilities can be
made computer-supported.
The author presents a development of computer-supported processes, which have facilitated evaluation of antivirus products'
virus detection capabilities in various operating environments. These include such processes as automatic virus replication in a
controlled environment, automatic evaluation of antivirus programs working actively in the background and automatic processes
developed for Windows environment. The major part of the dissertation is devoted to the development phases and self-assessment
of a system that can be used for automating these subtasks. Since we consider time saving of the processes as the most critical
characteristic, the self-assessment concentrates on efficiency of the processes compared to manually accomplished operations.
Problems with different tasks are addressed and also solutions for the problems are provided. The computer-supported processes
discussed are especially useful for those who are interested in antivirus product evaluation or virus related aspects of antivirus
product quality control. The author shows that the developed processes can save an enormous amount of work and can
improve the quality of the evaluation results.
Ph.D. Dissertation.
A-2002-7 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 190.
A-2002-8 Kati Viikki, Machine Learning on Otoneurological Data:
Decision Trees for Vertigo Diseases.
June 2002.
Abstract.
Expert systems may be characterised as computerised advisory systems that
perform in narrow domains at a level comparable to human experts. The success
of expert systems lies essentially in the knowledge embedded in their knowledge bases.
This study concerns refining and expanding the knowledge base of an otoneurological
expert system ONE. ONE was developed to support decision-making for diseases involving
vertigo. Its knowledge base contains descriptions or patterns for vertigo diseases in
the form of weights and fitness values. The knowledge for the first version of ONE
was elicited from experienced otoneurologists and the literature. In this study,
machine learning is utilised in knowledge acquisition. Decision tree induction is
applied to data collected on otoneurological patients in order to acquire diagnostic
knowledge. Special attention is paid to data pre-processing in order to construct
classifiers for real world diagnostic situations. This work produces a variable
grouping method based on graph theoretic techniques. The method is useful as such,
giving insight into data and, further, it can be used in feature subset selection.
The knowledge acquired by decision trees is used in the refinement of ONE's
knowledge base, in which fitness values learned from data and also different
weighting schemes are studied. The refinement work produces a better performing
knowledge base for real world situations.
Keywords and phrases: Machine learning, decision tree induction,
data pre-processing, feature subset selection, expert systems, knowledge
acquisition, knowledge base refinement, otoneurological data, vertigo
Ph.D. Dissertation.
A-2002-8 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 189.
A-2002-9 Juha Hautamäki, Task-driven framework specialization.
Goal-oriented approach. May 2002.
Abstract.
The importance of reusing approved design solutions is widely recognized in
software engineering. Object-oriented frameworks, design patterns, etc., are
ways to reuse existing knowledge. However, some problems remain, particularly
how to guide the application developer to reuse so that the design is
eventually implemented in a software project.
FRED (FRamework EDitor) is a prototype of a task-driven architecture-oriented
programming environment that can be used to implement architectural solutions.
Architecture-specific instructions are given to the tool as specialization
patterns; these formal specifications make it possible to automatically compute
how to implement design solutions during the software development process.
FRED manages the im-plementation process as a gradually progressing work,
where each step is recorded and may have effects to the steps to come.
This enables, for instance, documentation and source code generation that
uses application-specific names familiar to the application developer. Further,
the application developer can be instantly notified if he violates the
architectural rules embodied by the given specialization patterns.
This thesis describes the FRED environment. A goal-oriented approach is
introduced to model design solutions as a set of specialization patterns.
We also explain the mechanism to produce a sequence of programming tasks
to implement the solution. To experiment with the environment, an
industrial framework was annotated with thirteen specialization patterns.
Keywords and phrases: development environment, framework,
framework adaptation, framework specialization, pattern, software architecture,
software engineering, software reuse.
pdf-file
A-2002-10 Timo Niemi, Lasse Hirvonen and Kalervo Järvelin, Multidimensional data model
and query language for advanced applications. June 2002.
Abstract.
Multidimensional data analysis or OLAP offers a single subject-oriented
source for analysing summary data based on different factors (dimensions).
The OLAP approach gives a promising starting point for advanced analysis
and comparison among summary data collected from an application. At the
moment there is not one precise, commonly accepted logical/conceptual model
for multidimensional analysis. This is due to the fact that the
requirements of applications vary considerably. We develop such a
conceptual/logical multidimensional model on the basis of which it is
possible to define the complex and unpredictable analysing needs typical of
advanced applications. We use informetrics as our advanced sample
application. Summary data are considered in respect to some dimensions and
by changing dimensions the user can make another view to the same summary
data. In the paper we develop a multidimensional query language whose basic
idea is to afford the possibility of defining views in the way which is
natural and intuitive for ordinary users. We show that this view-oriented
query language has a great expressive power and its degree of
declarativeness is greater than in the existing operation-oriented or
SQL-like OLAP query languages.
Keywords and phrases: informetrics, OLAP, multidimensional data model, multidimensional
query language, user interface
A-2002-11 Torsti Rantapuska,
Motivational structure of end-user application developers in organisational learning. August 2002.
Ph.D. Dissertation.
A-2002-11 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 200.
A-2002-12 Marko Niinimäki, Miika Tuisku, and Matti Heikkurinen,
Patters, XML and MDV, a case study. August 2002.
Abstract.
In this paper, we aim to study design patterns in the context of a
software package called MDV (MetaData Visualisation). The development of
this software was relatively fast-paced and performed by a team split into
two physical locations for large part of the most active development period.
The original design documents did not contain any overt use of design
pattern methodology and all of the developers were not familiar with design
patterns. We believe that analysing the design of such a software, starting from
the original forces that drove the requirement specification, can provide a
valuable insight into the general nature of patterns. We will also discuss ways
to measure if the quality and productivity of further development of this kind
of project could be improved by using pattern-based analysis of existing
software.
pdf-file
A-2002-13 Isto Aho,
Interactive knapsacks: Theory and applications. November 2002.
Abstract.
The interactive knapsack problems are generalizations of the
classical knapsack problem. Three different new NP-complete decision problems,
interactive knapsack heuristic decision (IKHD), interactive knapsack
desicion (IKD), and multi-dimensional interactive knapsack (MDIK),
are presented for the interactive knapsack model. The interactions occur
between knapsacks when an item is put into a knapsack. We identify several
natural interaction types. Interactive knapsacks with one item are
closely related to the 0-1 multi-dimensional knapsack problem.
By using interactive knapsacks we model various planning and scheduling
problems in an innovative way. We show interactive knapsacks to have
several applications, for example, in electricity management, single
and multiprocessor scheduling, and packing of two, three and
n-dimensional items to different knapsacks. Many natural problems related to
interactive knapsacks are NP-complete. IKD and MDIK are shown to be strongly
NP-complete.
IKHO and IKO are introduced as optimization versions of IKHD and IKD,
respectively. IKHO and IKO are shown to be APX-hard. Further, we
describe special cases of IKHO and IKO solvable in polynomial time; given an
instance parameterized by k, the solution can be found in
polynomial time, where the polynomial has degree k. A similar construction solves
a special case of the 0-1 multi-dimensional knapsack and the 0-1
linear integer programming problems in polynomial time. We extend the 0-1
multi-dimensional knapsack solution to 0-n multi-dimensional
knapsack problems and to 0-n integer programming problems. Our algorithms
are based on the resource bounded shortest path search: we represent
restrictions efficiently in a form of a graph such that each feasible
solution has a path between given source and target vertices.
We apply interactive knapsacks to load clipping used in electricity
management. Specifically, we implement several heuristic methods,
dynamic programming, enumerative, and genetic algorithms for solving direct
load control problem. The enumerative method and dynamic programming are
slow while the heuristics and genetic algorithms are faster. The dynamic
programming gives best results in reasonable time. Heuristics,
however, are several times faster than the other methods.
Ph.D. Dissertation.
A-2002-13 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 217.
A-2002-14 F.L. Tiplea, E. Mäkinen, D. Trinca, and C. Enea,
Characterization results for time-varying codes. October 2002.
Abstract.
Time-varying associate variable
length code words to letters being encoded
depending on their positions in the input
string. These codes have been introduced
by Tiplea, Mäkinen and Enea as a proper extension
of L-codes.
This paper is devoted to a further study
of time-varying codes. First, we show that
adaptive Huffman encodings are special
cases of encodings by time-varying codes.
Then, we focus on three kinds of
characterization results: characterization
results based on decompositions
over families of sets of words,
a Schutzenberger like criterion,
and a Sardinas-Patterson like
characterization theorem.
All of them extend the corresponding
characterization results known for
classical variable length codes.
pdf-file
A-2002-16 Timo Poranen,
3D polyline grid drawings of graphs with linear crossing number. December 2002.
Abstract.
This article studies the properties of three dimensional visibility
representations of
planar graphs and three dimensional crossing-free polyline grid
drawings of non-planar
graphs with known crossing number.
First, we show how to construct in linear time a three dimensional
polygonal z-visibility representation for planar graph having n vertices
with
volume $\lceil \sqrt{\lfloor 3n/2 \rfloor -3} \rceil \times \lceil
\sqrt{\lfloor 3n/2 \rfloor -3} \rceil \times (n-1)$.
This sharpens earlier results for three dimensional visibility
representations for planar graphs.
Second, we show that a planar graph with n-vertices and m-edges,
without any restrictions concerning its degree, admits a three dimensional
crossing-free polyline grid drawing with volume
$\lceil \sqrt{\lfloor 3n/2 \rfloor -3}
\rceil \times \lceil \sqrt{\lfloor 3n/2 \rfloor -3} \rceil \times
3(n-1)$
having at most 2m total edge bends.
Third, we give a drawing algorithm for non-planar graphs. Let G be
a non-planar graph
with n-vertices and m edges and let $G_p$ be the planarized version
of G with n vertices and n' dummy vertices.
We show how to construct in O(n+n') time three dimensional
crossing-free polyline grid drawing of G with volume
$2 \lceil \sqrt{\lfloor 3(n+n')/2 \rfloor -3} \rceil \times 2 \lceil
\sqrt{\lfloor 3(n+n')/2 \rfloor -3} \rceil \times 3(n+n'-1)$
having at most 4m+19n' edge bends. It follows that a n-vertex
non-planar graph with O(n) crossings admits a three dimensional crossing-free polyline grid
drawing with $O(n^2)$ volume.
pdf-file
A-2002-17 Timo Niemi, Marko Junkkari, Kalervo Järvelin, and
Samu Viita,
Advanced query language for manipulating complex entities. December 2002.
Abstract.
Complex entities are one of the most popular ways to model
relationships
among data. Especially complex entities, known as physical assemblies,
are
popular in several applications. The existing query languages intended
for
manipulating complex entities support only extensional queries.
Likewise,
the user has to master in them the structures of complex entities
completely, which is impossible if a physical assembly consists of a
huge
number of parts. Further, they do not support the manipulation of
documents
related to parts of physical assemblies. In this paper we introduce a
novel, declarative and powerful query language, in which the above
deficiencies have been eliminated. Our query language supports text
information retrieval related to parts and it contains intensional
and
combined extensional-intensional querying primitives. These features
afford
the possibility of making queries of new types. In the paper we give
several sample queries which demonstrate the usefulness of these
query
types. In addition, we show that conventional extensional queries can
be
formulated intuitively and compactly in our query language. Among
others
this is due to our querying primitives allowing removal of the
explicit
specification of navigation from the user.
A-2002-17 is available as paper copy only.
A-2003-1 J. Mykkänen, J. Tohka, J. Luoma and U. Ruotsalainen,
Automatic extraction of brain surface and mid-sagittal from PET images applying
deformable models.
May 2003.
Abstract.
In this study, we propose new methods for automatic extraction of the
brain surface and the mid-sagittal plane from functional positron
emission tomography (PET) images. Designing general methods for
these
segmentation tasks is challenging because the spatial distribution of
intensity values in a PET image depends on the applied
radiopharmaceutical
and the contrast to noise ratio in a PET image is typically low. We
extracted the brain surface with a deformable model which is based on
global minimization of its energy. The global optimization allows
reliable automation of the extraction task. Based on the extracted
brain surface, the mid-sagittal plane was determined. Since we did
not
apply information from the corresponding anatomical images, the
extracted brain surface and mid-sagittal plane could be used also
when
registering PET images to anatomical images. Furthermore, we applied
the deformable model for extraction of the coarse cortical structure
based on the tracer uptake from FDG-PET brain images. We tested
the methods with the image of the Hoffman brain phantom (FDG) and
images from brain studies with FDG (17 images) and 11
C-Raclopride
tracers (4 images). The brain surface, the mid-sagittal plane, and
the
cortical structure were reliably delineated from all the images
without
any
user guidance. The proposed segmentation methods provide a promising
direction for automatic processing and analysis of PET brain images.
pdf-file
A-2003-2 Jouni Mykkänen,
Delineation of brain structures from functional positron emission tomography images.
July 2003.
Abstract.
Positron emission tomography (PET) imaging is a unique method for
studying biochemical processes involved in living species. It
provides quantitative information about the processes at a cellular
level, which is needed,
for example in
diagnosis of a disease and the development of new drugs. Quantitative
information can be determined from PET images by extracting volumes of
interest. In order to collect large databases of the functional data
derived from PET, new automatic methods for image analysis are
required.
The delineation of PET images is a challenging task due to noise and
individual
data contents in PET images.
It has not gained attention that it deserves.
This study proposes a new lossless image compression method and
novel approaches to delineate brain surfaces from PET brain images.
First, a low complexity lossless image compression method was
developed for noisy PET brain images. Next, a user-guided software
using intensity values of image was developed and utilized to
determine quantitative values from the PET brain images. Next, a
two-dimensional deformable model and the corresponding anatomical
references from MR images were applied to delineate cortical surfaces
from PET brain images. Deformable models are advanced delineation
methods entailing geometric shape and evolution rules, which connect
the model to data providing its adaptation to the salient features in
an image. This method was able to improve the registration alignment
and correct differences between the anatomical and functional
structures. However, proper segmentation of volumetric
PET images required a new three-dimensional deformable surface
model which was developed in close collaboration with this study.
It uses a global optimization to avoid the initialization problem
common with deformable models.
The new method was applied to extract surfaces
from images in PET brain studies with $^{18}$FDG and
$^{11}$C-Raclopride radiopharmaceuticals.
The delineation procedure was fully
automatic, repeatable and considerably faster than the entirely manual
delineation methods applied with PET images.
Consequently, the coarse cortical structures for the hemispheres
were determined in an iterative way and no anatomical references or user
interactions were required in the process.
This study contributes novel approaches for semi-automatic and
fully automatic surface delineation from PET brain images.
In addition,
an image compression procedure for PET brain images is proposed.
These provide new
possibilities for developing fully automatic applications for
neurological image analysis and databases.
Key words and phrases: brain surface extraction, volume of interest, deformable model,
three-dimensional image analysis, mid-sagittal plane, segmentation, compression.
Ph.D. Dissertation.
A-2003-2 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 271.
A-2003-3 Timo Poranen, Apptopinv - User's guide.
September 2003.
Abstract.
The maximum planar subgraph, maximum outerplanar subgraph, the
thickness and outerthickness of a graph are all NP-complete
optimization problems. Apptopinv is a program that contains
different heuristic algorithms for these four problems:
algorithms based on Hopcroft-Tarjan planarity testing algorithm,
the spanning-tree heuristic and various algorithms based on
the cactus-tree heuristic. Apptopinv contains also a
simulated annealing algorithm that can be used to
improve the solutions obtained from other heuristics.
Most of the heuristics have also a greedy version.
We have implemented graph generators for complete graphs, complete
k-partite graphs, complete hypercubes,
random graphs, random maximum planar and outerplanar
graphs and random regular graphs. Apptopinv supports three
different graph file formats.
Apptopinv is written in C++ programming language for
Linux-platform and GCC 2.95.3 compiler. To compile the
program, a commercial LEDA algorithm library (version 4.3
or newer) is needed.
pdf-file
A-2003-4 Heikki Hyyrö, Practical Methods for Approximate String Matching.
December 2003.
Abstract.
Given a pattern string and a text, the task of approximate string matching
is to find all locations in the text that are similar to the pattern.
This type of search may be done for example in applications of spelling
error correction or bioinformatics. Typically edit distance is used as
the measure of similarity (or distance) between two strings. In this
thesis we concentrate on unit-cost edit distance that defines the
distance beween two strings as the minimum number of edit operations
that are needed in transforming one of the strings into the other. More
specifically, we discuss the Levenshtein and the Damerau edit distances.
Approximate string matching algorithms can be divided into off-line and
on-line algorithms depending on whether they may or may not,
respectively, preprocess the text. In this thesis we propose practical
algorithms for both types of approximate string matching as well as for
computing edit distance.
Our main contributions are a new variant of the bit-parallel approximate
string matching algorithm of Myers, a method that makes it easy to modify
many existing Levenshtein edit distance algorithms into using the Damerau
edit distance, a bit-parallel algorithm for computing edit distance, a
more error tolerant version of the ABNDM algorithm, a two-phase filtering
scheme, a tuned indexed approximate string matching method for genome
searching, and an improved and extended version of the hybrid index of
Navarro and Baeza-Yates.
To evaluate their practicality, we compare most of the proposed methods
with previously existing algorithms. The test results support the claim of the
title of this thesis that our proposed algorithms work well in practice.
Ph.D. Dissertation.
A-2003-4 has appeared electronically in
Acta Electronica Universitatis Tamperensis, vol. 308.
A-2003-5 Poika Isokoski and Roope Raisamo,
Evaluation of a Multi-Device Extension of Quikwriting.
December 2003.
Abstract.
Several new text entry methods for mobile computers have been
proposed recently. Many of these have not been tested to reveal whether they
in fact perform as advertised. We report a longitudinal laboratory study
on the use of a system known as Quikwriting. We have extended Quikwriting
so that a stylus, a joystick, or a keyboard can be used as the input
device.
Twelve participants used the stylus and joystick modes of input in
twenty 15-minute sessions. In the end their performance with the keyboard
was tested to see if Quikwriting skill transfers to new devices easily.
Quikwriting was found to be functional with all of the tested devices,
but laborious to learn. The final text entry rates were 16.1 wpm with the
stylus, 13.2 wpm with the joystick, and 6.1 wpm with the keyboard.
A-2003-5 is available as paper copy only.
A-2004-1 Markopekka Niinimäki, Conceptual Modelling Languages.
January 2004.
Abstract. Conceptual modelling is needed to form a description of the
domain of application at hand. In order to express the result of
conceptual modelling, we need a modelling language. First order predicate
logic (FOPL) or its variants (like Horn-clauses and Description Logics)
and extensions (second order logics) can form a backbone of such a
language, but some criteria is needed to define the fruitfulness or
suitability of a modelling language, given the modelling task. The
modelling language together with its methodology constitute a modelling perspective.
Many accounts of conceptual modelling emphasise an
intensional perspective. This means that the starting point in conceptual
modelling is the contents of the concepts that subsist in the domain of
application (as opposed to "things" in the domain of application - they
belong to the extensions of these concepts). If an intensional perspective
is used, it should be visible in the modelling language as well;
therefore we divide modelling languages into intensional and extensional
languages, and hybrid languages that combine some aspects of these two.
First order predicate logic has often been used as an example of a
language with a well es-tablished extensional semantics. We examine FOPL
as a modelling language in connection with Sowa s Conceptual Graphs (CGs).
It can be demonstrated that a limited version of the language of CGs is
equal (in expressive power) to that of FOPL with unary and binary
predicates. However, contrary to the claims of proponents of CGs, CG
presentations are not necessarily easier to read or understand than the
same presentations expressed in FOPL (as can be demonstrated by comparing
typical but complex FOPL formulas and their CG counterparts).
Kauppi's concept calculus is based on concepts and the relation of intensional
containment. An approach where a modelling language is based completely on
concept calculus is presented in this thesis. This approach has the
advantage that the user can apply the operations of the calculus when
designing a conceptual schema of the domain of application. However, this
sort of modelling can be restrictive and impractical in many cases, since
it enforces rather strict concept structures. CONCEPT D, a modelling
language, can be seen as a less restrictive alternative.
Using CONCEPT D, the modeller reports the results of the modelling
task in the form of concept diagrams. But we often need to ask
"is this concept diagram correct" or "does it correspond well to the
domain of application". Without semantics (which connects the diagrams to something
extra-linguistic) we can only answer these questions on the basis of our
intuitions. We address these questions from two different angles. First we
demonstrate how to map (simplified) CONCEPT D concept diagrams into IFO
schemata that have well-defined semantics. Then we study what kind of
semantical theory (e.g. possible world semantics, situation semantics,
HIT-semantics) would capture the features that we want to express in
concept diagrams. CONCEPT D has been rarely used in applications where it
would be important to make a distinction between, for example, prime
number less than one and round square, but is has the capability of making
these distinctions. Therefore, it seems that it needs semantics
fine-grained enough. Finally, we discuss, based on the previous chapters,
on what premises HIT-semantics would serve as the semantical background of
conceptual modelling.
Ph.D. Dissertation.
A-2004-1 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 326.
A-2004-2 Markku Turunen, Jaspis
– A Spoken Dialogue Architecture and its Applications.
February 2004.
Abstract.
Speech can be an efficient and natural way for communication between
humans and computers. Many practical applications have been
constructed,
but the full potential of speech applications has not been utilized.
In
addition to technological shortcomings, the development of speech
applications lacks suitable techniques, methodology and development
tools. For example, mobile and multilingual communication needs
flexible
and adaptive interaction methods which take into account the needs of
different users and different environments. This dissertation
addresses
the following question: what kind of a system architecture do
advanced
speech applications require? The following challenges are
specifically
addressed: How could the system architecture support advanced
interaction techniques? How could application development be
supported
by suitable models, methodology and tools?
This dissertation introduces the Jaspis speech application
architecture
that has been designed to support adaptive and flexible
human-computer
interaction techniques. This work also presents several applications
constructed on the Jaspis architecture. Two multilingual e-mail
applications, and two timetable applications are presented to provide
concrete examples. The challenges of pervasive speech applications
are
introduced in the context of an ubiquitous computing application. The
findings from the use of the Jaspis-based applications are
reported.
Several Jaspis-based interaction models and tools are introduced to
facilitate the development of practical applications. The focus is on
human-computer interaction issues, and solutions are presented for
tasks
such as error management, Wizard of Oz experiments and corpora
collection. Finally, an enhanced version of the Jaspis architecture
is
presented. The Jaspis2 architecture focuses on distributed and
concurrent spoken dialogues, which are needed in pervasive
applications,
and in general to provide more natural interaction models. The main
contribution of this work, the Jaspis architecture, will be released
simultaneously with this dissertation as an open source software for
speech application researchers and developers.
Ph.D. Dissertation.
A-2004-2 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 325.
A-2004-3 Poika Isokoski, Manual Text Input:
Experiments, Models, and Systems.
April 2004.
Abstract.
Despite the emergence of speech controlled computers and direct
manipulation that both have diminished the need to operate computers
with
textual commands, manual text entry remains one of the dominant forms
of
human-computer interaction. This is because textual communication is
one
of the main reasons for using computers.
Mobile and pervasive computing have been popular research areas
recently.
Thus, these issues have a major part in the thesis at hand. Most of
the text entry methods that are discussed are for mobile computers.
One
of the three main contributions of the work is an architecture for a
middleware system intended to support personalized text entry in an
environment permeated with mobile and non-mobile computers.
The two other main contributions in this thesis are experimental work
on text entry methods and models of user performance in text entry
tasks.
The text entry methods tested in experiments were the minimal device
independent text entry method (MDITIM), two methods for entering
numbers
using a touchpad, Quikwriting in a multi-device environment, and a
menu-augmented soft-keyboard. MDITIM was found to be relatively
device independent, but not very efficient. The numeric entry
experiment
showed that the clock metaphor works with a touchpad, but with a high
error rate. An improved "hybrid" system exhibited a lower error rate.
Quikwriting was tested to evaluate the claims on its performance made
in
the original publication and to see if it works with input devices
other
than the stylus. The perfomance claims were found to be exaggerated,
but
Quikwriting worked well with the three tested input devices (stylus,
game
controller, and a keyboard). The menu augmented soft keyboard was
compared
to a traditional QWERTY soft keyboard to verify modeling results that
show
significant performance advantages. No performance advantage was
observed
during the 20 session experiment. However, extrapolations of the
learning
curves cross suggesting that with enough practice the users might be
able
to write faster with the menu augmented keyboard.
The results of the modeling part are two-fold. First, the explanatory
power of a simple model for unistroke writing time was measured. The
model accounted for about 70% of the variation when applied carefully,
and
about 60% on first exposure. This sets the level of accuracy that
more
complex models must achieve in order to be useful. Second, a model
that
combines two previously known models for text entry rate development
was
constructed. This model improves the accuracy of text entry rate
predictions between measured early learning curve and the theoretical
upper limit.
Ph.D. Dissertation.
A-2004-3 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 340.
A-2004-4 Kari Kilpinen, Reflective teacher using the
computer-network in teaching; how the psycho-epistemological learning styles help
to better design learning environments. May 2004.
Ph.D. Dissertation.
A-2004-4 has appeared electronically in
Acta Electronica Universitatis Tamperensis, vol. 365.
A-2004-5 Timo Niemi, Marko Junkkari, and Kalervo Järvelin,
Query language approach for next generation information systems. April 2004.
Abstract.
In developing next generation information systems (NGISs) three kinds of integration
is necessary: the integration of data-oriented, behavioral and deductive aspects of
application domains, the seamless integration of the manipulation of the essential
relationship types (is-a relationship, part-of relationship, association) and the
integration of the manipulation of the extensional and intensional levels of data.
Further, NGISs have to support the manipulation of text documents which can be associated
with entities or relationships among them in an application domain. Information in
text documents can also be used as sources for deduction. In this paper we address
these topics. We introduce a set of primitives which support required integration
in a natural and flexible way. Based on these primitives we have developed a
concept-oriented query language for NGISs. Its user can make expressive and compact
queries by combining available concepts and concept structures equipped with variables.
Our sample queries demonstrate that, in addition to conventional extensional queries,
our query language also supports intensional and combined extensional – intensional
queries which are beyond of the capabilities of contemporary query languages.
Keywords: Next Generation Information Systems (NGISs), Query languages,
XML documents, Extensional and intensional levels of data, Integration of data.
A-2004-6 Jaakko Riihimaa, Taxonomy of
information and communication technology innovations adopted by small and
medium sized enterprises. May 2004.
Ph.D. Dissertation.
A-2004-6 has appeared electronically in
Acta Electronica Universitatis Tamperensis, vol. 366.
A-2004-7 Timo Poranen, Approximation Algorithms for the Topological Invariants
of Graphs. September 2004.
Abstract.
Topological graph theory studies the embeddings of graphs on various
surfaces and the properties of these embeddings. Topological properties of
graphs have many applications in the fields of graph drawing, user interface
design, circuit design, and resource location optimization.
This thesis studies approximation methods for the following
NP-complete optimization problems: maximum planar subgraph, maximum outerplanar subgraph,
and thickness of a graph. We also study the outerthickness problem
which complexity status is not known.
We compare the solution quality and computation times of a simulated
annealing algorithm and
several algorithms based on triangular cactus heuristic, including
other heuristics taken from the literature, to approximately solve
these problems.
Triangular cactus heuristic was the first non-trivial approximation
algorithm for the
maximum planar and outerplanar subgraph problems. We give a modified
version of the triangular cactus
heuristic that has at least equal performance ratio and asymptotic
running time as the linear time version of the original algorithm.
A large number of experiments show that the new algorithm achieves
better approximations than the earlier methods.
We give two new theoretical results for the thickness and
outerthickness of a graph.
We prove a new upper bound for the thickness of complete tripartite
graphs, and lower
and upper bounds in the terms of the minimum and maximum degree of a
graph for outerthickness.
Also, the simulated annealing algorithm given in this work solves
partially an open problem related to
the thickness of the complete bipartite graphs. Our experiments show
that the general formula also holds for some previously unknown cases.
Ph.D. Dissertation.
A-2004-7 has appeared electronically in
Acta Electronica Universitatis Tamperensis, vol. 391.
A-2004-8 Marko Junkkari,
Modeling and manipulation of composed objects in NGIS. December 2004.
Abstract.
In Next Generation Information Systems (NGISs) object-orientation and deductive
aspects are integrated to databases. This means that any modeling methods
intended for NGISs need integrate data-oriented, behavioral and deductive
aspects of application domains. RDOOM (Relational Deductive Object-Oriented
Modeling) is a modeling method in which these aspects are seamlessly integrated
with each other. However, until now RDOOM has not been complete to model such
objects which contain other objects (called composed objects). In other words
among the principal data modeling relationships RDOOM has only dealt with the
association and the is-a relationships but not the part-of relationship which is
the third principal modeling relationship. Here, we extend the modeling of NGISs
by the manipulation of the part-of relationship. This work involves integration
of is-a and part-of hierarchies, deduction based on part-of structures, general
methods aimed at manipulate structurally different composed objects, and
manipulating unknown aspects in part-of hierarchies. In this paper, we present a
comprehensive set of data modeling primitives on which conceptual derivation can
be based.
Keywords: NGIS, data integration, formal specification,
conceptual derivation, data model, deduction, composed object, part-of
relationship, query languages, real word applications, inheritance, aggregation
A-2005-1 Paavo Arvola, Marko Junkkari, Timo Aalto and Jaana Kekäläinen,
Utilizing context in weighting of XML elements for information retrieval. April 2005.
Abstract.
A re-weighting method for elements in XML retrieval is proposed. The method is
based on the idea of using the ancestors of an element as a context: the better
context the element has - good interpreted as weighting score - the more its own
weight is increased in relevance scoring. Our basic weighting scheme is a tf*idf
modification based on BM25. We will also discuss the effects of tuning length
normalization on the size of retrieved elements, and the problem of overlapping
elements in XML evaluation.
Keywords: XML, structured documents, re-weighting, contextualization.
A-2005-2 Timo Niemi and Janne Jämsen,
Discovering of semantic associations. June 2005.
Abstract. In contemporary query languages
the user is responsible for the specification of navigation among semantically
related data. Because of the huge amount of data and complex structural relationships
among data in modern applications it is unrealistic to suppose that the user
could know completely the content and structure of available information. There
are several query languages whose idea is to facilitate navigation in unknown
structures of databases, e.g., a navigation path can contain unknown parts.
However the background assumption of these languages is that the user knows how
data are related to each other semantically in the structure at hand. So far
only little attention has been paid to how unknown semantic associations among
available data can be discovered. We address this problem in this paper. A
semantic association between two entities can be constructed if such a sequence
of relationships expressed explicitly in a database can be found that connects
these entities to each other. This sequence may contain several other entities
through which the original entities are connected to each other indirectly. We
introduce an expressive and declarative query language for discovering semantic
associations. In addition to discovering semantic associations between entities
given explicitly, our query language is able to discover semantic associations between
entities that are only known for some of their characteristics. Further, it
integrates the manipulation of semantic associations with the manipulation of
documents which may contain information on entities in semantic associations.
Because a semantic association may contain several relationships and entities,
the results of queries are represented on the basis of natural language in
order to facilitate correct interpretation by the user. We also categorize
several query types and give sample queries on them. These sample queries
demonstrate how also complex queries can be expressed compactly and intuitively
in our language.
Keywords: Semantic association, knowledge discovering, query language, document, XML.
A-2005-3 Kai Koskimies, Ludwik Kuzniarz, Jyrki Nummenmaa and Zheying Zhang
(eds.), Proceedings of the NWUML'2005: The 3rd Nordic Workshop on UML
and Software Modeling. August 2005.
pdf-file
A-2005-4 Timo Tossavainen, Virtual Reality and Posturography Applied to Postural
Control Research. October 2005.
Abstract.
This thesis describes design, development, and applications of an
integrated stimulation and measurement system for postural control research
based on virtual reality (VR) methods and force platform posturography. The
system exposes test subjects to immersive computer-generated environments intended
to disturb balance and measures the response using a force platform. Analysis is
carried out on stabilograms obtained from the force platform to determine the
outcome.
Our first experiments show that virtual environments affect balance and
that they can be designed to cause effects, such as leaning in different
directions, in test subjects. During the development, we compared the
head-mounted display (HMD) and CAVE at Tampere Virtual Reality Center for visual
stimulation. Test subjects were exposed to the same virtual environments using the two
displays and significant differences in the responses were found between HMD and
CAVE. The constructed VR posturography system was deployed in a laboratory in
the Hearing Center of Tampere University Central Hospital and tested on control
subjects and patients with diagnosed balance disorders. Responses of control
subjects and patients with Meniere's disease differed significantly
and provided good discrimination between the two groups. Finally, pattern
recognition methods were applied to summarize the differences in
measurements that are otherwise difficult to interpret.
The applications described in this thesis show that VR is a versatile and
effective visual stimulation method for use in postural control research. Many
of the experimental setups implemented multiple balance tests in sequence, all
using same hardware. VR posturography thus provided an easy way to quickly and
comprehensively characterize a test subject's postural stability.
Keywords. Virtual reality, posturography, postural control,
postural stability.
Ph.D. Dissertation.
A-2005-4 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 507.
A-2005-5 Tatiana Evreinova, Grigori Evreinov, and Roope Raisamo,
An alternative approach to
strengthening tactile memory in hearing impaired adults. September 2005.
Abstract.
Deaf and hearing-impaired people need special educational and
developmental tools to support their social inclusion. Research in
vibro-tactile pattern perception has shown that tactile memory could
be crucial aspect in coding and imaging semantic information to the
impaired. This paper describes a simple matching game designed to
facilitate learning 27 vibro-tactile composite patterns (tactons)
which can be produced with the Logitech tactile feedback mouse. Our
assumption was that a particular framework and game intrigue would induce a
player to mobilize the perceptive skills and deploy individual playing
tactics to recall the tactons when progressing through the game. The
performance of 10 subjects using soundproof headphones was investigated in terms
of the number of repetitions required to memorize and learn the
mono-frequency, bi-frequency and three-frequency tactons, and
selection time needed to match the tactons in the game script. The analysis of
the data collected indicated that the novice-to-expert transition was
significantly above chance when the results obtained in the first and
the last test sessions were statistically analyzed and compared.
There was also a significant difference between mean selection times needed
to match the composite patterns depending of their complexity in the
first and the last test sessions. Upon learning and training within game,
the tactons may be employed to assign alphabet characters or symbols to
communicate textual or symbolic information.
A-2005-6 Tatiana Evreinova, Alternative visualization of textual
information for people with sensory impairment. November 2005.
Abstract.
By virtue of lacking visual feedback or access to verbal communication, people
with a sensory impairment use alternative means for information imaging that
rely on residual senses. For this reason, a wide range of assistive hardware and
software came into the market to provide an efficient way of alternative
imaging, for instance, of textual information. Nevertheless, nearly one third of
these techniques were withdrawn from the market due to lack of use.
Recent innovations offer limited functionality and more often than not, the
low accuracy of the produced output hampers the use of assistive aids.
Designers should focus not on the technique itself, but on the optimal
combination of the intact modalities to provide the disabled user with efficient
access to textual information. One of the aims in the adequate use of assistive
aids is to shape appropriate modality-specific notions to mediate
communication with people having normal abilities. Implementation of the
novel assistive techniques may be based on diverse technologies employing
speech and speech-like signals, visual and vibro-tactile patterns, which can be
used to display unambiguously the semantics of the textual message in a case
when the environment has different constraints or the user has inferior
perceptive thresholds due to chronic disease. In such cases, the required
techniques should provide real-time or close to real time processing and
imaging of the textual information so that both ordinary users and people with
a sensory impairment would be able to use it autonomously without assistants
or interpreters.
The foremost purpose of this dissertation is to consider the latest assistive
technologies in order to suggest further improvements. Therefore, the summary
provides background for the research papers included and an analytical survey
of assistive methods/techniques. The problematic aspects affecting the use of
computer help for people having ocular pathology and hearing disorders is the
particular subject of our study. The considerations presented are intended for
the developers of advanced assistive user interfaces.
The empirical part of the dissertation consists of a collection of the assistive
aids which were designed to augment and expand access to the textual
information for people with a sensory impairment. The central idea of this
dissertation was blending signals of several modalities to reproduce distinct
cases of the recognizable spatial-temporal semantic constructions such as vibrotactile,
audio-tactile and color patterns within minimal array of the coding units
used for alternative imaging of textual information. Two prototypes of the
wearable assistive devices such as BlinkGlasses and TactilePointer and some
other software tools were designed to carry out empirical research in these
subjects. Eight research papers representing the main contribution of this
dissertation are introduced. Careful combination of the empirical research,
thorough evaluation and further analysis of the outcomes which the approaches
developed resulted in was the main principle for the completion of these
empirical studies.
A key question is whether people with a sensory impairment can take
advantage of the devices developed and if so, to what extent. How flexible the
use of assistive technologies will become and how powerful they are going to
be, will depend on the further development of the exploratory strategies
directed toward the improvement of the assistive aids.
Ph.D. Dissertation.
A-2005-6 has appeared electronically as
Acta Electronica Universitatis Tamperensis, vol. 478.