Dept. of Computer and Information science, Linköping University
Last updated: Tue, 02 Dec 1997 11:02:56
Annie Röstlinger, G. G. (1996). Generisk flexibilitet - på väg mot en komponentbaserad metodsyn. Technical Report LiTH-IDA-R-96-15, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Det existerar i dag många olika metoder som kan användas som stöd för utredningar avseende systemutveckling/verksamhetsutveckling. Dessa metoder representerar samlad kunskap om utvecklingsprocesser men metoderna används inte alltid i enlighet med metodkonstruktörernas intentioner. Metoder kan betraktas och brukas som statiska helheter, som oberoende fragment eller som mer dynamiska och komponentbaserade. Enligt våra erfarenheter från metodut-veckling och metodtillämpning avseende metoder inom SIMM-metodfamilj, finns det en stor potential i att beskriva och hantera metoder på ett mer flexibelt och komponentorienterat sätt. Metoder kan då mer effektivt utvecklas och anpassas för att ge stöd i olika utrednings-situationer och nya utredningssammanhang, vilket bör öka möjligheterna till bättre utredningar och förbättrade verksamheter.
Axelsson, J. (1996). Three Search Strategies for Architecture Synthesis and Partitioning of Real-Time Systems. Technical Report LiTH-IDA-R-96-32, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This report studies the problem of automatically selecting a suitable system architecture for implementing a real-time application. Given a library of hardware components, it is shown how an architecture can be synthesized with the goal of fulfilling the real-time constraints stated in the system's specification. In case the selected architecture contains several processing units, the specification is partitioned by assigning tasks to processing units. We investigate the use of three meta-heuristic search algorithms to solve the problem: genetic algorithms, simulated annealing, and tabu search; and it is described in detail how these can be adapted to the architecture synthesis problem. Their relative merits are discussed at length, as is the importance of scheduling to the solution quality.
Axelsson, K. (1996). På ny kurs med sjökarteavdelningen - en fallstudie från STRIKE-projektet. Technical Report LiTH-IDA-R-96-07, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Denna rapport beskriver ett aktionsforskningsprojekt som bedrivits i samarbete mellan VITS-gruppen och Sjökarteavdelningen på Sjöfartsverket. Arbetet har skett inom ramen för STRIKE-projektet (Strukturering av informationssystem och verksamheter - utvärdering och förändring). I rapporten beskrivs den verksamhetsförnyelse som skett på Sjökarteavdelningen. Detta är ett stort förändringsarbete som VITS-gruppen delvis deltagit i, men som även bedrivits utanför STRIKE-projektets ramar. Under samarbetet har verksamhetsanalys enligt SIMMetoden använts i prototypsyfte för att designa en ny verksamhetsstruktur, vilket har givit mycket goda resultat. Rapporten beskriver tillvägagångssättet och innehåller även erfarenheter kring detta. Vidare görs en jämförelse mellan detta förändringsarbete och det synsätt på förändringar som finns i BPR-ansatsen (Business Process Redesign), som visar på ett antal likheter och avvikelser mellan de olika angreppssätten. I verksamhetsförnyelsen ingår även att skapa en passande informationssystemstruktur för organisationen. Som ett led i detta arbete presenteras slutligen id{\'e}er kring hur en metodkomponent för systemstrukturering skulle kunna vara utformad.
Axelsson, K. (1996). Strukturering av informationssystem och verksamheter - en teori- och empiribaserad argumentation. Technical Report LiTH-IDA-R-96-40, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Denna rapport tar utgångspunkt i ett antal problemställningar som identifierats under en kartläggande studie av sex stycken verksamheter, vilka valt att realisera sin informationssystemarkitektur med stöd av en av två arkitekturstrategier. De studerade arkitekturstrategierna är Information Resource Management (IRM) och VerksamhetsBaserad Systemstrukturering (VBS). Eftersom realiseringarna i samtliga fall inneburit någon form av problem, har behovet av ett alternativt tillvägagångssätt vid systemstrukturering uppkommit. I denna rapport förs en argumentation för att systemstrukturering bör ske med utgångspunkt i verksamheten. Arkitekturstrategin väljs enligt detta synsätt efter att verksamheten analyserats, vilket innebär att strategivalet görs välgrundat. Det är även viktigt att man strävar efter att nå samstämmighet mellan verksamheten, dess mål och visioner och informationssystemarkitekturen. I rapporten relateras dessa tankar till viss teori inom informationssystemarkitekturområdet. Därefter presenteras en första preliminär version av en metodkomponent för systemstrukturering enligt SIMMetoden. Metodkomponenten innehåller fyra faser, där den befintliga verksamheten och dess informationssystemarkitektur först kartläggs och analyseras. Därefter värderas detta material och en framtida arkitekturstrategi fastställs. Med detta som utgångspunkt designas den framtida verksamheten och dess informationssystemarkitektur. Slutligen utvärderas resultatet i form av en verksamhetsstödjande informationssystemarkitekturmodell. Sist i rapporten görs ett försök att relatera metodkomponenten och det bakomliggande synsättet till de problemställningar som beskrivits i rapportens inledning.
Byers, D. (1996). Static Estimation of Software Testability. Technical Report LiTH-IDA-R-96-13, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Testability measurement of code has been of interest for many years in software development and maintenance. Complexity measures of various kinds have been proposed, but these do not have direct bearing on software testing. More refined measures, such as dynamic measurement of testability are better, but are expensive. Our goal is to develop a testability metric that can be determined through static analysis. Although not as precise as metrics based on dynamic analysis, it should provide a useful complement. In this paper we outline our first efforts in that direction. We define a metric that will predict the number of randomly generated test cases that will be required to reach a certain level of branch coverage in structured program code.
Coradeschi, S. (1996). Reasoning with Misperception in the Features and Fluents Framework. Technical Report LiTH-IDA-R-96-02, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this work we consider a way to deal with the problem of unreliable observations when an agent is reasoning about dynamical systems as they are formalized and systematically studied in Sandewall's approach to reasoning about action and change. The presence of incorrect observations can be detected in case it generates a contradiction. In this case a revision function resolves the inconsistency by constructing alternative consistent descriptions of the system. However, revision is in general expensive and therefore we define a delayed revision that postpones doing revision for some steps and we prove that it gives results similar to immediate revision. We also examine some forms of preferential revision that reduce the number of alternative descriptions of the system. We finally consider the relations between our work and Gardenfors' approach to belief revision.
Doherty, P. (1996). PMON+: A Fluent Logic for Action and Change. Formel Specification, Version 1.0. Technical Report LiTH-IDA-R-96-33, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This report describes the current state of work with PMON, a logic for reasoning about action and change, and its extensions. PMON has been assessed correct for the K-IA class using Sandewall's Features and Fluents framework which provides tools for assessing the correctness of logics of action and change. A syntactic characterization of PMON has previously been provided in terms of a circumscription axiom which is shown to be reducible to a first-order formula. This report introduces a number of new extensions which are also reducible and deal with ramification. The report is intended to provide a formal specification for the PMON family of logics and the surface language L(SD) used to represent action scenario descriptions. It should be considered a working draft. The title of the report has a version number because both the languages and logics used are continually evolving. Since this document is intended as a formal specification which is used by our group as a reference for research and implementation, it is understandably brief as regards intuitions and applications of the languages and logics defined. We do provide a set of benchmarks and comments concerning these which can serve as a means of comparing this formalism with others. The set of benchmarks is not complete and is only intended to provide representative examples of the expressivity and use of this particular family of logics. We describe its features and limitations in other publications by our group which can normally be found at "http://www.ida.liu.se/labs/kplab/".
Doherty, P., Lukaszewicz, W., and Szalas, A. (1996). Declarative PTIME Queries to Relational Databases. Technical Report LiTH-IDA-R-96-34, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this paper, we consider the problem of expressing and computing PTIME queries to relational deductive databases in a purely declarative query language, SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME and the whole class of PTIME queries is expressible in SHQL. Although similar results have been proven for fixpoint languages and extensions to datalog, the claim is that SHQL has the advantage of being purely declarative, where the negation operator is interpreted as classical negation, mixed quantifiers may be used and a query is simply a restricted first-order theory not limited by the rule-based syntactic restrictions associated with logic programs in general. We describe the PTIME algorithm used to compute queries in SHQL which is based in part on quantifier elimination techniques and also extend the method to incomplete relational databases using intuitions from Circumscription.
Doherty, P., Lukaszewicz, W., and Szalas, A. (1996). General Domain Circumscription and its First-Order Reduction. Technical Report LiTH-IDA-R-96-01, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory. We then show that for the class of "semi-universal" theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also show that for a certain class of domain circumscribed theories, that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions.
Drakengren, T. (1996). Compositionality and the Frame Problem. Technical Report LiTH-IDA-R-96-04, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The problem of compositionally specifying effects of actions has not yet received an appropriate solution, as shown in this paper. A general semantic-based method is proposed, the effect law semantics, which solves this, and has an associated logic for specification of actions. In addition, the semantics completely separates effects of actions from assumptions about inertia (the frame problem), and whether actions have their intended effects or not. This makes it suitable for generalisations, such as handling surprises and actions that may fail.
Drakengren, T. and Jonsson, P. (1996). Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. Technical Report LiTH-IDA-R-96-26, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper combines two important directions of research in temporal resoning: that of finding maximal tractable subclasses of Allen's interval algebra, and that of reasoning with metric temporal information. Eight new maximal tractable subclasses of Allen's interval algebra are presented, some of them subsuming previously reported tractable algebras. The algebras allow for metric temporal constraints on interval starting or ending points, using the recent framework of Horn DLR's. Two of the algebras can express the notion of sequentiality between intervals, being the first such algebras admitting both qualitative and metric time.
Drakengren, T. and Jonsson, P. (1996). Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report. Technical Report LiTH-IDA-R-96-14, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper continues Nebel and B{\"u}rckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (unless P=NP), in addition to their previously reported ORD-Horn subclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of these can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. The satisfiability algorithm, which is common for all the algebras, is shown to be linear.
Facchini, P. (1996). A Statistical Method for Real-Time Software Performance Estimation. Technical Report LiTH-IDA-R-96-22, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This report is the result of an equivalent to a Masters thesis project done at the Linköping University, Sweden, during the period February to July 1996. The execution time of a program or a block of a program is important in real-time design. Different methods to estimate the performance of a program, taking into account the features of a processor (clock frequency, memory access time), have been formulated. However, those methods cannot be used early in the design. This report introduces a new method of estimation based on statistical analysis and measurements which model the hardware. It uses linear regression to estimate the execution time of a program on different systems. A model, based on the execution time of narrow programs (describing basic operations), determines the characteristics of the different processors. Then, the estimation of the execution time of a program is the product of the values of this model and the regression parameters, which are calculated with linear regression. The method has been tested with Ada programs on Sparcstations and PCs. We point out the importance of the accuracy of measurements, which may have a non-negligible influence on the results. The error of the estimates is very small for a set of only Sparcstations, but is larger when PCs are added to that set. We discuss plausible causes of these results. The first part of this report is a description of the subject and of previous research. Then the report deals with the method of evaluation, followed by the description of the experiments. The last part is the analysis and conclusion about this method.
Fjällström, P.-O. (1996). PARALLEL ALGORITHMS FOR GEOMETRIC PROBLEMS ON COARSE GRAINED MULTICOMPUTERS. Technical Report LiTH-IDA-R-96-38, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We present scalable parallel algorithms for some geometric problems on coarse grained multicomputers. More specifically, for a square mesh-connected p-processor computer, we show that: 1. The all-farthest-neighbors problem for a convex n-gon can be solved in O(n/p) time, if n p2/4. 2. The maximum-perimeter triangle inscribed in a convex n-gon can be found in O(n(log (n/p) + log2 p)/p) time, if n p2. 3. If n p2, the two-dimensional batched range-searching problem (n points/queries) can be solved in O((n log n log p + k)/p + Ts(n log p, p)) time, where k is the number of reported points and Ts(m,p) is the time to sort m items on a p-processor computer. The two first results are based on the formulation of these problems as searching problems in totally monotone matrices.
Fjällström, P.-O. (1996). Parallel Interval-Cover Algorithms for Coarse Grained Multicomputers. Technical Report LiTH-IDA-R-96-39, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper presents sequential and parallel algorithms for interval-cover minimization problems. That is, given a set S of (weighted) intervals on the real line, and an interval [a,b], we want to find a subset of S that is a minimum cardinality or a minimum weight cover of [a,b]. The efficiency of our parallel algorithms depends on the relationship between n and p. More specifically, our parallel algorithm for the minimum cardinality cover problem gives an optimal speedup when Ts(p,p) is O(log n), where Ts(n,p) is the time to sort n elements evenly distributed over p processors. For the minimum weight cover problem, we obtain an optimal speedup when Tr(p,p) is O(n/p), where Tr(n,p) is the time to find the maximum of n elements evenly distributed over p processors.
Fjällström, P.-O. (1996). Range Searching on a Mesh-Connected Parallel Computer. Technical Report LiTH-IDA-R-96-27, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Given a set of n points and hyperrectangles in d-dimensional space, the range-searching problem is to determine which points each hype rectangle contains. We present two parallel algorithms for this problem on a mesh-connected parallel computer: one average case efficient algorithm based on cell division, and one worst-case efficient divide-and-conquer algorithm. In addition to the asymptotic analysis of their running times, we present an experimental evaluation of the algorithms.
Flodin, S., Orsborn, K., and Risch, T. (1996). Using Multi-Method Queries in Finite Element Analysis. Technical Report LiTH-IDA-R-96-28, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The object-oriented model is often motivated by its support for new emerging application areas such as finite element analysis (FEA), computer-aided design or office automation systems. However, our experience when building such a system (FEA) using an object-relational database management system is that an object-oriented model extended with multi-methods is needed. Our application domain also needs support for multi-methods where methods may be called with any configuration of bound or unbound arguments, multi-directional queries. In this paper we show by using excerpts from an FEA application the benefits of multi-directional multi-methods and we also show how to process queries with multi-directional multi-methods and how to make these optimizable in presence of late binding.
Fritzson, P. (1996). Proceedings of the Poster Session of CC'96 - International Conference on Compiler Construction. Technical Report LiTH-IDA-R-96-12, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The International Conference on Compiler Construction (CC) provides a forum for presentation and discussion of recent developments in the area of compiler construc tion, language implementation and language design. Its scope ranges from compilation methods and tools to implementation tec niques for specific requirements on languages and target architectures. It also includes lan guage design and programming environments issues which are related to language translation. There is an emphasis on practical and efficient techniques. This volume contains the papers which were accepted for presentation at the poster session of CC'96, the sixth International Conference on Compiler Construction, held in Linköping, Sweden, 22-26 April 1996. Note that the regular papers accepted for CC'96 are not included here but have been published by Springer Verlag as Volume 1060 in Lecture Notes in Computer Science.
Goldkuhl, G. (1996). Från IRM och VBS till PAKS: Process-, aktivitets- och komponentbaserad systemstrukturering. Technical Report LiTH-IDA-R-96-08, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Det finns olika strategier för att strukturera organisationers datorbaserade informationssystem; dvs strategier för att skapa sk informationssystemarkitekturer. Två kända strategier är IRM (Information Resource Management) och VBS(VerksamhetsBaserad Systemstrukturering). IRM innebär att man strukturerar organisationens informationssystem runt några centrala integrerade databaser. VBS innebär att man skapa ett antal lokala informationssystem tydligt kopplade till verksamhetsfunktioner. Dessa system är autonoma men med en definierad meddelandesamverkan sins emellan. I tidigare forskningsprojekt har IRM och VBS studerats både teoretiskt och empiriskt. På basis av erfarenheter från dessa tidigare studier har en analys företagits av dessa strategiers fördelar och nackdelar. Denna analys har lett fram till en formulering av en tentativ alternativ arkitekturstrategi. I rapporten presenteras denna arkitekturstrategi: Process-, aktivitets- och komponentbaserad systemstrukturering (PAKS). Denna strategi bygger på tre teoretiska hörnpelare * processer (affärsprocesstänkande) * aktiviteter (kommunikativt handlande) * komponenter ("cooperative business objects") PAKS-strategin skisseras och jämförs översiktligt med IRM och VBS.
Goldkuhl, G. (1996). Generic Business Frameworks and Action Modelling. Technical Report LiTH-IDA-R-96-17, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The communicative action perspective of business processes and information systems has attracted much attention recently. A viable approach in this area is: Action Workflow. This paper investigates the use of Action Workflow as a generic business framework, relating it to the alternative Business as Action game Theory. The latter provides a more exhaustive description of various business actions. Action Workflow is also related to the SIMM approach with Action Diagrams, an action modelling method. A communicative action expansion of this method is suggested in this paper. A discussion is performed concerning the relations between generic business frameworks and action modelling methods.
Goldkuhl, G. (1996). Metodarkitektur för metodanalys. Technical Report LiTH-IDA-R-96-06, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Metodanalys innebär studium av metoder. För att utföra metodanalys behövs en metametod. Metodanalys (MA) enligt SIMM är en sådan metametod som tidigare presenterats och tillämpats. En viktig del av metodanalys är sk metodmodellering, dvs strukturerad beskrivning och analys av metoder. Denna rapport innehåller vidareutveckling av denna metametod (MA/SIMM). Rapporten innehåller beskrivning av ett antal metodanalys-situationer: * metoddokumentering * metoddiagnos * metodutveckling * metodkombinering * metodimplementering i verktyg För dessa situationer presenteras sedan metodarkitekturer med förslag till arbetsmoment. Detta innebär att metodanalys/SIMM kan ses som * ett antal sammansatta metoder för specifika utredningssammanhang * ett antal generiska metodkomponenter att användas i olika sammanhang
Goldkuhl, G. (1996). Verksamhetsmodellering - några metodkomponenter inom SIMMetoden. Technical Report LiTH-IDA-R-96-09, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Verksamhetsmodellering är aktuellt att göra vid olika typer av utrednings-utvecklings- och utvärderingssituationer avseende verksamheter. Att göra grafiska verksamhetsmodeller har visat sig vara ett kraftfullt sätt att reda ut, strukturera och beskriva komplexa verksamheter på. Denna rapport beskriver olika grafiska modelleringstekniker inom SIMMetoden: * handlingsgrafer * funktionsgrafer * processgrafer * interaktionsgrafer I denna rapport ges en bakgrund till användning av verksamhetsmodellering; olika motiv och tillämpningssituationer diskuteras. Olika modelleringsstrategier (arbetsprinciper) för verksamhetsmodellering gås igenom, såsom * kompositionellt ("top down"), * kontextuellt("bottom all"), * induktivt ("bottom up") arbetssätt. Avslutningsvis diskuteras hur dessa modelleringsstrategier kan kombineras på ett konstruktivt och situationsanpassat sätt vid användning av olika metodkomponenter inom SIMMetoden.
Ingels, P. (1996). Layered HMMs in Robust Natural Language Text Processing. Technical Report LiTH-IDA-R-96-11, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper describes and experimentally evaluates the application of speech recognition methods to the problem of processing distorted natural language text in a robust manner. The method implements an advanced tokenizer that can detect and correct spelling mistakes and segmentation errors in the input stream and it does so in the context of higher level linguistic knowledge. The idea is to arrange Hidden Markov Models (HMM) in multiple layers where the HMMs in each layer are responsible for different aspects of the processing of the input.
Johansson, O. (1996). ProCAD - A Produkt Modeling System for Power Plant System Design. Technical Report LiTH-IDA-R-96-36, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: ProCAD is a product modeling system for power plant system design. It is used for functional design of steam turbine, gas turbine, combined cycle, and pressurised fluid bed coal combustion (PFBC) power plants. The product models can contain descriptions of thousands of functional components: turbines, electrical generators, pipes, pumps, instruments, valves, heat exchangers etc. The power plant system designer can interact with the detailed information in the product model database directly from the drawing environment in the CAD-system. Reports and product documentation is generated from the product model database using 4GL applications with an SQL-interface. The paper describes the system design of ProCAD. An overview of the structure of the product model database is given, and the CAD-client application for drawing process and instrumentation diagrams. The paper provides examples of important generic functionality for multi user product modeling systems, such as configurable project specific attributes in the product model database, assignment of update access rights on distinct substructures in the product model to different engineers, and functions for checking the consistency between file based CAD-drawings and information in the product model database.
Jonsson, P. and Bäckström, C. (1996). On the Size of Reactive Plans. Technical Report LiTH-IDA-R-96-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: One of the most wide-spread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness not present in the original definition. Furthermore, we isolate three different types of completeness which capture different behaviours exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. However, by relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial.
Jonsson, P. and Drakengren, T. (1996). RCC-5 and its Tractable Subclasses. Technical Report LiTH-IDA-R-96-25, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework. The satisfiability problem for RCC-5 is known to be NP-complete but not much is known about its approximately four billion subclasses. We provide a complete classification of satisfiability for all these subclasses into polynomial and NP-complete respectively. In the process, we identify all maximal tractable subalgebras which are four in total.
Karlsson, L. (1996). Planning, Truth Criteria and Systematic Approach to Action and Change. Technical Report LiTH-IDA-R-96-16, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper presents an analysis of partial-order planning based on Sandewall's systematic approach to reasoning about action and change. The partial-order planner TWEAK is analysed and reconstructed. The main result is a temporal logic-based version of the criterion for necessary truth in TWEAK plans. In a second step, the TWEAK truth criterion is extended to deal with context-dependent and nondeterministic actions. A temporal logic, called the fluent logic, is used for representing plans.
Lin, L., Risch, T., and Badal, D. (1996). Indexing Interpolated Time Sequences. Technical Report LiTH-IDA-R-96-03, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A time sequence is a discrete sequence of values, e.g. temperature measurements, varying over time. By applying an interpolation function a discrete time sequence can be coerced into a continues function over time, F(t), which we call an interpolated time sequence. Many applications need to deal with querying interpolated time sequences. Simple queries involve finding F(t') for a given time point t', which are easy to support using regular ordered indexes. The main contribution of this paper is a new index structure, the interpolation index (IP-index) which supports efficient retrievals of those time points t where F(t) = v' for a given v', i.e. efficient computation of interpolated inverse queries, F-1(v'). Performance measures show that the IP-index radically improves the search time for interpolated inverse queries. It is also shown that the insertion time of the IP-index for most periodic time sequences has an upper limit, and for largely monotonic sequences it is logarithmic. Keywords: time sequences, indexing, temporal databases.
Lin, L., Risch, T., and Badal, D. (1996). Indexing Values of Time Sequences. Technical Report LiTH-IDA-R-96-29, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A time sequence is a discrete sequence of values, e.g. temperature measurements, varying over time. Conventional indexes for time sequences are built on the time domain and cannot deal with inverse queries on a time sequence (i.e. computing the times when the values satisfy some conditions). To process an inverse query the entire time sequence has to be scanned. This paper presents a dynamic indexing technique on the value domain for large time sequences which can be implemented using regular ordered indexing techniques (e.g. B-trees). Our index (termed IP-index) dramatically improves the query processing time of inverse queries compared to linear scanning. For periodic time sequences that have a limited range and precision on their value domain (most time sequences have this property), the IP-index has an upper bound for insertion time and search time.
Lin, M., Malec, J., and Nadjm-Tehrani, S. (1996). On Semantics of Reactive Rule-based Systems. Technical Report LiTH-IDA-R-96-35, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this paper we address special issues which arise when the rule-based programming paradigm is emlployed in development of reactive real-time systems. We begin by presenting a rule-based language which has emerged while developing intelligent cruise control systems. We describe a naive operational semantics based on an an implemented inference engine, and explain why the semantics is not appropriate in safety-critical real-time contexts. We then define a number of correctness criteria ensuring termination, consistency and determinism, based on a formal declarative semantics. However, the declarative semantics is non-constructive. In order to be able to build an implementation satisfying the correctness criteria, two alternative approaches are proposed. Both approaches build upon static checks of a rule-based program. In the first approach some correctness criteria are met by accepting only stratified programs after the static checks. In the second approach we accept programs which are correct with respect to a constructive semantics. For both approaches we present the analysis methods and soundness results with respect to the desired declarative semantics.
Lindeber, L. (1996). Metodanalys av FA & VIBA/SIMM - en metodvärdering ur ett inter-organisatoriskt perspektiv. Technical Report LiTH-IDA-R-96-31, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Det ökade datautbytet mellan organisationer har skapat helt nya behov av metoder för utveckling och vidareutveckling av inter-organisatoriska informationssystem. Nya/vidareutvecklade metoder behövs för att kunna möta kraven på ökad komplexitet. Med utgångspunkt i vårt gemensamma synsätt vad gäller verksamhetsutveckling och affärsprocesstänkande har VITS-gruppen och Konsultföretaget FRONTEC startat ett samarbetsprojekt med avsikt att skapa en användbar metod för verksamhetsutveckling avseende inter-organisatoriska informationssystem. För att nå insikt i hur väl VITS-gruppens metod för verksamhetsutveckling/systemutveckling, SIMMetoden, kan möta kraven på komplexitet hari genomförts en metodvärdering mha MA/SIMM ur ett inter-organisatoriskt perspektiv. Syftet är att belysa SIMMetodens styrkor och svagheter ur ett IOIS-perspektiv med avsikten att få fram en underlag för fortsatt metodutveckling inom området. Utgångspunkten för analysen har varit ett antal kriterier som har betydelse vid utvecklingen av IOIS, bl a affärsrelationer, affärsprocesser, affärskommunikation etc. Vi har kommit fram till att ett flertal nya komponenter behövs (framförallt inom förändringsanalysen), ytterligare några kan användas efter komplettering/modifiering, andra kan direkt användas vid en verksamhetsutveckling sett ur ett inter-organisatoriskt perspektiv. SIMMetodens styrka ligger i dess grundläggande synsätt och de strukturerade sammanhängande beskrivningsformerna som möjliggör en aktiv dialog och en aktiv medverkan i utvecklingsprocessen. Sett ur ett IOIS-perspektiv förutsätter dock metoden implicit en verksamhet och saknar således analys av gränssnittet mellan parter.
Meyer, J.-J. C. and Doherty, P. (1996). Preferential Action Semantics, Preliminary Report. Technical Report LiTH-IDA-R-96-24, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this paper, we propose a new way of considering reasoning about action and change. Rather than placing a preferential structure onto the models of logical theories, we place such a structure directly on the semantics of the actions involved. In this way, we obtain a preferential semantics of actions by means of which we can not only deal with several of the traditional problems in this area such as the frame and ramification problems, but can generalize these solutions to a context which includes both nondeterministic and concurrent actions. In fact, the net result is an integration of semantical and verificational techniques from the paradigm of imperative and concurrent programs in particular, as known from traditional programming, with the AI perspective. In this paper, the main focus is on semantical (i.e. model theoretical) issues rather than providing a logical calculus, which would be the next step in the endeavor.
Nadjm-Tehrani, S. and Strömberg, J.-E. (1996). JAS-95 Lite: Modelling and Formal Analysis of Dynamic Properties. Technical Report LiTH-IDA-R-96-41, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: In this report we present the multi-disciplinary work performed in the first phase of the COHSY project concerning generation of models and analysis of {\em hybrid} systems -- mathematical models including both continuous and discrete elements. The participants of the project were SAAB Military aircraft, Volvo aerospace, and VOAC hydraulics, as well as three departments from Linköping University: Computer Science, Electrical engineering and Mechanical engineering. The report addresses modelling and formal verification of a fictitious system, the landing gear of an aircraft referred to as JAS-95 Lite, which involves hydro-mechanical and electro-mechanical sensors and actuators as well as electronic and software modules performing diagnosis and control. The technical system, is moreover in dynamic interaction with a human operator (the pilot). The main aim of this work has been to mathematically prove that specified requirements are satisfied by given design specifications for the controller and alternative models for the physical environment. An architectural model is used to facilitate the combination of alternative configurations. The report provides a summary of several tracks of activity, a major one being the application and illustration of state of the art techniques in physical modelling of the hardware, and mathematical modelling and verification of the closed loop system. The languages used for modelling range from engineering schematic diagrams to Bond Graphs, hybrid transition systems, hybrid automata, and the temporal logic Extended Duration Calculus. It also provides some insights into modelling in synchronous languages for high level specification of real-time programs -- the interest being the investigation of the applicability of tools available for analysis and subsequent code generation from high level designs. Two languages from this family are examined in the context of the case study: discrete models in Esterel and timed models in statecharts as implemented in the tool Statemate.
Nielsen, L., Nyberg, M., Frisk, E., Bäckström, C., Henriksson, A., Klein, I., Gustafsson, F., Gustafsson, S., and Palmqvist, J. (1996). Issues in Diagnosis, Supervision and Safety. Technical Report LiTH-IDA-R-96-37, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Issues concerning diagnosis, supervision and saftey are found in many technologically advanced products. There is now a trend to extend the functionality of diagnosis and supervision systems to handle more advanced situations. This report collects some of the initiatives taking place in research and some of the developments taking place in the industry.
Nilsson, H. and Sparud, J. (1996). The Evaluation Dependence Tree: an Execution Record for Lazy Functional Debugging. Technical Report LiTH-IDA-R-96-23, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. This should be reflected in the design of debuggers for such languages to avoid burdening the programmer with operational details, e.g. concerning the actual evaluation order. Conventional debugging techniques tend to focus too much on operational aspects to be suitable in this context. A record of the execution that only captures the declarative aspects of the execution, leaving out operational details, would be a viable basis for debugging lazy functional programs. Various declarative debugging tools could then be developed on top of such records. In this paper we propose a structure which we call the Evaluation Dependence Tree (EDT) for this purpose, and we describe two different construction methods. Performance problems are discussed along with possible solutions, and some performance figures from experiments in a realistic context are given.
Ohlsson, N., Zhao, M., and Helander, M. (1996). Application of Multivariate Analysis for Software Fault Prediction. Technical Report LiTH-IDA-R-96-30, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The need for quantitative methods to support project control has been expressed in a number of recent papers. A number of multivariate analysis techniques are available for analysing highdimensional observations of software design metrics. This paper presents a successful study in which principal component analysis (PCA) and discriminant coordinates (DC) were used to develop prediction models for data from Ericsson Telecom AB. Instead of dividing modules into faultprone and nonfaultprone, which has been common in previous studies, observations were categorised into several groups according to the ordered number of faults. The DC analysis revealed that the first discriminant coordinates statistically increase with the ordering of modules. This empirical result suggests an approach for ordering as a first step toward prediction of fault-prone modules that incorporates attributes of process and resources. The result of applying DC was compared with discriminant analysis (DA), which has been reported useful for building prediction models of fault-prone modules. The later models were found to be inadequate for predicting the most faultprone modules for the considered data set. The authors experienced a number of problems while applying the earlier reported prediction models. These are illustrated in this paper, and improvements are suggested.
Pettersson, M. (1996). A Compiler for Natural Semantics. Technical Report LiTH-IDA-R-96-05, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: Natural semantics is a formalism used for specifying both semantics and implementations of programming languages. Until recently, no practical implementation of the formalism existed. We have defined the Relational Meta-Language, RML, as an executable specification language for natural semantics. After a brief outline of the language, we describe the compilation strategy used by our rml2c compiler: transformations are applied to minimize non-determinism, and a continuation-passing style form is produced and simplified. Finally the CPS is emitted as low-level C code, using an efficient technique for implementing tailcalls. We also present performance measurements that support our choice of compilation strategy.
Röstlinger, A. (1996). Slutrapport avseende RASTER-projektet - utvärdering och förändring av datorstödda kommunala verksamheter. Technical Report LiTH-IDA-R-96-18, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: RASTER-projektet är ett forskningsprojekt som bedrivits av forskningsgruppen VITS vid Linköpings universitet. Projektet har bedrivits med ekonomiskt stöd av Svenska Kommunförbundet. Forskningsprojektet fokuserar på utvärdering av datorstödda kommunala verksamheter. Inom RASTER-projektet har vi utvecklat metodkomponenter för verksamhets- inriktad utvärdering av datasystem. Metoden innebär att datasystem och verksamhet utvärderas på ett integrerat sätt. Metodkomponenterna har utprovats genom ett antal fallstudier i kommuner. De olika fallstudierna har bedrivits på aktionsforskningsbasis som ett samarbete mellan VITS och respektive kommunal organisation. För att ge involverade aktörer stöd för att genomföra utvärderingar med hjälp av metoden har vi också utvecklat ett datorbaserat metodverktyg. Projektet har bedrivits med 1-åriga anslag under perioden 92/93-94/95 samt med en förstudie under 91/92.
Sandewall, E. (1996). Comparative Assessment of Update Methods Using Static Domain Constraints. Technical Report LiTH-IDA-R-96-20, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The paper analyzes and compares methods for ramification, or for update, which are based on minimization of change while respecting static domain constraints. We analyze how the choice of minimization strategy affects the set of preferred new states. Besides the classical case of straight minimization, we analyze alternative cases where state variables (fluents) are partitioned into two or three kinds, such as occluded/unoccluded, persistent/nonpersistent, frame/nonframe, or released/nonreleased, and where minimization treats changes in these categories differently. This includes the methods previously proposed by del Val and Shoham, and by Kartha and Lifschitz. We also discuss and analyze an additional technique, called changeset-partitioning, where minimization is done separately for each outcome of a nondeterministic action. We relate it to the previous methods, and argue that this new method is generally to be preferred over them.
Sandewall, E. (1996). Towards a World-Wide Data Base. Technical Report LiTH-IDA-R-96-21, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: The present paper proposes that a database can often be organized as a large collection of small text files, each containing the structured information that relates to a particular object. This means that the basic idea of WWW pages - small text files that are cross-linked by symbolic addresses - is generalized to become a database technique as well. The database pages are expressed in HORL notation (HyperObject Representation Language). Just like a WWW browser accesses and reads HTML pages dynamically as it needs them, our WWDB database system accesses and reads HORL pages as it needs them in the course of its data processing operations. When an HORL page is read by the database system, its contents are converted to an internal representation, and it does not have to be read again during the same session. In this paper, we first describe the application within which the WWDB concepts were developed, and then proceed to a description of the essential technical characteristics of the existing, experimental implementation. Finally we discuss what conclusions can be drawn from the project so far, and the perspectives for continued use of this technique.
Sandewall, E. (1996). Transition Cascade Semantics and first Assessments Results for Ramification, Preliminary Report. Technical Report LiTH-IDA-R-96-19, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This article reports on assessment results for several approaches to the ramification problem. Two types of assessments are reported: (1) Assessment of soundness for one minimization based and one causation-based method; (2) Relative range assessments for a number of minimization based methods. Assessment of soundness is based on an underlying semantics for ramification. We propose, define, and use a transition cascade semantics for this purpose. Transition cascade means that an action is viewed as consisting of an initial state transition which represents the invocation of the action, followed by a succession of other state transitions which may be understood as representing a causal chain. The assessment of an entailment method specifies restrictions on the invocation and causation relations which guarantee that the entailment method is sound. Relative range assessments compare entailment methods pairwise and specify whether the set of selected models obtained by one is a subset of the set of selected models obtained by the other.