8215557
Time Equations for Lazy Functional (Logic) Languages
There are very few approaches to measure the execution costs of lazy functional (logic) programs. The use of a lazy execution mechanism implies that the complexity of an evaluation depends on its context, i.e., the evaluation of the same expression may have different costs depending on the degree of evaluation required by the different contexts where it appears. In this paper, we present a novel approach to complexity analysis of functional (logic) programs. We focus on the construction of equations which compute the time-complexity of expressions. In contrast to previous approaches, it is simple, precise—i.e., it computes exact costs rather than upper/lower bounds—, and fully automatic.
5417799
Slicing XML Documents
Program slicing is a well-known technique to extract the program statements that (potentially) affect the values computed at some point of interest. In this work, we introduce a novel slicing method for XML documents. Essentially, given an XML document (which is valid w.r.t. some DTD), we produce a new XML document (a slice) that contains the relevant information in the original XML document according to some criterion. Furthermore, we also output a new DTD such that the computed slice is valid w.r.t. this DTD. A prototype implementation of the XML slicer has been undertaken.
2088546
Combining algorithmic debugging and program slicing
Currently, program slicing and algorithmic debugging are two of the most relevant debugging techniques for declarative languages. They help programmers to find bugs in a semiautomatic manner. On the one hand, program slicing is a technique to extract those program fragments that (potentially) affect the values computed at some point of interest. On the other hand, algorithmic debugging is able to locate a bug by automatically generating a series of questions and processing the programmer's answers. In this work, we show for functional languages how the combination of both techniques produces a more powerful debugging schema that reduces the number of questions that programmers must answer to locate a bug
1093169
An Embedded Language Approach to Router Specification in Curry
The development of modern routers require a significant effort to be designed, built, and verified. While hardware routers are faster, they are difficult to configure and maintain. Software routers, on the other hand, are slower but much more flexible, easier to configure and maintain, less expensive, etc. Recently, a modular architecture and toolkit for building software routers and other packet processors has been introduced: the Click system. It includes a specification language with features for declaring and connecting router elements and for designing abstractions.
62642642
GRASP—a new search algorithm for satisfiability
This paper introduces GRASP (Generic seaRch Algorithm for the Satisfiability Problem), an integrated algorithmic framework for SAT that unifies several previously proposed search-pruning techniques and facilitates identification of additional ones. GRASP is premised on the inevitability of conflicts during search and its most distinguishing feature is the augmentation of basic backtracking search with a powerful conflict analysis procedure. Analyzing conflicts to determine their causes enables GRASP to backtrack non-chronologically to earlier levels in the search tree, potentially pruning large portions of the search space. In addition, by "recording" the causes of conflicts, GRASP can recognize and preempt the occurrence of similar conflicts later on in the search. Finally, straightforward bookkeeping of the causality chains leading up to conflicts allows GRASP to identify assignments that are necessary for a solution to be found. Experimental results obtained from a large number of benchmarks, including many from the field of test pattern generation, indicate that application of the proposed conflict analysis techniques to SAT algorithms can be extremely effective for a large number of representative classes of SAT instances.
9058735
Supporting Disconnected Computing in Mobile Agent Systems
Mobile agents are typically referred as a very adequate paradigm for using in mobile and disconnected computing environments. They are autonomous, have a strong sense of location and are able to operate independently of a central server. Nevertheless, although this is true, for developing a mobile agent system that is capable of operating in a disconnected computing environment, much more is needed: persistence stores where the agents can be safely stored; agent reactivation mechanisms, which allow agents to migrate when a network connection is detected; policies and notification mechanisms for dealing with changing locations; among other things. In this paper, we present the mechanisms developed for the M&M mobile agent framework in order to address mobile and disconnected computing environments. These mechanisms can be readily adapted to any other platform that needs to deal with disconnected computing. Keyworks: Distributed agents, mobile agents, mobile computing, disconnected computing
38588422
Merging Web-Based with Cluster-Based Computing
This paper presents a Java-based software infrastructure that allows the merging of Web-based metacomputing with cluster-based parallel computing. We briefly compare the two approaches and we describe the implementation of a software bridge that supports the execution of metaapplications: some processes of the application may run over the Internet as Java applets while other processes of the same application can execute on a dedicated cluster of machines running PVM or MPI. We present some performance results that show the effectiveness of our approach.
42287277
A Divide-and-Conquer Approach to Acquire Syntactic Categories
In this paper we propose an unsupervised strategy for learning syntactic information that proceeds in several steps. First, we identify, cluster, and classify function words from unannotated corpora. Then, the acquired information is used in two different learning processes. On the one hand, it is used to learn morpho-syntactic categories of nouns and, on the other, it turns out to be useful to also induce syntactic/semantic relationships between content words. Experiments performed on Portuguese and English corpora are reported.
29620691
Heterogeneous parallel computing using Java and WMPI
In this paper, we present briefly the implementation of a Java interface forWMPI , a Windows-based implementation of MPI. Then, we describe a system that is oriented for Web-based computing and present a solution to integrate WMPIwith this tool by making use of a Java bridge component and the Java bindings for WMPI . This solution allows the execution of meta-applications over a mixed configuration of platforms, execution models and programming languages. The resulting system provides a way to solve the problem of heterogeneity and to unleash the potential of diverse computational resources and programming tools. Copyright  2000 John Wiley & Sons, Ltd.