3CAM - A NOVEL TERNARY CONTENT ADDRESSABLE MEMORY USING THREE-VALUED LOGIC

Content Addressable Memory (CAM) is a special type of Complementary Metal-Oxide-Semiconductor (CMOS) storage element that allows for a parallel search operation on a memory stack in addition to the read and write operations yielded by a conventional SRAM storage array. In practice, it is often desirable to be able to store a “don’t care” state for faster searching operation. However, commercially available CAM chips are forced to accomplish this functionality by having to include two binary memory storage elements per CAM cell,which is a waste of precious area and power resources. This research presents a novel CAM circuit that achieves the “don’t care” functionality with a single ternary memory storage element. Using the recent development of multiple-voltage-threshold (MVT) CMOS transistors, the functionality of the proposed circuit is validated and characteristics for performance, power consumption, noise immunity, and silicon area are presented. This workpresents the following contributions to the field of CAM and ternary-valued logic:• We present a novel Simple Ternary Inverter (STI) transistor geometry scheme for achieving ternary-valued functionality in existing SOI-CMOS 0.18µm processes.• We present a novel Ternary Content Addressable Memory based on Three-Valued Logic (3CAM) as a single-storage-element CAM cell with “don’t care” functionality.• We explore the application of macro partitioning schemes to our proposed 3CAM array to observe the benefits and tradeoffs of architecture design in the context of power, delay, and area.

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.

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.

Dephosphorylation of p-ERK1/2 in relation to tumor remission after HER-2 and Raf1 blocking therapy in a conditional mouse tumor model

Several studies have shown that HER-2/neu (erbB-2) blocking therapy strategies can cause tumor remission. However, the responsible molecular mechanisms are not yet known. Both ERK1/2 and Akt/PKB are critical for HER-2-mediated signal transduction. Therefore, we used a mouse tumor model that allows downregulation of HER-2 in tumor tissue by administration of anhydrotetracycline (ATc). Switching-off HER-2 caused a rapid tumor remission by more than 95% within 7 d of ATc administration compared to the volume before switching-off HER-2. Interestingly, HER-2 downregulation caused a dephosphorylation of p-ERK1/2 by more than 80% already before tumor remission occurred. Levels of total ERK protein were not influenced. In contrast, dephosphorylation of p-Akt occurred later, when the tumor was already in remission. These data suggest that in our HER-2 tumor model dephosphorylation of p-ERK1/2 may be more critical for tumor remission than dephosphorylation of p-Akt. To test this hypothesis we used a second mouse tumor model that allows ATc controlled expression of BXB-Raf1 because the latter constitutively signals to ERK1/2, but cannot activate Akt/PKB. As expected, downregulation of BXB-Raf1 in tumor tissue caused a strong dephosphorylation of p-ERK1/2, but did not decrease levels of p-Akt. Interestingly, tumor remission after switching-off BXB-Raf1 was similarly efficient as the effect of HER-2 downregulation, despite the lack of p-Akt dephosphorylation. In conclusion, two lines of evidence strongly suggest that dephosphorylation of p-ERK1/2 and not that of p-Akt is critical for the rapid tumor remission after downregulation of HER-2 or BXB-Raf1 in our tumor model: (i) dephosphorylation of p-ERK1/2 but not that of p-Akt precedes tumor remission after switching-off HER-2 and (ii) downregulation of BXB-Raf1 leads to a similarly efficient tumor remission as downregulation of HER-2, although no p-Akt dephosphorylation was observed after switching-off BXB-Raf1.

On the Behaviour of Marginal and Conditional Akaike Information Criteria in Linear Mixed Models

In linear mixed models, model selection frequently includes the selection of random effects. Two versions of the Akaike information criterion (AIC) have been used, based either on the marginal or on the conditional distribution. We show that the marginal AIC is no longer an asymptotically unbiased estimator of the Akaike information, and in fact favours smaller models without random effects. For the conditional AIC, we show that ignoring estimation uncertainty in the random effects covariance matrix, as is common practice, induces a bias that leads to the selection of any random effect not predicted to be exactly zero. We derive an analytic representation of a corrected version of the conditional AIC, which avoids the high computational cost and imprecision of available numerical approximations. An implementation in an R package is provided. All theoretical results are illustrated in simulation studies, and their impact in practice is investigated in an analysis of childhood malnutrition in Zambia.