Fundamentals of computation theory : 8th International Conference, FCT '91, Gosen, Germany, September 9-13, 1991 : proceedings
著者
書誌事項
Fundamentals of computation theory : 8th International Conference, FCT '91, Gosen, Germany, September 9-13, 1991 : proceedings
（Lecture notes in computer science, 529）
Springer-Verlag, c1991
- : gw
- : us
- タイトル別名
-
FCT '91 : fundamentals of computation theory
大学図書館所蔵 件 / 全59件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references
内容説明・目次
内容説明
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).
目次
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 Gauss 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.
「Nielsen BookData」 より
