28649866
A ramsey type problem concerning vertex colourings
Abstract Let H → k v G denote the fact that for every function π: V ( H ) → {1, …, k } there is an induced subgraph G ′ of H with G ′ ≅ G and V ( G ′) ⊆ π −1 ( i ) for some i . Folkman has shown that for all graphs G and for all positive integers k such a graph H exists. We examine here f ( G , k ), the minimum order of a graph H for which H → k v G . We show that for any fixed integer k ≥ 2 there are positive constants C 1 and C 2 such that C 1 n 2 ≤ max{ f ( G , k ): | V ( G )| = n } ≤ C 2 n 2 log 2 n .
2058234
Subdivisions and Chromatic Roots
It is well known that chromatic polynomials can have roots (chromatic roots) of arbitrarily large modulus. We prove here that for any graph G and any ?>0, there is a subdivision of G all of whose chromatic roots lie in |z?1|<1+?.
645538
Plant snoRNA database
The Plant snoRNA database (http://www.scri.sari.ac.uk/plant_snoRNA/) provides information on small nucleolar RNAs from Arabidopsis and eighteen other plant species. Information includes sequences, expression data, methylation and pseudouridylation target modification sites, initial gene organization (polycistronic, single gene and intronic) and the number of gene variants. The Arabidopsis information is divided into box C/D and box H/ACA snoRNAs, and within each of these groups, by target sites in rRNA, snRNA or unknown. Alignments of orthologous genes and gene variants from different plant species are available for many snoRNA genes. Plant snoRNA genes have been given a standard nomenclature, designed wherever possible, to provide a consistent identity with yeast and human orthologues.
7675324
Applications of Artificial Intelligence
One of the aims of artificial intelligence has been to make machines behave intelligently as humans do. Thus the study of artificial intelligence includes the study of how humans acquire and apply knowledge, reason under uncertainty and in complex environments, and how they do planning and solve problems. Knowledge-based automation deals with the application of artificial intelligence to a production environment in order to reduce the involvement of human beings to a minimum.
267100
Proximity-aware directory-based coherence for multi-core processor architectures
As the number of cores increases on chip multiprocessors, coherence is fast becoming a central issue for multi-core performance. This is exacerbated by the fact that interconnection speeds are not scaling well with technology. This paper describes mechanisms to accelerate coherence for a multi-core architecture that has multiple private L2 caches and a scalable point-to-point interconnect between cores. These techniques exploit the differences in geometry between chip multiprocessors and traditional multiprocessor architectures.
 Directory-based protocols have been proposed as a scalable alternative to snoop-based protocols. In this paper, we discuss implementations of coherence for CMPs and propose and evaluate a novel directory-based coherence scheme to improve the performance of parallel programs on such processors. Proximity-aware coherence accelerates read and write misses by initiating cache-to-cache transfers from the spatially closest sharer. This has the dual benefit of eliminating unnecessary accesses to off-chip memory, and minimizing the distance over which communicated data moves across the network. The proposed schemes result in speedups up to 74.9% for our workloads.
5243593
Steps Toward Automatic Theory Formation
This paper describes a theory formation system which can discover a partial axiomization of a data base represented as extensionally defined binary relations.- The system first discovers all possible intensional definitions of each binary relation in terms of the others. It then determines a minimal set of these relations from which the others can be defined. It then attempts to discover all the ways the relations of this minimal set can interact with each other, thus generating a set of inference rules. Although the system was originally designed to explore automatic techniques for theory construction for question-answering systems, it is currently being expanded to function as a symbiotic system to help social scientists explore certain kinds of data bases.
15658893
Theories of Causal Ordering
Abstract This paper is a response to Iwasaki and Simon [14] which criticizes de Kleer and Brown [8]. We argue that many of their criticisms, particularly concerning causality, modeling and stability, originate from the difference of concerns between engineering and economics. Our notion of causality arises from considering the interconnections of components, not equations. When no feedback is present, the ordering produced by our qualitative physics is similar to theirs. However, when feedback is present, our qualitative physics determines a causal ordering around feedback loops as well. Causal ordering is a general technique not only applicable to qualitative reasoning. Therefore we also explore the relationship between causal ordering and propagation of constraints upon which the methods of qualitative physics are based.