Fundamentals of Computation Theory: International Conference FCT '87 Kazan, USSR, June 22–26, 1987 Proceedings

Possibilities of probabilistic on-line counting machines....Pages 1-4
Functional systems on semilattices....Pages 5-9
Recognition of properties in k-valued logic and approximate algorithms....Pages 10-13
Linearized disjunctive normal forms of boolean functions....Pages 14-16
On a stable generating of random sequences by probabilistic automata....Pages 17-20
Automata classes induced by Post classes....Pages 21-23
Effective lower bounds for complexity of some classes of schemes....Pages 24-29
Stable finite automata mappings and Church-Rosser systems....Pages 30-33
The recursion theorem, approximations, and classifying index sets of recursively enumerable sets....Pages 34-37
Duality of functions and data in algorithms description....Pages 38-40
On direct methods of realization of normal algorithms by turing machines....Pages 41-41
Verbal operation on automaton....Pages 42-44
The new way of probabilistic compact testing....Pages 45-47
Computational problems in alphabetic coding theory....Pages 48-50
On the synthesis of "Irredundant" automata from a finite set of experiments....Pages 51-52
On the equivalence problem of states for cellular automata....Pages 53-54
Arsenals and lower bounds....Pages 55-64
Chain — like model of programs communication....Pages 65-67
Structor automata....Pages 68-73
On A-completeness for some classes of bounded determinate functions....Pages 74-77
Structure synthesis of parallel programs (Methodology and Tools)....Pages 78-81
Saturating flows in networks....Pages 82-91
On the number of DNF minimal relatively arbitrary measures of complexity....Pages 92-94
Soliton automata....Pages 95-102
On development of dialogue concurrent systems....Pages 103-108
Discrete analogue of the Neumann method is not optimal....Pages 109-112
A simplest probability model of asynchronous iterations....Pages 113-115
Semantic foundations of programming....Pages 116-122
Conditions for existence of nontrivial parallel decompositions of sequential machines....Pages 123-126
On the digital system diagnostics under uncertainty....Pages 127-131
The implicating vector problem and its applications to probabilistic and linear automata....Pages 132-136
Some asymptotic evalutions of complexity of information searching....Pages 137-139
On the complexity of approximate realization of continuous functions by schemes and formulas in continuous bases....Pages 140-144
Codes, connected with a fraction linear functions group and their decoding....Pages 145-149
On the capabilities of alternating and nondeterministic multitape automata....Pages 150-154
Fast parallel algorithms for optimal edge-colouring of some tree-structured graphs....Pages 155-162
On the complexity of elementary periodical functions realized by switching circuits....Pages 163-166
Efficient algorithmic construction of designs....Pages 167-171
On the complexity of Lie algebras....Pages 172-179
A characterization of sequential machines by means of their behaviour fragments....Pages 180-184
Some observations about NP complete sets....Pages 185-196
Three-dimensional traps and barrages for cooperating automata....Pages 197-203
Efficient implementation of structural recursion....Pages 204-213
Minimal numberings of the vertices of trees — Approximate approach....Pages 214-217
Dyck 1 -reductions of Context-free Languages....Pages 218-227
Information flow and width of branching programs....Pages 228-230
On some operations of partial monotone boolean function simplifying....Pages 231-233
On complexity of computations with limited memory....Pages 234-235
On the problem of completeness for the regular mappings....Pages 236-238
The number and the structure of typical Sperner and k-non-separable families of subsets of a finite set....Pages 239-243
A criterion of polynomial lower bounds of combinational complexity....Pages 244-245
On generalized process logic....Pages 246-250
Verification of programs with higher-order arrays....Pages 251-258
On the complexity of analyzing experiments for checking local faults of an automaton....Pages 259-262
Exponential lower bounds for real-time branching programs....Pages 263-267
On the conditions of supplementicity in functional systems....Pages 268-271
On one approximate algorithm for solving systems of linear inequalities with boolean variables....Pages 272-272
The problem of minimal implicating vector....Pages 273-278
Built-in self-testing of logic circuits using imperfect duplication....Pages 279-283
Algebras with approximation and recursive data structures....Pages 284-287
Procedural implementation of algebraic specifications of abstract data types....Pages 288-292
On the complexity of realizing some systems of the functions of the algebra of logic by contact and generalized contact circuits....Pages 293-296
On construction of A complete system of compression functions and on complexity of monotone realization of threshold boolean functions....Pages 297-300
Diophantine complexity....Pages 301-301
The power of nondeterminism in polynomial-size bounded-width branching programs....Pages 302-309
Estimation algorithms of infinite graphs percolation threshold....Pages 310-313
A solving of problems on technological models....Pages 314-317
Some formal systems of the logic programming....Pages 318-322
On the Programs with finite development....Pages 323-327
D-Representing code problem solution....Pages 328-331
Metric properties of random sequence....Pages 332-333
Adaptive strategies for partially observable controlled random series....Pages 334-338
The degrees of nondeterminism in pushdown automata....Pages 339-342
Statistically effective algorithms for automata control....Pages 343-346
Linear test procedures of recognition....Pages 347-348
Evaluation of cardinalities of some families of ξ-classes in $$P_{\aleph _0 }$$ ....Pages 349-353
On the temporal complexity of boolean mappings realizations in two-dimensional homogeneous automata....Pages 354-358
On approximate solution of the problem of equivalent transformations of programs....Pages 359-363
Randomized parallel computation....Pages 364-376
On checking correctness of some classes of control systems....Pages 377-382
The parallel complexity of some arithmetic and algebraic operations....Pages 383-385
On difficulties of solving a problem of decomposition of the system of boolean equations....Pages 386-388
The number of fuzzy monotone functions....Pages 389-390
Bounded set theory and polynomial computability....Pages 391-395
Index sets of factor-objects of the Post numbering....Pages 396-400
On realization of boolean functions by schemes consisting of checked elements....Pages 401-405
The complexity of the sequential choice mechanism....Pages 406-408
Nondeterministic finite algorithmic procedures as the models of abstract computability....Pages 409-411
The reducibility of random sequences by automata....Pages 412-413
On structure complexity of normal basis of finite field....Pages 414-416
On comparison of boolean bases....Pages 417-419
A tradeoff between pagenumber and width of book embeddings of graphs....Pages 420-423
On metric properties of automata and ɛ-approximation of automaton mappings....Pages 424-427
Algorithmization of obtaining the converse comparison theorems based on solving a logical equation....Pages 428-431
Synthesis of universal finite automats....Pages 432-434
On cartesian powers of P 2 ....Pages 435-435
Complexity gaps of Turing machines on infinite words....Pages 436-439
Distributed infimum approximation....Pages 440-447
On the number of keys in relational databases....Pages 448-455
Complexity and depth of formulas realizing functions from closed classes....Pages 456-461
Reliable networks from unreliable gates with almost minimal complexity....Pages 462-469
On the standard and pseudostandard star height of regular sets....Pages 470-471
To automation of theorem synthesis....Pages 472-476
On efficiency of prefix word-encoding of binary messages....Pages 477-478
Deductive program synthesis and Markov's principle....Pages 479-482
Complexity of the problem of approximation of stochastic matrix by rational elements....Pages 483-487
To the functional equivalence of Turing machines....Pages 488-491
Theorem proving in intermediate and modal logics....Pages 492-496
The analysis of concurrent logic control algorithms....Pages 497-500
On a connection between the resolution method and the inverse method....Pages 501-505