Fundamentals of Computation Theory

1. Front Matter

   PDF

2. Possibilities of probabilistic on-line counting machines

   • Farid. M. Ablaev

   Pages 1-4

3. Functional systems on semilattices

   • G. P. Agibalov

   Pages 5-9

4. Recognition of properties in k-valued logic and approximate algorithms

   • V. B. Alekseyev

   Pages 10-13

5. Linearized disjunctive normal forms of boolean functions

   • A. A. Alexanyan

   Pages 14-16

6. On a stable generating of random sequences by probabilistic automata

   • Ju. A. Al'pin, B. S. Kotchkarev, R. G. Mubarakzianov

   Pages 17-20

7. Automata classes induced by Post classes

   • S. V. Alyoshin

   Pages 21-23

8. Effective lower bounds for complexity of some classes of schemes

   • A. E. Andreev

   Pages 24-29

9. Stable finite automata mappings and Church-Rosser systems

   • A. V. Anisimov, V. A. Oleshchuk

   Pages 30-33

10. The recursion theorem, approximations, and classifying index sets of recursively enumerable sets

    • M. M. Arslanov

    Pages 34-37

11. Duality of functions and data in algorithms description

    • A. D. Astakhov

    Pages 38-40

12. On direct methods of realization of normal algorithms by turing machines

    • G. V. Babikov

    Pages 41-41

13. Verbal operation on automaton

    • D. N. Babin

    Pages 42-44

14. The new way of probabilistic compact testing

    • A. S. Barashko

    Pages 45-47

15. Computational problems in alphabetic coding theory

    • M. Yu. Baryshev, L. P. Zhil'tzova, A. A. Markov

    Pages 48-50

16. On the synthesis of "Irredundant" automata from a finite set of experiments

    • S. A. Bogomolov

    Pages 51-52

17. On the equivalence problem of states for cellular automata

    • A. A. Bolotov

    Pages 53-54

18. Arsenals and lower bounds

    • Lothar Budach

    Pages 55-64

19. Chain — like model of programs communication

    • R. G. Bukharajev, A. I. Enikeev, I. I. Makarov

    Pages 65-67

20. Structor automata

    • R. G. Bukharajev, I. R. Nasirov

    Pages 68-73

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.

• Algebra of Logic
• Alphabet
• Boolean function
• Boolean variable
• Resolution
• Variable
• algorithms
• automata
• coding theory
• complexity
• data structure
• logic
• programming
• set theory
• verification
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics