Fundamentals of Computation Theory
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.
| Erscheint lt. Verlag | 28.8.1991 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | XII, 432 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 233 mm |
| Gewicht | 720 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | algorithm • Algorithm analysis and problem complexity • Algorithmen • algorithms • Automata • Automatentheorie • boolean function • combinatorics • Complexity • Computational Complexity • Computational Geometry • cryptography • Cryptology • data structure • Discrete Mathematics • Diskrete Mathematik • Distributed Computing • formale Sprachen • formal language • Formal Language Theory • formal specification • Informatik • Komplexität • programming • Semantics |
| ISBN-13 | 9783540544586 / 9783540544586 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
