Computer Science
http://hdl.handle.net/1813/517
Fri, 22 Apr 2016 15:40:24 GMT2016-04-22T15:40:24ZComputer Sciencehttps://ecommons.cornell.edu:443/bitstream/id/3383/banner2.gif
http://hdl.handle.net/1813/517
A Calculus for Flow-Limited Authorization: Technical Report
http://hdl.handle.net/1813/42406
A Calculus for Flow-Limited Authorization: Technical Report
Arden, Owen; Myers, Andrew C.
Real-world applications routinely make authorization decisions based on dynamic computation. Reasoning about dynamically computed authority is challenging. Integrity of the system might be compromised if attackers can improperly influence the authorizing computation. Confidentiality can also be compromised by authorization, since authorization decisions are often based on sensitive data such as membership lists and passwords. Previous formal models for authorization do not fully address the security implications of permitting trust relationships to change, which limits their ability to reason about authority that derives from dynamic computation. Our goal is a way to construct authorization mechanisms that do not violate confidentiality or integrity.
We introduce the Flow-Limited Authorization Calculus (FLAC), which is both a simple, expressive model for reasoning about dynamic authorization and also a language for securely implementing various authorization mechanisms. FLAC is an extension of the Dependency Core Calculus, incorporating the Flow-Limited Authorization Model. FLAC provides strong end-to-end information security guarantees even for programs that incorporate and implement rich dynamic authorization mechanisms. These guarantees include noninterference and robust declassification, which prevent attackers from influencing information disclosures in unautho- rized ways. We prove these security properties formally for all FLAC programs and explore the expressiveness of FLAC with several examples.
Sat, 13 Feb 2016 00:00:00 GMThttp://hdl.handle.net/1813/424062016-02-13T00:00:00ZJRIF: Reactive Information Flow Control for Java
http://hdl.handle.net/1813/41194
JRIF: Reactive Information Flow Control for Java
Kozyri, Elisavet; Arden, Owen; Myers, Andrew C.; Schneider, Fred B.
A reactive information flow (RIF) automaton for a value v specifies (i) allowed uses for v and (ii) the RIF automaton for any value that might be directly or indirectly derived from v. RIF automata thus specify how transforming a value alters how the result might be used. Such labels are more expressive than existing approaches for controlling downgrading. We devised a type system around RIF automata and incorporated it into Jif, a dialect of Java that supports a classic form of labels for information flow. By implementing a compiler for the resulting JRIF language, we demonstrate how easy it is to replace a classic information-flow type system by a more expressive RIF-based type system. We programmed two example applications in JRIF, and we discuss insights they provide into the benefits of RIF-based security labels.
Fri, 12 Feb 2016 00:00:00 GMThttp://hdl.handle.net/1813/411942016-02-12T00:00:00ZA Conversation with Fred Schneider
http://hdl.handle.net/1813/41370
A Conversation with Fred Schneider
Schneider, Fred B.; Gries, David
Fred Schneider, an expert in concurrent and distributed systems and in computer and cybersecurity, shares insights about how his professional interests evolved, and provides sweeping views about how his field and department have changed.
Wed, 09 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/413702015-09-09T00:00:00ZA Conversation with Claire Cardie
http://hdl.handle.net/1813/41216
A Conversation with Claire Cardie
Cardie, Claire; Constable, Robert L.
Claire Cardie discusses the role of Gerard Salton, natural language processing and the creation of the Information Science Department.
Wed, 09 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/412162015-09-09T00:00:00ZA Conversation with Ken Birman
http://hdl.handle.net/1813/41207
A Conversation with Ken Birman
Birman, Ken; Van Renesse, Robbert
Ken Birman discusses the origins of cloud computing.
Thu, 10 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/412072015-09-10T00:00:00ZA Conversation with Dexter Kozen
http://hdl.handle.net/1813/41206
A Conversation with Dexter Kozen
Kozen, Dexter; Constable, Robert L.
Kozen discusses his experiences at Cornell – his research and teaching experience, textbooks, participation in sports & music, etc.
Wed, 09 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/412062015-09-09T00:00:00ZA Conversation with Charlie Van Loan
http://hdl.handle.net/1813/41201
A Conversation with Charlie Van Loan
Van Loan, Charlie; Bala, Kavita
Van Loan discusses his experiences with teaching, writing textbooks, administering degree programs, MatLab, matrices and more.
Tue, 15 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/412012015-09-15T00:00:00ZA Conversation with Tim Teitelbaum
http://hdl.handle.net/1813/40865
A Conversation with Tim Teitelbaum
Teitelbaum, Tim; Gries, David
A discussion of the teaching of large, introductory courses in programming in the early days-using the Terak and Macintosh computers and
the development of integrated programming environments that implement language-aware editing capabilities.
Thu, 10 Sep 2015 00:00:00 GMThttp://hdl.handle.net/1813/408652015-09-10T00:00:00ZA Conversation with David Gries
http://hdl.handle.net/1813/40576
A Conversation with David Gries
Gries, David; Constable, Robert L.
Tue, 21 Jul 2015 00:00:00 GMThttp://hdl.handle.net/1813/405762015-07-21T00:00:00ZA Conversation with John E. Hopcroft
http://hdl.handle.net/1813/40568
A Conversation with John E. Hopcroft
Hopcroft, John E.; Gries, David
This ACM Turing Award recipient talks about research, textbooks, working with graduate students, his role as a senior statesman of his field and concludes with some words of wisdom.
Tue, 21 Jul 2015 00:00:00 GMThttp://hdl.handle.net/1813/405682015-07-21T00:00:00ZA Conversation with Richard W. Conway
http://hdl.handle.net/1813/40564
A Conversation with Richard W. Conway
Conway, Richard W.; Gries, David
Tue, 21 Jul 2015 00:00:00 GMThttp://hdl.handle.net/1813/405642015-07-21T00:00:00ZA Conversation with Robert L. Constable
http://hdl.handle.net/1813/40560
A Conversation with Robert L. Constable
Constable, Robert L.; Gries, David
Tue, 21 Jul 2015 00:00:00 GMThttp://hdl.handle.net/1813/405602015-07-21T00:00:00ZA Conversation with Anil Nerode
http://hdl.handle.net/1813/40527
A Conversation with Anil Nerode
Nerode, Anil; Gries, David
Thu, 16 Oct 2014 00:00:00 GMThttp://hdl.handle.net/1813/405272014-10-16T00:00:00ZFlow-Limited Authorization
http://hdl.handle.net/1813/40138
Flow-Limited Authorization
Arden, Owen; Liu, Jed; Myers, Andrew
Because information flow control mechanisms often rely on an underlying
authorization mechanism, their security guarantees can be
subverted by weaknesses in authorization. Conversely, the security
of authorization can be subverted by information flows that
leak information or that influence the delegation of authority among
principals.
We argue that interactions between information flow and authorization
create security vulnerabilities that have not been fully identified or
addressed in prior work.
We explore how the security of decentralized information
flow control (DIFC) is affected by
three aspects of its underlying authorization mechanism: first,
delegation of authority between principals; second, revocation of
previously delegated authority; third, information flows created by
the authorization mechanisms themselves. It is no surprise
that revocation poses challenges, but we show that even delegation
is problematic because it enables unauthorized
downgrading. Our solution is a new security model, the Flow-Limited
Authorization Model (FLAM), which offers a new, integrated approach to
authorization and information flow control.
FLAM ensures robust authorization, a novel security condition for
authorization queries that ensures attackers cannot influence
authorization decisions or learn confidential trust relationships.
We discuss our prototype implementation and its algorithm for
proof search.
Content file updated at author's request on 2015-06-04.
Fri, 08 May 2015 00:00:00 GMThttp://hdl.handle.net/1813/401382015-05-08T00:00:00ZA Conversation with Juris Hartmanis
http://hdl.handle.net/1813/14934
A Conversation with Juris Hartmanis
Hartmanis, Juris
Juris Hartmanis is video taped in a far-reaching conversation (70 minutes) with colleague David Gries. They discuss Hartmanis’ childhood and family background and his immigration to the United States. Next they trace his extraordinary career at the GE Research Laboratory, where he collaborated with Richard Stearns on pioneering research that eventually was recognized by ACM’s prestigious, highest honor – the Turing Award. After having served earlier as an Instructor in Cornell’s Mathematics Department, Juris returned to Cornell as a full professor and the founding chair of a new department of Computer Science. This Department was embedded in two colleges, Engineering
and Arts and Sciences. Cornell was among the first Universities to establish a Department of Computer Science. His pioneering work on computational
complexity blossomed into a new field and under his leadership the Computer Science department matured into a robust, national leader with a strong theoretical emphasis.
After a successful stint at the National Science Foundation leading the transition
of the academic research network NSFnet to become the Internet, he returned to Cornell. At Cornell he continues an active program of research and maintains a leadership role in developing information technologies that have become a ubiquitous element across the entire Cornell academic scene.
Wed, 31 Mar 2010 00:00:00 GMThttp://hdl.handle.net/1813/149342010-03-31T00:00:00ZA Linear List Merging Algorithm
http://hdl.handle.net/1813/10810
A Linear List Merging Algorithm
Hopcroft, John E.; Ullman, Jeffrey D.
A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and to find the name of the list currently containing a given element. If the length of the sequence of requests is bounded by a constant times n, then the execution time of the algorithm on a random access computer is bounded by a constant times n.
Wed, 14 May 2008 13:42:16 GMThttp://hdl.handle.net/1813/108102008-05-14T13:42:16ZOn the Modelling Power of Petri Nets
http://hdl.handle.net/1813/7516
On the Modelling Power of Petri Nets
Meiling, Erik
The behavior of a Petri net is expressed as a formal language. Certain families of Petri net languages are characterized by propositions similar to the classical pumping theorems. The results are used to give examples of behaviors that cannot be expressed by languages in these families.
Sat, 01 Dec 1979 00:00:00 GMThttp://hdl.handle.net/1813/75161979-12-01T00:00:00ZCand and Cor Before and Then or Else in Ada
http://hdl.handle.net/1813/7515
Cand and Cor Before and Then or Else in Ada
Gries, David
NO ABSTRACT SUPPLIED
Thu, 01 Nov 1979 00:00:00 GMThttp://hdl.handle.net/1813/75151979-11-01T00:00:00ZA Proof Technique for Communicating Sequential Processes(With an Example)
http://hdl.handle.net/1813/7514
A Proof Technique for Communicating Sequential Processes(With an Example)
Levin, Gary Marc
We present proof rules for an extension of the Communicating Sequential Processes proposed by Hoare. The send and receive statements are treated symmetrically, simplifying the rules and allowing send to appear in guards. An example is given to explain the use of the technique. This is an outline of a substantial part of a PhD thesis that is expected to be completed in June 1980.
Thu, 01 Nov 1979 00:00:00 GMThttp://hdl.handle.net/1813/75141979-11-01T00:00:00ZOn Linear Natural Deduction
http://hdl.handle.net/1813/7513
On Linear Natural Deduction
Leivant, Daniel
NO ABSTRACT SUPPLIED
Thu, 01 Nov 1979 00:00:00 GMThttp://hdl.handle.net/1813/75131979-11-01T00:00:00ZThe System Architecture for CORE: A Tolerant Program Development Environment
http://hdl.handle.net/1813/7512
The System Architecture for CORE: A Tolerant Program Development Environment
Archer, James E., Jr.; Conway, Richard W.; Shore, Andrew I.; Silver, Leonard S.
CORE is a program development environment intended primarily to explore a highly tolerant useer interface. In some respects the internal architecture is also novel. It permits a highly interactive and supportive user interface to be implemented with processing routines which are essentially oblivious to any user interaction.
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75121979-10-01T00:00:00ZA Program Development System Execution Supervisor
http://hdl.handle.net/1813/7511
A Program Development System Execution Supervisor
Archer, James E., Jr.; Shore, Andrew I.
The Cornell Program Development System is an experimental vehicle to explore the applicability of highly cooperative tactics to a contemporary development environment. The CPDS provides significant facilities for modifying and immediately executing programs. The execution supervisor and the internal user program representation it uses to implement these facilities are described.
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75111979-10-01T00:00:00ZQuadratic Programming with M-Matrices
http://hdl.handle.net/1813/7510
Quadratic Programming with M-Matrices
Luk, Franklin T.; Pagano, Marcello
In this paper, we study the problem of quadratic programming with M-matrices. We describe (1) an effective algorithm for the case where the variables are subject to a lower bound constraint, and (2) an analogous algorithm for the case where the variables are subject to lower and upper bounds constraints. We demonstrate the special monotone behavior of the iterate and gradient vectors. The result on the gradient vector is new. It leads us to consider a simple updating procedure which preserves the monotonicity of both vectors. The procedure uses the fact that an M-matrix has a non-negative inverse. Two new algorithms are then constructed by incorporating this updating procedure into the two given algorithms. We give numerical examples which show that the new methods can be more efficient than the original ones.
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75101979-10-01T00:00:00ZAda/CS - An Instructional Subset of the Programming Language Ada
http://hdl.handle.net/1813/7509
Ada/CS - An Instructional Subset of the Programming Language Ada
Archer, James E., Jr.
NO ABSTRACT SUPPLIED
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75091979-10-01T00:00:00ZA Unified View of Semantics
http://hdl.handle.net/1813/7508
A Unified View of Semantics
Majster, Mila E.
NO ABSTRACT SUPPLIED
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75081979-10-01T00:00:00ZEfficient On-Line Construction and Correction of Position Trees
http://hdl.handle.net/1813/7507
Efficient On-Line Construction and Correction of Position Trees
Majster, Mila E.
This paper presents an on-line algorithm for the construction of position trees, i.e. an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on-line correction algorithm is presented which - upon a change in the string - can be used to construct the new position tree. Moreover, special attention is paid to computers with small memory. Compactification of the trees and transport costs between main and secondary storage are discussed.
Mon, 01 Oct 1979 00:00:00 GMThttp://hdl.handle.net/1813/75071979-10-01T00:00:00ZEnsuring Consistency in a Distributed Database System by Use of Distributed Semaphores
http://hdl.handle.net/1813/7506
Ensuring Consistency in a Distributed Database System by Use of Distributed Semaphores
Schneider, Fred B.
Solutions to the database consistency problem in distributed databases are developed. It is shown how any solution to the consistency problem for a centralized database system that involves locking can be adapted for use in distributed systems. This is done, constructively, in two steps. First, it is shown how locking can be implemented in terms of semaphores. Then, a semaphore implementation that is suitable for use in distributed systems is developed.
Sat, 01 Sep 1979 00:00:00 GMThttp://hdl.handle.net/1813/75061979-09-01T00:00:00ZSynchronization in Distributed Programs
http://hdl.handle.net/1813/7505
Synchronization in Distributed Programs
Schneider, Fred B.
A technique for solving synchronization problems in distributed programs is described. Use of this technique in environments in which processes may fail is discussed. The technique can be used to solve synchronization problems directly, to implement new synchronization mechanisms (which are presumably well suited for use in distributed programs), and to construct distributed versions of existing synchronization mechanisms. Use of the technique is illustrated with implementations of distributed semaphores and a conditional message passing facility.
Sat, 01 Sep 1979 00:00:00 GMThttp://hdl.handle.net/1813/75051979-09-01T00:00:00ZOn Easily Infinite Sets and On a Statement of R. Lipton
http://hdl.handle.net/1813/7504
On Easily Infinite Sets and On a Statement of R. Lipton
Leivant, Daniel
For a complexity measure $\kappa$, a set is $\kappa$-infinite if it contains a $\kappa$-decidable infinite subset. For a time-based $\kappa$, we prove that there is a recursive S s.t. both S and its complements, $\bar{S}$, are infinite but not $\kappa$-infinite. Lipton [6] states that the existence of a recursive set S s.t. neither S nor $\bar{S}$ os polynomially infinite is not a purely logical consequence of $\prod^{0}_{2}$ theorems of Peano's Arithmetic PA. His proof uses a construction of an algorithm within a non-standard model of of Arithmetic, in which the existence of infinite descending chains in such models is overlooked. We give a proof of a stronger statement to the effect that the existence of a recursive set S s.t. neither S nor $\bar{S}$ is linearly infinite is not a tautological consequence of all true $\prod^{0}_{2}$ assertions. We comment on other aspects of [6], and show $(\S 2)$ that a tautological consequence of true $\prod^{0}_{2}$ assertions may not be equivalent (in PA, say) to a $\prod^{0}_{2}$ sentence. The three sections of this paper use techniques of Recursion Theory, Proof Theory and Model Theory, respectively.
Sat, 01 Sep 1979 00:00:00 GMThttp://hdl.handle.net/1813/75041979-09-01T00:00:00ZA Logic For Correct Program Development
http://hdl.handle.net/1813/7503
A Logic For Correct Program Development
Bates, Joseph Louis
Wed, 01 Aug 1979 00:00:00 GMThttp://hdl.handle.net/1813/75031979-08-01T00:00:00ZThe Complexity of Parallel Computations
http://hdl.handle.net/1813/7502
The Complexity of Parallel Computations
Wyllie, James C.
Recent advances in microelectronics have brought closer to feasibility the construction of computers containing thousands (or more) of processing elements. This thesis addresses the question of effective utilization of such processing power. We study the computational complexity of synchronous paarallel computations using a model of computation based on random access machines operating in parallel and sharing a common memory, the P-RAM. Two main areas within the field of parallel computational complexity are investigated. First, we explore the power of the P-RAM model viewed as an abstract computing device. Later, we study techniques for developing efficient algorithms for parallel computers. We are able to give concise characterizations of the power of deterministic and nondeterministic P-RAMS in terms of the more widely known space and time complexity classes for multi-tape Turing machines. Roughly speaking, time-bounded deterministic P-RAMS are equivalent in power to (can accept the same sets as) space-bounded Turing machines, where the time and space bounds differ by at most a polynomial. In the context of comparing models of computation, we consider such polynomial differences in resources to be insignificant. Adding the feature of nondeterminism to the time-bounded P-RAM changes its power to that of a nondeterministic Turing machine with an exponentially higher running time. The later sections of the thesis examine algorithm design techniques for parallel computers. We first develop efficient procedures for some common operations on linked lists and arrays. Given this background, we introduce three techniques that permit the design of parallel algorithms that are efficient in terms of both their time and processor requirements. We illustrate the use of these techniques by presenting time and processor efficient algorithms for three problems, in each case improving upon the best previously known parallel resource bounds. We show how to compute minimum string edit distances, using the technique of pairwise function composition. We describe an algorithm for the off-line MIN that organizes its computation in the form of a complete binary tree. Finally, we present an algorithm for undirected graph connectivity that relies on redundancy in its representation of the input graph.
Wed, 01 Aug 1979 00:00:00 GMThttp://hdl.handle.net/1813/75021979-08-01T00:00:00ZA Linear Time Algorithm for the Generalized Consecutive Retrieval Problem
http://hdl.handle.net/1813/7501
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem
Dietz, Paul F.; Furst, Merrick; Hopcroft, John E.
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for efficient retrieval. A linear time algorithm for the GCRP is given. Further generalization leads to problems that are complete for NP.
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/75011979-07-01T00:00:00ZA Time-Space Tradeoff for In-Place Array Permutation
http://hdl.handle.net/1813/7500
A Time-Space Tradeoff for In-Place Array Permutation
Melville, Robert C.
NO ABSTRACT SUPPLIED
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/75001979-07-01T00:00:00ZConvergence Theorems for Least Change Secant Update Methods
http://hdl.handle.net/1813/7499
Convergence Theorems for Least Change Secant Update Methods
Dennis, John E. Jr.; Walker, Homer F.
The purpose of this paper is to present a convergence analysis of the least change secant methods in which part of the derivative matrix being approximated is computed by other means. The theorems and proofs given here can be viewed as generalizations of those given by Broyden-Dennis-More and by Dennis-More. The analysis is done in the orthogonal projection setting of Dennis-Schnabel and many readers might feel that it is easier to understand. The theorems here readily imply local and q-superlinear convergence of all the standard methods in addition to proving these results for the first time for the sparse symmetric method of Marwil and Toint and the nonlinear least squares method of Dennis-Gay-Welsch.
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/74991979-07-01T00:00:00ZLocal Convergence Theorems for Quasi-Newton Methods
http://hdl.handle.net/1813/7498
Local Convergence Theorems for Quasi-Newton Methods
Dennis, John E. Jr.; Walker, Homer F.
This paper presents generalizations of the two results which have been useful for analyzing methods of the form $x_{k+1} = x_{k} - B_{k}^{-1}F(x_{k})$. The bounded deterioration theorem of Broyden-Dennis-More is generalized to show that if \{$B_{k}$\} or \{$B_{k}^{-1}$\} is of bounded deterioration as a sequence of approximants to some $B_{*}$ or $B_{*}^{-1}$ then the iteration above has the same local convergence properties and arbitrarily nearly the same linear rate as would be achieved by the stationary iteration function which uses $B_{k} = B_{*}$. The characterization theorem for superlinear convergence given by Dennis-More is then generalized to give conditions under which the rates are the same. In the case when $B_{*} = F'(x_{*})$, these results reduce to those already known.
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/74981979-07-01T00:00:00ZEfficiency Considerations In Implementing Dijkstra's Guarded Command Constructs
http://hdl.handle.net/1813/7497
Efficiency Considerations In Implementing Dijkstra's Guarded Command Constructs
McGuire, Marguerite Elaine
The guarded command alternative and iterative constructs proposed by E. W. Dijkstra subsume the conventional alternative and iterative constructs. The extra flexibility of these guarded command constructs enables the programmer to express his ideas more directly and clearly. Moreover, Dijkstra has developed a calculus for the derivation of correct programs that utilizes these guarded command constructs. This thesis addresses the problem of efficiently implementing these guarded command constructs. Several new optimizations that are particularly well suited to the guarded command constructs are described. The most useful is the elimination of redundant boolean expressions. This optimization provides a means of implementing the guarded command alternative statement with efficiency comparable to the IF-THEN-ELSE statement. The main contribution of this thesis is a detailed description of an algorithm for eliminating redundant boolean expressions. The algorithm itself is presented in a program written in a PASCAL supplemented with the guarded command constructs. The basis method involves considering individual execution paths through the guarded command construct and applying rules of inference to recognize and avoid evaluation of many boolean expressions. It is shown that the number of execution paths through a guarded command construct remains small enough to make this method practical.
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/74971979-07-01T00:00:00ZThe Cornell Program Synthesizer: A Tutorial Introduction
http://hdl.handle.net/1813/7496
The Cornell Program Synthesizer: A Tutorial Introduction
Teitelbaum, Tim
This tutorial introduces a novice student to the basic facilities of the Cornell Program Synthesizer for developing programs written in the PL/CS dialect of PL/I. No knowledge of programming is assumed or required. It is assumed that you possess a Synthesizer diskette and have access to a TERAK microcomputer.
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/74961979-07-01T00:00:00ZOn the Proof Theory of the Modal Logic G
http://hdl.handle.net/1813/7495
On the Proof Theory of the Modal Logic G
Leivant, Daniel
NO ABSTRACT SUPPLIED
Sun, 01 Jul 1979 00:00:00 GMThttp://hdl.handle.net/1813/74951979-07-01T00:00:00ZA Procedure Call Proof Rule (With a Simple Explanation)
http://hdl.handle.net/1813/7494
A Procedure Call Proof Rule (With a Simple Explanation)
Gries, David; Levin, Gary Marc
NO ABSTRACT SUPPLIED
Tue, 01 May 1979 00:00:00 GMThttp://hdl.handle.net/1813/74941979-05-01T00:00:00ZUpson's Familiar Quotations
http://hdl.handle.net/1813/7493
Upson's Familiar Quotations
Gaulle, Al
This report is a compilation of several hundred examples of context free language and very irregular expressions. Contributions were submitted over the last five years by numerous computer science graduate students who collected these now immortal words in classes and seminars. We wish to express our gratitude to the faculty, guest lecturers, and students who provided the bulk of this work.
Tue, 01 May 1979 00:00:00 GMThttp://hdl.handle.net/1813/74931979-05-01T00:00:00ZA Hamiltonian-Schur Decomposition
http://hdl.handle.net/1813/7492
A Hamiltonian-Schur Decomposition
Paige, Chris; Van Loan, Charles
Sat, 01 Sep 1979 00:00:00 GMThttp://hdl.handle.net/1813/74921979-09-01T00:00:00ZComputer Science and the Liberal Arts Student
http://hdl.handle.net/1813/7491
Computer Science and the Liberal Arts Student
Van Loan, Charles
The computer science education of nontechnical liberal arts students is a matter of increasing concern. In this paper it is argued that computer scientists should promote and teach their subject more in line with the traditional aims of liberal education when dealing with students of this type. A framework for doing this is presented which involves a broad view of "computer literacy" based upon what other authors have written about "scientific literacy." The structure of a computer science appreciation course is outlined which embodies the ideas of liberal education described. The importance of historical perspective is emphasized. Key Words and Phrases: Computer literacy, liberal arts student, liberal education, history of computation, scientific literacy.
Tue, 01 May 1979 00:00:00 GMThttp://hdl.handle.net/1813/74911979-05-01T00:00:00ZRepresentation of Almost Constant Vectors
http://hdl.handle.net/1813/7490
Representation of Almost Constant Vectors
Steensgaard-Madsen, Jorgen
An example in a recent report on the programming language Russell has illustrated difficulties related to user defined storage management. Here is demonstrated how the dynamic approach to encapsulation earlier proposed by the author provides means to solve the particular storage management problem. The method used is, however, easily generalized to other similar cases. In addition to the example a number of notational conveniences are introduced. One that allows abbreviated references to components of record-like structures is called controlled coercion. Another allows a function-like use of classes. Keywords: Classes, abstract data types, storage management, programming languages.
Sun, 01 Apr 1979 00:00:00 GMThttp://hdl.handle.net/1813/74901979-04-01T00:00:00ZOn Restrictions to Ensure Reproducible Behavior in Concurrent Programs
http://hdl.handle.net/1813/7489
On Restrictions to Ensure Reproducible Behavior in Concurrent Programs
Schneider, Fred B.; Bernstein, A. J.
One of the major difficulties encountered when dealing with concurrent programs is that reproducible behavior may not be assumed. As a result, it is difficult to validate and debug such systems. In this paper, structural restrictions are presented that ensure that reproducible behavior will occur in concurrent programs. The application of this to system design is discussed. Keywords: time dependent behavior, concurrency, synchronization, monitors, Concurrent Pascal.
Thu, 01 Mar 1979 00:00:00 GMThttp://hdl.handle.net/1813/74891979-03-01T00:00:00ZAPL and the Grzegorczyk Hierarchy
http://hdl.handle.net/1813/7488
APL and the Grzegorczyk Hierarchy
Breidbart, Seth
We show in this paper that the set of "traditional" APL 1-liners (using arithmetic functions only) compute precisely the set of functions in the class E4 of Grzegorczyk hierarchy (the class immediately above the elementary functions). We also show that if we extend the set of 1-liners to include either the "execute" operator, or 1 line programs with gotos, then any partial recursive function can be computed.
Thu, 01 Mar 1979 00:00:00 GMThttp://hdl.handle.net/1813/74881979-03-01T00:00:00ZThe Cornell Program Synthesizer: A Microcomputer Implementationof PL/CS
http://hdl.handle.net/1813/7487
The Cornell Program Synthesizer: A Microcomputer Implementationof PL/CS
Teitelbaum, Tim
NO ABSTRACT SUPPLIED
Thu, 01 Mar 1979 00:00:00 GMThttp://hdl.handle.net/1813/74871979-03-01T00:00:00ZComments on a Draft Pascal Standard
http://hdl.handle.net/1813/7486
Comments on a Draft Pascal Standard
Steensgaard-Madsen, Jorgen
NO ABSTRACT SUPPLIED
Thu, 01 Feb 1979 00:00:00 GMThttp://hdl.handle.net/1813/74861979-02-01T00:00:00ZA Progress Report on Automatic Information Retrieval
http://hdl.handle.net/1813/7485
A Progress Report on Automatic Information Retrieval
Salton, Gerard
This study is a state-of-the-art report of work in automatic information retrieval. Various enhancements of operational on-line retrieval systems are described such as the utilization of special front-end devices providing compatibility among different search services, the introduction of fast back-end search devices, and the use of local clustering and query reformulation operations designed to improve retrieval output. Certain new algorithms for fast text matching and for optimum term weighting are also mentioned, as are advances in the construction of theoretical retrieval models.
Thu, 01 Feb 1979 00:00:00 GMThttp://hdl.handle.net/1813/74851979-02-01T00:00:00ZImplementation of an Unrestricted File Organization for Micro-PL/CS
http://hdl.handle.net/1813/7484
Implementation of an Unrestricted File Organization for Micro-PL/CS
Archer, James E. Jr.
Micro PL/CS is a version of PL/CS developed for a single-user, interactive environment. A file system extension makes PL/CS self-sufficient for standalone file processing and secondary storage management. The basis of the file system extension is the Unrestricted File Organization which provides a free mixture of sequential, indexed and random file operations. The structure, operation, and system-interfaced procedures of the UFO are presented and explained. The Micro-PL/CS file extension implementation is then sketched in terms of the UFO primitives.
Thu, 01 Feb 1979 00:00:00 GMThttp://hdl.handle.net/1813/74841979-02-01T00:00:00ZA File System Extension to Micro-PL/CS
http://hdl.handle.net/1813/7483
A File System Extension to Micro-PL/CS
Archer, James E., Jr.
Micro-PL/CS is a version of PL/CS developed for interactive use with a dedicated microprocessor. A file system extension is proposed to give PL/CS a simple, but extremely powerful file system capability. The system allows for the creation and manipulation of files for sequential, random, or keyed access (or any combination) in an unrestricted manner. Essential to the capability is a set of built-in functions and pseudo-variables which allow file manipulation without syntactic complication.
Thu, 01 Feb 1979 00:00:00 GMThttp://hdl.handle.net/1813/74831979-02-01T00:00:00Z