enter search term and/or author name
A Mechanical Proof of the Unsolvability of the Halting Problem
Robert S. Boyer, J. Strother Moore
Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
Yuri Gurevich, Larry Stockmeyer, Uzi Vishkin
An End-to-End Approach to the Resequencing Problem
François Baccelli, Erol Gelenbe, Brigitte Plateau
The Format Model: A Theory of database Organization
Richard Hull, Chee K. Yap
A mathematical theory for the study of data representation in databases is introduced and developed. The theory focuses on three data constructs (collection, composition and classification). "Formats" with semantically rich yet tractable...
Storing a Sparse Table with
Michael L. Fredman, János Komlós, Endre Szemerédi
The information-based study of the optimal solution of large linear systems is initiated by studying the case of Krylov information. Among the algorithms that use Krylov information are minimal residual, conjugate gradient, Chebyshev, and...
A mathematical model for communicating sequential processes is given, and a number of its interesting and useful properties are stated and proved. The possibilities of nondetermimsm are fully taken into account....
A Formal Method for the Abstract Specification of Software
An intuitive presentation of the trace method for the abstract specification of software contains sample specifications, syntactic and semantic definitions of consistency and totalness, methods for proving specifications consistent and total,...
Analysis of interleaved storage via a constant-service queuing system with Markov-chain-driven input
A popular means of increasing the effective rate of main storage accesses in a large computer is a multiplicity of memory modules accessible in parallel. Although such an organization usually achieves a net gain in access rate, it also creates...
Graph Problems on a Mesh-Connected Processor Array
Mikhail J. Atallah, S. Rao Kosaraju
A Polynomial Linear Search Algorithm for the
Friedhelm Meyer auf der Heide