= 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.