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

Farid. M. Ablaev (auth.), Lothar Budach, Rais Gatič Bukharajev, Oleg Borisovič Lupanov (eds.)3540187405, 9783540187400

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.

---

Table of contents :
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