On strong separations from AC o -- Number theoretic algorithms and cryptology -- Computations over infinite groups -- Efficiency of Monte Carlo algorithms in numerical analysis -- Approximation algorithms for counting problems in finite fields -- Lower bounds for deterministic and nondeterministic branching programs -- Graph theoretical methods for the design of parallel algorithms -- Lattice basis reduction: Improved practical algorithms and solving subset sum problems -- Information-based complexity: Recent results and open problems -- A survey of some aspects of computational learning theory -- Recent progress in circuit and communication complexity -- The consistency of a noninterleaving and an interleaving model for full TCSP -- A geometrical bound for integer programming with polynomial constraints -- A characterization of binary search networks -- About the effect of the number of successful paths in an infinite tree on the recognizability by a finite automaton with Buchi conditions -- Deterministic dequeue automata and LL(1) parsing of breadth-depth grammars -- The complexity of computing maximal word functions -- Unambiguity and fewness for logarithmic space -- Differential resultants and subresultants -- Unifying binary-search trees and permutations -- Computational complexity and hardest languages of automata with abstract storages -- Systolic Y-tree automata: closure properties and decision problems -- A new partition lemma for planar graphs and its application to circuit complexity -- Some notes on threshold circuits, and multiplication in depth 4 -- Nonlinear lower bounds on the number of processors of circuits with sublinear separators -- On space-bounded synchronized alternating turing machines -- Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems -- Optimal versus stable in Boolean formulae -- The Gauß lattice basis reduction algorithm succeeds with any norm -- Regularity of one-letter languages acceptable by 2-way finite probabilistic automata -- On the semantics of atomized statements — the parallel-choice option — -- Automatic proof methods for algebraic specifications -- On the complexity of graph reconstruction -- An optimal adaptive in-place sorting algorithm -- Data structures maxima -- Average-case analysis of equality of binary trees under the BST probability model -- On the subsets of rank two in a free monoid: A fast decision algorithm -- Exact analysis of three tree contraction algorithms -- Degrees of nondeterminism for pushdown automata -- Optimal embedding of a toroidal array in a linear array -- Boolean functions with a large number of subfunctions and small complexity and depth -- Adaptive linear list reorganization for a system processing set queries -- On the decidability of integer subgraph problems on context-free graph languages.

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).