We present our on-going work to develop techniques for specifying source code signatures of bug patterns. Specifically, we discuss two approaches. The first approach directly analyzes a program in the intermediate rep...
详细信息
ISBN:
(纸本)159593748X
We present our on-going work to develop techniques for specifying source code signatures of bug patterns. Specifically, we discuss two approaches. The first approach directly analyzes a program in the intermediate representation (IR) of the ROSE compiler infrastructure using ROSE's API. The second analyzes the program using the bddbddb system of Lam, Whaley, et al.. In this approach, we store the IR produced by ROSE as a relational database, express patterns as declarative inference rules on relations in the language Datalog, and bddbddb implements the Datalog programs using binary decision diagram (BDD) techniques. Both approaches readily apply to large-scale applications, since ROSE provides full type analysis, control flow, and other available analysis information. In this paper, we primarily consider bug patterns expressed with respect to the structure of the source code or the control flow, or both. More complex techniques to specify patterns that are functions of data flow properties may be addressed by either of the above approaches, but are not directly treated here. Our Datalog-based work includes explicit support for expressing patterns on the use of the Message Passing Interface (MPI) in parallel distributed memory programs. We show examples of this on-going work as well. Copyright 2007 acm.
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-para-meter tractability results. Indeed, by Courcelle's Theorem we know: Any property of finite structure...
详细信息
ISBN:
(纸本)1595936858
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-para-meter tractability results. Indeed, by Courcelle's Theorem we know: Any property of finite structures, which is expressible by an MSO sentence, can be decided in linear time (data complexity) if the structures have bounded treewidth. In principle, Courcelle's Theorem can be applied directly to construct concrete algorithms by transforming the MSO evaluation problem into a tree language recognition problem. The latter can then be solved via a finite tree automaton (FTA). However, this approach has turned out to be problematical, since even relatively simple MSO formulae may lead to a "state explosion" of the FTA. In this work we propose monadic datalog (i.e., data log where all intentional predicate symbols are unary) as an alternative method to tackle this class of fixed-parameter tractable problems. We show that if some property of finite structures is expressible in MSO then this property can also be expressed by means of a monadic datalog program over the structure plus the treedecomposition. Moreover, we show that the resulting fragment of datalogcan be evaluated in linear time (both w.r.t. the program size and w.r.t. the data size). This new approach is put to work by devising a new algorithm for the PRIMALITY problem (i.e., testing if some attribute in a relational schema is part of a key). We also report on experimental results with a prototype implementation. Copyright 2007 acm.
The Yarowsky algorithm is a rule-based semi-supervised learning algorithm that has been successfully applied to some problems in computational linguistics. The algorithm was not mathematically well understood until (A...
详细信息
ISBN:
(纸本)0974903930
The Yarowsky algorithm is a rule-based semi-supervised learning algorithm that has been successfully applied to some problems in computational linguistics. The algorithm was not mathematically well understood until (Abney 2004) which analyzed some specific variants of the algorithm, and also proposed some new algorithms for bootstrapping. In this paper, we extend Abney's work and show that some of his proposed algorithms actually optimize (an upper-bound on) an objective function based on a new definition of cross-entropy which is based on a particular instantiation of the Bregman distance between probability distributions. Moreover, we suggest some new algorithms for rule-based semi-supervised learning and show connections with harmonic functions and minimum multi-way cuts in graph-based semi-supervised learning.
The proceedings contain 356 papers. The topics discussed include: an evidential approach in ensembles;solving first-order constraints in the theory of finite or infinite trees;dynamic interactive spatial similarity re...
详细信息
ISBN:
(纸本)1595931082
The proceedings contain 356 papers. The topics discussed include: an evidential approach in ensembles;solving first-order constraints in the theory of finite or infinite trees;dynamic interactive spatial similarity retrieval in iconic image databases using enhanced digraph;strong agent mobility for aglets based on the IBM JikesRVM;a constraint logic programming approach to 3D structure determination of large protein complexes;innovative computational methods for transcriptomic data analysis;approaches to text mining for clinical medical records;real coded clonal selection algorithm for unconstrained global optimization using a hybrid inversely proportional hypermutation operator;detecting identifiable areas in mobile environments;distributed collaborative filtering for peer-to-peer file sharing systems;relevance feedback methods for logo and trademark image retrieval on the web;and handheld devices for cooperative educational activities.
The proceedings contain 356 papers. The topics discussed include: an evidential approach in ensembles;solving first-order constraints in the theory of finite or infinite trees;dynamic interactive spatial similarity re...
详细信息
ISBN:
(纸本)1595931082
The proceedings contain 356 papers. The topics discussed include: an evidential approach in ensembles;solving first-order constraints in the theory of finite or infinite trees;dynamic interactive spatial similarity retrieval in iconic image databases using enhanced digraph;strong agent mobility for aglets based on the IBM JikesRVM;a constraint logic programming approach to 3D structure determination of large protein complexes;innovative computational methods for transcriptomic data analysis;approaches to text mining for clinical medical records;real coded clonal selection algorithm for unconstrained global optimization using a hybrid inversely proportional hypermutation operator;detecting identifiable areas in mobile environments;distributed collaborative filtering for peer-to-peer file sharing systems;relevance feedback methods for logo and trademark image retrieval on the web;and handheld devices for cooperative educational activities.
暂无评论