Lower complexity bounds in justification logic

Justification Logic studies epistemic and provability phenomena by introducing justifications/proofs into the language in the form of justification terms. Pure justification logics serve as counterparts of traditional modal epistemic logics, and hybrid logics combine epistemic modalities with justification terms. The computational complexity of pure justification logics is typically lower than that of the corresponding modal logics. Moreover, the so-called reflected fragments, which still contain complete information about the respective justification logics, are known to be in~NP for a wide range of justification logics, pure and hybrid alike. This paper shows that, under reasonable additional restrictions, these reflected fragments are NP-complete, thereby proving a matching lower bound. The proof method is then extended to provide a uniform proof that the corresponding full pure justification logics are $\Pi^p_2$-hard, reproving and generalizing an earlier result by Milnikel.

The origin of the European Medieval Warm Period"

Proxy records and results of a three dimensional climate model show that European summer temperatures roughly a millennium ago were comparable to those of the last 25 years of the 20th century, supporting the existence of a summer "Medieval Warm Period" in Europe. Those two relatively mild periods were separated by a rather cold era, often referred to as the "Little Ice Age". Our modelling results suggest that the warm summer conditions during the early second millennium compared to the climate background state of the 13th–18th century are due to a large extent to the long term cooling induced by changes in land-use in Europe. During the last 200 years, the effect of increasing greenhouse gas concentrations, which was partly levelled off by that of sulphate aerosols, has dominated the climate history over Europe in summer. This induces a clear warming during the last 200 years, allowing summer temperature during the last 25 years to reach back the values simulated for the early second millennium. Volcanic and solar forcing plays a weaker role in this comparison between the last 25 years of the 20th century and the early second millennium. Our hypothesis appears consistent with proxy records but modelling results have to be weighted against the existing uncertainties in the external forcing factors, in particular related to land-use changes, and against the uncertainty of the regional climate sensitivity. Evidence for winter is more equivocal than for summer. The forced response in the model displays a clear temperature maximum at the end of the 20th century. However, the uncertainties are too large to state that this period is the warmest of the past millennium in Europe during winter.

Object-Oriented Legacy System Trace-based Logic Testing

When reengineering legacy systems, it is crucial to assess if the legacy behavior has been preserved or how it changed due to the reengineering effort. Ideally if a legacy system is covered by tests, running the tests on the new version can identify potential differences or discrepancies. However, writing tests for an unknown and large system is difficult due to the lack of internal knowledge. It is especially difficult to bring the system to an appropriate state. Our solution is based on the acknowledgment that one of the few trustable piece of information available when approaching a legacy system is the running system itself. Our approach reifies the execution traces and uses logic programming to express tests on them. Thereby it eliminates the need to programatically bring the system in a particular state, and handles the test-writer a high-level abstraction mechanism to query the trace. The resulting system, called TESTLOG, was used on several real-world case studies to validate our claims.

TRIO LOGIC REGRESSION - DETECTION OF SNP - SNP INTERACTIONS IN CASE-PARENT TRIOS

Statistical approaches to evaluate higher order SNP-SNP and SNP-environment interactions are critical in genetic association studies, as susceptibility to complex disease is likely to be related to the interaction of multiple SNPs and environmental factors. Logic regression (Kooperberg et al., 2001; Ruczinski et al., 2003) is one such approach, where interactions between SNPs and environmental variables are assessed in a regression framework, and interactions become part of the model search space. In this manuscript we extend the logic regression methodology, originally developed for cohort and case-control studies, for studies of trios with affected probands. Trio logic regression accounts for the linkage disequilibrium (LD) structure in the genotype data, and accommodates missing genotypes via haplotype-based imputation. We also derive an efficient algorithm to simulate case-parent trios where genetic risk is determined via epistatic interactions.