http://sedici.unlp.edu.ar:80/handle/10915/134627 Fri, 13 Nov 2026 08:11:06 GMT 2026-11-13T08:11:06Z http://sedici.unlp.edu.ar:80/handle/10915/135738 Contribucion a revista Electronic Journal of SADIO; vol. 1 Nota inaugural del Electronic Journal of SADIO, redactada para el primer volumen publicado de dicha revista. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135738 1998-06-26T00:00:00Z Nota inaugural del Electronic Journal of SADIO, redactada para el primer volumen publicado de dicha revista. http://sedici.unlp.edu.ar:80/handle/10915/135589 Contribucion a revista Electronic Journal of SADIO; vol. 1 The class of Computable Queries (CQ) was de ned by Chandra and Harel in 1980, as functions on structures rather than functions on numbers (as recursive functions). With this formulation of the notion of a query to a relational database (db), the field of Finite Model Theory became a suitable theoretical framework for relational databases. In this framework the notion of local expressibility of a given logic is the class of queries which can be expressed in that logic. On the other hand, in 1991, Abiteboul and Vianu de fined the Generic Machine, denoted as GMloose, which they proved to be strictly included in CQ. They also proved that this class of machines behaves as complete w.r.t. the whole class CQ when working on classes of ordered db. If we consider the structures as db instances, and if we are using a GMloose machine, it means that we will not be able to compute queries such as \give me the names of the salesmen who sell to an even number of clients unless our db is ordered. In the present Thesis, we study some properties of relational db which can increase the expressive power of relational languages or formalisms which are incomplete in the general case, when working on classes of db which satisfy that properties. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135589 1998-06-26T00:00:00Z The class of Computable Queries (CQ) was de ned by Chandra and Harel in 1980, as functions on structures rather than functions on numbers (as recursive functions). With this formulation of the notion of a query to a relational database (db), the field of Finite Model Theory became a suitable theoretical framework for relational databases. In this framework the notion of local expressibility of a given logic is the class of queries which can be expressed in that logic. On the other hand, in 1991, Abiteboul and Vianu de fined the Generic Machine, denoted as GMloose, which they proved to be strictly included in CQ. They also proved that this class of machines behaves as complete w.r.t. the whole class CQ when working on classes of ordered db. If we consider the structures as db instances, and if we are using a GMloose machine, it means that we will not be able to compute queries such as \give me the names of the salesmen who sell to an even number of clients unless our db is ordered. In the present Thesis, we study some properties of relational db which can increase the expressive power of relational languages or formalisms which are incomplete in the general case, when working on classes of db which satisfy that properties. http://sedici.unlp.edu.ar:80/handle/10915/135584 Contribucion a revista Electronic Journal of SADIO; vol. 1 Testing a software system consists of executing it over a suitable sample of input data and then checking if the output produced matches what was expected. Testing is widely used to enhance software quality, and, specifically, to uncover bugs that are inevitably introduced during the software development process. One of the most difficult problems in testing is knowing when to stop the testing process. On the one hand, it is not possible in general to give an answer to whether a test suite guarantees the absence of faults. On the other hand, we need a way to limit the cost of testing. Therefore, it is useful to have criteria to determine when a program has been tested enough. Ideally, the testing process should be planned in advance. However, in practice the tests are incorporated little by little, until some adequacy criterion is satisfied. In particular, different coverages can be used to determine when the program has been tested enough. The idea is to guarantee that each statement, decision or other feature of the program has been executed at least once under some test. A major problem is that testing takes a considerable amount of the time and resources spent on producing software [?]. Therefore, it would be useful to have ways 1. to reduce the cost of testing, and 2. to estimate this cost. In particular, the number of tests to be executed impacts heavily on the cost of testing. In fact, the time and resources needed for testing increase as the number of test cases increases. Hence, to reduce the cost of testing, the number of test cases generated to satisfy a selected test criterion should be as small as possible. Moreover, a bound on the number of tests that have to be performed to satisfy a selected test strategy can be used by managers and testers to estimate the effort needed to carry out the tests. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135584 1998-06-26T00:00:00Z Testing a software system consists of executing it over a suitable sample of input data and then checking if the output produced matches what was expected. Testing is widely used to enhance software quality, and, specifically, to uncover bugs that are inevitably introduced during the software development process. One of the most difficult problems in testing is knowing when to stop the testing process. On the one hand, it is not possible in general to give an answer to whether a test suite guarantees the absence of faults. On the other hand, we need a way to limit the cost of testing. Therefore, it is useful to have criteria to determine when a program has been tested enough. Ideally, the testing process should be planned in advance. However, in practice the tests are incorporated little by little, until some adequacy criterion is satisfied. In particular, different coverages can be used to determine when the program has been tested enough. The idea is to guarantee that each statement, decision or other feature of the program has been executed at least once under some test. A major problem is that testing takes a considerable amount of the time and resources spent on producing software [?]. Therefore, it would be useful to have ways 1. to reduce the cost of testing, and 2. to estimate this cost. In particular, the number of tests to be executed impacts heavily on the cost of testing. In fact, the time and resources needed for testing increase as the number of test cases increases. Hence, to reduce the cost of testing, the number of test cases generated to satisfy a selected test criterion should be as small as possible. Moreover, a bound on the number of tests that have to be performed to satisfy a selected test strategy can be used by managers and testers to estimate the effort needed to carry out the tests. http://sedici.unlp.edu.ar:80/handle/10915/135553 Articulo Electronic Journal of SADIO; vol. 1 For the development of safety-critical reactive systems, proving correctness is unavoidable. Here we describe some research issues on using and combining formal methods. Using the Electre reactive language we illustrate a technique to the design of a sound compiler with the Coq theorem prover. Based on the same source language semantic model, we present the outlines of a method to verify correctness claims with the SPIN model checker. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135553 1998-06-26T00:00:00Z For the development of safety-critical reactive systems, proving correctness is unavoidable. Here we describe some research issues on using and combining formal methods. Using the Electre reactive language we illustrate a technique to the design of a sound compiler with the Coq theorem prover. Based on the same source language semantic model, we present the outlines of a method to verify correctness claims with the SPIN model checker. http://sedici.unlp.edu.ar:80/handle/10915/135550 Articulo Electronic Journal of SADIO; vol. 1 The construction of information visualization systems is a difficult task. The provision of an object-oriented software architecture for this kind of systems can help to reduce this difficulty. However, this approach is not currently used in most visualization systems. In this work, Telescope, an object-oriented architecture for visualization systems, is presented. Its main goal is to facilitate this construction, taking advantage of the benefits of the object-oriented paradigm (reusability, extensibility, and maintainability). The Telescope architecture is based on six main components, which are common to all information visualization systems: data representation, data abstraction, data objects- graphical objects mapping, presentation, interaction and visualization state. CityVis, a visualization system for city data, developed using Telescope architecture is described, showing the implementation of each Telescope component. Also, the implementation of several features in visualization systems, such as visualization techniques and management of abstraction levels and revealed information is described. Finally, current work and conclusions of the project are explained. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135550 1998-06-26T00:00:00Z The construction of information visualization systems is a difficult task. The provision of an object-oriented software architecture for this kind of systems can help to reduce this difficulty. However, this approach is not currently used in most visualization systems. In this work, Telescope, an object-oriented architecture for visualization systems, is presented. Its main goal is to facilitate this construction, taking advantage of the benefits of the object-oriented paradigm (reusability, extensibility, and maintainability). The Telescope architecture is based on six main components, which are common to all information visualization systems: data representation, data abstraction, data objects- graphical objects mapping, presentation, interaction and visualization state. CityVis, a visualization system for city data, developed using Telescope architecture is described, showing the implementation of each Telescope component. Also, the implementation of several features in visualization systems, such as visualization techniques and management of abstraction levels and revealed information is described. Finally, current work and conclusions of the project are explained. http://sedici.unlp.edu.ar:80/handle/10915/135547 Articulo Electronic Journal of SADIO; vol. 1 This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessarily have an exponential sequential time complexity even if highly performant data structures (as e.g. the straight--line program encoding of polynomials) are used. The paper finishes with the motivated introduction of a new non-uniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135547 1998-06-26T00:00:00Z This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessarily have an exponential sequential time complexity even if highly performant data structures (as e.g. the straight--line program encoding of polynomials) are used. The paper finishes with the motivated introduction of a new non-uniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity. http://sedici.unlp.edu.ar:80/handle/10915/135545 Articulo Electronic Journal of SADIO; vol. 1 The Multi-threaded Paging problem (MTP) was introduced as a generalization of Paging for the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. At each step it is necessary to decide which request to serve among several possibilities, and also (as in normal Paging) which page of fast memory to remove on a page fault. In the fair version of the problem any algorithm must guarantee that the next request of each thread will be served within a predetermined finite time.In this paper we reduce the existing gaps between the known lower and upper bounds for the competitiveness of on-line algorithms for the fair version of MTP. We treat some particular situations, with finite and infinite input sequences. We prove higher lower bounds and present a new on-line algorithm. We close the gap for the case in which the cache can hold only one page; surprisingly, we obtain different bounds for even and odd number of sequences; we prove that any lazy algorithm achieves the on-line lower bound when the number of sequences is odd.Research supported in part by EC project DYNDATA under program KIT, and by UBACyT projects ``Algoritmos Eficientes para Problemas On-line con Aplicaciones'' and ``Modelos y Técnicas de Optimización Combinatoria". Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135545 1998-06-26T00:00:00Z The Multi-threaded Paging problem (MTP) was introduced as a generalization of Paging for the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. At each step it is necessary to decide which request to serve among several possibilities, and also (as in normal Paging) which page of fast memory to remove on a page fault. In the fair version of the problem any algorithm must guarantee that the next request of each thread will be served within a predetermined finite time.In this paper we reduce the existing gaps between the known lower and upper bounds for the competitiveness of on-line algorithms for the fair version of MTP. We treat some particular situations, with finite and infinite input sequences. We prove higher lower bounds and present a new on-line algorithm. We close the gap for the case in which the cache can hold only one page; surprisingly, we obtain different bounds for even and odd number of sequences; we prove that any lazy algorithm achieves the on-line lower bound when the number of sequences is odd.Research supported in part by EC project DYNDATA under program KIT, and by UBACyT projects ``Algoritmos Eficientes para Problemas On-line con Aplicaciones'' and ``Modelos y Técnicas de Optimización Combinatoria". http://sedici.unlp.edu.ar:80/handle/10915/135519 Articulo Electronic Journal of SADIO; vol. 1 A new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. The proposal consists in the decomposition of the occurrence matrix in two stages, using methodologies based on graph theory. First of all, Hopcroft-Karp´s algorithm is employed to match the vertices, this classification being carried out by means of a modification of Dulmage-Mendelsohn´s technique, which was devised by the authors. The second step is the application of Tarjan´s algorithm to the square blocks obtained as a result of the first stage. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135519 1998-06-26T00:00:00Z A new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. The proposal consists in the decomposition of the occurrence matrix in two stages, using methodologies based on graph theory. First of all, Hopcroft-Karp´s algorithm is employed to match the vertices, this classification being carried out by means of a modification of Dulmage-Mendelsohn´s technique, which was devised by the authors. The second step is the application of Tarjan´s algorithm to the square blocks obtained as a result of the first stage. http://sedici.unlp.edu.ar:80/handle/10915/135512 Articulo Electronic Journal of SADIO; vol. 1 Active databases (ADBs) are databases that include active components or agents that can execute actions. The rise of active databases in the picture of software development has a great impact on software systems and in the discipline of software engineering. However, we still lack the foundations that are needed to adequately support this new tool. These foundations are needed in order to properly apply known software engineering techniques to ADBs and systems that use them. Among the methods and techniques used to improve quality, we count systematic testing. In this work, we generalize structural testing techniques to ADB systems. We introduce a model of active databases, called dbgraph, suitable for testing. We show that dbgraphs can be used to generalize structural testing techniques for ADBs. Moreover, we introduce several new structural criteria aimed at find errors in a set of rules for an ADB. We also compare the strength of the coverage criteria presented in this work.Supported in part by UBACyT grant EX186. Fri, 26 Jun 1998 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/135512 1998-06-26T00:00:00Z Active databases (ADBs) are databases that include active components or agents that can execute actions. The rise of active databases in the picture of software development has a great impact on software systems and in the discipline of software engineering. However, we still lack the foundations that are needed to adequately support this new tool. These foundations are needed in order to properly apply known software engineering techniques to ADBs and systems that use them. Among the methods and techniques used to improve quality, we count systematic testing. In this work, we generalize structural testing techniques to ADB systems. We introduce a model of active databases, called dbgraph, suitable for testing. We show that dbgraphs can be used to generalize structural testing techniques for ADBs. Moreover, we introduce several new structural criteria aimed at find errors in a set of rules for an ADB. We also compare the strength of the coverage criteria presented in this work.Supported in part by UBACyT grant EX186.