An Admission Control Paradigm for Real-time Databases

We propose and evaluate an admission control paradigm for RTDBS, in which a transaction is submitted to the system as a pair of processes: a primary task, and a recovery block. The execution requirements of the primary task are not known a priori, whereas those of the recovery block are known a priori. Upon the submission of a transaction, an Admission Control Mechanism is employed to decide whether to admit or reject that transaction. Once admitted, a transaction is guaranteed to finish executing before its deadline. A transaction is considered to have finished executing if exactly one of two things occur: Either its primary task is completed (successful commitment), or its recovery block is completed (safe termination). Committed transactions bring a profit to the system, whereas a terminated transaction brings no profit. The goal of the admission control and scheduling protocols (e.g., concurrency control, I/O scheduling, memory management) employed in the system is to maximize system profit. We describe a number of admission control strategies and contrast (through simulations) their relative performance.

Ergodicity and Mixing Rate of One-Dimensional Cellular Automata

One-and two-dimensional cellular automata which are known to be fault-tolerant are very complex. On the other hand, only very simple cellular automata have actually been proven to lack fault-tolerance, i.e., to be mixing. The latter either have large noise probability ε or belong to the small family of two-state nearest-neighbor monotonic rules which includes local majority voting. For a certain simple automaton L called the soldiers rule, this problem has intrigued researchers for the last two decades since L is clearly more robust than local voting: in the absence of noise, L eliminates any finite island of perturbation from an initial configuration of all 0's or all 1's. The same holds for a 4-state monotonic variant of L, K, called two-line voting. We will prove that the probabilistic cellular automata Kε and Lε asymptotically lose all information about their initial state when subject to small, strongly biased noise. The mixing property trivially implies that the systems are ergodic. The finite-time information-retaining quality of a mixing system can be represented by its relaxation time Relax(⋅), which measures the time before the onset of significant information loss. This is known to grow as (1/ε)^c for noisy local voting. The impressive error-correction ability of L has prompted some researchers to conjecture that Relax(Lε) = 2^(c/ε). We prove the tight bound 2^(c1log^21/ε) ＜ Relax(Lε) ＜ 2^(c2log^21/ε) for a biased error model. The same holds for Kε. Moreover, the lower bound is independent of the bias assumption. The strong bias assumption makes it possible to apply sparsity/renormalization techniques, the main tools of our investigation, used earlier in the opposite context of proving fault-tolerance.

ARTMAP: Supervised Real-Time Learning and Classification of Nonstationary Data by a Self-Organizing Neural Network

This article introduces a new neural network architecture, called ARTMAP, that autonomously learns to classify arbitrarily many, arbitrarily ordered vectors into recognition categories based on predictive success. This supervised learning system is built up from a pair of Adaptive Resonance Theory modules (ARTa and ARTb) that are capable of self-organizing stable recognition categories in response to arbitrary sequences of input patterns. During training trials, the ARTa module receives a stream {a^(p)} of input patterns, and ARTb receives a stream {b^(p)} of input patterns, where b^(p) is the correct prediction given a^(p). These ART modules are linked by an associative learning network and an internal controller that ensures autonomous system operation in real time. During test trials, the remaining patterns a^(p) are presented without b^(p), and their predictions at ARTb are compared with b^(p). Tested on a benchmark machine learning database in both on-line and off-line simulations, the ARTMAP system learns orders of magnitude more quickly, efficiently, and accurately than alternative algorithms, and achieves 100% accuracy after training on less than half the input patterns in the database. It achieves these properties by using an internal controller that conjointly maximizes predictive generalization and minimizes predictive error by linking predictive success to category size on a trial-by-trial basis, using only local operations. This computation increases the vigilance parameter ρa of ARTa by the minimal amount needed to correct a predictive error at ARTb· Parameter ρa calibrates the minimum confidence that ARTa must have in a category, or hypothesis, activated by an input a^(p) in order for ARTa to accept that category, rather than search for a better one through an automatically controlled process of hypothesis testing. Parameter ρa is compared with the degree of match between a^(p) and the top-down learned expectation, or prototype, that is read-out subsequent to activation of an ARTa category. Search occurs if the degree of match is less than ρa. ARTMAP is hereby a type of self-organizing expert system that calibrates the selectivity of its hypotheses based upon predictive success. As a result, rare but important events can be quickly and sharply distinguished even if they are similar to frequent events with different consequences. Between input trials ρa relaxes to a baseline vigilance pa When ρa is large, the system runs in a conservative mode, wherein predictions are made only if the system is confident of the outcome. Very few false-alarm errors then occur at any stage of learning, yet the system reaches asymptote with no loss of speed. Because ARTMAP learning is self stabilizing, it can continue learning one or more databases, without degrading its corpus of memories, until its full memory capacity is utilized.

Typical delay determines waiting time on periodic-food schedules: Static and dynamic tests.

Pigeons and other animals soon learn to wait (pause) after food delivery on periodic-food schedules before resuming the food-rewarded response. Under most conditions the steady-state duration of the average waiting time, t, is a linear function of the typical interfood interval. We describe three experiments designed to explore the limits of this process. In all experiments, t was associated with one key color and the subsequent food delay, T, with another. In the first experiment, we compared the relation between t (waiting time) and T (food delay) under two conditions: when T was held constant, and when T was an inverse function of t. The pigeons could maximize the rate of food delivery under the first condition by setting t to a consistently short value; optimal behavior under the second condition required a linear relation with unit slope between t and T. Despite this difference in optimal policy, the pigeons in both cases showed the same linear relation, with slope less than one, between t and T. This result was confirmed in a second parametric experiment that added a third condition, in which T + t was held constant. Linear waiting appears to be an obligatory rule for pigeons. In a third experiment we arranged for a multiplicative relation between t and T (positive feedback), and produced either very short or very long waiting times as predicted by a quasi-dynamic model in which waiting time is strongly determined by the just-preceding food delay.

Comparison of pattern detection methods in microarray time series of the segmentation clock.

While genome-wide gene expression data are generated at an increasing rate, the repertoire of approaches for pattern discovery in these data is still limited. Identifying subtle patterns of interest in large amounts of data (tens of thousands of profiles) associated with a certain level of noise remains a challenge. A microarray time series was recently generated to study the transcriptional program of the mouse segmentation clock, a biological oscillator associated with the periodic formation of the segments of the body axis. A method related to Fourier analysis, the Lomb-Scargle periodogram, was used to detect periodic profiles in the dataset, leading to the identification of a novel set of cyclic genes associated with the segmentation clock. Here, we applied to the same microarray time series dataset four distinct mathematical methods to identify significant patterns in gene expression profiles. These methods are called: Phase consistency, Address reduction, Cyclohedron test and Stable persistence, and are based on different conceptual frameworks that are either hypothesis- or data-driven. Some of the methods, unlike Fourier transforms, are not dependent on the assumption of periodicity of the pattern of interest. Remarkably, these methods identified blindly the expression profiles of known cyclic genes as the most significant patterns in the dataset. Many candidate genes predicted by more than one approach appeared to be true positive cyclic genes and will be of particular interest for future research. In addition, these methods predicted novel candidate cyclic genes that were consistent with previous biological knowledge and experimental validation in mouse embryos. Our results demonstrate the utility of these novel pattern detection strategies, notably for detection of periodic profiles, and suggest that combining several distinct mathematical approaches to analyze microarray datasets is a valuable strategy for identifying genes that exhibit novel, interesting transcriptional patterns.

Measuring fast gene dynamics in single cells with time-lapse luminescence microscopy.

Time-lapse fluorescence microscopy is an important tool for measuring in vivo gene dynamics in single cells. However, fluorescent proteins are limited by slow chromophore maturation times and the cellular autofluorescence or phototoxicity that arises from light excitation. An alternative is luciferase, an enzyme that emits photons and is active upon folding. The photon flux per luciferase is significantly lower than that for fluorescent proteins. Thus time-lapse luminescence microscopy has been successfully used to track gene dynamics only in larger organisms and for slower processes, for which more total photons can be collected in one exposure. Here we tested green, yellow, and red beetle luciferases and optimized substrate conditions for in vivo luminescence. By combining time-lapse luminescence microscopy with a microfluidic device, we tracked the dynamics of cell cycle genes in single yeast with subminute exposure times over many generations. Our method was faster and in cells with much smaller volumes than previous work. Fluorescence of an optimized reporter (Venus) lagged luminescence by 15-20 min, which is consistent with its known rate of chromophore maturation in yeast. Our work demonstrates that luciferases are better than fluorescent proteins at faithfully tracking the underlying gene expression.

One hundred years of forgetting: A quantitative description of retention

A sample of 210 published data sets were assembled that (a) plotted amount remembered versus time, (b) had 5 or more points, and (c) were smooth enough to fit at least 1 of the functions tested with a correlation coefficient of .90 or greater. Each was fit to 105 different 2-parameter functions. The best fits were to the logarithmic function, the power function, the exponential in the square root of time, and the hyperbola in the square root of time. It is difficult to distinguish among these 4 functions with the available data, but the same set of 4 functions fit most data sets, with autobiographical memory being the exception. Theoretical motivations for the best fitting functions are offered. The methodological problems of evaluating functions and the advantages of searching existing data for regularities before formulating theories are considered.

Neuronal correlates of visual time perception at brief timescales.

Successful interaction with the world depends on accurate perception of the timing of external events. Neurons at early stages of the primate visual system represent time-varying stimuli with high precision. However, it is unknown whether this temporal fidelity is maintained in the prefrontal cortex, where changes in neuronal activity generally correlate with changes in perception. One reason to suspect that it is not maintained is that humans experience surprisingly large fluctuations in the perception of time. To investigate the neuronal correlates of time perception, we recorded from neurons in the prefrontal cortex and midbrain of monkeys performing a temporal-discrimination task. Visual time intervals were presented at a timescale relevant to natural behavior (<500 ms). At this brief timescale, neuronal adaptation--time-dependent changes in the size of successive responses--occurs. We found that visual activity fluctuated with timing judgments in the prefrontal cortex but not in comparable midbrain areas. Surprisingly, only response strength, not timing, predicted task performance. Intervals perceived as longer were associated with larger visual responses and shorter intervals with smaller responses, matching the dynamics of adaptation. These results suggest that the magnitude of prefrontal activity may be read out to provide temporal information that contributes to judging the passage of time.

Biogeography in deep time - What do phylogenetics, geology, and paleoclimate tell us about early platyrrhine evolution?

Molecular data have converged on a consensus about the genus-level phylogeny of extant platyrrhine monkeys, but for most extinct taxa and certainly for those older than the Pleistocene we must rely upon morphological evidence from fossils. This raises the question as to how well anatomical data mirror molecular phylogenies and how best to deal with discrepancies between the molecular and morphological data as we seek to extend our phylogenies to the placement of fossil taxa. Here I present parsimony-based phylogenetic analyses of extant and fossil platyrrhines based on an anatomical dataset of 399 dental characters and osteological features of the cranium and postcranium. I sample 16 extant taxa (one from each platyrrhine genus) and 20 extinct taxa of platyrrhines. The tree structure is constrained with a "molecular scaffold" of extant species as implemented in maximum parsimony using PAUP with the molecular-based 'backbone' approach. The data set encompasses most of the known extinct species of platyrrhines, ranging in age from latest Oligocene (∼26 Ma) to the Recent. The tree is rooted with extant catarrhines, and Late Eocene and Early Oligocene African anthropoids. Among the more interesting patterns to emerge are: (1) known early platyrrhines from the Late Oligocene through Early Miocene (26-16.5Ma) represent only stem platyrrhine taxa; (2) representatives of the three living platyrrhine families first occur between 15.7 Ma and 13.5 Ma; and (3) recently extinct primates from the Greater Antilles (Cuba, Jamaica, Hispaniola) are sister to the clade of extant platyrrhines and may have diverged in the Early Miocene. It is probable that the crown platyrrhine clade did not originate before about 20-24 Ma, a conclusion consistent with the phylogenetic analysis of fossil taxa presented here and with recent molecular clock estimates. The following biogeographic scenario is consistent with the phylogenetic findings and climatic and geologic evidence: Tropical South America has been a center for platyrrhine diversification since platyrrhines arrived on the continent in the middle Cenozoic. Platyrrhines dispersed from tropical South America to Patagonia at ∼25-24 Ma via a "Paraná Portal" through eastern South America across a retreating Paranense Sea. Phylogenetic bracketing suggests Antillean primates arrived via a sweepstakes route or island chain from northern South America in the Early Miocene, not via a proposed land bridge or island chain (GAARlandia) in the Early Oligocene (∼34 Ma). Patagonian and Antillean platyrrhines went extinct without leaving living descendants, the former at the end of the Early Miocene and the latter within the past six thousand years. Molecular evidence suggests crown platyrrhines arrived in Central America by crossing an intermittent connection through the Isthmus of Panama at or after 3.5Ma. Any more ancient Central American primates, should they be discovered, are unlikely to have given rise to the extant Central American taxa in situ.

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

A generic time and space accurate numerical approach to closely coupled fluid-structure interaction problems

Fluid structure interaction, as applied to flexible structures, has wide application in diverse areas such as flutter in aircraft, flow in elastic pipes and blood vessels and extrusion of metals through dies. However a comprehensive computational model of these multi-physics phenomena is a considerable challenge. Until recently work in this area focused on one phenomenon and represented the behaviour of the other more simply even to the extent in metal forming, for example, that the deformation of the die is totally ignored. More recently, strategies for solving the full coupling between the fluid and soild mechanics behaviour have developed. Conventionally, the computational modelling of fluid structure interaction is problematical since computational fluid dynamics (CFD) is solved using finite volume (FV) methods and computational structural mechanics (CSM) is based entirely on finite element (FE) methods. In the past the concurrent, but rather disparate, development paths for the finite element and finite volume methods have resulted in numerical software tools for CFD and CSM that are different in almost every respect. Hence, progress is frustrated in modelling the emerging multi-physics problem of fluid structure interaction in a consistent manner. Unless the fluid-structure coupling is either one way, very weak or both, transferring and filtering data from one mesh and solution procedure to another may lead to significant problems in computational convergence. Using a novel three phase technique the full interaction between the fluid and the dynamic structural response are represented. The procedure is demonstrated on some challenging applications in complex three dimensional geometries involving aircraft flutter, metal forming and blood flow in arteries.

Addressing time intervals

One of the fundamental questions regarding the temporal ontology is what is time composed of. While the traditional time structure is based on a set of points, a notion that has been prevalently adopted in classical physics and mathematics, it has also been noticed that intervals have been widely adopted for expre~sion of common sense temporal knowledge, especially in the domain of artificial intelligence. However, there has been a longstanding debate on how intervals should be addressed, leading to two different approaches to the treatment of intervals. In the first, intervals are addressed as derived objects constructed from points, e.g., as sets of points, or as pairs of points. In the second, intervals are taken as primitive themselves. This article provides a critical examination of these two approaches. By means of proposing a definition of intervals in terms of points and types, we shall demonstrate that, while the two different approaches have been viewed as rivals in the literature, they are actually reducible to logically equivalent expressions under some requisite interpretations, and therefore they can also be viewed as allies.

Uniqueness criteria for continuous-time Markov chains with general transition structures

We derive necessary and sufficient conditions for the existence of bounded or summable solutions to systems of linear equations associated with Markov chains. This substantially extends a famous result of G. E. H. Reuter, which provides a convenient means of checking various uniqueness criteria for birth-death processes. Our result allows chains with much more general transition structures to be accommodated. One application is to give a new proof of an important result of M. F. Chen concerning upwardly skip-free processes. We then use our generalization of Reuter's lemma to prove new results for downwardly skip-free chains, such as the Markov branching process and several of its many generalizations. This permits us to establish uniqueness criteria for several models, including the general birth, death, and catastrophe process, extended branching processes, and asymptotic birth-death processes, the latter being neither upwardly skip-free nor downwardly skip-free.

Ontological considerations of time, meta-predicates and temporal propositions

A natural approach to representing and reasoning about temporal propositions (i.e., statements with time-dependent truth-values) is to associate them with time elements. In the literature, there are three choices regarding the primitive for the ontology of time: (1) instantaneous points, (2) durative intervals and (3) both points and intervals. Problems may arise when one conflates different views of temporal structure and questions whether some certain types of temporal propositions can be validly and meaningfully associated with different time elements. In this paper, we shall summarize an ontological glossary with respect to time elements, and diversify a wider range of meta-predicates for ascribing temporal propositions to time elements. Based on these, we shall also devise a versatile categorization of temporal propositions, which can subsume those representative categories proposed in the literature, including that of Vendler, of McDermott, of Allen, of Shoham, of Galton and of Terenziani and Torasso. It is demonstrated that the new categorization of propositions, together with the proposed range of meta-predicates, provides the expressive power for modeling some typical temporal terms/phenomena, such as starting-instant, stopping-instant, dividing-instant, instigation, termination and intermingling etc.

Collection and analysis of pre-evacuation time data collected from evacuation trials conducted in library facilities in Brazil

Two evacuation trials were conducted within Brazilian library facilities by FSEG staff in January 2005. These trials represent one of the first such trials conducted in Brazil. The purpose of these evacuation trials was to collect pre-evacuation time data from a population with a cultural background different to that found in western Europe. In total some 34 pre-evacuation times were collected from the experiments and these ranged from 5 to 98 seconds with a mean pre-evacuation time of 46.7 seconds