Summary: This is a short obituary of Mikhail Taĭtslin (1936–2013).

From the foreword: In October 1997, whilst touching up this text, exactly 50 years had passed since I was accepted for graduate studies under P. S. Novikov. I started then to study and do research in logic and computability, which developed, as time will show, into research in Theoretical Computer Science (TCS).
After my emigration (in December 1980) from the Soviet Union (SU), I was encouraged by colleagues to experience the genre of memoirs. That is how my publications [“A survey of Russian approaches to perebor (brute-force search) algorithms”, Ann. Hist. Comput. 6, No. 4, 384–400 (1984; Zbl 0998.01527)], [Selected developments in Soviet mathematical cybernetics. Finite automata, combinatorial complexity, algorithmic complexity. Falls Church, Virginia: Delphic Associates (1986; Zbl 0613.68008)] appeared, and more recently [“In memory of S. A. Yanovskaya (1896–1966) on the centenary of her birth”, Mod. Log. 7, No. 2, 160–187 (1997; Zbl 0988.01511)], conceived as contributions to the history of TCS in the SU. The present paper is intended as a more intimate perspective on my research and teaching experience. It is mainly an account of how my interests shifted from classical logic and computability to TCS, notably to automata and computational complexity. Part of these reminiscences, recounting especially the scientific, ideological and human environment of those years (roughly 1945–67), were presented earlier at a Symposium (June 1991) on the occasion of my retirement.
[This paper is an extended and updated version of “From logic to theoretical computer science”, which appeared in: C. S. Calude (ed.), People and ideas in theoretical computer science. Singapore: Springer. 314–341 (1999; Zbl 0933.01039).]
For the entire collection see [Zbl 1132.68002].

Summary: To what mathematical models do digital computer circuits belong? In particular: (i) (Feedback reability.) Which cyclic circuits should be accepted? In other words, under which conditions is causally faithful the propagation of signals along closed cycles of the circuit? (ii) (Comparative power and completeness.) What are the appropriate primitives upon which circuits may be (or should be) assembled?
There are well-known answers to these questions for circuits operating in discrete time, and they point on the exclusive role of the unit-delay primitive. For example: (i) If every cycle in the circuit N$N$ passes through a delay, then N$N$ is feedback reliable. (ii) Every finite-memory operator F$F$ is implementable in a circuit over unit-delay and pointwise Boolean gates.
In what form, if any, can such phenomena and results be extended to circuits operating in continuous time? This is the main problem considered (and, hopefully, solved to some extent) in this paper. In order to tackle the problems one needs more insight into specific properties of continuous time signals and operators that are not visible at discrete time.

Summary: Paradigms in which continuous time is involved in cooperation with, or instead of, discrete time appear now in different areas related to automata, logic and interaction. Unfortunately, they are accompanied by a plethora of definitions, terminology and notation, which is not free of ad-hoc and ambiguous decisions. The overuse of definitions from scratch of intricate notions without a previous, explicit core of basic generic notions engenders further models and formalisms, and it is not clear where to stop. Hence (quoting J. Hartmanis), the challenge “to isolate the right concepts, to formulate the right models, and to discard many others, that do not capture the reality we want to understand…”.
We undertake this challenge with respect to some automata-theoretic concepts and issues that appear in the literature on continuous-time circuits and hybrid automata, by keeping to the following guidelines: 1. Building on Basic Automata Theory. 2. Coherence with original or potential discrete-time paradigms, whose continuous-time analogs and/or mutants we would like to understand. 3. Functions, notably input/output behavior of devices, should not be ignored in favor of sets (languages) accepted by them.
The paper outlines the approach which emerged in previous research and in teaching experience. As an illustration we offer a precise explanation of the evasive relationship between hybrid automata, constrained automata and control circuits.

For the entire collection see [Zbl 1074.68500].

Summary: Classical Automata Theory (AT) is mainly about devices that operate in discrete time. Recent research stimulated the interest to, and the development of, paradigms in which continuous time is involved whether in a pure way or in cooperation with discrete time. This development is in particular evident in the area that covers the following three interrelated trends: automata, logic (arguing about automata) and interaction (composition of automata).
For the entire collection see [Zbl 0967.00069].

Summary: There is a growing feeling in the community that the current literature on reactive and hybrid systems is plagued by a Babel of models, constructs and formalisms, and by an amazing discord of terminology and notation. Further models and formalisms are engendered, and it is not clear where to stop.
Hence, the urge toward a pithy conceptual/notational setting, supported by a consistent and comprehensive taxonomy for a wide range of formalisms and models.
The paper outlines an automata-based approach to this challenge, which emerged in previous research and in teaching experience. We compare our definitional suggestions with similar background in the current literature, where the subject is sometimes complicated by a premature mixture of semantics, syntax and pragmatics.
For the entire collection see [Zbl 0921.00033].

The author describes his career in the Soviet Union, mostly up to around 1970. He records his training in the Ukraine, contacts in Moscow with both mathematicians (especially with A. N. Kolmogorov) and logicians (especially with S. A. Yanovskaya), and employment in Penza and then Novosibirsk. Many of the social circumstances and relationships recorded are little known in the West. He also relates his intellectual progress. Broadly speaking, he passed from descriptive set theory through proof theory and recursion to computational complexity and finite automata. He gives some attention to the “perebor” (or brute force) algorithms, with which he has been especially associated.
For the entire collection see [Zbl 0913.00024].

Summary: We consider two orthogonal extensions of the basic finite automaton paradigm and clarify to what degree and in what form do they preserve fundamental facts from the theory of finite automata. Hopefully, this approach facilitates a lucid adaptation of Automata Theory to Hybrid Systems.
For the entire collection see [Zbl 0921.00032].

Summary: Currently there are already comprehensive papers which document and analyze the heritage of S. A. Yanovskaya, and her contribution to history and philosophy of mathematics as well as to the formation and defense of mathematical logic in the USSR [see I. H. Anellis, The heritage of S. A. Janovskaya, Hist. Philos. Log. 8, 45-56 (1987)]. Yet the centenary of her birth is an appropriate opportunity to raise recollections which may add some traits to the image of this eminent scholar and superb human being.
Here the author publishes and comments on (the translation of) some documents, among them letters addressed to him by S. A. From a personal perspective these documents, dated 1951, tell the story of how he was accused of “bourgeois idealism”, and how, due to the guidance and support of his mentors and especially of S. A., he managed to overcome the danger of these accusations in an era of persecution of “idealists”, “cosmopolites”, and others. But beyond my personal affairs the documents apparently present some additional evidence on the general atmosphere surrounding mathematical logic at that time and to the struggle of S. A. for its legitimacy and consolidation.

From the summary: There are currently comprehensive papers which document and analyze the legacy of S. A. Yanovskaya, and her contribution to history and philosophy of mathematics as well as to the formation and defense of mathematical logic in the USSR. The centenary of her birth is an appropriate opportunity to offer recollections which may add some traits to the picture of this eminent scholar and superb human being. We publish and comment on some documents, among them letters addressed to me by Yanovskaya.

Summary: The intention of the present paper is to elucidate at a more abstract (and hopefully more persuasive) level and relationship between modularity of net semantics and completeness of compositional proofs for nets. This is to be achieved by a separation of concerns which is not reflected in common terminology.

Summary: In the present sketchy survey we try to avoid cumbersome formalization, and to use often a very informal style, giving up mathematical rigor in favor of (hopefully) persuasive hints. Also, definitions of some important notions (mostly concerning syntax and semantics of nets) are omitted; references are given to existing sources. The main statements are summarized in Theorems. The auxiliary “Facts” are mostly adapted folklore or borrowed from our earlier papers. Proofs are completely omitted. We hope that despite these shortcomings, our presentation provides guidance in the area and contributes to a clearer understanding of the relationship between modularity, completeness and concurrency.

This paper is devoted to the compositional trace based proof systems for communicating processes. It comes in a line of publications by Gries, Owicki, Nguyen, Demers, Schneider, Widom, and Panangaden. Using the Brock-Ackerman anomaly, the Expressibility anomaly, and the Kernel anomaly, the authors explain some ‘vulnerable points” and limitations of the previous works on proof systems for networks. This paper gives a comparative analysis of some different models for processes and networks, focusing on the communication processes (traces are sequences of actions), snapshot processes (traces are sequences of states 0, and stuttering invariance of these processes. Attention is devoted to the compositional completeness of the proof rules.

Summary: We aim at a unified and coherent presentation of net models for concurrency like Petri nets and dataflow networks from the perspective of modularity and substitutivity. The major goal is to achieve a better understanding of the links between modularity issues for nets and laws (or anomalies) in algebras of processes and algebras of relations. To this end we develop Mazurkiewicz’s compositional approach which requires a careful analysis of homomorphisms from algebras of nets into algebras of processes and relations.
For the entire collection see [Zbl 0875.00067].

This aper is a presentation of another mathematical model to describe semantics of systems of concurrent processes. The processes are assumed to be defined by events to which they can respond, or in which they can engage. The presentation starts from a list of four models that have already been defined in the literature. The four models describe compositions of: linear (sequential) processes (e.g. CSP)$CSP)$, pomset (partially ordered multiset) processes (e.g. Petri nets), automaton (defined by transition diagrams) processes (e.g. CCS$CCS$), and event or behaviour structures (nets in general). The authors extend this list by so-called connected relations. The purpose of the new, fifth model is to capture algebraically concurrent systems that have so far eluded rigorous mathematical treatment as too complicated in any of the four models mentioned above. The connected relations model is promised to cope with systems such as P/T$P/T$ nets (the more sophisticated Petri nets) and data flow networks.
Connected relations can be defined for a variety of domains which may satisfy different finiteness conditions (generally, F$F$-domains). For the domain of natural numbers, connected relations have been known under the name of multitrees.
As in the four previous models, in connected relations there are basic process structurig operations: synchronization (combining processes to act concurrently), union (choice between processes), and hiding (elimination of events from the given combination of processes). Unlike in the four previous models, here processes may have values defined as connected relations in the corresponding F$F$-domain. If some relations in the F$F$-domain is a value of a process, the process is said to implement the relation.
The paper contains 2 examples how the connected relations model can be applied to data flow systems. Both are concerned with the problem of message passing in such systems. One is a description of data flow stream processing, and the other — processing of streams with “holes”.

Summary: [For the entire collection see Zbl 0758.00017.]
We investigate the relationship between three kinds of interpreted nets: nets of processes, nets of relations and nets of functions (or of sets of functions). The respective semantic definitions are based on three fundamental constructs: synchronization, strong conjunction and least fixed point operator.
We relate notions from concurrency, logic and domain theory and explain phenomena like Kahn’s principle and the Brock-Ackerman anomaly for data flow networks. We advocate the analysis of these phenomena on the abstract level of processes, relations and functions over arbitrary F$F$- domains instead of dealing only with concrete models of stream processing.
We get results which subsume and improve previous results on data flow networks and may be applied also to other formalisms describing distributed systems.

Summary: [For the entire collection see Zbl 0713.00018.]
We investigate and compare two ways of specifying stream relations (in particular - stream functions).
The first one uses relational programs, i.e. netlike program schemes in which the signature primitives are interpreted as relations over a given CPO. No stream domains are assumed; semantics is in fixed point style.
The second one is through data flow nets i.e., nets whose nodes are interpreted as processes (computational stations).
We prove the existence of an adequate data flow interpreter for relational programs over all relations (not only functional) and (essentially) its uniqueness. When dealing with functions the interpreter is modular and obeys the Kahn principle.
On the other hand analyzing the deviations from Kahn’s principle we identify two kinds of anomalies:
The first one (“meagerness” anomaly) is caused by the defect of the used processes (computational stations) and holds in fact for arbitrary (even for very simple functional) input-output behaviors. This anomaly may always be avoided through the use of appropriate processes.
The second (“ambiguity” anomaly) is rooted in the semantics of relational nets over arbitrary CPO (and not specifically over stream domains). It is unavoidable in any extension beyond functional behaviours.

[For the entire collection see Zbl 0683.68001.]
The three main tasks of the paper are: (1) To justify that Kahn’s principle (KP) is a linear interleaving phenomenon; (2) To provide a better understanding of the relationship between modularity and KP; and (3) To specify not only sufficient, but also necessary conditions to support the KP. Section 2 and 3 contain the conceptual background for input-output processes and nets of such processes. The considered models are: linear versus branching, or interleaving versus partial order. Section 4 deals with modularity issues for buffered linear processes. Smoothness is defined and argued that for classes of smooth processes there is a direct proof of modularity, without any fixed point arguments. In Section 5, the KP is revisited in order to reveal its full connection to communication and process theoretical phenomena. KP is proved to hold for the class of all smooth linear processes. Section 6 sketches the further research directions: higher-level processes, nondeterministic behaviour, parallelism.

[For the entire collection see Zbl 0669.00003.]
We examine situations where for a given system N there is a strong intuition and a general consensus about its interleaving behavior but the inherently causal aspects of the behavior are still to be discerned. As an application to the theory we aim at a better understanding of the semantics of Place-Transition systems.

Behavior structures integrate causality and branching. Nets of behavior structures provide a unifying approach to different net models of concurrency. The theory is illustrated with respect to nets over automata in particular with respect to Petri nets.

[For the entire collection see Zbl 0648.00002.]
This is rather a short historical survey than a paper giving new insight into the old matter. The title suggests that the following problem is to be considered: whether Turing or Church’s approach to computability has had more influence on programming methodology and philosophy in the history of computer science. Actually the author advocates as much as possible Church’s lambda calculus, whereas Turing machines and computability are merely mentioned in the introduction. Section 2 contains a non-formal and standard presentation of lambda calculus (without η$\eta$-conversion and without Church-Rosser property). Section 3 explains what is LISP for those who know LISP.
In Section 4 Landin’s language ISWIM is presented. It is a great pity that the author took ISWIM as an example instead of the language ML, since the first adds only some syntactic sugar to LISP while the latter is the substantial extension of LISP. Section 5 is on the history of denotational semantics. The precise denotational semantics for typed ISWIM is also given. It seems to be the most innovative part of the paper. In Section 6 assignment and go to statements are analyzed from the view-point of lambda calculus. The author proposes to translate assignment and go to statements into ISWIM, and this way to define their denotational semantics. Section 7 deals with parallelism, but somewhat painfully. No clear hint how to convolve lambda computability with parallelism is given. The paper is easy in reading and understanding.

[For the entire collection see Zbl 0695.00003.]
We illustrate the impact of logical relations revising some earlier work [the author, Lect. Notes Comput. Sci. 45, 137-152 (1976; Zbl 0352.02028); J. Y. Halpern, A. R. Meyer and the author, 11th ACM Symp. Principles of Programming Languages, 245-257 (1984)], presenting a simple version of results on observational equivalence obtained by J. C. Mitchell and A. R. Meyer [Lect. Notes Comput. Sci. 193, 225-236 (1985; Zbl 0565.68029)] and formulating some open questions. In particular we address the following topics: schematological abstractness and invariance with respect to locations.

The book presents a detailed account of the history of the development of Computer Science in the Soviet Union. The described period begins in the early 1950’s and ends in 1980. The author’s attention is focused on the three areas: finite automata, combinatorial complexity and algorithmic complexity. All significant achievements made by Soviet mathematicians in these domains are compared with similar results obtained in the West. The favourite research areas, the history and the main results of various research centers are presented. Special attention is given to the original results that are not well known in the West.

[For the entire collection see Zbl 0533.00026.]
The advantage of denotational over operational semantics are argued. A denotational semantics is provided for an ALGOL-like language with finite-mode procedures, blocks with local storage, and sharing (aliasing). Procedure declarations are completely explained in the usual framework of complete partial orders, but cpo’s inadequate for the semantics of blocks, and a new class of store models is developed. Partial correctness theory over store models is developed for commands which may contain calls to global procedures, but do not contain function procedures returning storable values.

The paper gives an exhaustive survey of the formal semantics of programming languages. Three basic approaches are considered: operational, denotational and axiomatic semantics. The author tries to assemble all these approaches in a uniform theory, i.e. that of algorithmic logic. Recursive procedures, module nesting and other sophisticated program constructs (like nondeterminism, random assignment etc.) are investigated. Besides the strict and elegant definitions, the various wellknown questions are discussed (effectivity problems, definability, axiomatizability etc.). Proofs are omitted and the author refers to the references.

The paper is another attempt to introduce a new construct into algorithmic logic. The aim of the paper is to characterize in a formal system procedure calls taking into account their syntactic environment. The approach is similar to that of Dynamic Logic, i.e. it admits nondeterminism and modalities. A formal system with some number of axioms and two spectal rules is described and analyzed.

The theoretic analysis of relaxation rules of Hoare’s logic is presented. These rules do not concern program constructs (like iteration, branching, recursion etc.) but they have rather general logical nature, as e.g. The author characterizes theoretically a wide class of relaxation rules, but does not give any evidence for their applicability. Moreover the incompleteness of Hoare’s logic, the main defect of this approach, remains unchanged when finite relaxation rules of any kind will be attached to that logic. The reviewer uses the term Hoare’s logic instead of algorithmic logic, because the first one is more relevant in spite of different opinion of the author.

Übersetzung aus Teor. Algorif. Mat. Logika, 159-176 (Russisch) (1974; ZbI. 304.02014).

This paper is a survey of results connected with the notion of frequency algorithm, which is related with the notions of approximative and probabilistic algorithm. A function f$f$ is said to be computed by an algorithm A$A$ with frequency r/n$r/n$ iff for every input (x1,…,xn)$\left(x_1,\dots ,x_n\right)$ the algorithm produces (y1,…,yn)$\left(y_1,\dots ,y_n\right)$ such that at least r$r$ of the equations f(x1)=y1,…,f(xn)=yn$f\left(x_1\right)=y_1,\dots ,f\left(x_n\right)=y_n$ are correct. Interesting theorems: 1. Any predicate P$P$ computable with frequency r/n>1/2$r/n>1/2$ is also computable in the usual sense. 2. There is an algorithm which computes uncountably many predicates with frequency 1/2. 3. For any computable function τ$\tau$ and for any n≥2$n\ge 2$ there is a predicate P$P$ such that: a) P$P$ is computable with frequency (n−1)/n$(n-1)/n$ in real time. b) P$P$ is not computable in the usual sense within time t$t$. Furthermore the concept of frequency computations is adapted to infinite sequences (x1,…,xn,…)$\left(x_1,\dots ,x_n,\dots \right)$ of inputs, and identification of black boxes by frequency algorithms is considered.

One of the best short introductions to the problem of decidability including many examples and applications.

Es handelt sich hier um eine elementare Einfihmung in die Grundbegriffe der Algorithmentheorie. Der Text ist klar und genau geschrieben, die meisten Details sind ausgefihrt. Nach einer breiten Einfihrung, in der der intuitive Algorithmenbegriff, Labyrinth- und Wortprobleme sowie einfache Rechner und ihre Maschinenprogramme betrachtet werden, folgen in der angegebenen Reihenfolge die Themen: Turing-Maschinen, die Verwendung von Unterprogrammen, rekursive Funktionen, Varianten äuBerer Speicher und algorithmisch unlösbare Probleme. Zum AbschluB geht Verf. auf kompliziertheitstheoretische Fragen und auf eindimensionale Zellularautomaten ein. Kommentare und auf weiterfiuhrende Literatur hinweisende Schlubbemerkungen sind eine wertvolle Ergänzung. Für Anfänger ist dieses Buch sehr gut geeignet als erste Einführung in seinen Gegenstand.

Translation from Trudy mat. Inst. Steklov 133, 221-232 (1973; Zb1. 292.02032).

The probabilisitic p-machines investigated in this paper are one-head Turing machines, that on each step receive in addition to the type-symbol also the output of a binary Bernoulli source with probabilities p, 1−p$1-p$. Deterministic machines may be identified with 1 -machines. The (perhaps partially) predicate Γ$\mathrm{\Gamma }$ is computed by the p-machine N$N$ with reliability Δ≥1/2$\mathrm{\Delta }\ge 1/2$ if and only if for each x$x$ in the domain of Γ$\mathrm{\Gamma }$ with probability >ΔN$>\mathrm{\Delta }N$ completes the computation and the result is Γ(x)$\mathrm{\Gamma }(x)$. The corresponding running time tN(x,Δ)$t_N(x,\mathrm{\Delta })$ is defined as the least t$t$ such that N$N$ with probability >Δ$>\mathrm{\Delta }$ completes the computation in t$t$ steps and the result is Γ(x)$\mathrm{\Gamma }(x)$. Basic results: 1) Case p=1/2$p=1/2$. Characteristic functions of NP-sets are computable with t(x,1/2)≤P(|x|)$t(x,1/2)\le P(|x|)$, where P$P$ is polynomial (though deterministic computations are presumably essentially slower). A partial predicate is described for which a computation with reliability Δ>1/2$\mathrm{\Delta }>1/2$ exists, that is essentially faster then each deterministic computation. 2) Arbitrary p$p$ and Δ>1/2$\mathrm{\Delta }>1/2$. Let Γ$\mathrm{\Gamma }$ be a predicate defined on the set of all positive integers; unary representation of integers is assumed. Then with a suitable p$p$, a p-computation of Γ$\mathrm{\Gamma }$ is possible in running time ≤4n(1+o(n))$\le 4^{n(1+o(n))}$. Nevertheless for each fixed λ(n)=o(4n)$\lambda (n)=o\left(4^n\right)$ among the predicates which are deterministically computable in running time 2O(4n)$2^{O\left(4^n\right)}$ such one exists, for which no p-computation (with arbi-020 trary p$p$ ) is possible in λ(n)$\lambda (n)$ steps. [Comment: By fast probabilistic p-computations sufficient information about p$p$ is not available.] Let p$p$ be a constructive real number and let Φp(n)${\mathrm{\Phi }}_p(n)$ denote the deterministic running time in computing the first n$n$ figures in the binary expansion of p$p$, p-machines with Φp(n)=o(2n)${\mathrm{\Phi }}_p(n)=o\left(2^n\right)$ do not allow computations which are essentially faster than 1/2-computations. Note: In VI Annual ACM Symposium on Theory of Computing (1974) a paper of J. T. G i11$i11$ III appear in which the definition of t(x,Δ)$t(x,\mathrm{\Delta })$ and some analogous results about 1/2$1/2$-computations are given.

Conditions A-B-C (see below) are formulated, which to the authors opinion must be fulfilled in any reasonable formalisation of ”program schema in signature ⟨x,φ1,…,ωk,P1,…,Pm⟩"$⟨x,{\phi }_1,\dots ,{\omega }_k,P_1,\dots ,P_m⟩"$. These conditions are proved to be sufficient for the translatability into schemas from Chandra and Manna class (arrays and equality tests between terms are allowed). Notations: Exec(R, Im$\mathrm{Im}$ ) = I-schema R$R$ is applicable to model Im$\mathrm{Im}$ and the result of is execution is y$y$ (Note that only models are considered with total functions ϕ1${\varphi }_1$ and total predicates Pf$P_f$ ). A. Let λ$\lambda$ be an isomorphism of the model Im$\mathrm{Im}$ onto some model ξ′${\xi }^{\mathrm{\prime }}$. Then B. For any I let τ(Im)$\tau (\mathrm{Im})$ be its smallest submodel, that contains the initial element x$x$ of the domain S$\mathfrak{S}$ and is closed under the functions φ1${\phi }_1$. Then: Let T$T$ be the set of all terms in x$x$ and φ1,T∈T,R${\phi }_1,T\in T,R$ a finite subset of T$T$ with consistently defined equality relation and predicates Pj$P_j$. The pair ⟨Re,τ⟩$⟨\mathrm{Re},\tau ⟩$ is R$R$-consistent =$=$ for each factor-termal model G$G$ such that Re$\mathrm{Re}$ is a restriction of Im,Exec(R,Im)=τ$\mathrm{Im},\mathrm{Exec}(R,\mathrm{Im})=\tau$. C. The set of all R-consistent pairs is recursivelyenumerable.

The function f$f$ of natural numbers is autoreducible if f$f$ can be computed by a Turing machine T$T$ with oracle f$f$ in such a way that T$T$ does not ask ” f(n)=$f(n)=$?” while computing T(n)$T(n)$ (but possibly asks f(m)=$f(m)=$? for m≠n$m\ne n$ ). A set or predicate is autoreducible if its characteristic function is. Any random sequence (in the sense of Kolmogorov-Loveland) is nonautoreducible, but this gives no information on recursively enumerable (r.e.) sets. Theorem 1. There exists a nonautoreducible r.e. set with non-immune complement. Theorem 2. There exists a nonautoreducible r.e$r.e$. set with immune complement (and no choice strategy can select from the corresponding 0,1-sequence any subsequence consisting entireIy of 0). Similar theorems for recursive sets are formulated in terms of computational complexity estimates. In particular, for any h$h$ there exists a recursive set of complexity h$h$ which cannot be autocomputed in any essentialy simpler way. Autoreducibility is not invariant under m-reducibility: put n∈G′↔[n/2]∈G$n\in G^{\mathrm{\prime }}\leftrightarrow [n/2]\in G$. Then G′$G^{\mathrm{\prime }}$ is autoreducible. Some nontrivial autoreducibility results are proved in $4$\mathrm{\$}4$. As consequences the author obtains previous results by Meyer and Fisher, and Hodzaev.

A large part of this book is devoted to varlous aspects of the behaviour of finite automata: the presentation of languages and ω$\omega$-languages, the realization of operators, the description andestimation of various behavioral parameters and spectra. Also the synthesis of automata on the basis of metalanguages is considered. Chapter IV is devoted to the concept of automaton identification, i.e. to the problem to construct for a given initialized automaton with unknown (or almost unknown) internal structure an automaton which functions in the same way as the given one. The ”statistical” estimates are based on a stochast1c procedure with equiprobable outcomes. So the probabllities are replaced by relations between the number of all automata which can be outcomes of this procedure and the number of such automata which possess an adequate property. Sections II.9 and II.10 of the original Russian edition (1970; th1s ZbI. 211, 21) are replaced by a version written by L$L$. Landweber. Translator’s notes refer to the different use of terms in the IIterature. It has to be noticed that the proof of theorem 1.14 a) is wrong like in the original edition. I think that this translation will find a lot of interested readers.

See the review of the Russian original in Zbl 0199.31201.

In this book the theory of finite abstract automata is developed. It consists of sex chapters. In Chapter C$C$ the concept of autonaton and different kinds of automata are presented, as well as their representations hy graphs are introduced. Chapter 1 is concerned with automata without outputs. In Chapter 2 automata with outputs and their equivalence are studied. The authors give estimates for the numbers of states of automata inducing a given mapping with finite welght. In Chapter 3 different kinds of meta-languages and syntheses regarding these metalanguages are revlewed. Chapter 4 is devoted to studying certaln types of declpherings strongly related to experiments on automata. Chapter 5 comprises of statistical estimates with respect to the investigations of the previous Chapter. The book is well-written. The authors give a rather comprehensive presentation of the theory without increasing too much the volume of the book by supplementing each chapter by further results (w1thout proofs) dealing with the subject matter of the relevant chapter. To ald the reader to understand the maln results several examples are also added.

It is well known [see, for example, W. W. B o ne$\mathrm{n}e$, Ann. of Math., II. Ser. 83, 520-571; 84, 49-84 (1966; this Zbl. 173, 12,13)], that for any recursively enumerable (r⋅e)$(r\cdot e)$ set Π$\mathrm{\Pi }$ one can build a finite presented ( f.p$f.p$. ) group G(Π)$G(\mathrm{\Pi })$ such that the solvability problem for Π$\mathrm{\Pi }$ is effectively reduced to the word problem for G(Π)$G(\mathrm{\Pi })$ and, vice versa, the word problem for G(Π)$G(\mathrm{\Pi })$ is reduced to the solvability problem for Π$\mathrm{\Pi }$. One of possible constructions of this kind is a construction of Boone which the author, in virtue of historical reasons, calls the construction of Novikov-Boone. The author makes clear the complexity of reduction algorithm of the problems pointed above. As a result of accurate analysis of these algorithms it becomes clear that both reductions can be made without extension. This means that if reducing the word problem for the group G(Π)$G(\mathrm{\Pi })$ to the solvability problem for I is carried out by the Turing machine with II-oracle, then for processing the word W$W$, written on the tape of this machine, only those cells of the tape are used where this word is. From here, particularly, it follows that the solvable word problems for f.p$f.p$. groups realize in themselves all the complexities of recursive sets.

Vgl. die Besprechung des russischen Originals in diesem Zb1$\mathrm{Z}\mathrm{b}1$.

Es werden einige Abschätzungen für die Kompliziertheit von Algorithmen gefunden, die in den Termini der oben besprochenen Arbeit des Verf. charakterisiert werden. Im §1$\mathrm{\S }1$ wird der Begriff der Kapazitätsfunktion bei gegebener Berechnung der Turing-Maschine gegeben, sowie auch einige Behauptungen über diese Funktionen und die Definition des Begriffs der optimalen Berechnung. $2$\mathrm{\$}2$ enthält die Formulierung der Resultate, und im $3$\mathrm{\$}3$ finden sich die Beweise. AuBerdem wurde die Existenz solcher Modelle gezeigt, für die das Übergehen ohne komplizierte Algorithmen vom Typ ”Aufzählen aller Varianten” (die Hypothese von W. JablonskiI) unmöglich ist.

Vgl. die Besprechung des russischen Originals in diesem Zbl. 104, 355.

Es wird die Frage der Kompliziertheitsabschätzung der Berechnungen an Turing- Maschinen betrachtet. Die Kompliziertheit wird bezüglich der Dauer (die Anzahl der Maschinengänge) in Abhängigkeit von der Länge (die Buchstabenanzahl) der Ausgangsdaten abgeschätzt. Bei diesem Standpunkt bezeichnet man als einfachste Berechnungen diejenigen, die ohne eine Verzögerung verwirklicht werden, d.h. ihre Dauer überschreitet nicht die Länge der Ausgangsdaten. Im §1$\mathrm{\S }1$ werden die grundlegenden Begriffe eingefihrt, und es wird ein Lemma für die Abschätzungen bewiesen. Im §2$\mathrm{\S }2$ werden Sätze bezüglich dem Begriff der Berechnung mit logarithmischer (oder sublogarithmischer) Verzögerung bewiesen. Es wird gezeigt, daß die Kompliziertheit bei solchen Berechnungen am nähesten (im gewissen Sinne) zur Kompliziertheit bei Berechnungen ohne Verzögerung steht. Im §3$\mathrm{\S }3$ wird gezeigt, daß unter den Funktionen, die mit logarithmischer Verzögerung berechnet sind solche existieren, die ohne Verzögerung nicht berechenbar sind.

This paper presents and formalizes some notions and concepts widely used in the theory of finite automata and related to other topics such as recursive arithmetic and predicate calculus. - Thus the behaviour and structure of finite automata are presented by means of the general and partial A-operators and their canonical equations. The language of canonical equations is used as an intermediary in the process of translation from the initial language into the scheme language, when synthesizing finite automata. The problem of the initial language is then discussed and the possibility of using languages based on the predicate calculus are investigated. Finally, an asymptotical evaluation of the structural complexity for the logical networks with memory is given.

Vgl. die Besprechung des russischen Originals in diesem Zbl. 71, 246.

In diesem Beitrag knüpft der Verf. an das bekannte Buch,Einführung in die Theorie der endlichen Automaten” (1962, dies. Zbl. 104, 355) von N. E. Kobrinskij und dem Verf. an. Es werden endliche Automaten, die ein Wort in ein Wort derselben Länge transformieren, untersucht. Diese Transformation kann mit Hilfe eines Baumes beschrieben werden, wie es in dem erwähnten Buch erörtert wurde. Die minimale Anzahl der Zustände eines endlichen diese Transformation realisierenden Automaten ist gleich dem Gewicht k(v)$k(v)$ des Baumes v$v$. Es werden hier zwei asymptotische Abschätzungen für k(v)$k(v)$ abgeleitet.

Es seien f$f$ eine einstellige Funktion, T$T$ eine einstellige rekursive Funktion, m$m$ und n$n$ derartige naturliche Zahlen, daß n>0,m≤n$n>0,m\le n$. Man sagt, f$f$ lasse sich mittels T$T$ mit der Frequenz m/n$\mathrm{m}/\mathrm{n}$ berechen, wenn es für beliebige paarweise verschiedene natürliche Zahlen x1,…,xn$x_1,\dots ,x_n$ unter den Gleichungen f(x1)=T(x1),…,f(xn)=T(xn)$f\left(x_1\right)=T\left(x_1\right),\dots ,f\left(x_n\right)=T\left(x_n\right)$ mindestens m$m$ wahre gibt. Die Funktion f$f$ heißt frequenzberechenbar, wenn sie sich mit ei. ner gewissen Frequenz mittels einer gewissen rekursiven Funktion berechnen läßt. Das Myhill-Routhsche Problem besteht in der Klärung folgender Fragen: 1) Existieren frequenzberechenbare Funktionen, die von den rekursiven verschieden sind? 2) Hängt der Vorrat frequenzberechenbarer Funktionen von der vorgegebenen Frequenz ab$ab$? - Es werden folgende Hauptresultate angefuhrt: 1. Die Menge der Funktionen, die mit der Frequenz m/n>12$\mathrm{m}/\mathrm{n}>\frac{1}{2}$ mittels einer gegebenen rekursiven Funktion berechenbar sind, ist höchstens abzählbar; zwei beliebige Funktionen aus dieser Menge unterscheiden sich höchstens für 2(n−m)$2(n-m)$ Werte des Arguments. - 2. Es existiert eine rekursive Funktion, die mit der Frequenz 12$\frac{1}{2}$ eine nichtabzählbare Menge von einstelligen Prädikaten berechnet. - 3. Jede Funktion, die mit einer Frequenz größer als 12$\frac{1}{2}$ berechenbar ist, ist gleich einer gewissen rekursiven Funktion. - Anmerkung des Ref. Der im Artikel eine wesentliche Rolle spielende Begriff der ”willkürlichen Funktion” wird vom Verf. nicht präzisiert und nicht erläutert. Daher erfordern die Resultate des Verf. (sowie die Problemstellung selbst) bei ihrer Betrachtung im Rahmen der konstruktiven Mathematik eine bestimmte Korrektur.

Vgl. die Besprechung des russischen Originals in diesem Zbl. 38, 150.

Vgl. die Besprechung des russischen Originals in diesem ZbI. 115, 7.

This is an excellent introduction to the theory of finite automata. It is probably also the only book which at present exists in its field, for it is a textbook, intended for students and engineers as well as mathematicians, which is quite self contained. It takes the reader through the necessary elementary logic and the operating details of the various types of physical elements in use to all the important theorems of finite automata theory which have any practical application. It is well organised and easy to read, being well illustrated by examples. The beginner should have no difficulty in following it all and the expert will find it valuable for the full exposition given of Trahten brot’s own work. An important contribution to the literature. The first chapter gives a brief but adequate treatment of the necessary parts of propositional, predicate and extended predicate logic with bounded as well as with unbounded quantifiers. It includes theorems on minimisation and representation of Boolean functions (applications of a basic theorem of Lupanov). The second starts off with a discussion of (input-output) operators and definitions of deterministic and bounded operators. An operator is said to be bounded if it has only a finite number of distinct residual operators; the residual operator associated with a fixed input sequence f0(1),…,f0(t0−1)$f_0(1),\dots ,f_0\left(t_0-1\right)$ being the operator which associates with an input sequence f(1),f(2),…$f(1),f(2),\dots$ the sequence of outputs produced for t≧t0$t\geqq t_0$ by the input sequence f0(1)…f0(t−1)f(1),f(2)…$f_0(1)\dots f_0(t-1)f(1),f(2)\dots$ A representation of deterministic operators by infinite trees is given, in which the branches from each point correspond from left to right with the input symbols in some fixed order, and are labelled with the output symbols produced. This leads on to a proof that a necessary and sufficient condition for an operator to be realisable by a finite automaton is that it be bounded and deterministic. Circuits of automata and logical nets are then considered and it is shown how every bounded deterministic operator can be realised by a logical 23∗${23}^{\ast }$ net. Chapter 3 is devoted to a survey of the physical properties of the types of basic element used in real automata - electromagnetic. semi-conducting, flip-flop, ferromagnetic. In each case methods of constructing circuits for the basic Boolean functions are given. Chapter 4 - the analysis of automata - contains basic theorems involving representing automata by their set of states and transfer and output functions, e.g. algorithms for deciding whether two bounded deterministic operators are the same or not, various questions concerning the periods of the output resulting from a periodic input. Chapter 5 is on ways of giving automata - by finite trees, transition matrices, next state and output functions as Boolean functions of present state and input, by formulae of the extended predicate calculus with bounded individual quantifiers. It is valuable to have this full treatment of the latter representation, due to Trahtenbrot himself. He also mentions the well known Kleene representation in terms of regular sets and shows how to translate from this into his own system. Chapter 6 is on practical methods of synthesis of automata and contains many examples, illustrating the application of the results of the earlier chapters. The final chapter 7 is on asymptotic bounds for the complexity of logical nets. The general problem is this: let an index of complexity (a positive real number) be assigned to each basic element and let the index of complexity of a net be defined as the sum of indices of complexity of its elements. Then bounds and asymptotic formulae are sought for the function L(m,n,k)$L(m,n,k)$ which is the upper bound of the set of smallest indices of complexity corresponding to realisations of all bounded deterministic operators of weight ≦2k$\leqq 2^k$ (i.e. corresponding to automata with ≦2k$\leqq 2^k$ states). These have been known for some time for k=0$k=0$ but the treatment of the case k≠0$k\ne 0$ is largely Trahtenbrot’s own work, though the methods used derive from Lupanov. Full details are given, together with a discussion of classes of operators having particularly simple realisations and of the simplifications which can be effected when one is free to choose the coding of input and output.

En utilisant la même méthode que dans le travail [ibid. 118, 646-649 (1958; ce Zbl. 84, 11)], l’A. resoud un problème de Tarski et de même on montre la possibilité de transférer certains résultats de la théorie d’algorithmes aux automats finis. Soit I le calcul de prédicates un-locaux, dans lequel sont admis seulement les quantificateurs restrictifs pour les variables et les quantificateurs non-restrictifs pour les prédicats; le domaine des variables est l’ensemble des nombres naturals. L’A. montre que chaque ensemble de nombres naturals définissable dans I est un ensemble périodique. Par ce résultat on résoud négativement le deuxième problème de Tarski; si l’addition est définissable dans I.

The second of these papers may be regarded as a (very useful) summary without proofs of the main theorems of the first which contains full proofs. They deal with the relation between finite automata and a system E$E$, which is usually called restricted second order arithmetic (individual variables ranging over natural numbers, monadic predicate variables ranging over arbitrary sets of natural numbers, 0,’(successor), propositional connectives, and quantifiers for both types of variable). They overlap slightly with Elgot (this Zbl. 111, 11) and Büchi [Proc. Congr. Logic, Methodology and Philosophy of Science 1960) p. 1-11) where a decision method for E$E$ is given. (This was not announced until these papers had reached the proof stage and some of the results here are stated as being conditional on the existence of a decision method for E$E$ ). The problems which are elegantly solved here are 1. the study of the sets and operators describable in E;2$E;2$. deciding which formulae represent operators realisable by finite automata and finding an algorithm for synthesing such an automaton when it exists. A valuable contribution to automata theory.

After defining logical nets, the effective transformation of the informations passing through a net, and the structure of a net there is given a detailed examination. Elements of the theory of codification and of the algebra of logics prepare the last section of this paper, which is on the synthesis of logical nets.

Lupanov has recently [Izvestija vysš. učebn. Zaved., Radiofizika Nr. 1, 120 (1958)] given a method of synthesis of logical nets leading to an asymptotic formula L(n)∼ϱ2n/n$L(n)\sim \varrho 2^n/n$, where L(n)$L(n)$ is the least number such that every Boolean function of n$n$ arguments may be realised by a net with index of simplicity ≦L(n)$\leqq L(n)$; here ϱ$\varrho$ is the least of the specific weights of the elements of the basis. If Q(n)=22n=$Q(n)=2^{2^n}=$ the number of n$n$-argument Boolean functions then this formula takes the form L(n)∼ϱlogQ(n)/loglogQ(n)$L(n)\sim \varrho \log Q(n)/\log \log Q(n)$. In this paper the author studies the corresponding problem for logical nets with memory, where the basis includes delay elements as well as elements realising Boolean functions and where feedback loops are allowed in the construction of the nets. The formula he obtains is L(n,m,k)∼ϱlogQ(n,m,k)/$L(n,m,k)\sim \varrho \log Q(n,m,k)/$ loglogQ(n,m,k)$\log \log Q(n,m,k)$; here Q(n,m,k)$Q(n,m,k)$ denotes the number of operators with n$n$ binary inputs, m$m$ binary outputs using ≤2k$\le 2^k$ internal states. He shows also that the proportion of operators of this kind which are realisable with index of simplicity <(1−ε)$<(1-\epsilon )$ times this estimate, tends to 0 as n+k→∞$n+k\to \mathrm{\infty }$ and logm/(n+k)→0$\log m/(n+k)\to 0$. He points out that the formula still holds if irreducible operators only are considered, also if together with (or in place of) delay elements other elements of finite weight (e. g. binary counters) are included in the basis. If elements with more than one output are used in the basis the formula still holds with a slightly different definition of ϱ$\mathit{\varrho }$. The methor of synthesis uses Lupanov’s method for the construction of some of the blocks needed to yield the operator; however a crucial step is the use in one block of a method of construction based on taking an optimal binary coding of the states of the operator together with a construction for obtaining monotonic operators by means of nets with less than average index of simplicity.

Vgl. die Besprechung des russischen Originals in diesem Zbl. 80. 114.

L’A. fait l’étude des schémas sans répétition en utilisant les méthodes d’Analysis situs. Il s’agit des fonctions booléennes à n$n$ variables réalisables avec n$n$ contactes. Les méthodes de synthèse des schémas sans répétition permettent d’effectuer la synthèse de schémas plus complexes. L’A. donne différents exemples d’application des méthodes.

The author gives a new characterization of the operators realizable by logical nets (i. e., finite automata). Consider the formal language L$L$ which has variables for individuals and for monadic predicates with the usual sentential connectives &, v,7$v,7$, with unbounded universal and existential quantifiers over the predicate variables Let a formula Q(X1,…,Xn;t)$Q\left(X_1,\dots ,X_n;t\right)$ of L$L$ which has X1,…,Xn$X_1,\dots ,X_n$ as the only free predicate variables and t$t$ as the only free individual variable be called a t$t$-formula if every individual quantifier which occurs in it is bounded above by t$t$ or by a variable bounded above by t$t$ or by a variable bounded above by a variable bounded above by t$t$ etc. If the individual variables are thought of as ranging over discrete instants of time t=0,1,2,…$t=0,1,2,\dots$ and all the symbols are given their usual meaning then such a formula can be regarded as defining a certain operation which maps the n$n$ input predicates X1,…,Xn$X_1,\dots ,X_n$ onto an output predicate Z$Z$ defined by Z(t)=A(X1,…,Xn;t)$Z(t)=A\left(X_1,\dots ,X_n;t\right)$. It is easily seen that for the case of a finite automaton with n$n$ binary input channels whose state at time t$t$ is given by Xi(t)(t=0,1,…;i=1,…,n)$X_i(t)(t=0,1,\dots ;i=1,\dots ,n)$ and a single output channel whose state at time t$t$ is Z(t)$Z(t)$ the value of Z(t)$Z(t)$ is given by a t$t$-formula A(X1,…,Xn;t)$A\left(X_1,\dots ,X_n;t\right)$. The author’s result is that the converse holds, i$i$. e. that to each such t$t$-formula corresponds a finite automaton. He sketsches the proof, which actually provides an algorithm for the construction of the automaton (e.g. in terms of delays and stroke elements). He points out that the method is applicable to a wider class of languages, e.g. it is possible to allow also two sided bounded quantifiers (x)$(x)$ etc. However he emphasises that if one tries to extend to too rich a. language Ω$\mathrm{\Omega }$ algorithms for deciding whether a formula represents a transformation realizable by a finite automaton and for synthesizing such an automaton when it. exists one soon comes up against algorithmic unsolvability of these problems, e.g., if Ω$\mathrm{\Omega }$ allows the usual schemes of recursive (or even a few primitive recursive) definition. Finally he says that all this can be interpreted in terms of the characterization of the representation of events in finite automata given by Kleene [Sha n non, C. E. and J. McCarthy, Automata studies (Ann. of Math. Studies Nr. 39, Princeton 1956), p. 3-41] and Medvedev (Sbornik Avtomati IL. 1956) For example the operation S1→S$S_1\to S$ introduced by Medvedev can immediately be written in the above form aince it is equivalent to an existential quantification on predicate variables.