Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Chemistry (1)
- Combinational circuits (1)
- Communication time (1)
- Complexity (1)
- Conditional rewriting (1)
-
- Decomposition time (1)
- Embedding (1)
- Hough transform (1)
- MIMD and SIMD hypercube multicomputers (1)
- Mesh (1)
- Multiprocessor algorithm (1)
- Parallel algorithms (1)
- Parallel mergesort (1)
- Pattern matching (1)
- Performance analysis (1)
- Programming (1)
- Programming languages and computers (1)
- Sorting (1)
- Star graph (1)
- Terms (1)
Articles 1 - 9 of 9
Full-Text Articles in Physical Sciences and Mathematics
Quantitative Footprinting Analysis. Binding To A Single Site, Robert Rehfuss, Jerry Goodisman, James C. Dabrowiak
Quantitative Footprinting Analysis. Binding To A Single Site, Robert Rehfuss, Jerry Goodisman, James C. Dabrowiak
Chemistry - All Scholarship
The theory for measuring ligand binding constants from footprinting autoradiographic data associated with a single binding site is derived. If the ligand and DNA cleavage agent compete for a common site, the spot intensities are not proportional to the amount of DNA not blocked by ligand. The analysis of a single site is experimentally illustrated by using results for the anticancer drug actinomycin D interacting with the duplex d(TAGCGCTA)2 as probed with the hydrolytic enzyme DNase I.
Two-Dimensional Pattern Matching With K Mismatches, Sanjay Ranka, Todd Heywood
Two-Dimensional Pattern Matching With K Mismatches, Sanjay Ranka, Todd Heywood
Electrical Engineering and Computer Science - Technical Reports
We give an algorithm which finds all occurrences of an m1 x m2 pattern array embedded as subarrays in an n1 x n2 array of text, where at most k mismatches are allowed per occurrence. The algorithm runs in time O((k+a)(blogb+ n1n2)), where a = min(m1m2) and b=max(m1m2). This improves upon the previously best known algorithm, and is asymptotically optimal for k ≈ a.
Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh
Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh
Electrical Engineering and Computer Science - Technical Reports
We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n degree star graph can efficiently simulate an n-dimensional mesh.
Analysis Of A Parallel Mergesort, Per Brinch Hansen
Analysis Of A Parallel Mergesort, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
The paper describes a performance model of a fine-grained, parallel mergesort which sorts N elements in 0(N) time using 0(logN) processors. The model predicts both the communication time involved in merging the elements and the decomposition time required to activate and terminate the binary tree of processes. The parallel algorithm is written in Joyce and runs on an Encore Multimax.
Term Rewriting With Conditionals And Priority Orderings, Chilukuri K. Mohan
Term Rewriting With Conditionals And Priority Orderings, Chilukuri K. Mohan
Electrical Engineering and Computer Science - Technical Reports
Conditional rewriting and priority rewriting are two recent generalizations of term rewriting systems. In the former, each rewrite rule is accompanied by an antecedent which must be shown to hold before rewriting can occur. In the latter, rewrite rules can be used only in a particular order. We compare these formalisms: neither formalism encompasses the other in a practical sense, but we give restrictions under which priority and conditional rewriting can be equivalent. We combine the two operational mechanisms, obtaining a natural and expressive formalism called Priority Conditional Rewriting Systems (PCRS). PCRS can be used to “fully-define” data type specifications …
A 15-Valued Algorithm For Test Pattern Generation, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann
A 15-Valued Algorithm For Test Pattern Generation, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann
Electrical Engineering and Computer Science - Technical Reports
In this report we present a new algorithm for detecting single stuck-at faults in combinational circuits. This algorithm is based on a 15-valued system and introduces several new concepts to make test generation more efficient. This 15-valued system allows us to impose all the constraints that must be satisfied in order to sensitize a single path. Consequently all deterministic implications are fully considered prior to the enumeration process. The resulting ability to identify inconsistencies prior to enumeration improves the possibility of quicker identification of redundant faults. Instead of sensitizing a single gate at a time, we sensitize subpaths by sensitizing …
The Nature Of Parallel Programming, Per Brinch Hansen
The Nature Of Parallel Programming, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
Parallel programming is the art of writing programs for computers that perform many operations simultaneously. This essay discusses the nature of parallel programming without going into technical details. It uses a sorting problem to illustrate what it means to solve a problem in parallel, how we write parallel programs, how parallel computers execute them, and how fast they run. The author expects that scientific users of parallel computers may find ease of programming more important than maximum performance. He suggests ways to make this possible.
Computing Hough Transforms On Hypercube Multicomputers, Sanjay Ranka, Sartaj Sahni
Computing Hough Transforms On Hypercube Multicomputers, Sanjay Ranka, Sartaj Sahni
Electrical Engineering and Computer Science - Technical Reports
Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputers are developed. Our algorithms can compute p angles of the Hough transform of an N x N image, p ≤ N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N2) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.
A Logic Programming Elucidation Of Oda - Document Descriptions And Processes, Howard A. Blair, Allen Brown Jr.
A Logic Programming Elucidation Of Oda - Document Descriptions And Processes, Howard A. Blair, Allen Brown Jr.
Electrical Engineering and Computer Science - Technical Reports
We are pursuing a programme of research in document representation. The principal aim of this research is to develop a document description language that has a precise formal semantics, that is fully expressive of the constructs typical of traditional (procedural) document description languages, that is constraint-based, and that cleanly separates specifications of form and content. The research is currently in the first of three envisioned three phases. In the first phase we are formalising the Office Document Architecture (ODA) by faithfully translating ODA document descriptions into logic programmes. The transition utilizes highly restricted forms of Prolog programmes.1 In the second …