Fundamentals of Computation Theory

This volume contains abridged versions of most of the sectional talks and some invited lectures given at the International Conference on Fundamentals of Computation Theory held at Kazan State University, Kazan, USSR, June 22-26, 1987. The conference was the sixth in the series of FCT Conferences organized every odd year, and the first one to take place in the USSR. FCT '87 was organized by the Section of Discrete Mathematics of the Academy of Sciences in the USSR, the Moscow State University (Department of Discrete Mathematics), and the Kazan State University (Department of Theoretical Cybernetics). This volume contains selected contributions to the following fields: Mathematical Models of Computation, Synthesis and Complexity of Control Systems, Probabilistic Computations, Theory of Programming, Computer-Assisted Deduction. The volume reflects the fact that FCT '87 was organized in the USSR: A wide range of problems typical of research in Mathematical Cybernetics in the USSR is comprehensively represented.

Inhalt
Possibilities of probabilistic on-line counting machines.- Functional systems on semilattices.- Recognition of properties in k-valued logic and approximate algorithms.- Linearized disjunctive normal forms of boolean functions.- On a stable generating of random sequences by probabilistic automata.- Automata classes induced by Post classes.- Effective lower bounds for complexity of some classes of schemes.- Stable finite automata mappings and Church-Rosser systems.- The recursion theorem, approximations, and classifying index sets of recursively enumerable sets.- Duality of functions and data in algorithms description.- On direct methods of realization of normal algorithms by turing machines.- Verbal operation on automaton.- The new way of probabilistic compact testing.- Computational problems in alphabetic coding theory.- On the synthesis of "Irredundant" automata from a finite set of experiments.- On the equivalence problem of states for cellular automata.- Arsenals and lower bounds.- Chain like model of programs communication.- Structor automata.- On A-completeness for some classes of bounded determinate functions.- Structure synthesis of parallel programs (Methodology and Tools).- Saturating flows in networks.- On the number of DNF minimal relatively arbitrary measures of complexity.- Soliton automata.- On development of dialogue concurrent systems.- Discrete analogue of the Neumann method is not optimal.- A simplest probability model of asynchronous iterations.- Semantic foundations of programming.- Conditions for existence of nontrivial parallel decompositions of sequential machines.- On the digital system diagnostics under uncertainty.- The implicating vector problem and its applications to probabilistic and linear automata.- Some asymptotic evalutions ofcomplexity of information searching.- On the complexity of approximate realization of continuous functions by schemes and formulas in continuous bases.- Codes, connected with a fraction linear functions group and their decoding.- On the capabilities of alternating and nondeterministic multitape automata.- Fast parallel algorithms for optimal edge-colouring of some tree-structured graphs.- On the complexity of elementary periodical functions realized by switching circuits.- Efficient algorithmic construction of designs.- On the complexity of Lie algebras.- A characterization of sequential machines by means of their behaviour fragments.- Some observations about NP complete sets.- Three-dimensional traps and barrages for cooperating automata.- Efficient implementation of structural recursion.- Minimal numberings of the vertices of trees Approximate approach.- Dyck1-reductions of Context-free Languages.- Information flow and width of branching programs.- On some operations of partial monotone boolean function simplifying.- On complexity of computations with limited memory.- On the problem of completeness for the regular mappings.- The number and the structure of typical Sperner and k-non-separable families of subsets of a finite set.- A criterion of polynomial lower bounds of combinational complexity.- On generalized process logic.- Verification of programs with higher-order arrays.- On the complexity of analyzing experiments for checking local faults of an automaton.- Exponential lower bounds for real-time branching programs.- On the conditions of supplementicity in functional systems.- On one approximate algorithm for solving systems of linear inequalities with boolean variables.- The problem of minimal implicating vector.- Built-in self-testing of logic circuitsusing imperfect duplication.- Algebras with approximation and recursive data structures.- Procedural implementation of algebraic specifications of abstract data types.- On the complexity of realizing some systems of the functions of the algebra of logic by contact and generalized contact circuits.- On construction of A complete system of compression functions and on complexity of monotone realization of threshold boolean functions.- Diophantine complexity.- The power of nondeterminism in polynomial-size bounded-width branching programs.- Estimation algorithms of infinite graphs percolation threshold.- A solving of problems on technological models.- Some formal systems of the logic programming.- On the Programs with finite development.- D-Representing code problem solution.- Metric properties of random sequence.- Adaptive strategies for partially observable controlled random series.- The degrees of nondeterminism in pushdown automata.- Statistically effective algorithms for automata control.- Linear test procedures of recognition.- Evaluation of cardinalities of some families of ?-classes in $$P_{\aleph _0 }$$ .- On the temporal complexity of boolean mappings realizations in two-dimensional homogeneous automata.- On approximate solution of the problem of equivalent transformations of programs.- Randomized parallel computation.- On checking correctness of some classes of control systems.- The parallel complexity of some arithmetic and algebraic operations.- On difficulties of solving a problem of decomposition of the system of boolean equations.- The number of fuzzy monotone functions.- Bounded set theory and polynomial computability.- Index sets of factor-objects of the Post numbering.- On realization of boolean functions by schemes consisting of checkedelements.- The complexity of the sequential choice mechanism.- Nondeterministic finite algorithmic procedures as the models of abstract computability.- The reducibility of random sequences by automata.- On structure complexity of normal basis of finite field.- On comparison of boolean bases.- A tradeoff between pagenumber and width of book embeddings of graphs.- On metric properties of automata and ?-approximation of automaton mappings.- Algorithmization of obtaining the converse comparison theorems based on solving a logical equation.- Synthesis of universal finite automats.- On cartesian powers of P2.- Complexity gaps of Turing machines on infinite words.- Distributed infimum approximation.- On the number of keys in relational databases.- Complexity and depth of formulas realizing functions from closed classes.- Reliable networks from unreliable gates with almost minimal complexity.- On the standard and pseudostandard star height of regular sets.- To automation of theorem synthesis.- On efficiency of prefix word-encoding of binary messages.- Deductive program synthesis and Markov's principle.- Complexity of the problem of approximation of stochastic matrix by rational elements.- To the functional equivalence of Turing machines.- Theorem proving in intermediate and modal logics.- The analysis of concurrent logic control algorithms.- On a connection between the resolution method and the inverse method.