**Proceedings of Symposia in Applied Mathematics**

Volume: 34;
1986;
233 pp;
Softcover

MSC: Primary 68;

Print ISBN: 978-0-8218-0086-7

Product Code: PSAPM/34

List Price: $48.00

Individual Member Price: $38.40

**Electronic ISBN: 978-0-8218-9249-7
Product Code: PSAPM/34.E**

List Price: $48.00

Individual Member Price: $38.40

# Mathematics of Information Processing

Share this page *Edited by *
*Michael M. Anshel; William Gewitz*

These introductory survey lectures, the result of a 1984 AMS Short
Course, focus on the algorithmic problems arising in the construction
and utilization of large-scale information systems. Addressed to both
mathematicians and computer scientists, the lectures require a
background in the methodologies of discrete mathematics, in particular
the elements of algebra, combinatorics and graph theory, discrete
probability, logic and the theory of computation.

All of the articles either are of high research value or survey profound
themes in current research. They cover the two fundamental aspects of the
field, i.e., database systems and communication networks. An overview of
database architectures, the theory of data dependencies, and transaction
management are provided, respectively, by the articles of Jacobs, Fagin and
Vardi, and Garcia-Molina. Chung evaluates problems in the design of
communication networks. Miller's discussion of data compression algorithms
links current research to classical information theory. Finally, Tuzhilin
describes a general framework evolved in the Soviet Union for modelling
problems of information processing.

#### Table of Contents

# Table of Contents

## Mathematics of Information Processing

- Contents vii8 free
- List of contributors ix10 free
- Preface xi12 free
- Diameters of communication networks 114 free
- The theory of data dependencies—a survey 1932
- Transaction management 7386
- Fundamental database issues 91104
- Data compression algorithms 107120
- Application of category theory of structural sets to modelling of information bases of systems 119132
- Introduction 120133
- 1. Information Base of a System 123136
- 2. Theory of Categories of Structural Sets 139152
- 3. Universal Query Language on Finite Primitive Sets 154167
- 3.1 Languages with Weights. Significant and Balanced Words. 155168
- 3.2 Complex-Schemes. Complexes 157170
- 3.3 Significant Words and Complexes 160173
- 3.4 Cartesian Complexes on a Given Set of Primitive Data and Variables. Constantsand Terms. 166179
- 3.5 Equivalence Relations 167180
- 3.6 Relations. Theorems. Classes of Relations. 169182
- 3.7 Substitutions. Quantifiers. 172185
- 3.8 The Relation "Belong" 173186

- 4. Systems and Their Information Bases 175188
- 5. Composition of Functional Information Bases 187200
- 5.1 Composition of Information Bases. Functional Information Bases. 188201
- 5.2 Variable Schemes and Functional Information Bases. The System of Functional Equations Associated with a Variable Scheme. 191204
- 5.3 Scheme-Vector Functions 196209
- 5.4 Solution of a System of Functional Equations Associated with a Variable Scheme 203216

- 6. Category of Spaces of Available States and Its Application to Modeling Computers and Their Languages 211224