Search For:

Displaying 1-18 out of 18 total
SIGACT (Paper Session)
Found in: Proceedings of the annual conference (ACM 76)
By George T. Ligler, Patrick C. Fischer, Patrick Fischer, Patrick Wang, Robert L. Probert, William C. Nylin
Issue Date:October 1976
pp. 1
These papers indicate the diversity of the theoretical area of computer science. The first explores programming language concepts in terms of Hoare's formal assignment axiom. The second is well described by its title. The third is a contribution to formal ...
     
On computability by certain classes of restricted turing machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Patrick C. Fischer
Issue Date:October 1963
pp. 23-32
The theory of abstract machines has been well developed for the finite automaton [RS] and the Turing machine [D]. More recently, machines intermediate in computing power between the above two classes of machines have been investigated. These machines have ...
 
Tape reversal complexity hierarchies
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Patrick C. Fischer, Juris Hartmanis, Manuel Blum
Issue Date:October 1968
pp. 373-382
No summary available.
 
On computational speed-up
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Albert Meyer, Patrick C. Fischer
Issue Date:October 1968
pp. 351-355
Let F be any effective mapping from total functions on the integers to total functions. Composition and iterated composition are examples of such mappings. The
 
On formalisms for turing machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Patrick C. Fischer
Issue Date:November 1964
pp. 68-75
No summary available.
 
Real time counter machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Patrick C. Fischer, Albert R. Meyer, Arnold L. Rosenberg
Issue Date:October 1967
pp. 148-154
An automaton called the balloon automaton is defined. The balloon automaton comes in four varieties, depending on whether the device is deterministic or nondeterministic, and whether the input head can move in one or two directions. Subsets of the balloon ...
 
Turing machines with several read-write heads
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Albert R. Meyer, Arnold L. Rosenberg, Patrick C. Fischer
Issue Date:October 1967
pp. 117-127
This paper describes some general results about hierarchies of undecidable problems in automata theory, and studies how properties of sets accepted by automata change from decidable to undecidable problems as the memory capacity of the automaton is increas...
 
Predecessor machines and regressing functions
Found in: Proceedings of the fourth annual ACM symposium on Theory of computing (STOC '72)
By John C. Warkentin, Patrick C. Fischer
Issue Date:May 1972
pp. 81-87
A predecessor machine is a random-access machine with a predecessor operation (i.e., an instruction which subtracts 1 from the contents of a memory cell), but with no operation which can increase the contents of a cell. A regressing function is a total fun...
     
Storage reorganization techniques for matrix computation in a paging environment
Found in: Communications of the ACM
By Patrick C. Fischer, Robert L. Probert
Issue Date:January 1988
pp. 405-415
As computer technology matures, our growing ability to create large systems is leading to basic changes in the nature of programming. Current programming language concepts will not be adequate for building and maintaining systems of the complexity called f...
     
Some classes of multilevel relational structures
Found in: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS '86)
By Dirk Van Gucht, Patrick C Fischer
Issue Date:March 1986
pp. 60-69
The design of an appropriate conceptual database scheme is one of the most difficult tasks in usual database applications. Especially, the design of a common global database scheme for many different user groups requires a great amount of effort and skill,...
     
Weak multivalued dependencies
Found in: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS '84)
By Dirk Van Gucht, Patrick C. Fischer
Issue Date:April 1984
pp. 266-274
Given a multirelational database scheme and a relational mapping f transforming it, an important question is whether the resulting scheme is equivalent to the original one. This question was addressed in the literature with respect to those relational sche...
     
Decomposition of a relation scheme into Boyce-Codd Normal Form
Found in: Proceedings of the ACM 1980 annual conference (ACM 80)
By Don-Min Tsou, Patrick C. Fischer
Issue Date:January 1980
pp. 411-417
Decomposition into Boyce-Codd Normal Form (BCNF) with a lossless join and preservation of dependencies is desired in the design of a relational database scheme. However, there may be no decomposition of a relation scheme into BCNF that is dependency preser...
     
Computations with a restricted number of nondeterministic steps (Extended Abstract)
Found in: Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77)
By Chandra M. R. Kintala, Patrick C. Fischer
Issue Date:May 1977
pp. 178-185
Nondeterminism is one of the most elusive concepts in computing. In this paper we direct our efforts towards viewing nondeterminism as an additional resource at the disposal of time or space bounded Turing machine computations and study the classes of lang...
     
A note on matrix multiplication in a paging environment
Found in: Proceedings of the annual conference (ACM 76)
By Patrick C. Fischer, Robert L. Probert
Issue Date:October 1976
pp. 17-21
In order to minimize the number of page fetches required when multiplying matrices occupying many pages of virtual storage, we consider adapting Strassen-like recursive methods to a paging environment. An algorithm with a theoretically better rate of growt...
     
Real-Time Simulation of Multihead Tape Units
Found in: Journal of the ACM (JACM)
By Albert R. Meyer, Arnold L. Rosenberg, Patrick C. Fischer
Issue Date:October 1972
pp. 590-607
Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been proved to be u...
     
The Solvability of the Halting Problem for 2-State Post Machines
Found in: Journal of the ACM (JACM)
By Patrick C. Fischer, Stal Aanderaa
Issue Date:October 1967
pp. 677-682
A Post machine is a Turing machine which cannot both write and move on the same machine step. It is shown that the halting problem for the class of 2-state Post machines is solvable. Thus, there can be no universal 2-state Post machine. This is in contrast...
     
On Formalisms for Turing Machines
Found in: Journal of the ACM (JACM)
By Patrick C. Fischer
Issue Date:October 1965
pp. 570-580
Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appe...
     
Automatic propagated and round-off error analysis
Found in: Preprints of papers presented at the 13th national meeting of the Association for Computing Machinery (ACM '58)
By Patrick C. Fischer
Issue Date:June 1958
pp. 1-2
The routine described below is a modification of the Carnegie Tech (IT) Compiler system for the IBM-650, which will provide automatic empirical analysis of propagated and round-off errors in computation. In the modified system, three kinds of variables are...
     
 1