= TABLE OF CONTENTS Preface I:: Part One ELEMENTS OF GENERAL ALGEBRA Chapter 1. Sets § 1.1. The concept of a set. Subsets. Inclusions 11 1.2. Basic operations on sets 15 1.3. Cardinality of sets. Countable sets 22 § 1.4. Continuum sets 27 § 1.5. Cardinal numbers 31 Chapter 2. Relations. Structures § 2.1. Basic definitions 36 § 2.2. Operations on relations 41 § 2.3. Functional relations. Displays 46 § 2-4. Equivalence and order relations 52 § 2.5. Completely ordered sets. Structures 58 Chapter 3. Universal algebras § 3.1. Concepts of models and universal algebras 67 § 3.2. Subalgebras. Systems of generators 76 § 3.3. Structure of subalgebras of universal algebra 81 § 3.4. Functions of logic algebra 87 § 3.5. Isolated sets. Congruences 94 § 3.6. Semigroups. Polybasic Algebras 101 Part Two ELEMENTS OF PROGRAMMING THEORY Chapter 4. Systems of algorithmic algebras § 4.1. The concept of a system of algorithmic algebras FROM § 4.2. Identical relations in a system of algorithmic al-algebras 125 § 4.3. Semigroups of periodically defined transformations. 141 § 4.4. Modified Post algebras 150 § 4.5. Implementation of regular schemes of address programs in homogeneous structures 163

table of contents

Preface

Part One

ELEMENTS OF THE OVSCHEY ALGEBRA

Chapter 1. Sets

§ 1.1. The concept of a set. Subsets. Inclusions 11

§ 1.2. Basic operations on sets 15

§ 1.3. Cardinality of sets. Countable sets 22

§ 1.4. Continuum sets 27

§ 1.5. Cardinal numbers 31

Chapter 2. Relationships. Structures

§ 2.1. Basic definitions 36

§ 2.2. Operations on relations 41

§ 2.3. Functional relations. Displays 46

§ 2-4. Equivalence and order relations 52

2.5. Completely ordered sets. Structures 58

Chapter 3. Universal algebras

§ 3.1. Concepts of models and universal algebras 67

§ 3.2. Subalgebras. Systems of generators 76

§ 3.3. Structure of subalgebras of universal algebra 81

§ 3.4. Functions of logic algebra 87

§ 3.5. Isolated sets. Congruences 94

§ 3.6. Semigroups. Multi-base algebras 101

Part Two

ELEMENTS OF PROGRAMMING THEORY

Chapter 4. Systems of algorithmic algebras

§ 4.1. The concept of a system of algorithmic algebras FROM

§ 4.2. Identical relations in a system of algorithmic al-

algebras 125

4.3. Semigroups of periodically defined transformations. . 141

§ 4.4. Modified Post algebras 150

§ 4.5. Implementation of regular schemes of address programs in

homogeneous structures 163

Chapter 5. Formal Languages and Grammars

- § 5.1. Representation of languages using grammars ¦ 172

§ 5.2. System of components. vs-Grammars 178

§ 5.3. Context-free languages 187

§ 5.4. Linear and automaton grammars 198

§ 5.5. Algebras of context-free languages 210

Chapter 6. Parametric programming systems

§ 6.1. Automata over internal memory 222

§ 6.2. Synthesis of store automata 234

§ 6.3. Methods of syntactic analysis in

programming systems 246

§ 6.4. Parametric grammars of the reverse-

recursive type 265

§ 6.5. SM-grammar metalanguage and translation problems 282

§ 6.6. SM-formalisms n nx application to programming systems

29 i

§ 6.7. Multi-base algebras and programming languages .... 302

Literature 306

Prev.\:this pointer is 313

Index of theorems and lemmas 319

PREFACE

Due to the rapid growth of computer technology and the constant growth of;

With the expansion of the scope of computer applications in modern cybernetics

, all new theoretical directions are emerging and intensively developing. In particular,

such a primarily empirical field

of knowledge as programming, whose task it is, is being formed into science. development

of means of human communication with a computer. Programming theory is based

on such important sections of discrete mathematics as the theory of algorithms,

computer science, automata theory and the theory of formal languages. Practical-

Its practical applications consist primarily in solving problems related to

with the development of computer mathematical support systems and the design

of the structures of the machines themselves. When solving problems

of computer programming automation and computer design, in particular, there is a need to

apply the ideas and methods of general algebra - one of the fundamental

and deeply developed areas of mathematics. This

makes it necessary to familiarize specialists in programming and

design of computer mathematical support systems with the basic

algebraic concepts and results.

The monograph is an introduction to the theory of programming

with a bias of applying the concepts and methods of the gorge of versalpy algebras in it.

The first part is devoted to the basic concepts of CSSCHEY algebra.

The intuitive theory of sets, the basic concepts of the theory of relations

and universal algebras are considered. Considerable attention is paid to structures, in particular

to the structures of subalgebras of universal algebras, in order to establish

criteria for completeness of necessary and sufficient conditions under which

an arbitrary system of elements generates a bottom algebra.

The concepts and results set out in the first part, . were selected

taking into account their difference in the second part of the book. So, the apparatus of theory.many

sets and relations are used in the study of the problem

of identity transformations in systems of algorithmic algebras (ch. 4, § 4.1,

4.2), classification of formal languages (ch. 5), development of

syntactic analysis methods for parametric programming systems

(ch. 6). Properties of the structure of subalgebras of universal algebras, considered-

considered in Chapter 3, they are used in the study of the completeness problem for

modified Post algebras (Chapters 4, 4.3, 4.4) and context-free algebras

languages (ch. 5, § 5.5). There are many problems with the device.x algebras (ch. 3, § 3.6)

are related to the concept of algorithmic algebras (ch. 4, § 4.1) n methods

of formalization of the enptakens n semantics of programming languages (ch. O, § 6.7).

In the first part, the results presented in [1,6, 8 —

10, 24, 25, 36, 49, 52, 54, 60, 61,'64, 66, 67, 70, 71, 73, 74, 77, 78, 86, 103,

108, 111-115, 118, 119, 127, 128, 133, 134, 139, 155 156). The

second part is devoted to the elements of programming theory. In Chapter 4

, the apparatus of algorithmic algebras proposed by V. M. Glush is considered-

kovym [26] for solving problems of the applied theory of algorithms. Special

attention is paid to the tasks that arise during design automation

Computer n programming. The connection of the apparatus of algorithmic

algebras with the concept of structural programming is established [41], which

is a complex of technological tools focused on

the construction of large algorithms and programs. It is shown that

algorithmic algebras can be considered as a theory of schemes of structurally

structured algorithms and programs and used in the development of a schematic

and mathematical software for modern

computing systems, in particular when solving the problem of formalization

of the semantics of programming languages (ch. 6, § 6.7). In Chapter 4

, the results presented in the papers are used [8, 18, 23-27, 31-37, 41, 43-50, 53-63, 65,

09, 72, 75-78, 80-82, 84, 91, 92, 113-117, 120-122, 128, 131, 133, 134, 136,

139, 145, 146, 148, 155, 156, 158].

The fifth chapter is an introduction to the theory of formal languages.

The issues of classification of generative grammars, forms are considered

their representations, algebraic properties of operations on languages. Izlo-

Stated re!The exhibits are used in Chapter 6 in solving the problems of analysis

and synthesis of automaton models of languages (sections 6.1, 6.2), creating formalisms

focused on the effective solution of the problems of constructing many

page system processes (sections 6.3—6.6), the development of algebraic methods

for describing the syntax and semantics of programming languages (§ 6.7). In Chapter 5

, the results presented in the papers are used [3, 7, 17-25, 36, 37, 48,

70, 80, 85, 94, 95, 99, 100, 109, 110, 118, 128, 137, 138, 146].

The methodology of constructing modern languages and systems

of programming is devoted to Chapter 6. In this edition, this chapter has been substantially

reworked. It reflects some new results. To do this, due

to the limited volume of the book, it was necessary to omit part of the material

presented in the first edition. So, in section 6.1, the concept

of automata with internal memory is considered [37], generalizing the well-known automata

structures (shop and BS automata, counter machines, etc.)

used in system programming (in the first edition this paragraph

it is devoted to a historical sketch of the development of programming ideas and the USSR

(zp abroad). In connection with the introduction of automata over internal memory

, the following paragraphs of the chapter have been changed to a certain extent, in

particular, the strategy of two-way syntactic analysis and its

generalization in connection with the construction of parallel programming systems

for multiprocessor computing complexes, methods

of formalization of syntax and semantics of programming languages with

the involvement of the apparatus of multi-domain algebras, Methods of constructing parameters-

parametric programming systems have been used in the development

of software programs for some modern computing systems, both

specialized and universal. Further

development of these methods will contribute to the creation of high-performance

computer complexes of subsequent generations. In Chapter 6

, the results presented in the papers are used [2-5,11-16, 18-21, 28-30, 36-42, 48, 51,

52, 62, 68, 70, 71, 79, 83, 85, 87-90, 93, 95-98, 101-107, 123-126. 128—

130, 132, 135, 140-147, 149-154, 157, 159, 160].

The present edition of the monograph has been amended due

to inaccuracies, typos or omissions made in the first edition.

Authors

CHAPTER 1 SETS

§ 1.1. The concept of a set.

Subsets. Inclusions.

The needs of intensively developing analysis, especially the theory

of functions of a real variable, caused at the end of the XIX century.