Search
Now showing items 1-10 of 12
Decidability of Equivalence for a Class of Data Flow Schemas
(1975-03)
In this paper we examine a class of computation schemas and consider the problem of deciding when pairs of elements in this class represent equivalent programs. We are able to show that equivalence is decidable for a ...
Decision Problems for Petri Nets and Vector Addition Systems
(1975-03)
Petri Nets, Generalized Petri Nets, and Vector Addition Systems can represent each other and thus have common decideability problems. The graphical appeal of Petri Nets is used in a new presentation of the classical problems ...
Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees
(1975-11)
A binary search tree can be used to store data in a computer system for retrieval by name. Different elements in the tree may be referenced with different probabilities. If we define the cost of the tree as the average ...
Computational Complexity of the Word Problem for Commutative Semigroups
(1975-10)
We analyze the computational complexity of some decision problems for commutative semigroups in terms of time and space on a Turing machine. The main result we present is that any decision procedure for the word problemm ...
Steam-oriented Computation in Recursive Data Flow Schemas
(1975-10)
In this thesis we present a parallel programming language based on a parallel computation model known as data flow schemas. Syntactically, the language resembles programming languages such as Algol 60, but does not have ...
CAMAC: Group Manipulation System
(1975-03)
CAMAC is a collection of group manipulation progams with an easy to use interface. With groups defined by either generating permutations or generators and relations the system can find coset tables, normalizers, centralizers, ...
First Version of a Data Flow Procedure Language
(1975-05)
A language for representing computational procedures based on the concept of data flow is presented in terms of a semantic model that permits concurrent execution of noninterfering program parts. Procedures in the language ...
Formal Properties of Well-formed Data Flow Schemas
(1975-06)
This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). ...