Physical Sciences and Mathematics Commons^™

Uniqueness Of Positive Solutions For A Class Of Elliptic Boundary Value Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

Uniqueness of non-negative solutions conjectured in an earlier paper by Shivaji is proved. Our methods are independent of those of that paper, where the problem was considered only in a ball. Further, our results apply to a wider class of nonlinearities.

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 Ω(n^1/(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(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Alkali Oxides. Analysis Of Bonding And Explanation Of The Reversal Of Ordering Of The 2Σ And 2Π States, Janet N. Allison, Robert J. Cave, William A. Goddard Iii

All HMC Faculty Publications and Research

We analyze the bonding in alkali oxides, MO, for M = Li, Na, K, Rb, and Cs. Using ab initio correlated wave functions we find that the ground state is ²II for M = Li, Na, and K and that the ground state is ²Ʃ^+ for M = Rb and Cs. The origin of this effect is explained.

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 …

The Changing Concept Of Change: The Derivative From Fermat To Weierstrass, Judith V. Grabiner

Pitzer Faculty Publications and Research

Historically speaking, there were four steps in the development of today's concept of the derivative, which I list here in chronological order. The derivative was first used; it was then discovered; it was then explored and developed; and it was finally defined. That is, examples of what we now recognize as derivatives first were used on an ad hoc basis in solving particular problems; then the general concept lying behind them these uses was identified (as part of the invention of calculus); then many properties of the derivative were explained and developed in applications both to …

Who Gave You The Epsilon? The Origins Of Cauchy's Rigorous Calculus, Judith V. Grabiner

Pitzer Faculty Publications and Research

This paper recounts the history of how calculus came to get a rigorous basis in terms of the algebra of inequalities. The result is a brief history of the 150 years from Newton and Leibniz to Cauchy that produced the foundations of analysis.

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

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.

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.

Sums Of Z-Ideals And Semiprime Ideals, Melvin Henriksen, Frank A. Smith

All HMC Faculty Publications and Research

If B is a ring (or module), and K is an ideal (or submodule) of B, let B(K) = {(a,b) є B x B:a-b є K}. The relationship between ideals (or submodules) of B and those of B(K) is examined carefully, and this construction is used to find a lattice-ordered subring of the ring C(R) of all continuous real-valued functions on the real line R with two z-ideals whose sum is not even semiprime.

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.

Results On Periodic Solutions Of Parabolic Equations Suggested By Elliptic Theory, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

No abstract provided.

Reduction Methods Via Minimax, Alfonso Castro

All HMC Faculty Publications and Research

Lecture notes in mathematics originally published in Differential Equations book series.

On Multiple Solutions Of Nonlinear Elliptic Equations With Odd Nonlinearities, Alfonso Castro, J. V. A. Gonçalves

All HMC Faculty Publications and Research

In this paper we stablish results on multiplicity of solutions for the boundary value problem where a e IR and f: R - IR is an odd continuous function.

Rearrangeable Networks With Limited Depth, Nicholas Pippenger, Andrew C.-C. Yao

All HMC Faculty Publications and Research

Rearrangeable networks are switching systems capable of establishing simultaneous independent communication paths in accordance with any one-to-one correspondence between their n inputs and n outputs. Classical results show that Ω( n log n ) switches are necessary and that O( n log n ) switches are sufficient for such networks. We are interested in the minimum possible number of switches in rearrangeable networks in which the depth (the length of the longest path from an input to an output) is at most k, where k is fixed as n increases. We show that Ω( n^{1 + 1/k} ) switches …

Some Properties Of Positive Derivations On F-Rings, Melvin Henriksen, Frank A. Smith

All HMC Faculty Publications and Research

Throughout A denotes an f-ring; that is, a lattice-ordered ring that is a subdirect union of totally ordered rings. We let D(A) denote the set of derivations D: A --> A such that a ≥ 0 implies Da ≥ 0, and we call such derivations positive. In [CDK], P. Coleville, G. Davis, and K. Keimel initiated a study of positive derivations on f-rings. Their main results are (i) D ε D(A) and A archimedean imply D = 0, and (ii) if A has an identity element 1 and a is the supremum of a set …

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.

The Design Of Oxygen Rebreather Equipment For Use In Foul-Air Speleology, Donald A. Mcfarlane

WM Keck Science Faculty Papers

The design of a lightweight oxygen rebreather set suitable for short duration explorations in foul-air caves is described, together with a discussion of its performance, limitations, and possible improvement.

On Periodic Solutions Of Weakly Coupled Systems Of Differential Equations, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

No abstract provided.

Bounds On The Performance Of Protocols For A Multiple-Access Broadcast Channel, Nicholas Pippenger

All HMC Faculty Publications and Research

A general model is presented for synchronous protocols that resolve conflicts among message transmissions to a multiple-access broadcast channel. An information-theoretic method is used now to show that if only finitely many types of conflicts can be distinguished by the protocol, utilization of the channel at rates approaching capacity is impossible. A random-coding argument is used to show that if the number of conflicting transmissions can be determined (which requires distinguishing infinitely many types of conflicts) then utilization of the channel at rates arbitrarily close to capacity can be achieved.

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.

Existence And Uniqueness For A Variational Hyperbolic System Without Resonance, Peter W. Bates, Alfonso Castro

All HMC Faculty Publications and Research

In this paper, we study the existence of weak solutions of the problem

□u + ∇G(u) = f(t,x) ; (t,x) є Ω ≡ (0,π)x(0,π)

u(t,x) = 0 ; (t,x) є ∂Ω

where □ is the wave operator ∂²/∂t² - ∂²/∂x², G: Rⁿ→R is a function of class C² such that ∇G(0) = 0 and f:Ώ→R^n is a continuous function having first derivative with respect to t in (L₂,(Ω))ⁿ and satisfying

f(0,x) = f(π,x) = 0

for all x є [0,π].

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.

Závisí Matematická Pravda Od Času?, Judith V. Grabiner

Pitzer Faculty Publications and Research

This is a Slovak translation of Judith Grabiner's "Is Mathematical Truth Time-Dependent?," published in Volume 81 of American Mathematical Monthly (April 1974).

Liverpool University Expedition To Jamaica, Donald A. Mcfarlane

WM Keck Science Faculty Papers

During summer 1977, five members of the Liverpool University Potholing Club spent six weeks working and exploring in the caves of Jamaica. The team consisted of Don McFarlane, John Dye, Malcolm Macduff, Mike Roger and Barry Williams, all of whom contributed to this report. The expedition base was at Troy, where the villagers are owed a debt of gratitude for their hospitality. This placed the expedition in the heart of the cave region, and a number of new caves and shafts were discovered and explored. The main discovery was the Still Waters Cave, located near Accompong, where 11,800 feet of …

A New Lower Bound For The Number Of Switches In Rearrangeable Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

For the commonest model of rearrangeable networks with $n$ inputs and $n$ outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches. Similar lower bounds for other models are also presented.

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 …

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 …

Two Point Boundary Value Problem With Jumping Nonlinearities, Alfonso Castro

All HMC Faculty Publications and Research

We prove that a certain two point BVP with jumping nonlinearities has a solution. Our result generalizes that of [2]. We use variational methods which permit giving a minimax characterization of the solution. Our proof exposes the similarities between the variational behavior of this problem and that of other semilinear problems with noninvertible linear part (see [5]).

James Eights, Albany Naturalist: New Evidence, Char Miller, Naomi Goldsmith

Pomona Faculty Publications and Research

Eights's contributions to scientific study and to the popularization of science have been understated and misunderstood.