Lothar Budach (ed.)

Fundamentals of Computation Theory

8th International Conference, FCT '91, Gosen, Germany, September 9-13, 1991. Proceedings
Mitarbeit:Budach, Lothar

• Broschiertes Buch

Produktbeschreibung

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

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Lecture Notes in Computer Science 529
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-54458-6
• 1991.
• Seitenzahl: 444
• Erscheinungstermin: 28. August 1991
• Englisch
• Abmessung: 235mm x 155mm x 24mm
• Gewicht: 720g
• ISBN-13: 9783540544586
• ISBN-10: 3540544585
• Artikelnr.: 09227735

Inhaltsangabe

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.