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

Physical Sciences and Mathematics Commons™

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

Syracuse University

1991

Electrical Engineering and Computer Science - Technical Reports

Articles 31 - 36 of 36

Full-Text Articles in Physical Sciences and Mathematics

A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang Mar 1991

A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang

Electrical Engineering and Computer Science - Technical Reports

Based on Fiting's Φ operator a unified framework for three-valued semantics of logic programming is presented. The truth space used in the framework is the class of partial interpretations. Underlying the truth space is two partial orderings, knowledge ordering and truth ordering. It turns out that the truth space with the truth ordering is a complete lattice and the truth space with knowledge ordering is a semi-complete lattice. Φ is proved to be continuous over the complete lattice and monotonic over the semi-complete lattice. With the use of Φ operator two well-known three-valued semantics for logic programming, Fitting's three-valued semantics …

Go to article

Duality In Logic Programming, Feng Yang Mar 1991

Duality In Logic Programming, Feng Yang

Electrical Engineering and Computer Science - Technical Reports

Various approximations of classic negation have been proposed for logic programming. But the semantics for those approximations are not entirely clear. In this paper a proof-theoretic operator, we call it failure operator, denoted as FP, is associated with each logic program to characterize the meaning of various negations in logic programming. It is shown that the failure operator FP is a dual of the TP, immediate consequence operator developed by Van Emden and Kowalski and is downward continuous. It has the desirable properties entirely analogous to what TP has such as continuity, having a unique least fixpoint and a unique …

Go to article

A Study Of Approximating The Moments Of The Job Completion Time In Pert Networks, Kishan Mehrotra, John Chai, Sharma Pillutla Mar 1991

A Study Of Approximating The Moments Of The Job Completion Time In Pert Networks, Kishan Mehrotra, John Chai, Sharma Pillutla

Electrical Engineering and Computer Science - Technical Reports

The importance of proper management of projects has not gone unrecognized in industry and academia. Consequently tools like Critical Path Method (CPM) and Program Evaluation Review Technique (PERT) for project planning have been the focus of attention of both practitioners and researchers. Determination of the Time to Complete the Job (TCJ) in PERT networks is important for planning and bidding purposes. The complexity involved in accurately determining the TCJ has led to the development of many approximating procedures. Most of them ignore the dependence between paths in the network. We propose an approximation to determine the TCJ which explicitly recognizes …

Go to article

A Practical Hierarchial Model Of Parallel Computation: The Model, Todd Heywood, Sanjay Ranka Feb 1991

A Practical Hierarchial Model Of Parallel Computation: The Model, Todd Heywood, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We introduce a model of parallel computation that retains the ideal properties of the PRAM by using it as a sub-model, while simultaneously being more reflective of realistic parallel architectures by accounting for and providing abstract control over communication and synchronization costs. The Hierarchical PRAM (H-PRAM) model controls conceptual complexity in the face of asynchrony in two ways. First, by providing the simplifying assumption of synchronization to the design of algorithms, but allowing the algorithms to work asynchronously with each other; and organizing this "control asynchrony" via an implicit hierarchy relation. Second, by allowing the restriction of "communication asynchrony" in …

Go to article

Average Dependence And Random Oracles (Preliminary Report), Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer Jan 1991

Average Dependence And Random Oracles (Preliminary Report), Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Electrical Engineering and Computer Science - Technical Reports

This paper is a technical investigation of issues in computational complexity theory relative to a random oracle. We introduce “average dependence,” an alternative method to Bennett and Gill’s “measure preserving map" technique and illustrate our technique by the following results.

Go to article

Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney Jan 1991

Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney

Electrical Engineering and Computer Science - Technical Reports

Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in Ө (log nlogm) time with Ө (mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less …

Go to article

First Prev