Fundamentals of Computation Theory

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.