Fundamentals of Computation Theory: 8th International Conference, FCT '91, Gosen, Germany, September 9-13, 1991. Proceedings

ISBN-13: 9783540544586 / Angielski / Miękka / 1991 / 432 str.

Lothar Budach

Opis

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

Spis treści

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.