Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Syracuse University

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 481 - 510 of 532

Full-Text Articles in Computer Sciences

Mapping Finite Element Graphs On Hypercubes, Yeh-Ching Chung, Sanjay Ranka Jan 1990

Mapping Finite Element Graphs On Hypercubes, Yeh-Ching Chung, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

In parallel computing, it is important to map a parallel program onto a parallel computer such that the total execution time of a parallel program is minimized. In general, a parallel program and a parallel computer can be represented by a task graph (TG) and a processor graph (PG), respectively. For a TG, nodes represent tasks of a parallel program and edges denote the data communication needed between tasks. The weights associated with nodes and edges represent the computational load and communication cost, respectively. For a PG, nodes and edges denote processors and communication channels, respectively. By using the graph …

Go to article

An Architecture For Distributed Multimedia Database Systems, P. B. Berra, C.Y.R. Chen, A. Ghafoor, C. C. Lin Jan 1990

An Architecture For Distributed Multimedia Database Systems, P. B. Berra, C.Y.R. Chen, A. Ghafoor, C. C. Lin

Electrical Engineering and Computer Science - All Scholarship

In the past few years considerable demand for user oriented multimedia information systems has developed. These systems must provide a rich set of functionality so that new, complex, and interesting applications can be addressed. This places considerable importance on the management of diverse data types including text, images, audio and video. These requirements generate the need for a new generation of distributed heterogeneous multimedia database systems. In this paper we identify a set of functional requirements for a multimedia server considering database management, object synchronization and integration, and multimedia query processing. A generalization of the requirements to a distributed system …

Go to article

Using Annotated C++, Marshall P. Cline, Doug Lea Jan 1990

Using Annotated C++, Marshall P. Cline, Doug Lea

Electrical Engineering and Computer Science - All Scholarship

A++ (‘‘Annotated C++’’) is both a formalism and a proposed CASE tool for annotating C++ code with object-oriented specifications, assertions, and related semantic information. Annotations provide programmers with a useful means for approaching class design, exceptions, correctness, standardization, software reusability and related issues in software engineering with C++. This paper shows how A++ provides arbitrarily fine granularity to the C++ type system, how it automates and streamlines exception testing, how it can aid in standardization of software components, and how it can safely remove redundant exception tests.

Go to article

Arithmetic Classification Of Perfect Models Of Stratified Programs (Addendum), Krzysztof R. Apt, Howard A. Blair Jan 1990

Arithmetic Classification Of Perfect Models Of Stratified Programs (Addendum), Krzysztof R. Apt, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

RECURSION-FREE PROGRAMS The following section completes the analysis of arithmetic complexity of perfect models and has been inadvertently omitted in the previous version of the paper. We say that a general program P is recursion-free if in its dependency graph Dp there is no cycle. Clearly recursion-free programs form a subclass of stratified programs. Recursion-free programs form a very simple generalization of the class of hierarchical programs introduced in [C78]. Hierarchical programs satisfy an additional condition on variable occurrences in clauses that prevents floundering, i.e. a forced selection of a non-ground negative literal in an SLDNF- derivation. In this section …

Go to article

Two-Dimensional Pattern Matching With K Mismatches, Sanjay Ranka, Todd Heywood Aug 1989

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.

Go to article

Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh Aug 1989

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.

Go to article

Analysis Of A Parallel Mergesort, Per Brinch Hansen Jul 1989

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.

Go to article

Term Rewriting With Conditionals And Priority Orderings, Chilukuri K. Mohan Jul 1989

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 …

Go to article

A 15-Valued Algorithm For Test Pattern Generation, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann Jul 1989

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 …

Go to article

The Nature Of Parallel Programming, Per Brinch Hansen Mar 1989

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.

Go to article

A Logic Programming Elucidation Of Oda - Document Descriptions And Processes, Howard A. Blair, Allen Brown Jr. Jan 1989

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 …

Go to article

Computing Hough Transforms On Hypercube Multicomputers, Sanjay Ranka, Sartaj Sahni Jan 1989

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.

Go to article

Joyce Performance On A Multiprocessor, Per Brinch Hansen, Rangachari Anand Sep 1988

Joyce Performance On A Multiprocessor, Per Brinch Hansen, Rangachari Anand

Electrical Engineering and Computer Science - Technical Reports

Joyce is a parallel programming language based on CSP and Pascal. The language has been moved from the IBM PC to the Encore Multimax. The paper explains how the multiprocessor implementation of Joyce was guided by performance evaluation. The measurements show that the speed-up of Joyce programs follows Amdahl’s law.

Go to article

A Multiprocessor Implementation Of Joyce, Per Brinch Hansen Sep 1988

A Multiprocessor Implementation Of Joyce, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Joyce is a programming language for parallel computers based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a multiprocessor implementation of Joyce.

Go to article

A Lexical Extension Of Montague Semantics, William C. Purdy Mar 1988

A Lexical Extension Of Montague Semantics, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Montague's linguistic theory provides a completely formalized account of language in general and natural language in particular. It would appear to be especially applicable to the problem of natural language understanding by computer systems. However the theory does not deal with meaning at the lexical level. As a result, deduction in a system based on Montague semantics is severely restricted. This paper considers lexical extension of Montague semantics as a way to remove this restriction. Representation of lexical semantics by a logic program or semantic net is complex. An alternative representation, called a semantic space, is described. This alternative lacks …

Go to article

Metaprolog Design And Implementation, Hamid Bacha Jan 1988

Metaprolog Design And Implementation, Hamid Bacha

Electrical Engineering and Computer Science - Technical Reports

Many researchers in the area of logic programming have recognized the limits of logic languages such as Prolog and suggested a meta level approach as an alternative. Some of the main drawbacks cited are the control strategy, the presence of a single database, and the ad hoc extensions to the base logic programming paradigm to allow the dynamic modification of the database. The MetaProlog language, which includes Prolog and some of its metalanguage, deals with some of these problems. In this paper, the design and implementation of MetaProlog are described and the changes to the Warren Abstract Machine (WAM) on …

Go to article

Metaprolog User Manual, Hamid Bacha Jan 1988

Metaprolog User Manual, Hamid Bacha

Electrical Engineering and Computer Science - Technical Reports

MetaProlog is a logic-based programming language which subsumes the full Prolog language. This implementation is an incremental compiler (which also looks and feels like an interpreter) supporting meta-level constructs that are usually provided by the underlying architecture in other systems and are not directly available to the user. The most obvious feature of MetaProlog is the ability to handle multiple databases (referred to as theories) at the same time. In contrast to ordinary Prolog’s single-theory database, a MetaProlog database is a collection of theories. A theory is a first-class object and can be passed around as the value of a …

Go to article

Domains For Logic Programming, I. Filippenko, F. L. Morris Jun 1987

Domains For Logic Programming, I. Filippenko, F. L. Morris

Electrical Engineering and Computer Science - Technical Reports

We construct Scott domains well suited to use in an abstract implementation of logic programming, and perhaps to the modelling of other first-order data structures. The domain elements, which we call ‘grafts’, are in effect a sort of directed graphs. The approximation order in the domains corresponds to the relation between tuples of terms, “has a substitution instance”; the price to be paid is that one equivalence class of (tuples of) terms under renaming of variables is represented by many grafts. Graft domains come in two flavors—plain and ‘acyclic’—for modelling on an equal footing logic programming without and with the …

Go to article

Meta-Level Programming: A Compiled Approach, Hamid Bacha Feb 1987

Meta-Level Programming: A Compiled Approach, Hamid Bacha

Electrical Engineering and Computer Science - Technical Reports

There has been some intense research lately focused on the area of meta-level inference systems. In logic programming, the limitations of Prolog are widely recognized and a meta-level approach has been suggested. Unfortunately, only meta-interpreters have been considered so far. Moreover, these meta-interpreters are often themselves written on top of a Prolog interpreter. These cascaded layers of interpreters result in an enormous slow down, rendering the resulting system practically useless for all but a small number of toy applications. This paper will report on the implementation of a fast incremental metaProlog compiler. In the process, it will explore some of …

Go to article

An Attribute-Grammar Implementation Of Government-Binding Theory, Nelson Correa Jan 1987

An Attribute-Grammar Implementation Of Government-Binding Theory, Nelson Correa

Electrical Engineering and Computer Science - All Scholarship

The syntactic analysis of languages with respect to Government binding (GB) grammar is a problem that has received relatively little attention until recently. This paper describes an attribute grammar specification of the Government binding theory. The paper focuses on the description of the attribution rules responsible for determining antecedent trace relations in phrase-structure trees, and on some theoretical implications of those rules for the GB model. The specification relies on a transformation-le variant of Government "binding theory, briefly discussed by Chomsky (1981), in which the rule move-a is replaced by an interpretive rule. Here the interpretive rule is specified by …

Go to article

Mpj: A Proposed Java Message Passing Api And Environment For High Performance Computing, Mark Baker, Bryan Carpenter Jan 1987

Mpj: A Proposed Java Message Passing Api And Environment For High Performance Computing, Mark Baker, Bryan Carpenter

Northeast Parallel Architecture Center

In this paper we sketch out a proposed reference implementation for message passing in Java (MPJ), an MPI-like API from the Message-Passing Working Group of the Java Grande Forum [1,2]. The proposal relies heavily on RMI and Jini for finding computational resources, creating slave processes, and handling failures. User-level communication is implemented efficiently directly on top of Java sockets.

Go to article

The Design And Implementation Of A High-Speed Incremental Portable Prolog Compiler, Kenneth A. Bowen, Kevin A. Buettner, Ilyas Cicekli, Andrew Turk Nov 1985

The Design And Implementation Of A High-Speed Incremental Portable Prolog Compiler, Kenneth A. Bowen, Kevin A. Buettner, Ilyas Cicekli, Andrew Turk

Electrical Engineering and Computer Science - Technical Reports

The design and implementation of a relatively portable Prolog compiler achieving 12K LIPS on the standard benchmark is described. The compiler is incremental and uses decompilation to implement retract, clause, and listing, as well as support the needs of its four-port debugger. The system supports modules, garbage collection, database pointers, and a full range of built-ins.

Go to article

A Meta-Level Extension Of Prolog, Kenneth A. Bowen, Tobias Weinberg May 1985

A Meta-Level Extension Of Prolog, Kenneth A. Bowen, Tobias Weinberg

Electrical Engineering and Computer Science - Technical Reports

Prolog has many attractive features as a programming tool for artificial intelligence. These include code that is easy to understand, programs that are easy to modify, and a clear relation between its logical and procedural semantics. Moreover, it has proved possible to create clear and efficient implementations. Nonetheless, we perceive several shortcomings. Chief among these is difficulty representing dynamic databases (databases which change in time) and an apparent restriction to backward chaining, backtracking, and depth-first search. Our intent in this paper is to present an extension to Prolog, called metaProlog, which preserves the virtues of Prolog while introducing powerful constructions …

Go to article

A Finitary Retract Model For The Polymorphic Lambda-Calculus, Nancy Mccracken Jan 1982

A Finitary Retract Model For The Polymorphic Lambda-Calculus, Nancy Mccracken

Electrical Engineering and Computer Science - Technical Reports

There has been great interest in recent years in designing programming languages which permit functions which may accept types as parameters (polymorphic functions) and types with type parameters (type generators). Unfortunately the semantics of such functions and types has not been as well understood as their practical use in software design. In [McCracken 1979], a denotational semantics was given for a simple programming language with these features. The semantics used closures, which are a special case of the more familiar retractions, over the Scott universal domain, Pw to represent types. It was then possible to interpret polymorphic functions as continuous …

Go to article

Some Results On Optimum Premium Payment Plans, Jeyaraj Vadiveloo, Kishan Mehrotra, Kenneth Kaminsky Nov 1981

Some Results On Optimum Premium Payment Plans, Jeyaraj Vadiveloo, Kishan Mehrotra, Kenneth Kaminsky

Electrical Engineering and Computer Science - Technical Reports

Any insurance plan consists of a sequence of payments every year (or some other fixed time interval) in return for certain death benefits. The benefits may take the form of a wide variety of insurances or annuities. For simplicity, we will assume that premiums and benefits are paid annually. In this paper, we investigate the appropriateness of this type of plan. Naturally, appropriateness of any plan cannot be measured without an optimality criteria. Three such criteria, which are statistical in nature, are introduced in this paper. For the principal "safety" criterion which we use, the optimal premium are those which …

Go to article

On App Decoding, Carlos R.P. Hartmann, Luther D. Rudolph, Kishan Mehrotra, Guy J. Snedeker Jun 1981

On App Decoding, Carlos R.P. Hartmann, Luther D. Rudolph, Kishan Mehrotra, Guy J. Snedeker

Electrical Engineering and Computer Science - Technical Reports

In this paper we show that APP decoding for a linear code C is optimum not for C, but for a minimum-distance-2 code which contains C as a subcode when the codewords of are transmitted with equal probability. However, APP decoding is shown to be a symptotically optimum for C for high SNR when C is a binary one-step orthogonolizable code with equiprobable codewords transmitted over the AWGN channel.

Go to article

Application Of Information Theory To The Construction Of Efficient Decision Trees, Carlos R.P. Hartmann, Pramod Varshney, Kishan Mehrotra, Carl L. Gerberich Mar 1981

Application Of Information Theory To The Construction Of Efficient Decision Trees, Carlos R.P. Hartmann, Pramod Varshney, Kishan Mehrotra, Carl L. Gerberich

Electrical Engineering and Computer Science - Technical Reports

This paper treats the problem of conversion of decision tables to decision trees. In most cases, the construction of optimal decision trees is an NP-complete problem and, therefore, a heuristic approach to this problem is necessary. In our heuristic approach, we apply information theoretic concepts to construct efficient decision trees for decision tables which may include “don’t-care” entries. In contrast to most of the existing heuristic algorithms, our algorithm is systematic and has a sound theoretical justification. The algorithm has low design complexity and yet provides us with near-optimal decision trees.

Go to article

Bounds On The Number Of Samples Needed For Neural Learning, Kishan G. Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Jul 1980

Bounds On The Number Of Samples Needed For Neural Learning, Kishan G. Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

This paper addresses the relationship between the number of hidden layer nodes in a neural network, the complexity of a multi-class discrimination problem, and the number of samples needed for effective learning. Bounds are given for the latter. We show that Ω(min(d,n).M) boundary samples are required for successful classification of M clusters of samples using a 2 hidden layer neural network with d-dimensional inputs and n nodes in the first hidden layer.

Go to article

Computing Cyclic List Structures, F. Lockwood Morris, Jennifer Schwarz Jun 1980

Computing Cyclic List Structures, F. Lockwood Morris, Jennifer Schwarz

Electrical Engineering and Computer Science - Technical Reports

It is argued that list structures containing cycles are useful and unobjectionable Lisp entities. If this is so, it is desirable to have a means of computing them less foreign to the equational-definition style characteristic of Lisp than are the list-structure-altering primitives rplaca and rplacd. A notion is developed of a reasonable system of mutually recursive equations, guaranteed to have a unique solution in list structures. The notion is given in terms of the computations invoked by the equations, without reference to the forms of expressions appearing in them. A variety of programming examples are presented, including a curious implementation …

Go to article

An Information Theoretic Approach To The Construction Of Efficient Decision Trees, Jaime M. De Faria, Carlos R.P. Hartmann, Carl L. Gerberich, Pramod Varshney Jan 1980

An Information Theoretic Approach To The Construction Of Efficient Decision Trees, Jaime M. De Faria, Carlos R.P. Hartmann, Carl L. Gerberich, Pramod Varshney

Electrical Engineering and Computer Science - Technical Reports

This paper treats the problem of construction of efficient decision trees. Construction of optimal decision trees is an NP-complete problem and, therefore, a heuristic approach for the design of efficient decision trees is considered. The approach is based on information theoretic concepts and the proposed algorithm provides us with a simple procedure for the construction of near-optimal decision trees.

Go to article

First Prev Next Last