Search

Anomaly detection is essential in many application domains, such as cyber security, law enforcement, medicine, and fraud protection. However, the decision-making of current deep learning approaches is notoriously hard to understand, which often limits their practical applicability. To overcome this limitation, we propose a framework for learning inherently interpretable anomaly detectors from sequential data. More specifically, we consider the task of learning a deterministic finite automaton (DFA) from a given multi-set of unlabeled sequences. We show that this problem is computationally hard and develop two learning algorithms based on constraint optimization. Moreover, we introduce novel regularization schemes for our optimization problems that improve the overall interpretability of our DFAs. Using a prototype implementation, we demonstrate that our approach shows promising results in terms of accuracy and F1 score.

We introduce stochastic decision Petri nets (SDPNs), which are a form of stochastic Petri nets equipped with rewards and a control mechanism via the deactivation of controllable transitions. Such nets can be translated into Markov decision processes (MDPs), potentially leading to a combinatorial explosion in the number of states due to concurrency. Hence we restrict ourselves to instances where nets are either safe, free-choice and acyclic nets (SAFC nets) or even occurrence nets and policies are defined by a constant deactivation pattern. We obtain complexity-theoretic results for such cases via a close connection to Bayesian networks, in particular we show that for SAFC nets the question whether there is a policy guaranteeing a reward above a certain threshold is $\mathsf{NP}^\mathsf{PP}$-complete. We also introduce a partial-order procedure which uses an SMT solver to address this problem.

1. Dispersal is a critical process that shapes the structure of wild animal populations. In species that form multi-level societies, natal dispersal might be social (associating with a different social community while remaining near the natal area), spatial (moving away from the natal area while continuing to associate with the same community) or both social and spatial (associating with a different community and moving away from the natal area).2. For such species, classical spatial measures of dispersal, such as distance moved, might not capture social dispersal.3. We examined dispersal outcomes for 67 male and 70 female giraffe calves over 7 years in a large, unfenced, ecologically heterogeneous landscape. We tested predictions about the influence of sex, food availability, low- and high-impact human settlements, and local giraffe population density on social or spatial dispersal, dispersal distance, and age of dispersal.4. We found that dispersal is sex-specific, with females being predominately philopatric. When dispersing, both sexes did so at a mean of 4 years of age. Most (69% of total) young males dispersed, with 84% of male dispersers associating with a different adult female social community than that of their mother, but one in four of these dispersers remained spatially near to their natal area. For adolescent males that dispersed socially but not spatially, overlapping female social communities may represent a potential pool of unrelated mating partners without the risks of travelling to unfamiliar areas. Just 26% of young females dispersed and half of these continued to associate with the adult female social community into which they were born, confirming the importance of maintaining ties among females from calf to adulthood. Furthermore, individuals born farther from high-impact human settlements were more likely to spatially or socially-and-spatially disperse, move greater distances from their natal areas, and disperse at a younger age.5. Our study highlights the potential importance of social structure in dispersal decisions, and of tracking social structure when studying dispersal in multi-level societies, as effective dispersal can be attained without large-scale spatial displacements. published

The framework of graded semantics uses graded monads to capture behavioural equivalences of varying granularity, for example as found on the linear-time/branching-time spectrum, over general system types. We describe a generic Spoiler-Duplicator game for graded semantics that is extracted from the given graded monad, and may be seen as playing out an equational proof; instances include standard pebble games for simulation and bisimulation as well as games for trace-like equivalences and coalgebraic behavioural equivalence. Considerations on an infinite variant of such games lead to a novel notion of infinite-depth graded semantics. Under reasonable restrictions, the infinite-depth graded semantics associated to a given graded equivalence can be characterized in terms of a determinization construction for coalgebras under the equivalence at hand.

Populations are typically defined as spatially contiguous sets of individuals, but large populations of social species can be composed of discrete social communities that often overlap in space. Masai giraffes (Giraffa camelopardalis tippelskirchi) of Tanzania live in distinct social subpopulations that overlap spatially, enabling us to simultaneously explore environmental and social factors correlated with demographic variation in a metapopulation of >1,400 adult females and calves. We considered statistically distinct communities in the social network as subpopulations and tested for variation among the 10 subpopulations in adult female survival, calf survival, and reproductive rate (calf‐to‐adult female ratio). We then related variation in demographic rates among subpopulations to differences in vegetation, soil type, proximity to 2 types of human settlements, local giraffe population density, and social metrics of relationship strength and exclusivity among adult females. We did not find any among‐subpopulation effects on adult female survival, suggesting adult female survival is buffered against environmental heterogeneity among subpopulations. Variation in calf demographic rates among subpopulations were correlated with vegetation, soils, anthropogenic factors, and giraffe population density but not with adult female relationship metrics, despite substantial spatial overlap. Subpopulations with more dense bushlands in their ranges had lower calf survival probabilities, and those closer to human settlements had higher reproductive rates, possibly because of spatial gradients in natural predation. Reproductive rates were higher in subpopulations with more volcanic soils, and calf survival probabilities were greater in subpopulations with higher local adult female densities, possibly related to higher‐quality habitat associated with fertile soils or lower predation risk, or to greater competitive ability. The variation in fitness among subpopulations suggests that giraffes do not move unhindered among resource patches to equalize reproductive success, as expected according to an ideal free distribution. The differences in calf survival and reproductive rates could rather indicate intercommunity differences in competitive ability, perception, learning, or experience. Our approach of comparing demography among spatially overlapping yet distinct socially defined subpopulations provides a biologically meaningful way to quantify environmental and social factors influencing fine‐scale demographic variation for social species. published

We consider probabilistic systems with hidden state and unobservable transitions, an extension of Hidden Markov Models (HMMs) that in particular admits unobservable {\epsilon}-transitions (also called null transitions), allowing state changes of which the observer is unaware. Due to the presence of {\epsilon}-loops this additional feature complicates the theory and requires to carefully set up the corresponding probability space and random variables. In particular we present an algorithm for determining the most probable explanation given an observation (a generalization of the Viterbi algorithm for HMMs) and a method for parameter learning that adapts the probabilities of a given model based on an observation (a generalization of the Baum-Welch algorithm). The latter algorithm guarantees that the given observation has a higher (or equal) probability after adjustment of the parameters and its correctness can be derived directly from the so-called EM algorithm.

We introduce a general and compositional, yet simple, framework that allows to derive soundness and expressiveness results for modal logics characterizing behavioural equivalences or metrics (also known as Hennessy-Milner theorems). It is based on Galois connections between sets of (real-valued) predicates on the one hand and equivalence relations/metrics on the other hand and covers a part of the linear-time-branching-time spectrum, both for the qualitative case (behavioural equivalences) and the quantitative case (behavioural metrics). We derive behaviour functions from a given logic and give a condition, called compatibility, that characterizes under which conditions a logically induced equivalence/metric is induced by a fixpoint equation. In particular, this framework allows to derive a new fixpoint characterization of directed trace metrics., LIPIcs, Vol. 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), pages 12:1-12:18

Response to lithium varies widely between individuals with bipolar disorder (BD). Polygenic risk scores (PRSs) can uncover pharmacogenomics effects and may help predict drug response. Patients (N = 2,510) with BD were assessed for long-term lithium response in the Consortium on Lithium Genetics using the Retrospective Criteria of Long-Term Treatment Response in Research Subjects with Bipolar Disorder score. PRSs for attention-deficit/hyperactivity disorder (ADHD), major depressive disorder (MDD), and schizophrenia (SCZ) were computed using lassosum and in a model including all three PRSs and other covariates, and the PRS of ADHD (β = -0.14; 95% confidence interval [CI]: -0.24 to -0.03; p value = 0.010) and MDD (β = -0.16; 95% CI: -0.27 to -0.04; p value = 0.005) predicted worse quantitative lithium response. A higher SCZ PRS was associated with higher rates of medication nonadherence (OR = 1.61; 95% CI: 1.34-1.93; p value = 2e-7). This study indicates that genetic risk for ADHD and depression may influence lithium treatment response. Interestingly, a higher SCZ PRS was associated with poor adherence, which can negatively impact treatment response. Incorporating genetic risk of ADHD, depression, and SCZ in combination with clinical risk may lead to better clinical care for patients with BD.

Genealogical relationships are fundamental components of genetic studies. However, it is often challenging to infer correct and complete pedigrees even when genome-wide information is available. For example, inbreeding can obfuscate genetic differences between individuals, making it difficult to even distinguish first-degree relatives such as parent-offspring from full siblings. Similarly, genotyping errors can interfere with the detection of genetic similarity between parents and their offspring. Inbreeding is common in natural, domesticated, and experimental populations and genotyping of these populations often has more errors than in human datasets, so efficient methods for building pedigrees under these conditions are necessary. Here, we present a new method for parent-offspring inference in inbred pedigrees called SPORE (Specific Parent-Offspring Relationship Estimation). SPORE is vastly superior to existing pedigree-inference methods at detecting parent-offspring relationships, in particular when inbreeding is high or in the presence of genotyping errors, or both. SPORE therefore fills an important void in the arsenal of pedigree inference tools.Author SummaryKnowing the genealogical relationships among individuals is critical for genetic analyses, such as for identifying the mutations that cause diseases or that contribute to valuable agricultural traits such as milk production. Although many tools exist for establishing pedigrees using genetic information, these tools fail when individuals are highly inbred, such as in domesticated animals, or in groups of people in which consanguineous matings are common. Furthermore, existing tools do not work well when genetic information has errors at levels observed in modern datasets. Here, we present a novel approach to solve these problems. Our method is significantly more accurate than existing tools and more tolerant of errors in the genetic data. We expect that our method, which is simple to use and computationally efficient, will be a useful tool in a diversity of settings, from the studies of human and natural populations, to agricultural and experimental settings.

Lithium is the gold standard therapy for Bipolar Disorder (BD) but its effectiveness differs widely between individuals. The molecular mechanisms underlying treatment response heterogeneity are not well understood, and personalized treatment in BD remains elusive. Genetic analyses of the lithium treatment response phenotype may generate novel molecular insights into lithium's therapeutic mechanisms and lead to testable hypotheses to improve BD management and outcomes. We used fixed effect meta-analysis techniques to develop meta-analytic polygenic risk scores (MET-PRS) from combinations of highly correlated psychiatric traits, namely schizophrenia (SCZ), major depression (MD) and bipolar disorder (BD). We compared the effects of cross-disorder MET-PRS and single genetic trait PRS on lithium response. For the PRS analyses, we included clinical data on lithium treatment response and genetic information for n = 2283 BD cases from the International Consortium on Lithium Genetics (ConLi+Gen; www.ConLiGen.org ). Higher SCZ and MD PRSs were associated with poorer lithium treatment response whereas BD-PRS had no association with treatment outcome. The combined MET2-PRS comprising of SCZ and MD variants (MET2-PRS) and a model using SCZ and MD-PRS sequentially improved response prediction, compared to single-disorder PRS or to a combined score using all three traits (MET3-PRS). Patients in the highest decile for MET2-PRS loading had 2.5 times higher odds of being classified as poor responders than patients with the lowest decile MET2-PRS scores. An exploratory functional pathway analysis of top MET2-PRS variants was conducted. Findings may inform the development of future testing strategies for personalized lithium prescribing in BD.

Whether females breed in their natal group is an important factor in the evolution of extended families in animal sociality. Breeding in natal groups comes with clear costs and benefits, depending on size of the group and presence of older relatives, including mothers. Studying individual decisions about whether to stay or leave can provide insight into the mechanisms and trade-offs governing the formation and structure of family groups. We investigated the family dynamics of a large population of free-ranging commensal house mice. Using dynamic community detection on long term datasets, we determined which females first bred in their natal group. We then looked at how this influenced breeding success. We found most females (77%) exhibited strong philopatry, breeding in their natal groups. Whether a female bred elsewhere was only predictable when natal groups were extremely small and related or large and unrelated. Despite this preference, breeding elsewhere made no difference in how quickly and successfully a female bred. However, presence of their mother did lead females to breed sooner when born during high breeding activity, when competition over reproduction is high. Based on these results, potential loss of fitness does not seem to be the main driver of philopatry in female house mice. The effect of the presence of mothers may indicate retaining prior social connections is an important benefit of breeding in the natal group. Mothers providing benefits also suggests lack of conflict between generations, which is likely an important attribute in the development of extended family groups.Lay summaryWhether animals breed in the group they are born in influences how they form extended family groups. Whether females stay will depend on properties such as presence of older relatives, including mothers. Using long-term wild mouse data, we track groups and which group females bred in. Most stayed, but leaving didn’t reduce breeding success. Presence of mother, who generally stayed, did lead to earlier breeding. This might be a key advantage to remaining to breed.

This paper exploits extended Bayesian networks for uncertainty reasoning on Petri nets, where firing of transitions is probabilistic. In particular, Bayesian networks are used as symbolic representations of probability distributions, modelling the observer’s knowledge about the tokens in the net. The observer can study the net by monitoring successful and failed steps. An update mechanism for Bayesian nets is enabled by relaxing some of their restrictions, leading to modular Bayesian nets that can conveniently be represented and modified. As for every symbolic representation, the question is how to derive information - in this case marginal probability distributions - from a modular Bayesian net. We show how to do this by generalizing the known method of variable elimination. The approach is illustrated by examples about the spreading of diseases (SIR model) and information diffusion in social networks. We have implemented our approach and provide runtime results., LIPIcs, Vol. 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), pages 38:1-38:17

Additional figures and tables

Natural disasters can cause rapid demographic changes which disturb the social structure of a population as individuals may lose connections. These changes also have indirect effects as survivors alter their within-group connections or move between groups. As group membership and network position may influence individual fitness, indirect effects may affect how individuals and populations recover from catastrophic events. Here we study changes in the social structure after a large predation event in a population of wild house mice (Mus musculus domesticus), where a third of adults were lost. Using social network analysis, we examine how heterogeneity in sociality results in varied responses to losing connections. We then investigate how these differences influence the overall network structure. An individual's reaction to losing associates depended on its sociality prior to the event. Those that were less social before formed more weak connections afterwards, while more social individuals reduced the number of survivors they associated with. Otherwise, the number and size of social groups were highly robust. This indicates that social preferences can drive how individuals adjust their social behaviour after catastrophic turnover events, despite the population's resilience in social structure.

Not only males but also females compete over reproduction. In a population of free-living house mice (Mus musculus domesticus), we analyzed how (metabolic) costs of aggressive interactions (reflected in fresh wounds and long-term corticosterone concentrations in hair) are predicted by individual reproductive physiology and reproductive success in males and females. Over eight years, we studied wounds and reproduction of more than 2800 adults under naturally varying environmental conditions and analyzed steroid hormones from more than 1000 hair samples. Hair corticosterone were higher and wounds more frequent in males than females. In males, wound occurrence increased with increasing breeding activity in the population, without affecting hair corticosterone levels. Unexpectedly, individual male reproductive success did not predict wounds, while hair corticosterone increased with increasing levels of hair testosterone and reproductive success. High corticosterone in hair of males might therefore reflect metabolic costs of fighting over reproduction. In females, hair corticosterone was generally lower than in males and high levels did not impede pregnancy. Reproductive investment (reflected in hair progesterone) was dissociated from reproductive success. Occasional wounds in females indicated individuals without recent reproductive success and revealed reproductive competition, presumably driven by instability in the social environment. In both sexes, corticosterone increased with age, but there was no evidence that received overt aggression, as indicated by wounds or elevated corticosterone, suppressed reproductive physiology. Our results diverge from laboratory findings and emphasize the need to also study animals in their natural environment in order to understand the complexity of their behavioral physiology.

Bipolar disorder (BD) is a common, highly heritable neuropsychiatric disease characterized by recurrent episodes of mania and depression. Lithium is the best-established long-term treatment for BD, even though individual response is highly variable. Evidence suggests that some of this variability has a genetic basis. This is supported by the largest genome-wide association study (GWAS) of lithium response to date conducted by the International Consortium on Lithium Genetics (ConLiGen). Recently, we performed the first genome-wide analysis of the involvement of miRNAs in BD and identified nine BD-associated miRNAs. However, it is unknown whether these miRNAs are also associated with lithium response in BD. In the present study, we therefore tested whether common variants at these nine candidate miRNAs contribute to the variance in lithium response in BD. Furthermore, we systematically analyzed whether any other miRNA in the genome is implicated in the response to lithium. For this purpose, we performed gene-based tests for all known miRNA coding genes in the ConLiGen GWAS dataset (n = 2,563 patients) using a set-based testing approach adapted from the versatile gene-based test for GWAS (VEGAS2). In the candidate approach, miR-499a showed a nominally significant association with lithium response, providing some evidence for involvement in both development and treatment of BD. In the genome-wide miRNA analysis, 71 miRNAs showed nominally significant associations with the dichotomous phenotype and 106 with the continuous trait for treatment response. A total of 15 miRNAs revealed nominal significance in both phenotypes with miR-633 showing the strongest association with the continuous trait (p = 9.80E-04) and miR-607 with the dichotomous phenotype (p = 5.79E-04). No association between miRNAs and treatment response to lithium in BD in either of the tested conditions withstood multiple testing correction. Given the limited power of our study, the investigation of miRNAs in larger GWAS samples of BD and lithium response is warranted.

Supplemental material, 2018_Supplement_table_III_ for Impulsivity predicts illness severity in long-term course of bipolar disorder: A prospective approach by Jonas Rote, Alice-Mai-Ly Dingelstadt, Annette Aigner, Michael Bauer, Jana Fiebig, Barbara König, Johanna Kunze, Steffi Pfeiffer, Andrea Pfennig, Esther Quinlivan, Christian Simhandl and Thomas J Stamm in Australian & New Zealand Journal of Psychiatry

In probabilistic transition systems, behavioural metrics provide a more fine-grained and stable measure of system equivalence than crisp notions of bisimilarity. They correlate strongly to quantitative probabilistic logics, and in fact the distance induced by a probabilistic modal logic taking values in the real unit interval has been shown to coincide with behavioural distance. For probabilistic systems, probabilistic modal logic thus plays an analogous role to that of Hennessy-Milner logic on classical labelled transition systems. In the quantitative setting, invariance of modal logic under bisimilarity becomes non-expansivity of formula evaluation w.r.t. behavioural distance. In the present paper, we provide a characterization of the expressive power of probabilistic modal logic based on this observation: We prove a probabilistic analogue of the classical van Benthem theorem, which states that modal logic is precisely the bisimulation-invariant fragment of first-order logic. Specifically, we show that quantitative probabilistic modal logic lies dense in the bisimulation-invariant fragment, in the indicated sense of non-expansive formula evaluation, of quantitative probabilistic first-order logic; more precisely, bisimulation-invariant first-order formulas are approximable by modal formulas of bounded rank. For a description logic perspective on the same result, see arXiv:1906.00784.

Up-to techniques are a well-known method for enhancing coinductive proofs of behavioural equivalences. We introduce up-to techniques for behavioural metrics between systems modelled as coalgebras and we provide abstract results to prove their oundness in a compositional way. In order to obtain a general framework, we need a systematic way to lift functors: we show that the Wasserstein lifting of a functor, introduced in a previous work, corresponds to a change of base in a fibrational sense. This observation enables us to reuse existing results about soundness of up-to techniques in a fibrational setting. We focus on the fibrations of predicates and relations valued in a quantale, for which pseudo-metric spaces are an example. To illustrate our approach we provide an example on distances between regular languages., Comment: long version of our CONCUR 2018 paper

Parental care is associated with costs. Communal offspring care in species with altricial young may reduce the costs for a parent but it comes with a risk of exploitation jeopardizing the evolution of stable cooperation. Female house mice can either rear their young alone or communally with one or several other females. In the latter case females pool litters and do not discriminate in their maternal behaviour between their own and alien offspring. Differences in litter size between females or differences in the amount of investment they provide might therefore result in one female exploiting another. To analyse the potential for conflict during cooperation we compared under laboratory conditions the maternal investment (milk quantity and quality at peak lactation when a female's own offspring were 15 days old) of wild bred females nursing communally with one partner with that of females nursing solitarily. To increase the probability of asymmetry in litter sizes between communally nursing females we used a genetic tool to reduce in utero litter size for one of the two partners. Communally nursing females invested according to the total number of pups in the joint nest and not according to their own litter size making them vulnerable to exploitation. Females that gave birth to the smaller litter consequently overinvested; they had a higher investment per weaned offspring than females that gave birth to larger litters in communal nests or solitarily nursing females. Communal nursing in house mice thus represents a public good situation. Both partners invest according to the combined litter size but they differ in the benefit they gain which is the number of weaned offspring.

Bipolar disorder (BD) is a genetically complex mental illness characterized by severe oscillations of mood and behaviour. Genome-wide association studies (GWAS) have identified several risk loci that together account for a small portion of the heritability. To identify additional risk loci, we performed a two-stage meta-analysis of >9 million genetic variants in 9,784 bipolar disorder patients and 30,471 controls, the largest GWAS of BD to date. In this study, to increase power we used ∼2,000 lithium-treated cases with a long-term diagnosis of BD from the Consortium on Lithium Genetics, excess controls, and analytic methods optimized for markers on the X-chromosome. In addition to four known loci, results revealed genome-wide significant associations at two novel loci: an intergenic region on 9p21.3 (rs12553324, P = 5.87 × 10 - 9; odds ratio (OR) = 1.12) and markers within ERBB2 (rs2517959, P = 4.53 × 10 - 9; OR = 1.13). No significant X-chromosome associations were detected and X-linked markers explained very little BD heritability. The results add to a growing list of common autosomal variants involved in BD and illustrate the power of comparing well-characterized cases to an excess of controls in GWAS.

This tutorial paints a high-level picture of the concepts involved in verification of graph transformation systems. We distinguish three fundamentally different application scenarios for graph rewriting: (1) as grammars (in which case we are interested in the language, or set, of terminal graphs for a fixed start graph); (2) as production systems (in which case we are interested in the relation between start and terminal graphs); or (3) as behavioural specifications (in which case we are interested in the transition system as a whole). We then list some types of questions one might want to answer through verification: confluence and termination, reachability, temporal properties, or contractual properties. Finally, we list some techniques that can help in providing answers: model checking, unfolding, assertional reasoning, and abstraction.

BackgroundLithium is a first-line treatment in bipolar disorder, but individual response is variable. Previous studies have suggested that lithium response is a heritable trait. However, no genetic markers of treatment response have been reproducibly identified.MethodsHere, we report the results of a genome-wide association study of lithium response in 2563 patients collected by 22 participating sites from the International Consortium on Lithium Genetics (ConLiGen). Data from common single nucleotide polymorphisms (SNPs) were tested for association with categorical and continuous ratings of lithium response. Lithium response was measured using a well established scale (Alda scale). Genotyped SNPs were used to generate data at more than 6 million sites, using standard genomic imputation methods. Traits were regressed against genotype dosage. Results were combined across two batches by meta-analysis.FindingsA single locus of four linked SNPs on chromosome 21 met genome-wide significance criteria for association with lithium response (rs79663003, p=1·37 × 10(-8); rs78015114, p=1·31 × 10(-8); rs74795342, p=3·31 × 10(-9); and rs75222709, p=3·50 × 10(-9)). In an independent, prospective study of 73 patients treated with lithium monotherapy for a period of up to 2 years, carriers of the response-associated alleles had a significantly lower rate of relapse than carriers of the alternate alleles (p=0·03268, hazard ratio 3·8, 95% CI 1·1-13·0).InterpretationThe response-associated region contains two genes for long, non-coding RNAs (lncRNAs), AL157359.3 and AL157359.4. LncRNAs are increasingly appreciated as important regulators of gene expression, particularly in the CNS. Confirmed biomarkers of lithium response would constitute an important step forward in the clinical management of bipolar disorder. Further studies are needed to establish the biological context and potential clinical utility of these findings.FundingDeutsche Forschungsgemeinschaft, National Institute of Mental Health Intramural Research Program.

International audience; We investigate the possibility of deriving metric trace semantics in a coalgebraic framework.First, we generalize a technique for systematically lifting functors from the category Set ofsets to the category PMet of pseudometric spaces, by identifying conditions under whichalso natural transformations, monads and distributive laws can be lifted. By exploiting somerecent work on an abstract determinization, these results enable the derivation of trace metricsstarting from coalgebras in Set. More precisely, for a coalgebra on Set we determinize it,thus obtaining a coalgebra in the Eilenberg-Moore category of a monad. When the monadcan be lifted to PMet, we can equip the final coalgebra with a behavioral distance. The tracedistance between two states of the original coalgebra is the distance between their images in thedeterminized coalgebra through the unit of the monad. We show how our framework appliesto nondeterministic automata and probabilistic automata.

We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting instead of string rewriting and by generalizing to ordered semirings. In this way we obtain a framework which includes the tropical and arctic type graphs introduced in a previous paper and a new variant of arithmetic type graphs. These type graphs can be used to assign weights to graphs and to show that these weights decrease in every rewriting step in order to prove termination. We present an example involving counters and discuss the implementation in the tool Grez.

Graph transformation systems (GTSs) can be seen as wellstructured transition systems (WSTSs), thus obtaining decidability results for certain classes of GTSs. In earlier work it was shown that wellstructuredness can be obtained using the minor ordering as a well-quasiorder. In this paper we extend this idea to obtain a general framework in which several types of GTSs can be seen as (restricted) WSTSs. We instantiate this framework with the subgraph ordering and the induced subgraph ordering and apply it to analyse a simple access rights management system., Comment: Extended version (including proofs) of a paper accepted at CONCUR 2014

We investigate to what extent the interaction dynamics of a population of wild house mouse (Mus musculus domesticus) in their environment can be explained by a simple stochastic model. We use a Markov chain model to describe the transitions of mice in a discrete space of nestboxes, and implement a multi-agent simulation of the model. We find that some important features of our behavioural dataset can be reproduced using this simplified stochastic representation, and discuss the improvements that could be made to our model in order to increase the accuracy of its predictions. Our findings have implications for the understanding of the complexity underlying social behaviour in the animal kingdom and the cognitive requirements of such behaviour., Comment: 12 pages, 5 figures, 2 tables. Originally published in the Proceedings of the European Conference on Complex Systems 2010 (ECCS'10), Lisbon, September 13-17, 2010

Model transformation is a prime technique in modern, model-driven software design. One of the most challenging issues is to show that the semantics of the models is not affected by the transformation. So far, there is hardly any research into this issue, in particular in those cases where the source and target languages are different. In this paper, we are using two different state-of-the-art proof techniques (explicit bisimulation construction versus borrowed contexts) to show bisimilarity preservation of a given model transformation between two simple (self-defined) languages, both of which are equipped with a graph transformation-based operational semantics. The contrast between these proof techniques is interesting because they are based on different model transformation strategies: triple graph grammars versus in situ transformation. We proceed to compare the proofs and discuss scalability to a more realistic setting.

The physiological basis for population differentiation of dispersal timing during individual development in male wild house mice is still unknown. As major urinary proteins (MUPs) are known to convey information about competitive ability in male mice, we examined individual MUP profiles defined by isoelectric-focusing (IEF) patterns in relation to developmental timing of dispersive motivation. As an experimental paradigm marking the development of the dispersal propensity, we used agonistic onset between litter mate brothers when kept in pairs under laboratory conditions. Agonistic onset is known to reflect the initiation of dispersive motivation. Hence, we compared individual MUP IEF patterns between fraternal pairs that did or did not develop agonistic relationships before the age of 2months. Urine was collected on the day of weaning and at the beginning of adulthood. We investigated whether there was a significant co-occurrence of particular MUP IEF patterns with the agonistic onset in male mice. We assumed that, based on this co-occurrence, particular MUP IEF patterns and/or a particular dynamic of MUP IEF expression from weaning to adulthood may be considered a physiological predictor of a specific behavioral strategy in male mice (i.e. submissive-philopatric or agonistic-dispersive strategy). We found that agonistic males expressed more MUP IEF bands than amicable ones at weaning, but these differences disappeared later on. The presence of two particular IEF bands at weaning was significantly associated with early agonistic onset. Our study suggests that MUPs could have a predictive value for the onset of aggressive behavior and dispersal tendency in male wild house mice

Dispersal propensity, reflecting one of the most decisive mammalian life history traits, has been suggested to vary heritably and to locally adapt to prevailing dispersal conditions in wild house mouse populations. Because individual dispersal propensity highly significantly covaries with the developmental timing of the onset of agonistic interactions between littermate brothers, we used agonistic onset as an endophenotype to explore the potential genetic basis of dispersal-related behavioral variation in male house mice. We found significant covariation of microsatellite marker compositions with the probability of fraternal pairs to exhibit agonistic relationships before the age of 2months. In particular, the presence of two alleles associated with a serotonin transporter protein gene (Slc6a4) and a testosterone dehydrogenase gene (Cyp3a11), respectively, strongly covaried with the probability of early agonistic onset. These results are congruent with recent findings of microsatellite length polymorphisms marking regulatory variation of gene expression that is relevant for social behavior, including dispersal propensity development, in other mammals. Genetic variability for ontogenetic timing of agonistic onset would be in agreement with genotypic differentiation of the dispersive behavioral syndrome in natural populations that could lead to local adaptation

We describe the tool Augur for the verification of systems with dynamically evolving structure specified by graph transformation. After giving a short introduction to graph transformation systems (GTSs), we describe the verification techniques used by the tool, namely the approximation of GTSs by Petri nets. Instead of verifying properties directly in the original system, they can be checked on the approximating Petri net. We explain the workings of the different modules of the Augur tool using two small case studies where we model reconfigurable networks and mobile processes. Appeared in The Formal Specification Column

We verify a mutual exclusion protocol with dynamic process creation based on token passing. The protocol is specified using object-based graph grammars. We introduce the protocol and show how the mutual exclusion property and other properties can be verified using the tool Augur, a verification tool for graph transformation systems based on an approximated unfolding technique.

We invite the reader to join our quest for the largest subsemigroup of a transformation monoid on~$n$ elements generated by two transformations. Some of the presented results were independently obtained by the authors [HoKo,HoKo02b,HoKo03] and Krawetz, Lawrence, and Shallit [Kr03,KLS03]. In particular, we will see how a surprising connection to graph colouring and chromatic polynomials is very helpful to count the elements of the investigated subsemigroup of transformations. At the end of our search, we will present some applications of these results to state complexity problems for one- and two-way finite automata. Appeared in The Formal Language Theory Column

The unfolding semantics of graph transformation systems can represent a basis for their formal verification. For general, possibly infinite-state, graph transformation systems one can construct finite under- and over- approximations of the (infinite) unfolding, with arbitrary accuracy. Such approximations can be used to check properties of a graph transformation system, like safety and liveness properties, expressed in suitable fragments of the μ-calculus. For finite-state graph transformation systems, a variant of McMillan's approach (originally developed for Petri nets) allows us to single out a finite under-approximation which is a so-called complete prefix of the unfolding, i.e., which provides an "exact" representation of the behaviour the original system as far as reachable states are concerned. Some problems related to the constructive definition of the prefix are discussed.

The study of finite-state adventures, abbreviated by FSA, is a topic that has, despite its origins that can be traced back to medieval times, been neglected in the relevant literature. We attempt to close this gap and give a full account of a five-level hierarchy of finite-state adventures.

We define a construction operation on hypergraphs using a co-limit and show that its expressiveness concerning graph rewriting is equal to the graph expressions of Courcelle and the double-pushout approach of Ehrig. With an inductive way of representing graphs, graph rewriting arises naturally as a derived concept. The usefulness of our approach for the compositional modelling of concurrent systems is then shown by defining the semantics of a process calculus with mobility and of petri nets.

München, Techn. Univ., Dipl.-Arbeit, 1995 The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem (TSP). An amount of goods is assigned to every node of a graph and they are to be collected by vehicles restricted in their capacity and time and brought to a depot. The aim is to minimize the overall costs. The decision problem for vehicle routing is NP-complete, which means that there probably is no polynomial-time algorithm for VRP and we are forced to resort to heuristics. Several heuristics are introduced, including Sweep, several variants of the Savings-procedure, a giant tour algorithm and a $k$-opt algorithm for the improvement of existing tours. The heuristics are tested on graphs representing real-world road networks and are compared in their results and their computational complexity. Technische Universität München (in German)

Supplementary materials. Included are a supplementary table (Table S1) and two supplementary figures (Figures S1-S2). (DOCX 2196 kb)

Supplementary materials. Included are a supplementary table (Table S1) and two supplementary figures (Figures S1-S2). (DOCX 2196 kb)

Dissertation, Universität Duisburg-Essen, 2016 The aim of this thesis is the definition of a high-level framework for verifying concurrent and distributed systems. Verification in computer science is challenging, since models that are sufficiently expressive to describe real-life case studies suffer from the undecidability of interesting problems. This also holds for the graph transformation systems used in this thesis. To still be able to analyse these system we have to restrict either the class of systems we can model, the class of states we can express or the properties we can verify. In fact, in the framework we will present, all these limitations are possible and each allows to solve different verification problems. For modelling we use graphs as the states of the system and graph transformation rules to model state changes. More precisely, we use hypergraphs, where an edge may be incident to an arbitrary long sequence of nodes. As rule formalism we use the single pushout approach based on category theory. This provides us with a powerful formalisms that allows us to use a finite set of rules to describe an infinite transition system. To obtain decidability results while still maintaining an infinite state space we use the theory of well-structured transition systems (WSTS), the main source of decidability results in the infinite case. We need to equip our state space with a well-quasi-order (wqo) which is a simulation relation for the transition relation (this is also known as compatibility condition or monotonicity requirement). If a system can be seen as a WSTS and some additional conditions are satisfied, one can decide the coverability problem, i.e., the problem of verifying whether, from a given initial state one can reach a state that covers a final state, i.e. is larger than the final state with respect to a chosen order. This problem can be used for verification by giving a finite set of minimal error states that represent an infinite class of erroneous states (i.e. all larger states). By checking whether one of these minimal states is coverable, we verify whether an error is reachable. The theory of WSTS provides us with a generic backwards algorithm to solve this problem. For graphs we will introduce three orders, the minor ordering, the subgraph ordering and the induced subgraph ordering, and investigate which graph transformation systems form WSTS with these orders. Since only the minor ordering is a wqo on all graphs, we will first define so-called Q-restricted WSTS, where we only require that the chosen order is a wqo on the downward-closed class Q. We examine how this affects the decidability of the coverability problem and present appropriate classes Q such that the subgraph ordering and induced subgraph ordering form Q-restricted WSTS. Furthermore, we will prove the computability of the backward algorithm for these Q-restricted WSTS. More precisely, we will do this in the form of a framework and give necessary conditions for orders to be compatible with this framework. For the three mentioned orders we prove that they satisfy these conditions. Being compatible with different orders strengthens the framework in the following way: On the one hand error specifications have to be invariant wrt. the order, meaning that different orders can describe different properties. On the other hand, there is the following trade-off: coarser orders are wqos on larger sets of graphs, but fewer GTS are well-structured wrt. coarse orders (analogously the reverse holds for fine orders). Finally, we will present the tool Uncover which implements most of the theoretical framework defined in this thesis. The practical value of our approach is illustrated by several case studies and runtime results.

OBJECTIVES: Bipolar disorder (BD) with early disease onset is associated with an unfavorable clinical outcome and constitutes a clinically and biologically homogenous subgroup within the heterogeneous BD spectrum. Previous studies have found an accumulation of early age at onset (AAO) in BD families and have therefore hypothesized that there is a larger genetic contribution to the early-onset cases than to late onset BD. To investigate the genetic background of this subphenotype, we evaluated whether an increased polygenic burden of BD- and schizophrenia (SCZ)-associated risk variants is associated with an earlier AAO in BD patients. METHODS: A total of 1995 BD type 1 patients from the Consortium of Lithium Genetics (ConLiGen), PsyCourse and Bonn-Mannheim samples were genotyped and their BD and SCZ polygenic risk scores (PRSs) were calculated using the summary statistics of the Psychiatric Genomics Consortium as a training data set. AAO was either separated into onset groups of clinical interest (childhood and adolescence [≤18 years] vs adulthood [>18 years]) or considered as a continuous measure. The associations between BD- and SCZ-PRSs and AAO were evaluated with regression models. RESULTS: BD- and SCZ-PRSs were not significantly associated with age at disease onset. Results remained the same when analyses were stratified by site of recruitment. CONCLUSIONS: The current study is the largest conducted so far to investigate the association between the cumulative BD and SCZ polygenic risk and AAO in BD patients. The reported negative results suggest that such a polygenic influence, if there is any, is not large, and highlight the importance of conducting further, larger scale studies to obtain more information on the genetic architecture of this clinically relevant phenotype. peerReviewed

In group living animals, reproductive competition plays an important role in shaping social relationships and associations among female group members. In this study, we investigated the impact of male presence on the development of female-female competition and female sociality in groups of female wild house mice, using physiological and behavioral parameters. We predicted that, by eliciting intra-sexual competition, males influence social relationships among female group members and thus affect female associations to potential cooperation partners. To test this hypothesis we compared stress hormone production, the frequency of agonistic interactions, social hierarchies and social partner preferences in groups of unrelated, unfamiliar females in the absence and presence of males. Our results revealed no indication that the introduction of males into all-female groups of wild house mice elicited increased competition among female group members, neither on the physiological nor on the behavioral level. We found no effect of male presence on female glucocorticoid secretion, aggression, dominance hierarchies or on the females' sociability. Females thus seem not to intensely compete over access to males. This female ability to behaviorally and physiologically deal with even previously unfamiliar same-sex group members may be an important feature of female house mouse societies. In fact, it could be a necessary prerequisite to establish cooperative relationships between females in the context of reproduction, such as communal nursing of young.

Communal nursing, the provision of milk to non-offspring, has been argued to be a non-adaptive by-product of group living. We used 2 years of field data from a wild house mouse population to investigate this question. Communal nursing never occurred among females that previously lacked overlap in nest box use. Females nursed communally in only 33 % of cases in which there was a communal nursing partner available from the same social group. Solitarily nursing females were not socially isolated in their group; nevertheless, high spatial associations prior to reproduction predict which potential female partner was chosen for communal nursing. An increase in partner availability increased the probability of communal nursing, but population density itself had a negative effect, which may reflect increased female reproductive competition during summer. These results argue that females are selective in their choice of nursing partners and provide further support that communal nursing with the right partner is adaptive. Electronic supplementary material The online version of this article (doi:10.1007/s00114-013-1130-6) contains supplementary material, which is available to authorized users.

Our research focuses on mechanisms that promote and stabilize social behavior, fitness consequences of cooperation, and how interactions with conspecifics structure groups and populations. To this end, we studied wild house mice (Mus musculus domesticus) in the laboratory, in semi-natural enclosures and in the field. In 2002, we initiated a project on a free-living population of house mice in a barn near Zurich, Switzerland, where mice were equipped with RFID transponders and were provided with 40 nest boxes for resting and breeding. The population typically comprised between 250 and 400 mice. To analyze social group membership, social interactions and social preferences of the mice in our study population over their lifespan, we installed a continuous transponder reading system (AniLoc, FBI Science GmbH, Germany). Mice accessed nest boxes through tunnels equipped with two antennas each. When a mouse implanted with an RFID transponder passed the electromagnetic field of an antenna, its identity was transmitted and registered in real time with AniLoc. Additionally, body weights of mice were automatically registered at eight drinking facilities (Intelliscale, FBI Science GmbH, Germany). Here, a mouse sits on a freely movable platform that connects to a scale registering body weight when drinking, and an antenna around the head of the water bottle registers the drinking individual’s RFID transponder. The system enabled continuous remote monitoring of the behavior of a free-living, open population of house mice, when using nest boxes and when drinking. Since such safe places are an important resource for survival and reproduction, time of day, duration and frequency of meetings with conspecifics reveal information about the function of their interactions. Trigger efficiency of antennas was 98.2 %. Mice entered and left the nest boxes with an average speed of 0.03 m/s, which is within the antennas’ detection capacity (detection speed of 1 m/s or 3.6 km/h). The antenna devices documented not only social structuring of our study population but also spatial genetic structuring. The observation that mice lived in rather closed social groups and tended to share nest boxes with relatives highlights the importance of kin selection for the evolution and maintenance of social behavior. We suggest that such automatic recording of activity, spatial distribution and social interactions is helpful not only in field studies, for a variety of species, but also in captivity or laboratory studies, to answer basic questions in behavioral ecology, population ecology, population genetics, conservation biology, disease ecology, or animal welfare.

ESBMC is a context-bounded symbolic model checker that allows the verification of single- and multi-threaded C code with shared variables and locks. ESBMC supports full ANSI-C, and can verify programs that make use of bit-level operations, arrays, pointers, structs, unions, memory allocation and foating-point arithmetic. It can reason about arithmetic under- and overflows, pointer safety, memory leaks, array bounds violations, atomicity and order violations, local and global deadlocks, data races, and user-specified assertions. However, as other bounded model checkers, ESBMC is in general incomplete.