Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 5 of 5
Full-Text Articles in Entire DC Network
Safe Stratified Datalog With Integer Order Programs, Peter Revesz
Safe Stratified Datalog With Integer Order Programs, Peter Revesz
CSE Conference and Workshop Papers
Guaranteeing termination of programs on all valid inputs is important for database applications. Termination cannot be guaranteed in Stratified Datalog with integer (gap)-order programs on generalized databases because they express any Turing-computable function. This paper introduces a restriction of those programs that can express only computable queries. The restricted language has a high expressive power and a non-elementary data complexity.
Hga: A Hardware-Based Genetic Algorithm, Stephen D. Scott, Ashok Samal, Sharad C. Seth
Hga: A Hardware-Based Genetic Algorithm, Stephen D. Scott, Ashok Samal, Sharad C. Seth
CSE Conference and Workshop Papers
A genetic algorithm (GA) is a robust problem-solving method based on natural selection. Hardware's speed advantage and its ability to parallelize offer great rewards to genetic algorithms. Speedups of 1-3 orders of magnitude have been observed when frequently used software routines were implemented in hardware by way of reprogrammable field-programmable gate arrays (FPGAs). Reprogrammability is essential in a general-purpose GA engine because certain GA modules require changeability (e.g. the function to be optimized by the GA). Thus a hardware-based GA is both feasible and desirable. A fully functional hardware-based genetic algorithm (the HGA) is presented here as a proof-of-concept system. …
A System For Recognizing A Large Class Of Engineering Drawings, Yuhong Yu, Ashok Samal, Sharad C. Seth
A System For Recognizing A Large Class Of Engineering Drawings, Yuhong Yu, Ashok Samal, Sharad C. Seth
CSE Conference and Workshop Papers
We present a complete system for recognizing a large class of symbolic engineering drawings that includes flowcharts, chemical plant diagrams, and logic & electrical circuits. The output of the system, a netlist identifying the symbol types and interconnections, may be used for design verification or as a compact portable representation of the drawing. The automatic recognition task is done in two stages: (1) domain-independent rules segment symbols from connection lines in the preprocessed drawing image and (2) an understanding subsystem makes use of a set of domain-specific matchers to classify symbols and correct errors automatically. A graphical user interface is …
Parallel Test Generation With Low Communication Overhead, Sivaramakrishnan Venkatraman, Sharad C. Seth, Prathima Agrawal
Parallel Test Generation With Low Communication Overhead, Sivaramakrishnan Venkatraman, Sharad C. Seth, Prathima Agrawal
CSE Conference and Workshop Papers
In this paper we present a method of parallelizing test generation for combinational logic using boolean satisfiability. We propose a dynamic search-space allocation strategy to split work between the available processors. This strategy is easy to implement with a greedy heuristic and is economical in its demand for inter-processor communication. We derive an analytical model to predict the performance of the parallel versus sequential implementations. The effectiveness of our method and analysis is demonstrated by an implementation on a Sequent (shared memory) multiprocessor. The experimental data shows significant performance improvement in parallel implementation, validates our analytical model, and allows predictions …
A Trainable, Single-Pass Algorithm For Column Segmentation, Son Sylwester, Sharad C. Seth
A Trainable, Single-Pass Algorithm For Column Segmentation, Son Sylwester, Sharad C. Seth
CSE Conference and Workshop Papers
Column Segmentation logically precedes OCR in the document analysis process. The trainable algorithm described here, XYCUT, relies on horizontal and vertical binary profiles to produce an XY- tree representing the column structure of a page of a technical document in a single pass through the bit image. Training against ground truth adjusts a single, resolution independent, parameter using only local information and guided by an edit distance function. The algorithm correctly segments the page image for a (fairly) wide range of parameter values, although small, local and repairable errors may be made, an effect measured by a repair cost function.