Dept. of Computer and Information science, Linköping University
Last updated: Tue, 02 Dec 1997 11:02:04
Ahrenberg, L. and Jönsson, A. (1987). An Interactive System for Tagging Dialogues. Technical Report LiTH-IDA-R-87-22, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of 14th Conference of the Association for Literary and Linguistic Computing, Göteborg 1-5 June, 1987. (bibtex),
Abstract: This report describes an interactive, menu-based system, called DagTag, which supports tagging and analysis of dialogues. DagTag supports direct tagging of units above word level, in particular dialogue units such as sequences and moves. As a dialogue is tagged it is associated with a hierarchical structure of descriptors and search in a data-base of tagged dialogues can be performed by the use of any substructure of such descriptors as well as with word strings. DagTag has been developed with the primary purpose of analysing dialogues collected from sessions with natural language interfaces, but can also be used for the analysis of ordinary human dialogue.
Bäckström, C. (1987). Logical Modelling of Simplified Geometrical Objects and Mechanical Assembly Processes. Technical Report LiTH-IDA-R-87-05, Department of Computer and Information Science, Linköping University, Sweden. Also published in Spatial Reasoning, vol. 1" ed. Su-shing Chen, Ablex. (bibtex),
Abstract: This paper describes a logical model for geometric reasoning about assembly processes in a simplified world called the 2D+ world. The 2D+ world is a restricted 2+-dimensional world, which is powerful enough to express most of the interesting assembly problems. A static description of this world in first order predicate calculus, and a dynamic description of assembly operations is provided. Assembly operations are expressed in a dynamic logic, extended with two new very restrictedly used operators to attack the frame problem. An algorithm for verifying sequences of assembly operations is also provided.The reason for using a logical geometry model instead of the usual procedural models, is that logical descriptions are better suited to symbolic reasoning than procedural ones. This is especially important since the combination of geometric and symbolic reasoning (geombolic reasoning) is known to be a very hard problem.
Bilos, R. (1987). A Token-Based Syntax Sensitive Editor. Technical Report LiTH-IDA-R-87-02, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper presents TOSSED, a token-oriented syntax sensitive editor being implemented at Linköping University, Linköping, Sweden.The main objectives of the editor is to enable the users to edit programs as easily and freely as with a conventional text editor and give them some features offered by a syntax-directed editor as template instantiation, automatic indentation and prettyprinting, lexical and syntactic error handling.Almost all syntax-directed editors are primarily designed to enter program text but they are awkward to use when modifying program structure. TOSSED is designed to handle both entering and modification of programs in a flexible way and has commands for template insertion, deletion, conversion etc.The user is guaranteed a lexically and syntactically correct program on exit from the editor which avoids many unnecessary compilations.
Chowdhury, S. I. (1987). State of the Art in Statistical Expert Systems. Technical Report LiTH-IDA-R-87-16, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the Conference on Expert Systems and their Applications, Avignon, May 1987. (bibtex),
Abstract: Artificial Intelligence (AI) contributions to statistics would strengthen the statistical packages against their weaknesses and potential misuse by more or less ignorant users. This paper describes and discusses most of the works done in the field (AI in statistics) to date. One common aspect of AI and statistics is that they are both tools for use in other domains. Statistics is perhaps one of the relatively few disciplines which can also contribute something back to AI. Modern statistics deals primarily with statistical inference based on knowledge represented and extracted by numerical methods whereas AI deals with symbolic representation of knowledge and their use. AI and statistics combined together could be a very powerful tool for understanding, explaining and predicting the behavior of a Universe of Discourse.
Dahlbäck, N. (1987). Kommunikation med datorer i naturligt språk - vad är det och vem behöver det?. Technical Report LiTH-IDA-R-87-15, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Sammanfattning I denna rapport beskrives först några av de argument som framförts för och emot dialoger med datorer i naturligt språk. Därefter diskuteras några grundläggande egenskaper i vår språkliga kommunikation, och några hittills otillräckligt beaktade konsekvenser av detta synsätt för forskningen om kommunikation med datorer i naturligt språk. Avslutningsvis berörs vilka användargrupper som kan komma att dra nytta av kommunikation mellan människa och dator i naturligt språk.
Drabent, W. (1987). Do Logic Programs Resemble Programs in Conventional Languages?. Technical Report LiTH-IDA-R-87-01, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc of the Fourth IEEE Symposium on Logic Programming, San Francisco, Aug.31-Sept.4. 1987. (bibtex),
Abstract: No abstract available
Fritzson, P. (1987). Window System Architectures - an Overview. Technical Report LiTH-IDA-R-87-14, Department of Computer and Information Science, Linköping University, Sweden. Also presented at A Tutorial on Software Development Environments, Linköping University, Nov. 24-25 1986. (bibtex),
Abstract: No abstract available
Hägglund, S. (1987). Knowledge-Based Training of Case Management Routines and Emergency Procedures. Technical Report LiTH-IDA-R-87-11, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: An important area of intelligent computer-assisted instruction is training through simulations. This paper presents experiences from two applications and discusses how tutoring and training facilities can be achieved in a systematic fashion as a by-product of a knowledge-based expert system. In the first application a knowledge base developed for a rule-based consultation system giving advice on economical and legal issues was reused for training. The other project developed an authoring environment for designing knowledge-based patient management problems to be used in medical education, with a special emphasis on procedures for emergency decision making. These experiences form the background for the development of a generalized approach, which tries to incorporate authoring support for knowledge-based training, in particular of emergency procedures, in a hybrid expert systems development environment. Application domains include medicine, economy and process control.
Haneclou, P. (1987). A Formal Approach to Reason-Maintenance based on Abstract Domains. Technical Report LiTH-IDA-R-87-07, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Recently the need for a more formal treatment of reason-maintenance has become obvious. Current systems are often ad hoc and most of them only apply to toy-world problems. This paper presents an approach that gives a strict formalization of reason-maintenance. Our approach is similar to the approach taken in denotational semantics (Scott domains).A strict formalization gives one a firm ground to stand on when designing a reason-maintenance system, while also giving the means to determine properties about the system without actually having to build it first.Our abstract domain is a lattice of information states called valuations. valuations are mappings from formulae to truth-values. In order to treat incomplete and inconsistent information we assume an extended set of truth-values. Besides true and false we have the truth-values undefined, meaning lack of information and contradiction, meaning inconsistent information. Sets of inference rules are represented as relations over the set of valuations. The work of a reason-maintenance system is then characterized in terms of operations on the set of valuations.
Hultman, J. (1987). COOPS - A Software System for Defining and Controlling Actions in a Mechanical System. Technical Report LiTH-IDA-R-87-06, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper presents a computer system for defining and controlling actions in a mechanical system. It considers questions such as how to represent dependencies between sensor data and output data in such a system.It also approaches the question of how to specify whether actions should be executed in parallel or in sequence. The paper gives a concrete example of how to specify the control of a specific mechanical system. It also comments briefly on the actual implementation and future extensions.
Kuchcinski, K. and Peng, Z. (1987). Parallelism Extraction from Sequential Programs for VLSI Applications. Technical Report LiTH-IDA-R-87-20, Department of Computer and Information Science, Linköping University, Sweden. Also published in Microprocessing and Microprogramming, the Euromicro Journal, 1988. (bibtex),
Abstract: The paper describes a new approach for automatic extraction of parallelism from sequential programs. The proposed method translates first the sequential programs to their intermediate ETPN (extended timed Petri net) representation and then extracts parallel operations by data dependency analysis. The data dependency analysis is carried out iteratively using interval partitioning and place composition techniques so as to reduce the extraction algorithm complexity. The parallel algorithms produced by the extraction process can then be optimized and improved by an iterative improvement algorithm driven by an optimization strategy and finally implemented directly in VLSI.
Larsson:, T. (1987). Specification and Verification of VLSI Systems Actional Behaviour. Technical Report LiTH-IDA-R-87-17, Department of Computer and Information Science, Linköping University, Sweden. This is a close version of a paper presented at the 8th international conference on Computer Hardware Description Languages, CHDL, 1987. (bibtex),
Abstract: A specification language, ASL, a semantic model, and transformation rules related to the language are presented. The behaviour of a system is divided into time dependent actional aspects and into time independent functional transformation and data type aspects. The paper focuses upon the specification of a systems actional behaviour and the semantics of this part of the specification language. A set of calculus, port, and event reduction rules are proposed as tools for verification.
Lawson, H. W. (1987). Challenges and Directions in Computers and Education. Technical Report LiTH-IDA-R-87-21, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Computer systems, the problem solving approaches made possible in conjunction with this revolutionary technology as well as the wide spread application (usage) of computer systems are all a permanent part of the culture of modern society. Therefore, there exists both a vested interest as well as a responsibility to provide computer culture education at varying levels of the educational system. Unfortunately, a clear, well bounded, definition of the computer related discipline(s) has not, as yet, been developed. The bodies of knowledge in the disciplines has followed the turbulent expansion of the computer industry. Further, the impact of computer technology upon the entire educational system (from higher levels down to primary and even at preschool levels) is the subject of great highly "localized" debate amongst educators, policy makers, parents and other interested parties.A search is now ongoing in many parts of the world to define an "essence" or "core" of computer related discipline(s). Thus, one could ask the question: "How can meaningful (well distributed) computer related education be established at lower levels of the educational system when we do not have an established consensus of the relevant discipline(s) at higher levels?". Obviously, we are in need of a "global" strategy that will guide the distribution of computer relevant knowledge amongst the various levels of the educational system.This process of distribution which has taken centuries in other classical disciplines should proceed for computer related disciplines based upon a professional consensus of content. Therefore, it is extremely important that professionals, especially educators, express their personal views on these strategic matters.The purpose of the current paper is to express some personal views related to identifying the challenges and potential directions with respect to a global view of computer related education. In addressing the challenges, we shall consider some important historical developments, the nature of learning, the current set of computer related disciplines, the (past, present and future) challenges, the fundamental problems in mastering computer related knowledge as well as the relationship to other disciplines. In addressing the directions, we first consider one definition of an "essence" or "core" of computer related disciplines and build further upon these notions. We address the proper role of programming, computer related problem solving approaches as well as the utilization of analogical reasoning and learning by example. Further, we consider the "architecture" abstraction, introduce a common denominator paradigm that can be applied in all computer related disciplines, comment on the use of analogical reasoning in relationship to the paradigm and discuss the implications for primary and secondary education. Finally, we seek a deeper meaning of the evolving computer culture in respect to the evolution of cultures in general.
Levcopoulos, C., Lingas, A., and Sack, J.-R. (1987). Nearly Optimal Heuristics for Binary Search Trees with Geometric Generalizations. Technical Report LiTH-IDA-R-87-08, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc of ICALP'87, Karlsruhe, July 1987. (bibtex),
Abstract: New results concerning optimal binary search trees with zero key access probabilities (with applications eg. in code theory and in point location) are derived. It is shown that for an arbitrarily small positive constant epsilon, there exists a linear-time heuristic for such search trees, producing solutions within the factor of 1+epsilon from the optimum. Also, by using an interesting amortization argument, we give a simple and practical, linear-time implementation of a known greedy heuristic for such trees. The above results are obtained in a more general setting, namely in the context of minimum length triangulations of so-called semi-circular polygons. They are carried over to binary search trees by proving a duality between minimum weight partitions of infinitely-flat semi-circular polygons into m-gons and optimal (m-1)-way search trees. This duality helps also to obtain better heuristics for minimum length partitions of polygons using known algorithms for optimal search trees.
Lingas, A. (1987). On Parallel Complexity of the Subgraph Isomorphism Problem. Technical Report LiTH-IDA-R-87-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A simple parallel algorithm for subgraph isomorphism for graphs of valence d(n) and separator s(n) is presented. The algorithm runs in time O((logn)**3 d(n)s(n)) and uses exp(O(s(n)logn(d(n)+logn)) processors.
Lingas, A. and Karpinski, M. (1987). Subtree Isomorphism and Bipartite Perfect Matching are Mutually NC Reducible. Technical Report LiTH-IDA-R-87-09, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A simple NC reduction of the problem of subtree isomorphism to that of bipartite perfect matching is presented. The reduction implies the membership of the subtree isomorphism problem in random NC. It is also shown that the problem of perfect bipartite matching is NC reducible to that of subtree isomorphism. Finally, it is observed that the latter problem is in NC if the first tree is of valence O(logn).
Löwgren, J. (1987). Applying a Rapid Prototyping System to Control Panel Dialogues. Technical Report LiTH-IDA-R-87-26, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this paper, a rapid prototyping system called IDEN (for Interface Design ENvironment) is presented. This is a system for prototyping the physical part of a user interface (e. g. button panels, trackballs, graphic or text displays etc.) as well as the dialogue part. The results of the evaluation of IDEN by prototyping a part of a large application are discussed. We find some problems with IDEN in particular and rapid prototyping systems in general, as well as some interesting prospects of developing IDEN into more than a rapid prototyping system. Among these prospects are the areas of user training and automatic documentation generation.
Moen, S. (1987). Drawing Dynamic Trees. Technical Report LiTH-IDA-R-87-24, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper describes the design and implementation of a layout algorithm for dynamic trees. The algorithm employs geometrical objects called tree contours and supports insert and delete operations on subtrees. Its worst-case running time is linear with respect to the number of tree nodes. The implementation is based on the useful family of string trees. An overview of a directory browser shows how the algorithm can be used in practice.
Nordin, H. (1987). Reuse and Maintenance Techniques in Knowledge-based Systems. Technical Report LiTH-IDA-R-87-18, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: As more and more knowledge-based systems are developed, the need for reuse and maintenance of the knowledge bases increases. Compared to traditional software engineering, the situation is improved by the separation of different kinds of knowledge and their explicit representation. Still, problems remain. In particular, it is often unclear how different parts of the knowledge base depend on each other, and on the deeper principles on which they are based. In this report, I claim that this is an important problem in the domains we have studied, and propose a project to study how it can be alleviated. I will use two main approaches. The first tries to find approximate partitions by analyzing both the knowledge in the system and meta-level knowledge, e.g. in the form of justifications. The second approach goes a step further and analyses the derivation of the knowledge in order to know what needs to be changed when a certain piece of knowledge changes. The resulting analysis tools will be integrated into an environment with support for development of technical fault diagnosis systems from reusable causal models to deliverable systems based on faults and symptoms.
Patel, M. R. (1987). A Threaded Interpretive Language Supporting Programming in the Large. Technical Report LiTH-IDA-R-87-03, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc of the Sixth Rochester Forth Conference, University of Rochester, Rochester, New York, June 11-14, 1986. (bibtex),
Abstract: One of the most crucial elements that threaded programming language such as FORTH lack is the ability to generate modules and support linkage, dynamic or static, between modules. This is regarded to be one of the main reasons to why FORTH is difficult to use in development of Large Software Systems.Traditional threaded languages may be regarded to be closed systems since code may only be reused on source level. This leads to some problems when dealing with Large Software System. Problems such as long compilation time and name conflicts arise. The use of vocabularies can solve some of the problems but not all.This paper discusses the definition and development of a FORTH inspired threaded language able to generate sharable code modules, support dynamic linkage between code modules, and thus supporting Programming in the Large.
Peng, Z. (1987). Construction of Asynchronous Concurrent Systems from their Behavioral Specifications. Technical Report LiTH-IDA-R-87-19, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 10th World Computer Congress, Dublin, Ireland, Sept. 1-5, 1986. (bibtex),
Abstract: This paper describes a systematic method to construct asynchronous concurrent systems from their high level behavioral specifications. A high level behavioral specification specifies what a system should be able to do without prescribing the physical structure of the implementation. This specification is first mapped into an intermediate design representation which consists of separate but related models of control and data part. The intermediate representation is then analyzed, transformed, and finally partitioned into a set of processing modules whose actions are coordinated to implement the specified behaviors of the designed system.
Wire'n, M. (1987). A Comparison of Rule-Invocation Strategies in Context-Free Chart Parsing. Technical Report LiTH-IDA-R-87-13, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the Third Conference of the European Chapter of the Association for Computational Linguistics. Copenhagen, April 1|3, 1987. (bibtex),
Abstract: No abstract available