Fundamentals of Computation Theory: 8th International Conference, FCT ’91 Gosen, Germany, September 9–13, 1991 Proceedings

Eric Allender, Vivek Gore (auth.), L. Budach (eds.)3540544585, 9783540544586

This volume contains papers which were contributed for presentation at the international conference “Fundamentals of Computation Theory – FCT ’91” heldat Gosen, near Berlin, September 9-13, 1991. This was the eighth in the series of FCT conferences organized every odd year. The programme of theconference, including invited lectures and selected contributions, falls into the following categories: – Semantics and logical concepts in the theory of computing, formal specification, – Automata and formal languages, Computational geometry, – Algorithmic aspects of algebra and algebraic geometry, cryptography, – Complexity (sequential, parallel, distributed computing, structure, lower bounds, complexity of analytical problems, general concepts), – Algorithms (efficient, probabilistic, parallel, sequential, distributed), – Counting and combinatorics in connection with mathematical computer science. The proceedings of previous FCT meetings are available as Lecture Notes in Computer Science (Vols. 380, 278, 199, 158, 117, 56).

---

Table of contents :
On strong separations from AC o ….Pages 1-15
Number theoretic algorithms and cryptology….Pages 16-21
Computations over infinite groups….Pages 22-32
Efficiency of Monte Carlo algorithms in numerical analysis….Pages 33-44
Approximation algorithms for counting problems in finite fields….Pages 45-46
Lower bounds for deterministic and nondeterministic branching programs….Pages 47-60
Graph theoretical methods for the design of parallel algorithms….Pages 61-67
Lattice basis reduction: Improved practical algorithms and solving subset sum problems….Pages 68-85
Information-based complexity: Recent results and open problems….Pages 86-88
A survey of some aspects of computational learning theory….Pages 89-103
Recent progress in circuit and communication complexity….Pages 104-104
The consistency of a noninterleaving and an interleaving model for full TCSP ….Pages 105-120
A geometrical bound for integer programming with polynomial constraints….Pages 121-125
A characterization of binary search networks….Pages 126-135
About the effect of the number of successful paths in an infinite tree on the recognizability by a finite automaton with Buchi conditions….Pages 136-145
Deterministic dequeue automata and LL(1) parsing of breadth-depth grammars….Pages 146-156
The complexity of computing maximal word functions….Pages 157-167
Unambiguity and fewness for logarithmic space….Pages 168-179
Differential resultants and subresultants….Pages 180-189
Unifying binary-search trees and permutations….Pages 190-199
Computational complexity and hardest languages of automata with abstract storages….Pages 200-209
Systolic Y-tree automata: closure properties and decision problems….Pages 210-219
A new partition lemma for planar graphs and its application to circuit complexity….Pages 220-229
Some notes on threshold circuits, and multiplication in depth 4….Pages 230-239
Nonlinear lower bounds on the number of processors of circuits with sublinear separators….Pages 240-247
On space-bounded synchronized alternating turing machines….Pages 248-257
Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems….Pages 258-264
Optimal versus stable in Boolean formulae….Pages 265-274
The Gauß lattice basis reduction algorithm succeeds with any norm….Pages 275-286
Regularity of one-letter languages acceptable by 2-way finite probabilistic automata….Pages 287-296
On the semantics of atomized statements — the parallel-choice option —….Pages 297-306
Automatic proof methods for algebraic specifications….Pages 307-317
On the complexity of graph reconstruction….Pages 318-328
An optimal adaptive in-place sorting algorithm….Pages 329-338
Data structures maxima….Pages 339-349
Average-case analysis of equality of binary trees under the BST probability model….Pages 350-359
On the subsets of rank two in a free monoid: A fast decision algorithm….Pages 360-369
Exact analysis of three tree contraction algorithms….Pages 370-379
Degrees of nondeterminism for pushdown automata….Pages 380-389
Optimal embedding of a toroidal array in a linear array….Pages 390-394
Boolean functions with a large number of subfunctions and small complexity and depth….Pages 395-404
Adaptive linear list reorganization for a system processing set queries….Pages 405-414
On the decidability of integer subgraph problems on context-free graph languages….Pages 415-426