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.

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.

BOLD correlates of EEG alpha phase-locking and the fMRI default mode network

Phase locking or synchronization of brain areas is a key concept of information processing in the brain. Synchronous oscillations have been observed and investigated extensively in EEG during the past decades. EEG oscillations occur over a wide frequency range. In EEG, a prominent type of oscillations is alpha-band activity, present typically when a subject is awake, but at rest with closed eyes. The spectral power of alpha rhythms has recently been investigated in simultaneous EEG/fMRI recordings, establishing a wide-range cortico-thalamic network. However, spectral power and synchronization are different measures and little is known about the correlations between BOLD effects and EEG synchronization. Interestingly, the fMRI BOLD signal also displays synchronous oscillations across different brain regions. These oscillations delineate so-called resting state networks (RSNs) that resemble the correlation patterns of simultaneous EEG/fMRI recordings. However, the nature of these BOLD oscillations and their relations to EEG activity is still poorly understood. One hypothesis is that the subunits constituting a specific RSN may be coordinated by different EEG rhythms. In this study we report on evidence for this hypothesis. The BOLD correlates of global EEG synchronization (GFS) in the alpha frequency band are located in brain areas involved in specific RSNs, e.g. the 'default mode network'. Furthermore, our results confirm the hypothesis that specific RSNs are organized by long-range synchronization at least in the alpha frequency band. Finally, we could localize specific areas where the GFS BOLD correlates and the associated RSN overlap. Thus, we claim that not only the spectral dynamics of EEG are important, but also their spatio-temporal organization.