Computational complexity of queries based on itemsets

We investigate determining the exact bounds of the frequencies of conjunctions based on frequent sets. Our scenario is an important special case of some general probabilistic logic problems that are known to be intractable. We show that despite the limitations our problems are also intractable, namely, we show that checking whether the maximal consistent frequency of a query is larger than a given threshold is NP-complete and that evaluating the Maximum Entropy estimate of a query is PP-hard. We also prove that checking consistency is NP-complete.     

Influence of Ti Powder Characteristics on Combustion Synthesis of Porous NiTi Alloy

Porous NiTi shape memory alloy (SMA) is a novel biomedical material used for human hard tissue implant .The influence of elemental titanium powder characteristics such as powder morphology, particle size and specific surface area( SSA) on the minimal ignition temperature ,combustion temperature and final product of porous Ni-Ti SMA fabricated by combustion synthesis method was investigated in this paper by scanning electron microscopy (SEM) and laser diffraction.The preliminary data indicated that the titanium powder characteristics had a strong effect on combustion synthesis of porous NiTi SMA.     

Width-restricted layering of acyclic digraphs with consideration of dummy nodes

This paper deals with the problem of finding graph layerings restricted to a given maximal width. However, other than previous approaches for width-restricted layering, we take into account the space for dummy nodes, which are introduced by edges crossing a layer. The main result is that the problem of finding a width-restricted layering under consideration of dummy nodes is NP-complete even when all regular nodes have the same constant width and all dummy nodes have the same constant width.     

Putting it all together – Formal verification of the VAMP

In the verified architecture microprocessor (VAMP) project we have designed, functionally verified, and synthesized a processor with full DLX instruction set, delayed branch, Tomasulo scheduler, maskable nested precise interrupts, pipelined fully IEEE compatible dual precision floating point unit with variable latency, and separate instruction and data caches. The verification has been carried out in the theorem proving system PVS. The processor has been implemented on a Xilinx FPGA. A shorter version of this article with the title “Instantiating uninterpreted functional units and memory system: functional verification of the VAMP” appeared in [8]. The work reported here was done while all the authors were with Saarland University.     

A space- and time-efficient local-spin spin lock

A simple code transformation is presented that reduces the space complexity of Yang and Anderson's local-spin mutual exclusion algorithm. In both the original and the transformed algorithm, only atomic read and write instructions are used; each process generates Θ(logN) remote memory references per lock request, where N is the number of processes. The transformed algorithm uses Θ(N) distinct variables, which is clearly optimal.     

Trade-offs between gaze and working memory use.

Eye movements during natural tasks suggest that observers do not use working memory to capacity but instead use eye movements to acquire relevant information immediately before needed. Results here however, show that this strategy is sensitive to memory load and to observers' expectations about what information will be relevant. Depending upon the predictability of what object features would be needed in a brick sorting task, subjects spontaneously modulated the order in which they sampled and stored visual information using working memory more when the task was predictable and reverting to a just-in-time strategy when the task was unpredictable and the memory load was higher. This self organization was evidenced by subjects' sequence of eye movements and also their sorting decisions following missed feature changes. These results reveal that attentional selection, fixations, and use of working memory reflect a dynamic optimization with respect to a set of constraints, such as task predictablity and memory load. They also reveal that change blindness depends critically on the local task context, by virtue of its influence on the information selected for storage in working memory. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Generation and context memory.

Generation enhances memory for occurrence but may not enhance other aspects of memory. The present study further delineates the negative generation effect in context memory reported in N. W. Mulligan (2004). First, the negative generation effect occurred for perceptual attributes of the target item (its color and font) but not for extratarget aspects of context (location and background color). Second, nonvisual generation tasks with either semantic or nonsemantic generation rules (antonym and rhyme generation, respectively) produced the same pattern of results. In contrast, a visual (or data-driven) generation task (letter transposition) did not disrupt context memory for color. Third, generating nonwords produced no effect on item memory but persisted in producing a negative effect on context memory for target attributes, implying that (a) the negative generation effect in context memory is not mediated by semantic encoding, and (b) the negative effect on context memory can be dissociated from the positive effect on item memory. The results are interpreted in terms of the processing account of generation. The original, perceptual-conceptual version of this account is too narrow, but a modified processing account, based on a more generic visual versus nonvisual processing distinction, accommodates the results. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

A hierarchical model for structure learning based on the physiological characteristics of neurons

Almost all applications of Artificial Neural Networks (ANNs) depend mainly on their memory ability. The characteristics of typical ANN models are fixed connections, with evolved weights, globalized representations, and globalized optimizations, all based on a mathematical approach. This makes those models to be deficient in robustness, efficiency of learning, capacity, anti-jamming between training sets, and correlativity of samples, etc. In this paper, we attempt to address these problems by adopting the characteristics of biological neurons in morphology and signal processing. A hierarchical neural network was designed and realized to implement structure learning and representations based on connected structures. The basic characteristics of this model are localized and random connections, field limitations of neuron fan-in and fan-out, dynamic behavior of neurons, and samples represented through different sub-circuits of neurons specialized into different response patterns. At the end of this paper, some important aspects of error correction, capacity, learning efficiency, and soundness of structural representation are analyzed theoretically. This paper has demonstrated the feasibility and advantages of structure learning and representation. This model can serve as a fundamental element of cognitive systems such as perception and associative memory.     

A Multinomial Model of Event-Based Prospective Memory.

Prospective memory is remembering to perform an action in the future. The authors introduce the 1st formal model of event-based prospective memory, namely, a multinomial model that includes 2 separate parameters related to prospective memory processes. The 1st measures preparatory attentional processes, and the 2nd measures retrospective memory processes. The model was validated in 4 experiments. Manipulations of instructions to place importance on either the prospective memory task or the background task (Experiments 1 and 2) and manipulations of distinctiveness of prospective memory targets (Experiment 2) had expected effects on model parameters, as did a manipulation of the difficulty of prospective memory target encoding (Experiments 3 and 4). An alternative model was also evaluated. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.