Fundamentals of Computation Theory International Conference FCT '87 Kazan, USSR, June 22-26, 1987. Proceedings
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 org...
| Other Authors: | , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1987, 1987
|
| Edition: | 1st ed. 1987 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- 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
- 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
- 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
- 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