Understanding the segregation of cells is crucial to answer questions about tissue formation in embryos or tumor progression. Steinberg proposed that separation of cells can be compared to the separation of two liquids. Such a separation is well described by the Cahn-Hilliard (CH) equations and the segregation indices exhibit an algebraic decay with exponent 1/3 with respect to time. Similar exponents are also observed in cell-based models. However, the scaling behavior in these numerical models is usually only examined in the asymptotic regime and these models have not been directly applied to actual cell segregation data. In contrast, experimental data also reveals other scaling exponents and even slow logarithmic scaling laws. These discrepancies are commonly attributed to the effects of collective motion or velocity-dependent interactions. By calibrating a 2D cellular automaton (CA) model which efficiently implements a dynamic variant of the differential adhesion hypothesis to 2D experimental data from Méhes et al., we reproduce the biological cell segregation experiments with just adhesive forces. The segregation in the cellular automaton model follows a logarithmic scaling initially, which is in contrast to the proposed algebraic scaling with exponent 1/3. However, within the less than two orders of magnitudes in time which are observable in the experiments, a logarithmic scaling may appear as a pseudo-algebraic scaling. In particular, we demonstrate that the cellular automaton model can exhibit a range of exponents ≤1/3 for such a pseudo-algebraic scaling. Moreover, the time span of the experiment falls into the transitory regime of the cellular automaton rather than the asymptotic one. We additionally develop a method for the calibration of the 2D Cahn-Hilliard model and find a match with experimental data within the transitory regime of the Cahn-Hilliard model with exponent 1/4. On the one hand this demonstrates that the transitory behavior is relevant for the experiment rather than the asymptotic one. On the other hand this corroborates the ambiguity of the scaling behavior, when segregation processes can be only observed on short time spans.

Cancer development is a multistep process often starting with a single cell in which a number of epigenetic and genetic alterations have accumulated thus transforming it into a tumor cell. The progeny of such a single benign tumor cell expands in the tissue and can at some point progress to malignant tumor cells until a detectable tumor is formed. The dynamics from the early phase of a single cell to a detectable tumor with billions of tumor cells are complex and still not fully resolved, not even for the well-known prototype of multistage carcinogenesis, the adenoma-adenocarcinoma sequence of colorectal cancer. Mathematical models of such carcinogenesis are frequently tested and calibrated based on reported age-specific incidence rates of cancer, but they usually require calibration of four or more parameters due to the wide range of processes these models aim to reflect. We present a cell-based model, which focuses on the competition between wild-type and tumor cells in colonic crypts, with which we are able reproduce epidemiological incidence rates of colon cancer. Additionally, the fraction of cancerous tumors with precancerous lesions predicted by the model agree with clinical estimates. The correspondence between model and reported data suggests that the fate of tumor development is majorly determined by the early phase of tumor growth and progression long before a tumor becomes detectable. Due to the focus on the early phase of tumor development, the model has only a single fit parameter, the time scale set by an effective replacement rate of stem cells in the crypt. We find this effective rate to be considerable smaller than the actual replacement rate, which implies that the time scale is limited by the processes succeeding clonal conversion of crypts.

Sperm of marine invertebrates have to find eggs cells in the ocean. Turbulent flows mix sperm and egg cells up to the millimeter scale; below this, active swimming and chemotaxis become important. Previous work addressed either turbulent mixing or chemotaxis in still water. Here, we present a general theory of sperm chemotaxis inside the smallest eddies of turbulent flow, where signaling molecules released by egg cells are spread into thin concentration filaments. Sperm cells 'surf' along these filaments towards the egg. External flows make filaments longer, but also thinner. These opposing effects set an optimal flow strength. The optimum predicted by our theory matches flow measurements in shallow coastal waters. Our theory quantitatively agrees with two previous fertilization experiments in Taylor-Couette chambers and provides a mechanistic understanding of these early experiments. 'Surfing along concentration filaments' could be a paradigm for navigation in complex environments in the presence of turbulent flow.

To navigate their surroundings, cells rely on sensory input that is corrupted by noise. In cells performing chemotaxis, such noise arises from the stochastic binding of signalling molecules at low chemoattractant concentrations. We reveal a fundamental relationship between the speed of chemotactic steering and the strength of directional fluctuations that result from the amplification of noise in a chemical input signal. This relation implies a trade-off between steering that is slow and reliable, and steering that is fast but less reliable. We show that dynamic switching between these two modes of steering can substantially increase the probability to find a target, such as an egg to be found by sperm cells. This decision making confers no advantage in the absence of noise, but is beneficial when chemical signals are detectable, yet characterized by low signal-to-noise ratios. The latter applies at intermediate distances from a target, where signalling molecules are diluted, thus defining a 'noise zone' that cells have to cross. Our results explain decision making observed in recent experiments on sea urchin sperm chemotaxis. More generally, our theory demonstrates how decision making enables chemotactic agents to cope with high levels of noise in gradient sensing by dynamically adjusting the persistence length of a biased random walk.

Software-as-a-Service (SaaS) is a delivery model whose basic idea is to provide applications to the customer on demand over the Internet. Thereby, SaaS promotes multi-tenancy as a tool to exploit economies of scale. A major drawback of SaaS is the customers' hesitation of sharing infrastructure, application code, or data with other tenants. The common way in research to address this problem is to create new approaches to implement and improve the tenants' isolation on a commonly used instance. Our approach, called mixed-tenancy approach, tackles this hesitation differently. It allows customers to choose with whom they want to share the instances of an application as well as the underlying infrastructure, and a valid deployment is computed in accordance with customer's constraints. This paper addresses the major algorithmic problem related to the mixed-tenancy approach. In particular, we analyze the problem of computing valid and optimal deployments. In doing so, we provide a theoretical analysis of the complexity of this problem, proposing several heuristics and discussing their quality.

We consider concept learning from examples. The learner receives - step by step - larger and larger initial segments of a sequence of examples describing an unknown target concept, processes these examples, and computes hypotheses. The learner is successful, if its hypotheses stabilize on a correct representation of the target concept. The underlying model is called identification in the limit. The present study concerns different versions of incremental learning in the limit. In contrast to the general case, now the learner has only limited access to the examples provided so far. In the special case of iterative learning, the learner builds its new hypotheses just on the basis of the current hypothesis and the next example, without having access to any of the other examples presented so far. In the case of bounded example-memory learning, the learner may in addition memorize up to an a priori fixed number of examples already presented. Formal studies have shown that restricting the accessibility of the input data results in a loss of learning power, i.e. there are concept classes learnable in the limit, but not identifiable by any incremental learner at all. The present analysis aims at illustrating this phenomenon and giving insights into the structure of concept classes incremental learners can cope with. Examples of identifiable and non-identifiable classes are given; different learning models are compared to one another with respect to the competence of the corresponding learners.

In the problem area of evaluating complex software systems, there are two distinguished areas of research, development, and application identified by the two buzzwords validation and verification, respectively. From the perspective adopted by the authors, verification is usually more formally based and, thus, can be supported by formal reasoning tools like theorem provers, for instance. The scope of verification approaches is limited by the difficulty of finding a sufficiently complete formalization to build upon. In paramount realistic problem domains, validation seems to be more appropriate, although it is less stringent in character and, therefore, validation results are often less definite. The aim of this paper is to exemplify a validation approach based on a clear and thoroughly formal theory. In this way, validation and verification should be brought closer to each other. To allow for precise and sufficiently clear results, the authors have selected the application domain of algorithms and systems for learning formal languages. By means of the validation toolkit TIC, some series of validation experiments have been performed. The results are presented for the sake of illustrating the underlying formal concepts in use. Comparing the validity of one learning approach to the invalidity of another one can be seen as an interesting result in its own right.

In the present paper we study the learnability of the enumerable families L of uniformly recursive languages in dependence on the number of allowed mind changes, i.e., with respect to a well-studied measure of efficiency. We distinguish between exact learnability ( L has to be learnt w.r.t. the hypothesis space L itself), class preserving learning ( L has to be inferred w.r.t. some hypothesis space G having the same range as L ), and class comprising inference ( L has to be inferred w.r.t. some hypothesis space G that has a range including range ( L )) as well as between learning from positive and negative examples. The measure of efficiency is applied to prove the superiority of class comprising learning algorithms over class preserving learning which itself turns out to be superior to exact learning algorithms. In particular, we considerably improve results obtained previously and show that a suitable choice of the hypothesis space may result in a considerable speed up of learning algorithms, even if instead of positive and negative data only positive examples will be presented. Furthermore, we completely separate all modes of learning with a bounded number of mind changes from class preserving learning that avoids overgeneralization.

The present paper deals with monotonic and dual monotonic language learning from positive and negative examples. The three notions of monotonicity reflect different formalizations of the requirement that the learner has to produce always better and better generalizations when fed more and more data on the concept to be learnt. The three versions of dual monotonicity describe the concept that the inference device has to produce exclusively specializations that fit better and better to the target language. We characterize strong-monotonic, monotonic, weak-monotonic, dual strong-monotonic, dual monotonic and dual weak-monotonic as well as finite language learning from positive and negative data in terms of recursively generable finite sets. Thereby, we elaborate a unifying approach to monotonic language learning by showing that there is exactly one learning algorithm which can perform any monotonic inference task.

We study the learnability of indexed families L = (L j ) j2IN of uniformly recursive languages under certain monotonicity constraints. Thereby we distinguish between exact learnability (L has to be learnt with respect to the space L of hypotheses), class preserving learning (L has to be inferred with respect to some space G of hypotheses having the same range as L), and class comprising inference (L has to be learnt with respect to some space G of hypotheses that has a range comprising range(L)). In particular, it is proved that, whenever monotonicity requirements are involved, then exact learning is almost always weaker than class preserving inference which itself turns out to be almost always weaker than class comprising learning. Next, we provide additionally insight into the problem under what conditions, for example, exact and class preserving learning procedures are of equal power. Finally, we deal with the question what kind of languages has to be added to the space of hypo...

The present paper deals with strong-monotonic, monotonic and weak-monotonic language learning from positive data as well as from positive and negative examples. The three notions of monotonicity reflect different formalizations of the requirement that the learner has to produce always better and better generalizations when fed more and more data on the concept to be learnt. We characterize strong-monotonic, monotonic, weak-monotonic and finite language learning from positive data in terms of recursively generable finite sets, thereby solving a problem of Angluin (1980). Moreover, we study monotonic inference with iteratively working learning devices which are of special interest in applications. In particular, it is proved that strong-monotonic inference can be performed with iteratively learning devices without limiting the inference capabilities, while monotonic and weak-monotonic inference cannot.