Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Algorithms (11)
- Codes (8)
- Logic programming (8)
- Logic (7)
- Neural networks (6)
-
- Semantics (6)
- Programming (5)
- Parallel algorithms (4)
- Parallel computing (4)
- Deadlock detection (3)
- Decoding (3)
- Reasoning (3)
- Simulated annealing (3)
- Sorting (3)
- Static analysis (3)
- Block codes (2)
- Combinational circuits (2)
- Communicating agents (2)
- Concurrent programming (2)
- Concurrent programs (2)
- Data allocation (2)
- Data partitioning (2)
- Decision trees (2)
- Fast Fourier transform (2)
- Formal verification (2)
- Generic algorithms (2)
- Genetic algorithms (2)
- Householder reduction (2)
- Hypercube (2)
- ISR-PRAM (2)
Articles 31 - 60 of 178
Full-Text Articles in Physical Sciences and Mathematics
Fluted Formulas And The Limits Of Decidability, William C. Purdy
Fluted Formulas And The Limits Of Decidability, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
In the predicate calculus, variables provide a flexible indexing service that selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be fluted. Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the …
A Domain-Specific Parallel Programming System I: Design And Application To Ecological Modelling, Elaine Wenderholm, Micah Beck
A Domain-Specific Parallel Programming System I: Design And Application To Ecological Modelling, Elaine Wenderholm, Micah Beck
Electrical Engineering and Computer Science - Technical Reports
The goal of the εm project is to make parallel programming easily accessible to a broad community of scientists. Previous approaches such as the use of general parallel programming languages and parallelizing compilers for sequential languages have fallen short in this respect. The approach is to design a special purpose programming language which is oriented towards a specific area of application. The result is a specialized and effective scientific tool. εm is a high-level programming system which puts parallelism into the hands of scientists who are not sophisticated programmers. By restricting and simplifying the programming interface, εm eases both the …
Analysis Of Myoelectrical Signals For Building A Dextrous Hand, Christopher T. Creel, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Analysis Of Myoelectrical Signals For Building A Dextrous Hand, Christopher T. Creel, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
We analyze techniques for myoelectrical signals classification for the purpose of designing a multifunctional prosthetic device for human amputees. The main advantage of our system over existing models is that it is more robust, easier to work with, more general, and efficient enough to run in real time. We achieve this with the help of "Supervised Growing Cell Structures." an artificial neural network model designed by Fritzke [10]. The current paper focuses on the flexion of the index, middle and ring fingers, as these are the most difficult movements to tackle.
Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
We present a new "knowledge-based non-uniform crossover" (KNUX) operator for genetic algorithms (GA's) that generalizes uniform crossover. We extend this to "Dynamic KNUX" (DKNUX), which constantly updates the knowledge extracted so far from the environment's feedback on previously generated chromosomes. KNUX can improve on good solutions previously obtained by using other algorithms. The modifications made by KNUX are orthogonal to other changes in parameters of GA's, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving the move-selection procedures, after having chosen a fixed move-generation mechanism, KNUX and DKNUX make the move-generation …
Decoding Linear Block Codes Using A Priority-First Search: Performance Analysis And Suboptimal Version, Yunghsiang S. Han, Carlos R.P. Hartmann, Kishan Mehrotra
Decoding Linear Block Codes Using A Priority-First Search: Performance Analysis And Suboptimal Version, Yunghsiang S. Han, Carlos R.P. Hartmann, Kishan Mehrotra
Electrical Engineering and Computer Science - Technical Reports
An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's Algorithm was proposed by Han, Hartmann, and Chen. In this report we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computation performance of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB and 0.5 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code and the (128, 64) …
Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Genetic Algorithms For Soft Decision Decoding Of Linear Block Codes, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104, 52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 30,000 codewords, whereas the search space contains 4.5 x 1015 codewords. We define a new crossover operator that exploits domain-specific information and compare it …
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
Electrical Engineering and Computer Science - Technical Reports
We propose that the phenomenon of local state may be understood in terms of Strachey's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of locally-declared variables in the same way that a parametrically polymorphic function is independent of types to which it is instantiated. A connection between parametricity and representational abstraction was first suggested by J. C. Reynolds. Reynolds used logical relations to formalize this connection in languages with type variables and user-defined types. We use relational parametricity to construct a model for an Algol-like language in …
On Inverse Sigmoid Functions, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
On Inverse Sigmoid Functions, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
Networks with sigmoid node functions have been shown to be universal approximators, and can use straightforward implementations of learning algorithms. Mathematically, what is common to different sigmoid functions used by different researchers? We establish a common representation of inverse sigmoid functions in terms of the Guass Hypergeometric function, generalizing different node function formulations. We also show that the continuous Hopfield network equation can be transformed into a Legendre differential equation, without assuming the specific form of the node function; this establishes a link between Hopfield nets and the method of function approximation using Legendre polynomials
Putting Humpty-Dumpty Together Again: Reconstructing Functions From Their Projections., Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Putting Humpty-Dumpty Together Again: Reconstructing Functions From Their Projections., Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
We present a problem decomposition approach to reduce neural net training times. The basic idea is to train neural nets in parallel on marginal distributions obtained from the original distribution (via projection), and then reconstruct the original table from the marginals (via a procedure similar to the join operator in database theory). A function is said to be reconstructible, if it may be recovered without error from its projections. Most distributions are non-reconstructible. The main result of this paper is the Reconstruction theorem, which enables non-reconstructible functions to be expressed in terms of reconstructible ones, and thus facilitates the application …
A Generalization Of The Trie Data Structure, Richard H. Connelly, F. Lockwood Morris
A Generalization Of The Trie Data Structure, Richard H. Connelly, F. Lockwood Morris
Electrical Engineering and Computer Science - Technical Reports
Tries, a form of string-indexed look-up structure, are generalized to permit indexing by terms built according to an arbitrary signature. The construction is parametric with respect to the type of data to be stored as values; this is essential, because the recursion which defines tries appeals from one value type to others. "Trie" (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism. The trie functor is in principle definable by the "initial fixed point" semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the "category-cpo", a class of category …
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Electrical Engineering and Computer Science - Technical Reports
ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …
Binary Resolution In Surface Reasoning, William C. Purdy
Binary Resolution In Surface Reasoning, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
Intuition suggests the hypothesis that everyday human reasoning is conducted in the written or spoken natural language, rather than in some disparate representation into which the surface language is translated. An examination of human reasoning reveals patterns of inference that parallel binary resolution. But any standard implementation of resolution requires Skolemization. Skolemization would seem an unlikely component of human reasoning. This appears to contradict the hypothesis that human reasoning takes place at the surface. To reconcile these observations, this paper develops a new rule of inference, which operates on surface expressions directly. This rule is shown to produce results which …
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.
All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang
All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang
Electrical Engineering and Computer Science - Technical Reports
In this paper we present several algorithms for all-too-many personalized communications which avoid node contention.
Simulated Annealing, Per Brinch Hansen
Simulated Annealing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.
Parallel Monte Carlo Trials, Per Brinch Hansen
Parallel Monte Carlo Trials, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
The best results of Monte Carlo methods are generally obtained by performing the same computation many times with different random numbers. We develop a generic algorithm for parallel execution of Monte Carlo trials on a multicomputer. The generic algorithm has been adapted for simulated annealing and primality testing by simple substitutions of data types and procedures. The performance of the parallel algorithms was measured on a Computing Surface.
Primality Testing, Per Brinch Hansen
Primality Testing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Electrical Engineering and Computer Science - Technical Reports
In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair
Electrical Engineering and Computer Science - Technical Reports
We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …
Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary
Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary
Electrical Engineering and Computer Science - Technical Reports
In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
Electrical Engineering and Computer Science - Technical Reports
This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.
A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris
A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris
Electrical Engineering and Computer Science - Technical Reports
A miniswap Si,1 ≤ i < n, compares two adjacent keys Пi, Пi+1 in the sequence (П1, ... , Пn), and transposes them if they are out of order. A full sweep is any composition of all n - 1 possible miniswaps. We prove that the composition of any n- 1 full sweeps is a sorting function.
Conceptual Background For Symbolic Computation, Klaus Berkling
Conceptual Background For Symbolic Computation, Klaus Berkling
Electrical Engineering and Computer Science - Technical Reports
This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …
Fault-Detection In Networks, H. F. Mattson Jr
Fault-Detection In Networks, H. F. Mattson Jr
Electrical Engineering and Computer Science - Technical Reports
To find broken links in networks we use the cut-set space. Information on which nodes can talk, or not, to which other nodes allows reduction of the problem to that of decoding the cut-set code of a graph. Special classes of such codes are known to have polynomial-time decoding algorithms. We present a simple algorithm to achieve the reduction and apply it in two examples.
A Declarative Foundation Of Λprolog With Equality, Mino Bai
A Declarative Foundation Of Λprolog With Equality, Mino Bai
Electrical Engineering and Computer Science - Technical Reports
We build general model-theoretic semantics for higher-order logic programming languages. Usual semantics for first-order logic is two-level: i.e., at a lower level we define a domain of individuals, and then, we define satisfaction of formulas with respect to this domain. In a higher-order logic which includes the propositional type in its primitive set of types, the definition of satisfaction of formulas is mutually recursive with the process of evaluation of terms. As result of this in higher-order logic it is extremely difficult to define an effective semantics. For example to define T p operator for logic program P, we need …
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf
Electrical Engineering and Computer Science - Technical Reports
This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be computed by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs …
Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka
Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
This paper presents benchmarking results for image processing algorithms on the Connection Machine model CM-5 and compares them with the results from the CM-2 and the Sun-4. Image processing algorithms with varying communication and computational requirements were implemented, tested and timed. The performance and the scalabilty of the CM-5 were analyzed and compared with that of the CM-2.
A Note On Many-One And 1-Truth-Table Complete Languages, Steven Homer, Stuart A. Kurtz, James S. Royer
A Note On Many-One And 1-Truth-Table Complete Languages, Steven Homer, Stuart A. Kurtz, James S. Royer
Electrical Engineering and Computer Science - Technical Reports
The polynomial time 1-tt complete sets for EXP and RE are polynomial time many-one complete.