Fundamentals of Computation Theory

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Possibilities of probabilistic on-line counting machines
3. Altmetric Badge
   Chapter 2 Functional systems on semilattices
4. Altmetric Badge
   Chapter 3 Recognition of properties in k-valued logic and approximate algorithms
5. Altmetric Badge
   Chapter 4 Linearized disjunctive normal forms of boolean functions
6. Altmetric Badge
   Chapter 5 On a stable generating of random sequences by probabilistic automata
7. Altmetric Badge
   Chapter 6 Automata classes induced by Post classes
8. Altmetric Badge
   Chapter 7 Effective lower bounds for complexity of some classes of schemes
9. Altmetric Badge
   Chapter 8 Stable finite automata mappings and Church-Rosser systems
10. Altmetric Badge
    Chapter 9 The recursion theorem, approximations, and classifying index sets of recursively enumerable sets
11. Altmetric Badge
    Chapter 10 Duality of functions and data in algorithms description
12. Altmetric Badge
    Chapter 11 On direct methods of realization of normal algorithms by turing machines
13. Altmetric Badge
    Chapter 12 Verbal operation on automaton
14. Altmetric Badge
    Chapter 13 The new way of probabilistic compact testing
15. Altmetric Badge
    Chapter 14 Computational problems in alphabetic coding theory
16. Altmetric Badge
    Chapter 15 On the synthesis of "Irredundant" automata from a finite set of experiments
17. Altmetric Badge
    Chapter 16 On the equivalence problem of states for cellular automata
18. Altmetric Badge
    Chapter 17 Arsenals and lower bounds
19. Altmetric Badge
    Chapter 18 Chain — like model of programs communication
20. Altmetric Badge
    Chapter 19 Structor automata
21. Altmetric Badge
    Chapter 20 On A-completeness for some classes of bounded determinate functions
22. Altmetric Badge
    Chapter 21 Structure synthesis of parallel programs (Methodology and Tools)
23. Altmetric Badge
    Chapter 22 Saturating flows in networks
24. Altmetric Badge
    Chapter 23 On the number of DNF minimal relatively arbitrary measures of complexity
25. Altmetric Badge
    Chapter 24 Soliton automata
26. Altmetric Badge
    Chapter 25 On development of dialogue concurrent systems
27. Altmetric Badge
    Chapter 26 Discrete analogue of the Neumann method is not optimal
28. Altmetric Badge
    Chapter 27 A simplest probability model of asynchronous iterations
29. Altmetric Badge
    Chapter 28 Semantic foundations of programming
30. Altmetric Badge
    Chapter 29 Conditions for existence of nontrivial parallel decompositions of sequential machines
31. Altmetric Badge
    Chapter 30 On the digital system diagnostics under uncertainty
32. Altmetric Badge
    Chapter 31 The implicating vector problem and its applications to probabilistic and linear automata
33. Altmetric Badge
    Chapter 32 Some asymptotic evalutions of complexity of information searching
34. Altmetric Badge
    Chapter 33 On the complexity of approximate realization of continuous functions by schemes and formulas in continuous bases
35. Altmetric Badge
    Chapter 34 Codes, connected with a fraction linear functions group and their decoding
36. Altmetric Badge
    Chapter 35 On the capabilities of alternating and nondeterministic multitape automata
37. Altmetric Badge
    Chapter 36 Fast parallel algorithms for optimal edge-colouring of some tree-structured graphs
38. Altmetric Badge
    Chapter 37 On the complexity of elementary periodical functions realized by switching circuits
39. Altmetric Badge
    Chapter 38 Efficient algorithmic construction of designs
40. Altmetric Badge
    Chapter 39 On the complexity of Lie algebras
41. Altmetric Badge
    Chapter 40 A characterization of sequential machines by means of their behaviour fragments
42. Altmetric Badge
    Chapter 41 Some observations about NP complete sets
43. Altmetric Badge
    Chapter 42 Three-dimensional traps and barrages for cooperating automata
44. Altmetric Badge
    Chapter 43 Efficient implementation of structural recursion
45. Altmetric Badge
    Chapter 44 Minimal numberings of the vertices of trees — Approximate approach
46. Altmetric Badge
    Chapter 45 Dyck 1 -reductions of Context-free Languages
47. Altmetric Badge
    Chapter 46 Information flow and width of branching programs
48. Altmetric Badge
    Chapter 47 On some operations of partial monotone boolean function simplifying
49. Altmetric Badge
    Chapter 48 On complexity of computations with limited memory
50. Altmetric Badge
    Chapter 49 On the problem of completeness for the regular mappings
51. Altmetric Badge
    Chapter 50 The number and the structure of typical Sperner and k-non-separable families of subsets of a finite set
52. Altmetric Badge
    Chapter 51 A criterion of polynomial lower bounds of combinational complexity
53. Altmetric Badge
    Chapter 52 On generalized process logic
54. Altmetric Badge
    Chapter 53 Verification of programs with higher-order arrays
55. Altmetric Badge
    Chapter 54 On the complexity of analyzing experiments for checking local faults of an automaton
56. Altmetric Badge
    Chapter 55 Exponential lower bounds for real-time branching programs
57. Altmetric Badge
    Chapter 56 On the conditions of supplementicity in functional systems
58. Altmetric Badge
    Chapter 57 On one approximate algorithm for solving systems of linear inequalities with boolean variables
59. Altmetric Badge
    Chapter 58 The problem of minimal implicating vector
60. Altmetric Badge
    Chapter 59 Built-in self-testing of logic circuits using imperfect duplication
61. Altmetric Badge
    Chapter 60 Algebras with approximation and recursive data structures
62. Altmetric Badge
    Chapter 61 Procedural implementation of algebraic specifications of abstract data types
63. Altmetric Badge
    Chapter 62 On the complexity of realizing some systems of the functions of the algebra of logic by contact and generalized contact circuits
64. Altmetric Badge
    Chapter 63 On construction of A complete system of compression functions and on complexity of monotone realization of threshold boolean functions
65. Altmetric Badge
    Chapter 64 Diophantine complexity
66. Altmetric Badge
    Chapter 65 The power of nondeterminism in polynomial-size bounded-width branching programs
67. Altmetric Badge
    Chapter 66 Estimation algorithms of infinite graphs percolation threshold
68. Altmetric Badge
    Chapter 67 A solving of problems on technological models
69. Altmetric Badge
    Chapter 68 Some formal systems of the logic programming
70. Altmetric Badge
    Chapter 69 On the Programs with finite development
71. Altmetric Badge
    Chapter 70 D-Representing code problem solution
72. Altmetric Badge
    Chapter 71 Metric properties of random sequence
73. Altmetric Badge
    Chapter 72 Adaptive strategies for partially observable controlled random series
74. Altmetric Badge
    Chapter 73 The degrees of nondeterminism in pushdown automata
75. Altmetric Badge
    Chapter 74 Statistically effective algorithms for automata control
76. Altmetric Badge
    Chapter 75 Linear test procedures of recognition
77. Altmetric Badge
    Chapter 76 Evaluation of cardinalities of some families of ξ-classes in $$P_{\aleph _0 }$$
78. Altmetric Badge
    Chapter 77 On the temporal complexity of boolean mappings realizations in two-dimensional homogeneous automata
79. Altmetric Badge
    Chapter 78 On approximate solution of the problem of equivalent transformations of programs
80. Altmetric Badge
    Chapter 79 Randomized parallel computation
81. Altmetric Badge
    Chapter 80 On checking correctness of some classes of control systems
82. Altmetric Badge
    Chapter 81 The parallel complexity of some arithmetic and algebraic operations
83. Altmetric Badge
    Chapter 82 On difficulties of solving a problem of decomposition of the system of boolean equations
84. Altmetric Badge
    Chapter 83 The number of fuzzy monotone functions
85. Altmetric Badge
    Chapter 84 Bounded set theory and polynomial computability
86. Altmetric Badge
    Chapter 85 Index sets of factor-objects of the Post numbering
87. Altmetric Badge
    Chapter 86 On realization of boolean functions by schemes consisting of checked elements
88. Altmetric Badge
    Chapter 87 The complexity of the sequential choice mechanism
89. Altmetric Badge
    Chapter 88 Nondeterministic finite algorithmic procedures as the models of abstract computability
90. Altmetric Badge
    Chapter 89 The reducibility of random sequences by automata
91. Altmetric Badge
    Chapter 90 On structure complexity of normal basis of finite field
92. Altmetric Badge
    Chapter 91 On comparison of boolean bases
93. Altmetric Badge
    Chapter 92 A tradeoff between pagenumber and width of book embeddings of graphs
94. Altmetric Badge
    Chapter 93 On metric properties of automata and ɛ-approximation of automaton mappings
95. Altmetric Badge
    Chapter 94 Algorithmization of obtaining the converse comparison theorems based on solving a logical equation
96. Altmetric Badge
    Chapter 95 Synthesis of universal finite automats
97. Altmetric Badge
    Chapter 96 On cartesian powers of P 2
98. Altmetric Badge
    Chapter 97 Complexity gaps of Turing machines on infinite words
99. Altmetric Badge
    Chapter 98 Distributed infimum approximation
100. Altmetric Badge
     Chapter 99 On the number of keys in relational databases
101. Altmetric Badge
     Chapter 100 Complexity and depth of formulas realizing functions from closed classes
102. Altmetric Badge
     Chapter 101 Reliable networks from unreliable gates with almost minimal complexity
103. Altmetric Badge
     Chapter 102 On the standard and pseudostandard star height of regular sets
104. Altmetric Badge
     Chapter 103 To automation of theorem synthesis
105. Altmetric Badge
     Chapter 104 On efficiency of prefix word-encoding of binary messages
106. Altmetric Badge
     Chapter 105 Deductive program synthesis and Markov's principle
107. Altmetric Badge
     Chapter 106 Complexity of the problem of approximation of stochastic matrix by rational elements
108. Altmetric Badge
     Chapter 107 To the functional equivalence of Turing machines
109. Altmetric Badge
     Chapter 108 Theorem proving in intermediate and modal logics
110. Altmetric Badge
     Chapter 109 The analysis of concurrent logic control algorithms
111. Altmetric Badge
     Chapter 110 On a connection between the resolution method and the inverse method