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

Physical Sciences and Mathematics Commons™

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

Computer Sciences

Claremont Colleges

Keyword
Publication Year
Publication
Publication Type

Articles 151 - 178 of 178

Full-Text Articles in Physical Sciences and Mathematics

Do We Really Know What Makes Educational Software Effective? A Call For Empirical Research On Effectiveness, Karen Jolicoeur, Dale E. Berger Nov 1986

Do We Really Know What Makes Educational Software Effective? A Call For Empirical Research On Effectiveness, Karen Jolicoeur, Dale E. Berger

CGU Faculty Publications and Research

Empirical information on specific factors that make educational software effective in reaching instructional objectives would be of considerable value. The authors describe the current state of evaluation research with educational software and discuss how popular software review methods fall short of meeting our need to know how well specific programs work.

Go to article

Computers And The Nature Of Man: A Historian's Perspective On Controversies About Artificial Intelligence, Judith V. Grabiner Oct 1986

Computers And The Nature Of Man: A Historian's Perspective On Controversies About Artificial Intelligence, Judith V. Grabiner

Pitzer Faculty Publications and Research

The purpose of the present paper is to provide a historical perspective on recent controversies, from Turing's time on, about artificial intelligence, and to make clear that these are in fact controversies about the nature of man. First, I shall briefly review three recent controversies about artificial intelligence, controversies over whether computers can think and over whether people are no more than information-processing machines. These three controversies were each initiated by philosophers who, irrespective of what the programs of their time actually did, viewed with alarm the argument that if a machine can think, a thinking being is just a …

Go to article

Distributed Recovery In Applicative Systems, Frank C. H. Lin, Robert M. Keller Aug 1986

Distributed Recovery In Applicative Systems, Frank C. H. Lin, Robert M. Keller

All HMC Faculty Publications and Research

Applicative systems are promising candidates for achieving high performance computing through aggregation of processors. This paper studies the fault recovery problems in a class of applicative systems. The concept of functional checkpointing is proposed as the nucleus of a distributed recovery mechanism. This entails incrementally building a resilient structure as the evaluation of an applicative program proceeds. A simple rollback algorithm is suggested to regenerate the corrupted structure by redoing the most effective functional checkpoints. Another algorithm, which attempts to recover intermediate results, is also presented. The parent of a faulty task reproduces a functional twin of the failed task. …

Go to article

Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger Jan 1986

Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.

Go to article

Approaching Distributed Database Implementations Through Functional Programming Concepts, Robert M. Keller, Gary Lindstrom May 1985

Approaching Distributed Database Implementations Through Functional Programming Concepts, Robert M. Keller, Gary Lindstrom

All HMC Faculty Publications and Research

The application of functional programming concepts to the data representation and querying aspects of databases has been discussed by Shipman and Buneman, et al. respectively. We argue the suitability of a function-based approach to additional aspects of database systems, including updating, transaction serialization, and physical distribution and communication. It is shown how the NmergeH extension of a purely functional model permits serializable concurrent "primary site" distribution control. We also present preliminary experimental results which indicate that a reasonable degree of concurrency is attainable from the functional approach.

Go to article

Simulated Performance Of A Reduction-Based Multiprocessing System, Robert M. Keller, Frank C. H. Lin Jul 1984

Simulated Performance Of A Reduction-Based Multiprocessing System, Robert M. Keller, Frank C. H. Lin

All HMC Faculty Publications and Research

Multiprocessing systems have the potential for increasing system speed over what is now offered by device technology. They must provide the means of generating work for the processors, getting the work to processors, and coherently collecting the results from the processors. For most applications, they should also ensure the repeatability of behavior, i.e., determinacy, speed-independence, or elimination of "critical races." Determinacy can be destroyed, for example, by permitting-in separate, concurrent processes statements such as "x: = x + 1" and "if x = 0 then… else…", which share a common variable. Here, there may be a critical race, in that …

Go to article

Rediflow Multiprocessing, Robert M. Keller, Frank C. H. Lin, Jiro Tanaka Feb 1984

Rediflow Multiprocessing, Robert M. Keller, Frank C. H. Lin, Jiro Tanaka

All HMC Faculty Publications and Research

We discuss the concepts underlying Rediflow, a multiprocessing system being designed to support concurrent programming through a hybrid model of reduction, dataflow, and von Neumann processes. The techniques of automatic load-balancing in Rediflow are described in some detail.

Go to article

Consistency Testing For Data-Flow Circuits, Chu S. Jhon, Robert M. Keller Jan 1984

Consistency Testing For Data-Flow Circuits, Chu S. Jhon, Robert M. Keller

All HMC Faculty Publications and Research

One means of making VLSI design tractable is to proceed from a high-level specification of a circuit in terms of functionality, to the circuit level. A notable error which may occur in a topdown design starting with a data-flow graph representation of a circuit is a design inconsistency due to deadlock. This paper attempts to further develop the theoretical basis for algorithms which analyze the deadlock property of circuits on the basis of their data-flow graph representations. A systematic scheme to verify the absence of deadlock in data-flow graphs is also presented.

Go to article

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis Jan 1984

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Πk-formulae of size n for which every Σk-formula has size exp Ω(n1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σk-formula of size exp O(n1/(k-1)). Thus our hierarchy theorem is the best possible.

Go to article

Specification Of Synchronizing Processes, Krithivasan Ramamritham, Robert M. Keller Nov 1983

Specification Of Synchronizing Processes, Krithivasan Ramamritham, Robert M. Keller

All HMC Faculty Publications and Research

The formalism of temporal logic has been suggested to be an appropriate tool for expressing the semantics of concurrent programs. This paper is concerned with the application of temporal logic to the specification of factors affecting the synchronization of concurrent processes. Towards this end, we first introduce a model for synchronization and axiomatize its behavior. SYSL, a very high-level language for specifying synchronization properties, is then described. It is designed using the primitives of temporal logic and features constructs to express properties that affect synchronization in a fairly natural and modular fashion. Since the statements in the language have intuitive …

Go to article

On Determinism Versus Non-Determinism And Related Problems, Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, William T. Trotter Jan 1983

On Determinism Versus Non-Determinism And Related Problems, Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, William T. Trotter

All HMC Faculty Publications and Research

We show that, for multi-tape Turing machines, non-deterministic linear time is more deterministic Turing machines (that receive their input on their work tape) require time Q(n2) to powerful than deterministic linear time. We also recognize non-palindromes of length n (it is easy to discuss the prospects for extending this result to see that time O(n log n) is. sufficient for a more general Turing machines. non-deterministic machine). 1. Introduction

Go to article

Course Syllabus: Perspectives On Computers And Society, Judith V. Grabiner Oct 1982

Course Syllabus: Perspectives On Computers And Society, Judith V. Grabiner

Pitzer Faculty Publications and Research

Weizenbaum's statement is a compelling exhortation to his fellow professionals; nevertheless, I cannot wholly agree. It should be possible for nonprofessionals to understand, as a result of their own reading and experience, how computers interact with the rest of human life. The problems are not just technical, and their nature is not entirely unprecedented.

Go to article

Data Flow Program Graphs, Alan L. Davis, Robert M. Keller Feb 1982

Data Flow Program Graphs, Alan L. Davis, Robert M. Keller

All HMC Faculty Publications and Research

Data flow languages form a subclass of the languages which are based primarily upon function application (i.e., applicative languages). By data flow language we mean any applicative language based entirely upon the notion of data flowing from one function entity to another or any language that directly supports such flowing. This flow concept gives data flow languages the advantage of allowing program definitions to be represented exclusively by graphs. Graphical representations and their applications are the subject of this article.

Go to article

Probabilistic Simulations, Nicholas J. Pippenger Jan 1982

Probabilistic Simulations, Nicholas J. Pippenger

All HMC Faculty Publications and Research

The results of this paper concern the question of how fast machines with one type of storage media can simulate machines with a different type of storage media. Most work on this question has focused on the question of how fast one deterministic machine can simulate another. In this paper we shall look at the question of how fast a probabilistic machine can simulate another. This approach should be of interest in its own right, in view of the great attention that probabilistic algorithms have recently attracted.

Go to article

Specifying And Proving Properties Of Sentinels, Krithivasan Ramamritham, Robert M. Keller Mar 1981

Specifying And Proving Properties Of Sentinels, Krithivasan Ramamritham, Robert M. Keller

All HMC Faculty Publications and Research

This paper presents a technique for specifying and verifying properties of "sentinels," a high-level language construct for synchronizing access to shared resources. Statements in the specification language possess formal temporal semantics. As a prelude to proving the correctness of sentinels, the semantics of constructs used in sentinels is given. The proof technique involves showing that the temporal behavior of a sentinel conforms to that defined by the specification. The methodology is illustrated by applying it to a typical synchronization problem.

Go to article

Algebraic Complexity Theory, Nicholas Pippenger Jan 1981

Algebraic Complexity Theory, Nicholas Pippenger

All HMC Faculty Publications and Research

Algebraic complexity theory, the study of the minimum number of operations sufficient to perform algebraic computations, is surveyed with emphasis on the general theory of bilinear forms and two of its applications: polynomial multiplication and matrix multiplication. Though by no means exhausting algebraic complexity theory, these topics illustrate well its development and its methods, and provide examples of its most striking successes.

Go to article

Hierarchical Analysis Of A Distributed Evaluator, Robert M. Keller, Gary Lindstrom Aug 1980

Hierarchical Analysis Of A Distributed Evaluator, Robert M. Keller, Gary Lindstrom

All HMC Faculty Publications and Research

We outline the analysis of a distributed evaluator for an applicative language FGL (Function Graph Language). Our goal is to show that the least fixed point semantics of FGL are faithfully implemented by the hardware evaluator envisioned in the Applicative Multi-Processor System AMPS. Included in the analysis are a formalization of demand-driven computation , the introduction of an intermediate graphic language IGL to aid in our proofs, and discussion of pragmatic issues involved in the AMPS machine language design.

Go to article

On The Evaluation Of Powers And Monomials, Nicholas Pippenger Jan 1980

On The Evaluation Of Powers And Monomials, Nicholas Pippenger

All HMC Faculty Publications and Research

Let $y_1 , \cdots ,y_p $ be monomials over the indeterminates $x_1 , \cdots ,x_q $. For every $y = (y_1 , \cdots ,y_p )$ there is some minimum number $L(y)$ of multiplications sufficient to compute $y_1 , \cdots ,y_p $ from $x_1 , \cdots ,x_q $ and the identity 1. Let $L(p,q,N)$ denote the maximum of $L(y)$ over all $y$ for which the exponent of any indeterminate in any monomial is at most $N$. We show that if $p = (N + 1^{o(q)} )$ and $q = (N + 1^{o(p)} )$, then $L(p,q,N) = \min \{ p,q\} \log N …

Go to article

Comparative Schematology And Pebbling With Auxiliary Pushdowns, Nicholas J. Pippenger Jan 1980

Comparative Schematology And Pebbling With Auxiliary Pushdowns, Nicholas J. Pippenger

All HMC Faculty Publications and Research

This paper has three claims to interest. First, it combines comparative schematology with complexity theory. This combination is capable of distinguishing among Strong's “languages of maximal power,” a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone. Secondly, this paper inaugurates the study of pebbling with auxiliary pushdowns, which bears to plain pebbling the same relationship as Cook's study of space-bounded machines with auxiliary pushdowns bears to plain space-bounded machines. This extension of pebbling serves as the …

Go to article

On The Application Of Coding Theory To Hashing, Nicholas Pippenger Jan 1979

On The Application Of Coding Theory To Hashing, Nicholas Pippenger

All HMC Faculty Publications and Research

Quick proofs are given for the characterization (due to Schay, Raver, Hanan, and Palermo) of the collision distance of a linear hashing function and for a dual function (called the restriction distance), which relates to the accessibility of addresses by sets of keys and the uniform distribution of sets of keys over addresses.

Go to article

Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder Jan 1979

Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder

All HMC Faculty Publications and Research

The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.

Go to article

Generalized Connectors, Nicholas Pippenger Jan 1978

Generalized Connectors, Nicholas Pippenger

All HMC Faculty Publications and Research

An $n$-connector is an acyclic directed graph having $n$ inputs and $n$ outputs and satisfying the following condition: given any one-to-one correspondence between inputs and distinct outputs, there exists a set of vertex-disjoint paths that join each input to the corresponding output. It is known that the minimum possible number of edges in an $n$-connector lies between lower and upper bounds that are asymptotic to $3n\log _3 n$ and $6n\log _3 n$ respectively. A generalized $n$-connector satisfies the following stronger condition: given any one-to-many correspondence between inputs and disjoint sets of outputs, there exists a set of vertex-disjoint trees that …

Go to article

Superconcentrators, Nicholas Pippenger Jan 1977

Superconcentrators, Nicholas Pippenger

All HMC Faculty Publications and Research

An $n$-superconcentrator is an acyclic directed graph with $n$ inputs and $n$ outputs for which, for every $r \leqq n$, every set of $r$ inputs, and every set of $r$ outputs, there exists an $r$-flow (a set of $r$ vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist $n$-superconcentrators with $39n + O(\log n)$ (in fact, at most $40n$) edges, depth $O(\log n)$, and maximum degree (in-degree plus out-degree) 16.

Go to article

Towards A Theory Of Universal Speed-Independent Modules, Robert M. Keller Jan 1974

Towards A Theory Of Universal Speed-Independent Modules, Robert M. Keller

All HMC Faculty Publications and Research

Of concern here are asynchronous modules, i.e., those whose activity is regulated by initiation and completion signals with no clocks being present. First a number of operating conditions are described that are deemed essential or useful in a system of asynchronous modules, while retaining an air of independence of particular hardware implementations as much as possible. Second, some results are presented concerning sets of modules that are universal with respect to these conditions. That is, from these sets any arbitrarily complex module may be constructed as a network. It is stipulated that such constructions be speed independent, i.e., independent of …

Go to article

A Novel Method Of Constructing Sorting Networks, Robert M. Keller Jan 1973

A Novel Method Of Constructing Sorting Networks, Robert M. Keller

All HMC Faculty Publications and Research

The construction of sorting networks has been a topic of much recent discussion. In view of the apparent difficulty of verifying whether a reasonably large proposed sorting network actually does sort, the most useful approach for constructing large networks seems to be to devise a recursive scheme which constructs a network which is guaranteed to sort, obviating the verification phase. In this note, another such approach is presented.

Go to article

On The Decomposition Of Asynchronous Systems, Robert M. Keller Oct 1972

On The Decomposition Of Asynchronous Systems, Robert M. Keller

All HMC Faculty Publications and Research

This paper reports of part of a continuing investigation of parallel computation, in particular, efforts toward understanding the nature of different types of parallel control. The first section defines an asynchronous system to be a simple type of state machine. This was arrived at in an attempt to generalize from the types of control in parallel program schemata and networks of asynchronous modules without bounded delays. Asynchronous systems with output are also defined in a familiar way. The deviation from standard work comes in the definition of a parallel decomposition of asynchronous systems. Some preliminary work on compositions of this …

Go to article

On Maximally Parallel Schemata, Robert M. Keller Oct 1970

On Maximally Parallel Schemata, Robert M. Keller

All HMC Faculty Publications and Research

A model for parallel computation called a schema is presented. This model is similar to that presented in the recent work of Karp and Miller. Section 1 presents a description of the model, and some results on the characterization of computations within it. Section 2 summarizes some results on determinacy and equivalence. Section 3 presents a formalization of the property of maximal parallelism in schemata. Several alternate characterizations are shown to be equivalent for certain classes. Section 4 presents results on the complexity of a maximally parallel schema equivalent to a given schema.

Go to article

Problems Encountered With Control Networks In Highly-Restructurable Digital Systems, Donald F. Wann, Robert A. Ellis, Mishell J. Stucki, Robert M. Keller Sep 1967

Problems Encountered With Control Networks In Highly-Restructurable Digital Systems, Donald F. Wann, Robert A. Ellis, Mishell J. Stucki, Robert M. Keller

All HMC Faculty Publications and Research

This paper discusses problems encountered with control networks in highly restructurable digital systems. In particular the treatment of implementation errors is covered with emphasis on concurrent processing. The implementation of concurrent processing networks may result in errors which will be quite complex to detect and systematic methods are warranted. Four meta control elements are employed in obtaining convenient concurrent structures. We analyze several error detecting schemes and conclude that the arc-node method with node partitioning appears to be the most realistic approach at this time.

Go to article

First Prev