



LEADER 
07321nmm a2200457 u 4500 
001 
EB000658378 
003 
EBX01000000000000001349443 
005 
00000000000000.0 
007 
cr 
008 
140122  eng 
020 


a 9783540481386

100 
1 

a Budach, Lothar
e [editor]

245 
0 
0 
a Fundamentals of Computation Theory
h Elektronische Ressource
b International Conference FCT '87 Kazan, USSR, June 2226, 1987. Proceedings
c edited by Lothar Budach, Rais G. Bukharajev, Oleg B. Lupanov

250 


a 1st ed. 1987

260 


a Berlin, Heidelberg
b Springer Berlin Heidelberg
c 1987, 1987

300 


a XIV, 508 p
b online resource

505 
0 

a On the problem of completeness for the regular mappings  The number and the structure of typical Sperner and knonseparable families of subsets of a finite set  A criterion of polynomial lower bounds of combinational complexity  On generalized process logic  Verification of programs with higherorder arrays  On the complexity of analyzing experiments for checking local faults of an automaton  Exponential lower bounds for realtime 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  Builtin selftesting of logic circuitsusing imperfect duplication  Algebras with approximation and recursive data structures  Procedural implementation of algebraic specifications of abstract data types 

505 
0 

a Possibilities of probabilistic online counting machines  Functional systems on semilattices  Recognition of properties in kvalued 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 ChurchRosser 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 

505 
0 

a 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 polynomialsize boundedwidth 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  DRepresenting 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

505 
0 

a 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 edgecolouring of some treestructured 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  Threedimensional traps and barrages for cooperating automata  Efficient implementation of structural recursion  Minimal numberings of the vertices of trees — Approximate approach  Dyck1reductions of Contextfree Languages  Information flow and width of branching programs  On some operations of partial monotone boolean function simplifying  On complexity of computations with limited memory 

505 
0 

a Arsenals and lower bounds  Chain — like model of programs communication  Structor automata  On Acompleteness 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 

653 


a Computer systems

653 


a Computer science

653 


a Computer System Implementation

653 


a Mathematical logic

653 


a Algorithms

653 


a Formal Languages and Automata Theory

653 


a Machine theory

653 


a Discrete Mathematics

653 


a Discrete mathematics

653 


a Mathematical Logic and Foundations

653 


a Theory of Computation

700 
1 

a Bukharajev, Rais G.
e [editor]

700 
1 

a Lupanov, Oleg B.
e [editor]

041 
0 
7 
a eng
2 ISO 6392

989 


b SBA
a Springer Book Archives 2004

490 
0 

a Lecture Notes in Computer Science

028 
5 
0 
a 10.1007/3540187405

856 
4 
0 
u https://doi.org/10.1007/3540187405?nosfx=y
x Verlag
3 Volltext

082 
0 

a 004.0151

520 


a 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 2226, 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, ComputerAssisted 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
