bluuebunny/crossref_metadata_2025_split huggingface dataset:
Generalized algorithmic debugging and testing
Authors: Fritzson Peter , Shahmehri Nahid , Kamkar Mariam , Gyimothy Tibor 
Published: July 2002

This paper presents a method for semi-automatic bug localization, generalized algorithmic debugging, which has been integrated with the category partition method for functional testing. In this way the efficiency of the algorithmic debugging method for bug localization can be improved by using test specifications and test results. The long-range goal of this work is a semi-automatic debugging and testing system which can be used during large-scale program development of nontrivial programs.The method is generally applicable to procedural langua ges and is not dependent on any ad hoc assumptions regarding the subject program. The original form of algorithmic debugging, introduced by Shapiro, was however limited to small Prolog programs without side-effects, but has later been generalized to concurrent logic programming languages. Another drawback of the original method is the large number of interactions with the user during bug localization.To our knowledge, this is the first method which uses category partition testing to improve the bug localization properties of algorithmic debugging. The method can avoid irrelevant questions to the programmer by categorizing input parameters and then match these against test cases in the test database. Additionally, we use program slicing, a data flow analysis technique, to dynamically compute which parts of the program are relevant for the search, thus further improving bug localization.We believe that this is the first generalization of algorithmic debugging for programs with side-effects written in imperative languages such as Pascal. These improvements together makes it more feasible to debug larger programs. However, additional improvements are needed to make it handle pointer-related side-effects and concurrent Pascal programs.A prototype generalized algorithmic debugger for a Pascal subset without pointer side-effects and a test case generator for application programs in Pascal, C, dBase, and LOTUS have been implemented.
Diversity-based inference of finite automata
Authors: Rivest Ronald L. , Schapire Robert E. 
Published: July 2002

We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments.Our procedures use a new representation for finite automata, based on the notion of equivalence betweentests. We call the number of such equivalence classes thediversityof the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. For the special class ofpermutation automata, we describe an inference procedure that runs in time polynomial in the diversity and log(1/δ), where δ is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) We also discuss techniques for handling more general automata.We present evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately 1019states) in about 2 minutes on a DEC MicroVax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction (10-14) of the global states were even visited.)Finally, we present a new procedure for inferring automata of a special type in which the global state is composed of a vector of binary local state variables, all of which are observable (orvisible) to the experimenter. Our inference procedure runs provably in time polynomial in the size of this vector (which happens to be the diversity of the automaton), even though the global state space may be exponentially larger. The procedure plans and executes experiments on the unknown automaton; we show that the number of input symbols given to the automaton during this process is (to within a constant factor) the best possible.
Applications of inductive logic programming
Authors: Bratko Ivan , Muggleton Stephen 
Published: July 2002

Techniques of machine learning have been successfully applied to various problems [1, 12]. Most of these applications rely on attribute-based learning, exemplified by the induction of decision trees as in the program C4.5 [20]. Broadly speaking, attribute-based learning also includes such approaches to learning as neural networks and nearest neighbor techniques. The advantages of attribute-based learning are: relative simplicity, efficiency, and existence of effective techniques for handling noisy data. However, attribute-based learning is limited to non-relational descriptions of objects in the sense that the learned descriptions donotspecifyrelationsamong the objects' parts. Attribute-based learning thus has two strong limitations:the background knowledge can be expressed in rather limited form, andthe lack of relations makes the concept description language inappropriate for some domains.
Provably efficient scheduling for languages with fine-grained parallelism
Authors: Blelloch Guy E. , Gibbons Phillip B. , Matias Yossi 
Published: July 2002

Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages can express the full parallelism in the program without specifying the mapping of program tasks to processors. A common concern in executing such programs is to schedule tasks to processors dynamically so as to minimize not only the execution time, but also the amount of space (memory) needed. Without careful scheduling, the parallel execution onpprocessors can use a factor ofpor larger more space than a sequential implementation of the same program.This paper first identifies a class of parallel schedules that are provably efficient in both time and space. For any computation withwunits of work and critical path lengthd, and for any sequential schedule that takes space s1, we provide a parallel schedule that takes fewer than w/p + d steps on p processors and requires less than s1+ p·d space. This matches the lower bound that we show, and significantly improves upon the best previous bound of s1·p spaces for the common case whered«s1.The paper then describes a scheduler for implementing high-level languages withnestedparallelism, that generates schedules in this class. During program execution, as the structure of the computation is revealed, the scheduler keeps track of the active tasks, allocates the tasks to the processors, and performs the necessary task synchronization. The scheduler is itself a parallel algorithm, and incurs at most a constant factor overhead in time and space, even when the scheduling granularity is individual units of work. The algorithm is the first efficient solution to the scheduling problem discussed here, even if space considerations are ignored.
Inductive analysis of the Internet protocol TLS
Authors: Paulson Lawrence C. 
Published: July 2002

Internet browsers use security protocols to protect sensitive messages. An inductive analysis of TLS (a descendant of SSL 3.0) has been performed using the theorem prover Isabelle. Proofs are based on higher-order logic and make no assumptions concerning beliefs of finiteness. All the obvious security goals can be proved; session resumption appears to be secure even if old session keys are compromised. The proofs suggest minor changes to simplify the analysis.
TLS, even at an abstract level, is much more complicated than most protocols verified by researchers. Session keys are negotiated rather than distributed, and the protocol has many optional parts. Netherless, the resources needed to verify TLS are modest: six man-weeks of effort and three minutes of processor time.
Space/time trade-offs in hash coding with allowable errors
Authors: Bloom Burton H. 
Published: July 2002

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency.
The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods.
In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.
Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.
An extension of the Munkres algorithm for the assignment problem to rectangular matrices
Authors: Bourgeois François , Lassalle Jean-Claude 
Published: July 2002

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices.
Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.
The family of concurrent logic programming languages
Authors: Shapiro Ehud 
Published: July 2002

Concurrent logic languages are high-level programming languages for parallel and distributed systems that offer a wide range of both known and novel concurrent programming techniques. Being logic programming languages, they preserve many advantages of the abstract logic programming model, including the logical reading of programs and computations, the convenience of representing data structures with logical terms and manipulating them using unification, and the amenability to metaprogramming. Operationally, their model of computation consists of a dynamic set of concurrent processes, communicating by instantiating shared logical variables, synchronizing by waiting for variables to be instantiated, and making nondeterministic choices, possibly based on the availability of values of variables.This paper surveys the family of concurrent logic programming languages within a uniform operational framework. It demonstrates the expressive power of even the simplest language in the family and investigates how varying the basic synchronization and control constructs affect the expressiveness and efficiency of the resulting languages.In addition, the paper reports on techniques for sequential and parallel implementation of languages in this family, mentions their applications to date, and relates these languages to the abstract logic programming model, to the programming language PROLOG, and to other concurrent computational models and programming languages.
Organic Molecules in the Interstellar Medium, Comets, and Meteorites: A Voyage from Dark Clouds to the Early Earth
Authors: Ehrenfreund Pascale , Charnley Steven B. 
Published: July 2002

▪ Abstract  Our understanding of the evolution of organic molecules, and their voyage from molecular clouds to the early solar system and Earth, has changed dramatically. Incorporating recent observational results from the ground and space, as well as laboratory simulation experiments and new methods for theoretical modeling, this review recapitulates the inventory and distribution of organic molecules in different environments. The evolution, survival, transport, and transformation of organics is monitored, from molecular clouds and the diffuse interstellar medium to their incorporation into solar system material such as comets and meteorites. We constrain gas phase and grain surface formation pathways to organic molecules in dense interstellar clouds, using recent observations with the Infrared Space Observatory (ISO) and ground-based radiotelescopes. The main spectroscopic evidence for carbonaceous compounds in the diffuse interstellar medium is discussed (UV bump at 2200 Å, diffuse interstellar bands, extended red emission, and infrared absorption and emission bands). We critically review the signatures and unsolved problemsrelated to the main organic components suggested to be present in the diffuse gas, such as polycyclic aromatic hydrocarbons (PAHs), fullerenes, diamonds, and carbonaceous solids. We also briefly discuss the circumstellar formation of organics around late-typestars.In the solar system, space missions to comet Halley and observations of the bright comets Hyakutake and Hale-Bopp have recently allowed a reexamination of the organic chemistry of dust and volatiles in long-period comets. We review the advances in this area and also discuss progress being made in elucidating the complex organic inventory of carbonaceous meteorites. The knowledge of organic chemistry in molecular clouds, comets, and meteorites and their common link provides constraints for the processes that lead to the origin, evolution, and distribution of life in the Galaxy.
TRANSCRIPTIONAL REGULATION BY CYCLIC AMP
Authors: Montminy Marc 
Published: July 2002

A number of hormones and growth factors have been shown to stimulate target cells via second messenger pathways that in turn regulate the phosphorylation of specific nuclear factors. The second messenger cyclic AMP, for example, regulates a striking number of physiologic processes, including intermediary metabolism, cellular proliferation, and neuronal signaling, by altering basic patterns of gene expression. Our understanding of cyclic AMP signaling in the nucleus has expanded considerably over the past decade, owing in large part to the characterization of cyclic AMP–responsive promoter elements, transcription factors that bind them, and signal-dependent coactivators that mediate target gene induction. More importantly, these studies have revealed new insights into biological problems as diverse as biological clocks and long-term memory. The purpose of this review is to describe the components of the cyclic AMP response unit and to analyze how these components cooperate to induce target gene expression in response to hormonal stimulation.
Microfabrication in Biology and Medicine
Authors: Voldman Joel , Gray Martha L. , Schmidt Martin A. 
Published: July 2002

▪ Abstract  Microfabrication uses integrated-circuit manufacturing technology supplemented by its own processes to create objects with dimensions in the range of micrometers to millimeters. These objects can have miniature moving parts, stationary structures, or both. Microfabrication has been used for many applications in biology and medicine. These applications fall into four domains: tools for molecular biology and biochemistry, tools for cell biology, medical devices, and biosensors. Microfabricated device structures may provide significantly enhanced function with respect to a conventional device. Sometimes microfabrication can enable devices with novel capabilities. These enhancing and enabling qualities are conferred when microfabrication is used appropriately to address the right types of problems.Herein, we describe microfabrication technology and its application to biology and medicine. We detail several classes of advantages conferred by microfabrication and how these advantages have been used to date.
Inbreeding Depression in Conservation Biology
Authors: Hedrick Philip W. , Kalinowski Steven T. 
Published: July 2002

▪ Abstract  Inbreeding depression is of major concern in the management and conservation of endangered species. Inbreeding appears universally to reduce fitness, but its magnitude and specific effects are highly variable because they depend on the genetic constitution of the species or populations and on how these genotypes interact with the environment. Recent natural experiments are consistent with greater inbreeding depression in more stressful environments. In small populations of randomly mating individuals, such as are characteristic of many endangered species, all individuals may suffer from inbreeding depression because of the cumulative effects of genetic drift that decrease the fitness of all individuals in the population. In three recent cases, introductions into populations with low fitness appeared to restore fitness to levels similar to those before the effects of genetic drift. Inbreeding depression may potentially be reduced, or purged, by breeding related individuals. However, the Speke's gazelle example, often cited as a demonstration of reduction of inbreeding depression, appears to be the result of a temporal change in fitness in inbred individuals and not a reduction in inbreeding depression.      Down, July 17, 1870  My Dear Lubbock,  …In England and many parts of Europe the marriages of cousins are objected to from their supposed injurious consequences: but this belief rests on no direct evidence. It is therefore manifestly desirable that the belief should be either proved false, or should be confirmed, so that in this latter case the marriages of cousins might be discouraged…   It is moreover, much to be wished that the truth of the often repeated assertion that consanguineous marriages lead to deafness and dumbness, blindness, &c, should be ascertained: and all such assertions could be easily tested by the returns from a single census.      Believe me,      Yours very sincerely,      Charles Darwin
HIGHER-ORDER PREDATORS AND THE REGULATION OF INSECT HERBIVORE POPULATIONS
Authors: Rosenheim Jay A. 
Published: July 2002

▪ Abstract  Empirical research has not supported the prediction that populations of terrestrial herbivorous arthropods are regulated solely by their natural enemies. Instead, both natural enemies (top-down effects) and resources (bottom-up effects) may play important regulatory roles. This review evaluates the hypothesis that higher-order predators may constrain the top-down control of herbivore populations. Natural enemies of herbivorous arthropods generally are not top predators within terrestrial food webs. Insect pathogens and entomopathogenic nematodes inhabiting the soil may be attacked by diverse micro- and mesofauna. Predatory and parasitic insects are attacked by their own suite of predators, parasitoids, and pathogens. The view of natural enemy ecology that has emerged from laboratory studies, where natural enemies are often isolated from all elements of the biotic community except for their hosts or prey, may be an unreliable guide to field dynamics.Experimental work suggests that interactions of biological control agents with their own natural enemies can disrupt the effective control of herbivore populations. Disruption has been observed experimentally in interactions of bacteria with bacteriophages, nematodes with nematophagous fungi, parasitoids with predators, parasitoids with hyperparasitoids, and predators with other predators. Higher-order predators have been little studied; manipulative field experiments will be especially valuable in furthering our understanding of their roles in arthropod communities.
THE INSECT VOLTAGE-GATED SODIUM CHANNEL AS TARGET OF INSECTICIDES
Authors: Zlotkin Eliahu 
Published: July 2002

▪ Abstract  Examination of the function, chemistry, and pharmacology of the voltage-gated insect sodium channel (ISC) reveals that the ISC closely resembles its vertebrate counterpart in electrophysiology and ion conductance, primary structure and allocation of all functional domains, and its pharmacological diversity and flexibility exhibited by the occurrence of different allosterically coupled receptor-binding sites for various neurotoxicants. The toxicants include several groups of insecticides, namely DDT and its analogues, pyrethroids, N-alkylamides, and dihydropyrazoles, which affect channel gating and ion permeability. Despite their similarity, the insect and vertebrate channels are pharmacologically distinguishable, as revealed by the responsiveness of the heterologously expressed Drosophila para clone to channel modifiers and blockers and the occurrence of the insect-selective sodium channel neurotoxins derived from arachnid venoms presently used for the design of recombinant baculovirus-mediated selective bioinsecticides. The pharmacological specificity of the ISC may lead to the design of insect-selective toxicants, and its pharmacological flexibility may direct the use of ISC insecticides for resistance management. Insecticide resistance [such as knockdown resistance (KDR)] is acquired by natural selection and operated by increased metabolism, channel mutagenesis, or both. The resistance issue can be dealt with in several ways. One is by simultaneous application of low doses of synergistic, allosterically coupled mixtures (thus delaying or preventing the onset of resistance). An alternative is to replace an insecticide to which resistance was acquired by channel mutation with a different ISC toxicant to which increased susceptibility was conferred by the same mutation. Such a possibility was exemplified by a significant increase in susceptibility to N-alkylamides, as well as an insect-selective neurotoxin revealed by KDR insects. Third, both of these methods can be combined. Thus owing to its pharmacological uniqueness, the ISC may serve as a high-priority target for future selective and resistance-manageable insecticides.
MILTON VAN DYKE, THE MAN AND HIS WORK
Authors: Schwartz Leonard W. 
Published: July 2002

I was moved and honored when the Editors of the Annual Review of Fluid Mechanics asked me to write a biography of Professor Van Dyke. I did my Ph.D. with Milton in the Department of Aeronautics and Astronautics at Stanford during the late 1960s and early 1970s. Since the first time that I met him almost 35 years ago, I have admired and respected him as a scientist but also have enjoyed his kindness, modesty, and wit. A few years ago, several of Milton’s students organized a birthday celebration for him. His wife, Sylvia, wrote a biography of him as part of the informal proceedings volume. In writing this article, I have drawn liberally from that biography as well as from other written and oral recollections of Milton. I also discuss some of Milton’s technical work. The emphasis and perspective on these works is my own, including, of course, any possible misinterpretations. Prior to becoming a full-time graduate student at Stanford, I had worked in the Re-entry Aerodynamics Group at Lockheed Missiles and Space Company in Sunnyvale, California. Thus, I was quite familiar with several of Milton’s papers on supersonic and hypersonic flow. Some of this work and follow-up work by other NACA and NASA scientists was used by us virtually on a daily basis. In addition to Milton’s technical mathematics and fluid mechanics and his personal history, I highlight his extensive “public service” work. These largely unsung contributions bring many benefits to the worldwide fluid mechanics community. Perhaps most obviously, Milton co-founded the Annual Review of Fluid Mechanics more than 30 years ago. He has been the principal guide of this most important repository of our professional knowledge ever since.