Willkommen, schön sind Sie da!
Logo Ex Libris

Fundamentals of Computation Theory

  • Kartonierter Einband
  • 444 Seiten
(0) Erste Bewertung abgeben
Bewertungen & Rezensionen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
This volume contains papers which were contributed for presentation at the international conference "Fundamentals of Computation T... Weiterlesen
20%
100.00 CHF 80.00
Sie sparen CHF 20.00
Print on Demand - Auslieferung erfolgt in der Regel innert 4 bis 6 Wochen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

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

This volume contains selected papers from FCT '91. Topics covered include: semantics and logical concepts, automata and formal languages, computational geometry, complexity, algorithms, and counting and combinatorics.

Klappentext

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



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

Produktinformationen

Titel: Fundamentals of Computation Theory
Untertitel: 8th International Conference, FCT '91, Gosen, Germany, September 9-13, 1991. Proceedings
Editor:
EAN: 9783540544586
ISBN: 3540544585
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Anzahl Seiten: 444
Gewicht: 668g
Größe: H235mm x B155mm x T23mm
Jahr: 1991
Untertitel: Englisch
Auflage: 1991

Weitere Produkte aus der Reihe "Lecture Notes in Computer Science"