@TechReport{A-1990-1, authorkey = "NummenmaaJ", author = "Jyrki Nummenmaa", title = "Constructing compact rectilinear planar layouts using canonical representation of planar graphs", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-1", note = "available as a paper copy only; revised version appeared in Theoretical Computer Science 99 (1992), 213--230", } @TechReport{A-1990-2, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "Operation-oriented query language approach for recursive queries", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-2", note = "available as a paper copy only; revised version appeared in Information Systems 17, 1 (1992), 49--75 and 17, 1 (1992), 77-106", } @TechReport{A-1990-3, authorkey = "KauranenK MakinenE", author = "Kimmo Kauranen and Erkki M{\"a}kinen", title = "A note on Cohen's formal model for computer viruses", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-3", note = "available as a paper copy only; revised version appeared in ACM SIGSAC Review 8, 2 (1990), 40--43", } @TechReport{A-1990-4, authorkey = "JarnvallE", author = "Esa J{\"a}rnvall", title = "Fine tuning a locally adaptive data compression scheme", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-4", note = "available as a paper copy only", } @TechReport{A-1990-6, authorkey = "JarvelinK NiemiT", author = "Kalervo J{\"a}rvelin and Timo Niemi", title = "Entity-based query construction for relational database access", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-6", note = "available as a paper copy only", } @TechReport{A-1990-7, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Remarks on the assignment heuristic for drawing bipartite graphs", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-7", note = "available as a paper copy only", } @TechReport{A-1990-8, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On drawing regular bipartite graphs", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-8", note = "available as a paper copy only; revised version appeared in International Journal of Computer Mathematics 43 (1992), 39-43", } @TechReport{A-1990-9, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "The rule-based prototype implementation for the operation-oriented recursive query language approach ant its integretion with relational databases", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-9", note = "available as a paper copy only", } @TechReport{A-1990-11, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "Deductive database queries based on transitive relationship and entity types", institution = "Department of Computer Science, University of Tampere", year = "1990", number = "A-1990-11", note = "available as a paper copy only", } @TechReport{A-1991-1, authorkey = "KoskimiesK", author = "Kai Koskimies", title = "Object-orietation in attribute grammars", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-1", note = "available as a paper copy only", } @TechReport{A-1991-2, authorkey = "KoskimiesK MakinenE", author = "Kai Koskimies and Erkki M{\"a}kinen", title = "On a grammar transformation related to class hierarchies", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-2", note = "available as a paper copy only", } @TechReport{A-1991-3, authorkey = "JarvinenP", author = "Pertti J{\"a}rvinen", title = "On approaches in information systems research", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-3", note = "available as a paper copy only", } @TechReport{A-1991-4, authorkey = "HelttulaE", author = "Esa Helttula", title = "Manipulating disjoint sets: algorithms, testing, and animation", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-4", note = "available as a paper copy only", } @TechReport{A-1991-6, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On homomorphic images of left Szilard languages", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-8", note = "available as a paper copy only; revised version appeared in International Journal of Computer Mathematics 46 (1992) 131--135", } @TechReport{A-1991-7, authorkey = "KoskimiesK VihavainenJ", author = "Kai Koskimies and Juha Vihavainen", title = "The problem of unexpected subclasses", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-7", note = "available as a paper copy only", } @TechReport{A-1991-8, authorkey = "AulinA JarvinenP", author = "Arvid Aulin and Pertti J{\"a}rvinen", title = "A new derivation of entropy laws related to the survival of complex dynamic systems", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-8", note = "available as a paper copy only", } @TechReport{A-1991-9, authorkey = "HietalaP NummenmaaJ", author = "Pentti Hietala and Jyrki Nummenmaa", title = "{MEDUSA} --- {A} multimodal database user interface with a computer supported learning aid", institution = "Department of Computer Science, University of Tampere", year = "1991", number = "A-1991-9", note = "available as a paper copy only", } @TechReport{A-1992-1, authorkey = "JarvinenP", author = "Pertti J{\"a}rvinen", title = "Impacts of electronic markets on work", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-1", abstract = "The domain of electronic markets are increasing in relation to electronic hierarchies. Hence it is important to analyze possible impacts of electronic markets on a human being at work. A man can be in different positions concerning electronic markets: 1. a developer of an inter-organizational information system (IOS), 2. a user (a seller or a buyer) of electronic markets, and 3. an object of markets, i. e. a specialist whose services are sold on electronic markets. First, to construct the IOS a developer has to perform particular tasks: requirements analysis, design, implementation and thereafter often also maintenance. Second, a user of electronic markets can do different things depending on whether she/he is working in a producer company, in a distributor firm, in a buyer company, in a network provider company or in financial services. Third, services offered by a human being on electronic markets should inform potential buyers about her or his service. On the other hand a buyer must describe which kind of service she or he needs. In the first position, the idea of the IOS means that the production/consumption chain is lengthened. The developer of the IOS must master this chain over two or more organizations. Hence, she or he must be more competent than nowadays. Concerning the second position, a user of electronic markets, by definition, will lose social contacts. Her variety to communicate will diminish, because she or he must use the standardized product/service description language and/or the information retrieval language at hand. In the third position, the services offered by a certain expert must be described as in detail as possible. But this creates a dilemma, if a task can be described in elementary operations, it could be automated, i.e. the task is no more necessarily performed by a human being but by a computer or by an automaton.", note = "available as a paper copy only", } @TechReport{A-1992-2, authorkey = "JarvinenP", author = "Pertti J{\"a}rvinen", title = "On purchasing process of a software package---how to teach it?", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-2", abstract = "In the software industry there is a mass production of packages for some well-defined purposes, as for text processing, network management, book-keeping, budgeting etc. Different suppliers produce packages intended for the similar tasks, and they have both the same and slightly differing features. The proportional importance of software costs compared with hardware costs is still increasing. Hence, selection of the package is a problem proper where particular knowledge and skills are needed. The course on purchasing of a software package was organized by this author in two last springs in the University of Tampere. The course was intended to students in computer science, but one third of the participants were from other disciplines, called application sciences. This fact gave an opportunity to form groups with three students, two from computer science and one from application sciences. The latter person played an important role, when a group defined its needs and requirements. Each group had chance to define its purchasing order, i.e. a software package to be purchased. Some of the orders were real ones and some others tentative ones. The local software companies allowed the groups to visit and to negotiate whether the package offered was suitable to the purposes defined by the group. After collecting the data about candidate packages the student groups made a comparison and then recommended one of the packages to be purchased. The groups also considered the ready made contracts and planned their proposals for changes and amendments to the conventional contracts. In this paper I shall describe the pros and cons of the approach outlined above. I will also give short descriptions of the reports prepared by the groups, actions to be taken and evaluation of various features of the course. The students expressed their views on teaching and working modes, on assessment of learning and on the whole approch. Students' evaluation was rather positive. This strongly supports the approach selected. The recommendations for improving our approach are minor and concern such wishes as changing starting time (8 o'clock) and usage of teaching material.", note = "available as a paper copy only", } @TechReport{A-1992-3, authorkey = "JarvelinK NiemiT", author = "Kalervo J{\"a}rvelin and Timo Niemi", title = "General value conversion and aggregation operations: definition and integration with relational, entity-based and deductive data retrieval techniques", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-3", abstract = "Existing DBMS's do not support sufficiently advanced information retrieval in heterogeneous fact database environments. From the user viewpoint this means that many information needs cannot be satisfied solely by traditional fact database operations. Transitive computation, multi-level aggregation and value conversion are frequently needed together with traditional operations. The possibilities for providing these capabilities in fact database management systems based on the relational data model are considered in this paper. It is important that the extensions for advanced data retrieval are made in a uniform way with other relational processing. This means that, on one hand, new relational operations are developed, and on the other hand, non-relational operations are integrated with relational processing via predicates expressed within relational operations. In this paper, relational algebra is extended by two generalized relational operations: one for multi-level aggregation and the other for value conversion. A set of non-relational operations (called deductive operations) for performing transitive computation is also introduced. User's query formulation can also be facilitated by providing him with an entity-based data retrieval operation on a high abstraction level. Such a high-level entity-based data retrieval operation is also introduced. The value conversion operation provides unit of measurement-related transparency. It supports very versatile conversion (including conversion of compound attributes) and checks automatically the derivability of conversion requests. The conversion expressions require minimal information from the user. The data aggregation operation provides aggregation level transparency. It supports, among others, multiple layered aggregation levels and hierarchical reclassification of the classification attributes determining the aggregation levels. In the data aggregation operation, the functional dependencies between the source and result relations are connected in a complex way. Both operations are defined in this paper in an exact way so that they construct both the instances and the schemas, including functional dependencies, of the result relations. Complex data retrieval requires that value conversion, aggregation, deductive operations and entity-based data retrieval operation are integrated with traditional relational operations. In this paper, a query language for advanced information retrieval consisting of these operations is developed. This language allows the intermixing of these operations with each other without limiting the nesting levels. Special attention is paid to the structures, primitives and principles in terms of which the operations and the query language can be implemented. All these aspects are defined formally, in a functional way. In other words, the definition is independent of any programming language. In addition, the concretization of these aspects in a prototype system based on Prolog-language and a workstation environment are considered.", note = "available as a paper copy only; the material of this report has appeared in three separate journal articles: 1) An entity-based query interface for relational database access, Part I: Entity type representation. Data & Knowledge Engineering 10 (1993) 117--150, 2) An entity-based query interface for relational database access, Part II: Entity query construction and updating, Data & Knowledge Engineering 10 (1993) 151--186, and 3) Deductive Information Retrieval Based on Classifications, Journal of the American Society for Information Science 44,10 (1993) 557--578", } @TechReport{A-1992-4, authorkey = "JarvinenP", author = "Pertti J{\"a}rvinen", title = "On research into the individual and computing systems", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1992-4.ps.Z", } @TechReport{A-1992-5, authorkey = "KoskimiesK VihavainenJ", author = "Kai Koskimies and Juha Vihavainen", title = "Incremental parser construction with metaobjects", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1992-5.ps.Z", } @TechReport{A-1992-6, authorkey = "LahteenmakiE", author = "Eero L{\"a}hteenm{\"a}ki", title = "Strateginen tarkastelu tietotekniikan mahdollisuuksista yritysten tekstitiedon hallinnassa", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-6", note = "available as a paper copy only", } @TechReport{A-1992-7, authorkey = "KorpimiesK", author = "Kai Korpimies", title = "A connectionist tutoring system", institution = "Department of Computer Science, University of Tampere", year = "1992", number = "A-1992-7", abstract = "In this report, a connectionist tutoring system for English verb conjugation is presented. In the system both the expert and the student are modelled with connectionist networks. The architecture of the networks is borrowed from a study by Rumelhart and McClelland (1986), whereas the theoretical framework is largely provided by Smolensky's PTC theory (1988). The focal point of the report is in the comparison of the knowledge which is implicitly represented in the networks. A method is proposed, based on studying how the networks process individual examples.", note = "available as a paper copy only", } @TechReport{A-1993-1, authorkey = "JarnvallE KoskimiesK", author = "Esa J{\"a}rnvall and Kai Koskimies", title = "Language implementation model in Ta{LE}", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-1", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-1.ps.Z", } @TechReport{A-1993-2, authorkey = "JarvinenP", author = "Pertti J{\"a}rvinen", title = "Notes on assumptions of user modelling", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-2", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-2.ps.Z", } @TechReport{A-1993-3, authorkey = "KoskimiesK MakinenE", author = "Kai Koskimies and Erkki M{\"a}kinen", title = "Inferring state machines from trace diagrams", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-3", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-3.ps.Z", note = "revised version appeared in Software --- Practice & Experience 24 (1994) 643--658 under a different title", } @TechReport{A-1993-4, authorkey = "JarnvallE KoskimiesK", author = "Esa J{\"a}rnvall and Kai Koskimies", title = "Computer-aided language implementation with Ta{LE}", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-4.ps.Z", } @TechReport{A-1993-5, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "A form-based user interface for {NF2} relations and its implementation strategy", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-5", 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.", note = "available as a paper copy only, revised version appeared in Information Processing & Management 31 (1995), 215--231 under the title A Straightforward NF2 Relational Interface with Applications in Information Retrieval", } @TechReport{A-1993-6, authorkey = "NieminenK", author = "Kari Nieminen", title = "A bi-directional model from an equation to mathematical word problems", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-6.ps.Z", } @TechReport{A-1993-7, authorkey = "PetterssonM", author = "Matti Pettersson", title = "Analysis in analysis", institution = "Department of Computer Science, University of Tampere", year = "1993", number = "A-1993-7", abstract = "Research in cognitive psychology suggest that the concepts human beings use vary across individuals, time and contexts. In this paper we study implications of these findings for system analysis methodologies. These methodologies seem to assume stability and generalizability of mental entities and thus the interrelations of concepts, operations and technology are poorly understood. Based on studies in cognitive psychology, two conclusions are made: First, a theory view of system development is proposed. Second, to ensure development of both the concepts and the technology, system development should be understood as a creative learning process.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1993-7.ps.Z", } @TechReport{A-1994-1, authorkey = "MakinenE SierantaM", author = "Erkki M{\"a}kinen and Mika Sieranta", title = "Genetic algorithms for drawing bipartite graphs", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-1", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-1.ps.Z", note = "revised version appeared in Intern. J. Computer Math. 53 (1994), 157--166", } @TechReport{A-1994-2, authorkey = "LehikoinenJ MakinenE", author = "Juha Lehikoinen and Erkki M{\"a}kinen", title = "Notes on distance-based coding methods for binary trees", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-2", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-2.ps.Z", note = "shorter version appeared in EATCS Bulletin 55 (1995), 166--169", } @TechReport{A-1994-3, authorkey = "KlemettiH LapinleimuI MakinenE SierantaM", author = "Harri Klemetti and Ismo Lapinleimu and Erkki M{\"a}kinen and Mika Sieranta", title = "Trimming the spring algorithm for drawing hypergraphs", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-3", 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.", note = "available only as a paper copy, fully revised version appeared in SIGCSE Bulletin 27, 3 (1995), 34--38", } @TechReport{A-1994-4, authorkey = "NiittymakiM", author = "Maarit Niittym{\"a}ki", title = "Implementing a {PL}/{M}-to-{C} converter with Ta{LE}", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-4.ps.Z", } @TechReport{A-1994-5, authorkey = "MannistoT SystaT TuomiJ", author = "Tatu M{\"a}nnist{\"o} and Tarja Syst{\"a} and Jyrki Tuomi", title = "{SCED} report and user manual", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-5.ps.Z", } @TechReport{A-1994-6, authorkey = "JuutistenahoA", author = "Ari Juutistenaho", title = "Linear time algorithms for layout of generalized trees", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-6.ps.Z", note = "revised version will appear in Fundamenta Informaticae", } @TechReport{A-1994-7, authorkey = "JuutistenahoA", author = "Ari Juutistenaho", title = "Linear time algorithms for layout of acyclic digraphs with variable-sized vertices", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-7", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-7.ps.Z", } @TechReport{A-1994-8, authorkey = "WikstromCE", author = "Carl-Erik Wikstr{\"o}m", title = "An investigation of factors influencing the success of customer-oriented marketing information systems", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-8", 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.", note = "available as a paper copy only", } @TechReport{A-1994-9, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "A note on the grammatical inference problem for even linear languages", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-9", abstract = "This note introduces subclasses of even linear languages for which there exist inference algorithms using positive samples only.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-9.ps.Z", note = "revised version appeared in Fundamenta Informaticae 25 (1996) 175--181", } @TechReport{A-1994-10, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "Prolog-based implementation of a straightforward {NF2} relational query interface", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-10", 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.", note = "available as a paper copy only; revised version appeared in Information & Software Technology 38 (1996) 11--24 under the title The Processing Strategy for the Frc-interface", } @TechReport{A-1994-11, authorkey = "MannistoT SystaT TuomiJ", author = "Tatu M{\"a}nnist{\"o} and Tarja Syst{\"a} and Jyrki Tuomi", title = "Design of state diagram facilities in {SCED}", institution = "Department of Computer Science, University of Tampere", year = "1994", number = "A-1994-11", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1994-11.ps.Z", } @TechReport{A-1995-1, authorkey = "NummenmaaJ", author = "Jyrki Nummenmaa", title = "Designing desirable database schemes", institution = "Department of Computer Science, University of Tampere", year = "1995", number = "A-1995-1", note = "Ph. D. Thesis, available only as a paper copy", } @TechReport{A-1995-2, authorkey = "KujansuuE LindbergT MakinenE", author = "Eija Kujansuu and Tuukka Lindberg and Erkki M{\"a}kinen", title = "The stable roommates problem and chess tournament pairings", institution = "Department of Computer Science, University of Tampere", year = "1995", number = "A-1995-2", 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.", note = "a revised version appeared in Divulgaciones Matematicas 7, 1 (1999), 19-28", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1995-2.ps.Z", } @TechReport{A-1995-3, authorkey = "HyrskykariA", author = "Aulikki Hyrskykari", title = "Development of program visualization", institution = "Department of Computer Science, University of Tampere", year = "1995", number = "A-1995-3", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1995-3.ps.Z", } @TechReport{A-1995-4, authorkey = "RaihaL", author = "Liisa R{\"a}ih{\"a}", title = "Note on approximate comparison of sequences with normalization", institution = "Department of Computer Science, University of Tampere", year = "1995", number = "A-1995-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1995-4.ps.Z", } @TechReport{A-1996-1, authorkey = "KoskimiesK MannistoT SystaT TuomiJ", author = "Kai Koskimies and Tatu M{\"a}nnist{\"o} and Tarja Syst{\"a} and Jyrki Tuomi", title = "On the role of scenarios in object-oriented software design", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-1", 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.", url = "ftp://cs.uta.fi/pub/reports/A-1996-1.ps.Z", } @TechReport{A-1996-2, authorkey = "AhoI MakinenE SystaT", author = "Isto Aho and Erkki M{\"a}kinen and Tarja Syst{\"a}", title = "Remarks on the thickness of a graph", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-2", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-2.ps.Z", note = "revised version appeared in Information Scineces 108 (1998), 1-4", } @TechReport{A-1996-3, authorkey = "HarsuM", author = "Maarit Harsu", title = "Automated construction of source-to-source translators", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-3", 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.", note = "available only as a paper copy", } @TechReport{A-1996-4, authorkey = "KoskimiesK MannistoT SystaT TuomiJ", author = "Kai Koskimies and Tatu M{\"a}nnist{\"o} and Tarja Syst{\"a} and Jyrki Tuomi", title = "{SCED}: {A} tool for dynamic modelling of object systems", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-4.ps.Z", } @TechReport{A-1996-5, authorkey = "RaisamoR RaihaKJ", author = "Roope Raisamo and Kari-Jouko R{\"a}ih{\"a}", title = "Techniques for Aligning Objects in Drawing Programs", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-5.ps.Z", } @TechReport{A-1996-6, authorkey = "MakinenE TipleaFL", author = "Erkki M{\"a}kinen and Ferucio Laurentiu Tiplea", title = "Pattern ambiguities for pure context-free grammars", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-6.ps.Z", note = "revised version appeared in Fundamenta Informaticae 30, 2 (1997),183-191", } @TechReport{A-1996-7, authorkey = "AhoI KlapuriH SaarinenJ MakinenE", author = "Isto Aho and Harri Klapuri and Jukka Saarinen and Erkki M{\"a}kinen", title = "Optimal load clipping with time of use rates", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-7", 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.", note = "available only as a paper copy; revised version appeared in International Journal of Electrical Power \& Energy Systems 20, 4 (1998) 269-280", } @TechReport{A-1996-8, authorkey = "TipleaFL MakinenE", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen", title = "Jumping Petri nets. Specific properties", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-8", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-8.ps.Z", note = "revised version appeared in Fundamenta Informaticae 32, 3-4 (1997), 373-392.", } @TechReport{A-1996-9, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Inferring uniquely terminating regular languages from positive data", institution = "Department of Computer Science, University of Tampere", year = "1996", number = "A-1996-9", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1996-9.ps.Z", note = "revised version has appeared in Information Processing Letters 62 (1997), 57--60", } @TechReport{A-1997-1, authorkey = "VehvilainenM", author = "Marja Vehvil{\"a}inen", title = "Gender, expertise and information technology", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-1", 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.", note = "Ph.D. Thesis, available only as paper copy", } @TechReport{A-1997-2, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Ranking and unranking left Szilard languages", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-2", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-2.ps.Z", note = "revised version has appeared in International Journal of Computer Mathematics 68 (1998), 29-38", } @TechReport{A-1997-3, authorkey = "HautamakiJ", author = "Juha Hautam{\"a}ki", title = "A survey of frameworks", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-3", 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. This paper is one of the preliminary reports of the FRED (Framework Editor for Java) project.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-3.ps.Z", } @TechReport{A-1997-4, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On lexicographic enumeration of regular and context-free languages", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-4.ps.Z", note = "revised version has appeared in Acta Cybernetica 13 (1997), 55-61", } @TechReport{A-1997-6, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Inferring regular languages by merging nonterminals", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-6.ps.Z", note = "revised version has appeared in International Journal of Computer Mathematics 70 (1999), 601--616", } @TechReport{A-1997-7, authorkey = "HarsuM", author = "Maarit Harsu", title = "Automated conversion of {PL}/{M} to {C}", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-7", 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.", note = "A-1997-7 is available as paper copy only.", } @TechReport{A-1997-9, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "Constructor-oriented query processing strategy for {NF2} relational queries: Part {I}. Implementation on top of a relational database.", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-9", 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.", note = "A-1997-9 is available as paper copy only.", } @TechReport{A-1997-10, authorkey = "NiemiT JarvelinK", author = "Timo Niemi and Kalervo J{\"a}rvelin", title = "Constructor-oriented query processing strategy for {NF2} relational queries: Part {II}. Implementation based on constructor- oriented representations of {NF2} relations.", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-10", 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.", note = "A-1997-10 is available as paper copy only.", } @TechReport{A-1997-12, authorkey = "HakalaM HautamakiJ TuomiJ ViljamaaA ViljamaaJ", author = "Markku Hakala and Juha Hautam{\"a}ki and Jyrki Tuomi and Antti Viljamaa and Jukka Viljamaa", title = "Design of a Java Framework Engineering Tool", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-12", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-12.ps.Z", } @TechReport{A-1997-13, authorkey = "HarsuM", author = "Maarit Harsu", title = "Translation of conditional compilation", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-13", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-13.ps.Z", } @TechReport{A-1997-14, authorkey = "KoshibaT MakinenE TakadaY", author = "Takeshi Koshiba and Erkki M{\"a}kinen and Yuji Takada", title = "Inferring pure context-free languages from positive data", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-14", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-14.ps.Z", note = "a revised version has appeared in Acta Cybernetica 14 (2000), 469-477.", } @TechReport{A-1997-15, authorkey = "AhoI KemppainenH KoskimiesK MakinenE NiemiT", author = "Isto Aho and Harri Kemppainen and Kai Koskimies and Erkki M{\"a}kinen and Tapio Niemi", title = "Searching neural network structures with {L} systems and genetic algorithms", institution = "Department of Computer Science, University of Tampere", year = "1997", number = "A-1997-15", 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. Keywords: genetic algorithms, Lindenmayer systems, back propagation, network structure, xor problem", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1997-15.ps.Z", note = "a revised version has appeared in International Journal of Computer Mathematics 73, 1 (1999), 55-75", } @TechReport{A-1998-1, authorkey = "JunkkariM NiinimakiM", author = "Marko Junkkari and Marko Niinim{\"a}ki", title = "An algebraic approach to Kauppi's concept theory", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-1", 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.", note = "a revised version appeared in Jaakkola, Kangassalo and Kawaguchi (eds.) Information Modelling and Knowledge Bases X. IOS Press, 1999. pp. 90-102", } @TechReport{A-1998-2, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Binary tree code words as context-free languages", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-2", 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''.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-2.ps.Z", note = "a revised version appeared in The Computer Journal 41, 6 (1998), 422-424", } @TechReport{A-1998-4, authorkey = "JunkkariM NiinimakiM", author = "Marko Junkkari and Marko Niinim{\"a}ki", title = "A Path-Oriented Approach to Hierarchical Concept Structures", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-4.ps.Z", } @TechReport{A-1998-5, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Constructing a binary tree efficiently from its traversals", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-5.ps.Z", note = "a revised version appeared as International Journal of Computer Mathematics 75 (2000), 143-147", } @TechReport{A-1998-6, authorkey = "HarsuM", author = "Maarit Harsu", title = "A survey of object identification in software re-engineering", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-5.ps.Z", } @TechReport{A-1998-7, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On inferring zero-reversible languages", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-7", abstract = "We use a purely language-theoretic definition for zero-reversible languages to show that there exists a linear time inference method for this class of languages using positive data only.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-7.ps.Z", note = "a revised version appeared in Acta Cybernetica 14 (2000), 479-484.", } @TechReport{A-1998-8, authorkey = "HeikkinenM OvaskaS", author = "Maire Heikkinen and Saila Ovaska", title = "Lotus Notes in a software house: a case study of experiences and change impacts", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-8", 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.", note = "A-1998-8 is available as paper copy only", } @TechReport{A-1998-9, authorkey = "ForsmanL PenttinenMJ", author = "Lauri Forsman and Markku J. Penttinen", title = "Investment and risk management analysis of proactive as against reactive network maintenance", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-9", 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", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-9.ps.Z", } @TechReport{A-1998-10, authorkey = "KangassaloH", author = "Hannu Kangassalo", title = "Are global understanding, communication, and information management in information systems possible?", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-10", note = "A-1998-10 is available as paper copy only", } @TechReport{A-1998-11, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On inferring linear single-tree languages", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-11", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-11.ps.Z", note = "a revised version has appeared in Information Processing Letters 73 (2000), 1-3.", } @TechReport{A-1998-12, authorkey = "JunkkariM NiinimakiM", author = "Marko Junkkari and Marko Niinim{\"a}ki", title = "Functional representation of Kauppi's concept operations and concept associations", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-12", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-12.ps.Z", } @TechReport{A-1998-13, authorkey = "JunkkariM", author = "Marko Junkkari", title = "The modeling primitives for component relationships and a `design by examples' method", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-13", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1998-13.ps.Z", } @TechReport{A-1998-14, authorkey = "NummenmaaJ", author = "Jyrki Nummenmaa", title = "Functional dependencies in a hierarchical conceptual model", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-14", 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.", note = "A-1998-14 is available as paper copy only", } @TechReport{A-1998-15, authorkey = "NiemiT JunkkariM JarvelinK", author = "Timo Niemi and Marko Junkkari and Kalervo J{\"a}rvelin", title = "Deductive object-oriented approach to systems analysis and its representation with the set theory", institution = "Department of Computer Science, University of Tampere", year = "1998", number = "A-1998-15", 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.", note = "A-1998-15 is available as paper copy only.", } @TechReport{A-1999-1, authorkey = "RaisamoR RaihaKJ", author = "Roope Raisamo and Kari-Jouko R{\"a}ih{\"a}", title = "Design and evaluation of the alignment stick", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-1", 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.", url = "ftp://ftp..cs.uta.fi/pub/reports/A-1999-1.ps.Z", } @TechReport{A-1999-2, authorkey = "AuramoY", author = "Yrj{\"o} Auramo", title = "Construction of an expert system to support otoneurological vertigo diagnosis", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-2", 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.", note = "Ph.D. Thesis; A-1999-2 is available as paper copy only.", } @TechReport{A-1999-3, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "Inferring finite transducers", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-3", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-3.ps.Z", } @TechReport{A-1999-4, authorkey = "NiiniakiM", author = "Marko Niini{\"a}ki", title = "Understanding the semantics of conceptual graphs", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-4", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-4.ps.Z", } @TechReport{A-1999-5, authorkey = "AhoI", author = "Isto Aho", title = "Interactive knapsacks", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-5.ps.Z", note = "a revised version has appeared as Fundamenta Informaticae 44 (2000), 1-23", } @TechReport{A-1999-6, authorkey = "MykkanenJ JuholaM RuotsalainenU", author = "Jouni Mykk{\"a}nen and Martti Juhola and Ulla Ruotsalainen", title = "Three-dimensional {ROI}s in Brain {PET}", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-6", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-6.ps.Z", } @TechReport{A-1999-7, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On the longest upsequence problem for permutations", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-7", abstract = "We consider the problem of finding the longest upsequence for a given permutation. 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-7.ps.Z", note = "a revised has appeared as International Journal of Computer Mathematics 77, 1 (2001), 45-53", } @TechReport{A-1999-8, authorkey = "MakinenE", author = "Erkki M{\"a}kinen", title = "On the inclusion problem for very simple detrinistic pushdown automata", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-8", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-8.ps.Z", } @TechReport{A-1999-9, authorkey = "SystaT YuP", author = "Tarja Syst{\"a} and Ping Yu", title = "Using {OO} Metrics and Rigi to Evaluate Java Software", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-9", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-9.ps.Z", } @TechReport{A-1999-10, authorkey = "NiemiT NummenmaaJ", author = "Tapio Niemi and Jyrki Nummenmaa", title = "A query method based on intensional concept definition", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-10", 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.", note = "A-1999-10 is available as paper copy only.", } @TechReport{A-1999-11, authorkey = "RaisamoR", author = "Roope Raisamo", title = "Evaluating different touched-based interaction techniques in a public information kiosk", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-11", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-11.ps.Z", } @TechReport{A-1999-12, authorkey = "NiemiT ChristensenM JarvelinK", author = "Timo Niemi and Maria Christensen and Kalervo J{\"a}rvelin", title = "Query language based approach based on application specific concepts", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-12", 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 t hese 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. Key words: Deductive object-oriented databases, query languages, query formulation, integration of deductive and object-oriented aspects", note = "available as a paper copy only", } @TechReport{A-1999-13, authorkey = "RaisamoR", author = "Roope Raisamo", title = "Multimodal human-computer interaction: a constructive and empirical study", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-13", 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.", url = "http://granum.uta.fi/pdf/951-44-4702-6.pdf", } @TechReport{A-1999-14, authorkey = "IsokoskiP", author = "Poika Isokoski", title = "A minimal device-independent text input method", institution = "Department of Computer Science, University of Tampere", year = "1999", number = "A-1999-14", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-1999-14.ps.Z", } @TechReport{A-2000-1, authorkey = "TipleaFL MakinenE ApachiteC", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen and Corina Apachite", title = "Synchronized Extension Systems", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-1", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-1.ps.Z", note = "a revised version has appeared as Acta Informatica 37, 6 (2001), 449-465", } @TechReport{A-2000-2, authorkey = "MakinenE SiltanevaJ", author = "Erkki M{\"a}kinen and Jarmo Siltaneva", title = "A note on Remy's algorithm for generating random binary trees", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-2", abstract = "This note discusses the implementation of R\'{e}my'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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-2.ps.Z", note = "to appear in Missouri Journal of Mathematical Sciences", } @TechReport{A-2000-3, authorkey = "PoranenT NummenmaaJ", author = "Timo Poranen and Jyrki Nummenmaa", title = "Efficient algorithms for {MC} games", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-3", 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 $\mathcal{G}(E,\Phi)$, where $E$ is finite state process and $\Phi$ 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.", % url = {ftp://ftp.cs.uta.fi/pub/reports/A-2000-3.ps.Z}, } @TechReport{A-2000-4, authorkey = "SystT", author = "Tarja Syst{\"}", title = "Static and dynamic reserve engineering techniques for Java software systems", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-4", note = "Ph.D. Thesis. Appeared electronically as Acta Electronica Universitatis Tamperensis, vol. 30", url = "http://acta.uta.fi/pdf/951-44-4811-1.pdf", } @TechReport{A-2000-5, authorkey = "MakinenE PoranenT VuorenmaaP", author = "Erkki M{\"a}kinen and Timo Poranen and Petri Vuorenmaa", title = "A genetic algorithm for determining the thickness of a graph", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-5", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-5.ps.Z", } @TechReport{A-2000-6, authorkey = "HeimonenJM edsMR", author = "Juha-Matti Heimonen and Mikko Ruohonen (eds.)", title = "Pertti {J}{\"a}rvinen 60 years - Work for science", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-6", url = "ftp://ftp.cs.uta.fi/pub/reports/pdf/A-2000-6.pdf", } @TechReport{A-2000-7, authorkey = "MakinenE SystaT", author = "Erkki M{\"a}kinen and Tarja Syst{\"a}", title = "Minimally adequate teacher designs software", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-7", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-7.ps.Z", } @TechReport{A-2000-8, authorkey = "HarsuM", author = "Maarit Harsu", title = "Re-engineering legacy software through language conversion", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-8", 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", note = "Ph.D. Thesis.", url = "http://acta.uta.fi/pdf/951-44-4899-5.pdf", } @TechReport{A-2000-9, authorkey = "MakinenE SystaT", author = "Erkki M{\"a}kinen and Tarja Syst{\"a}", title = "Implementing Minimally Adequate Synthesizer", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-9", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-9.ps.Z", } @TechReport{A-2000-10, authorkey = "NykanenP", author = "Pirkko Nyk{\"a}nen", title = "Decision Support Systems in Health Informatics Perspective", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-10", 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.", note = "Ph.D. Thesis. Appeared electronically as Acta Electronica Universitatis Tamperensis, vol. 55", url = "http://acta.uta.fi/pdf/951-44-4897-9.pdf", } @TechReport{A-2000-11, authorkey = "TipleaFL MakinenE", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen", title = "A note on synchronized extension systems", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-11", abstract = "The concept of a synchronized extension system (SE-system, for short) has been introduced by Tiplea, M{\"a}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{\"a}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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-11.ps.Z", note = "a revised version will appear in Information Processing Letters", } @TechReport{A-2000-12, authorkey = "AhoI", author = "Isto Aho", title = "Notes on the properties of dynamic programming used in direct load control scheduling", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-12", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-12.ps.Z", } @TechReport{A-2000-14, authorkey = "TipleaFL MakinenE", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen", title = "A note on {SE}-Systems and regular canonical systems", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-14", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-14.ps.Z", } @TechReport{A-2000-15, authorkey = "TipleaFL MakinenE", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen", title = "On {SE}-Systems and monadic string rewriting systems", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-15", 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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-15.ps.Z", } @TechReport{A-2000-16, authorkey = "PoranenT", author = "Timo Poranen", title = "A new algorithm for drawing series-parallel digraphs in 3{D}", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-16", 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).", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-16.ps.Z", } @TechReport{A-2000-17, authorkey = "TipleaFL MakinenE EneaC", author = "Ferucio Laurentiu Tiplea and Erkki M{\"a}kinen and Constantin Enea", title = "{SE}-Systems, timing mechanisms, and time-varying codes", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-17", abstract = "We show that synchronize extension systems [Tiplea, M{\"a}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.", url = "ftp://ftp.cs.uta.fi/pub/reports/A-2000-17.ps.Z", } @TechReport{A-2000-18, authorkey = "NummenmaaJ ThanischP", author = "Jyrki Nummenmaa and Peter Thanisch", title = "Practical distributed Commit in modern environments", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2000", number = "A-2000-18", 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.", note = "available as a paper copy only", } @TechReport{A-2001-1, authorkey = "ViikkiK", author = "Kati Viikki", title = "A variable grouping method based on graph theoretic techniques", institution = "Department of Computer and Information Sciences, University of Tampere", year = "2001", number = "A-2000-1", 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.", }