Skip to main content
SpringerLink
Log in

Fundamentals of Computation Theory

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

  • Conference proceedings
  • © 1991

Overview

Editors:
  1. L. Budach
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 529)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (43 papers)

  1. Front Matter

    Download chapter PDF

  2. On strong separations from AC o

    • Eric Allender, Vivek Gore
    Pages 1-15

  3. Number theoretic algorithms and cryptology

    • Johannes Buchmann
    Pages 16-21

  4. Computations over infinite groups

    • Jin-yi Cai
    Pages 22-32

  5. Efficiency of Monte Carlo algorithms in numerical analysis

    • Stefan Heinrich
    Pages 33-44

  6. Approximation algorithms for counting problems in finite fields

    • Marek Karpinski
    Pages 45-46

  7. Lower bounds for deterministic and nondeterministic branching programs

    • Alexander A. Razborov
    Pages 47-60

  8. Graph theoretical methods for the design of parallel algorithms

    • Rüdiger Reischuk
    Pages 61-67

  9. Lattice basis reduction: Improved practical algorithms and solving subset sum problems

    • C. P. Schnorr, M. Euchner
    Pages 68-85

  10. Information-based complexity: Recent results and open problems

    • Joseph F. Traub
    Pages 86-88

  11. A survey of some aspects of computational learning theory

    • György Turán
    Pages 89-103

  12. Recent progress in circuit and communication complexity

    • Andrew Chi-Chih Yao
    Pages 104-104

  13. The consistency of a noninterleaving and an interleaving model for full TCSP

    • Christel Baier, Mila E. Majster-Cederbaum
    Pages 105-120

  14. A geometrical bound for integer programming with polynomial constraints

    • Bernd Bank, Teresa Krick, Reinhard Mandel, Pablo Solernó
    Pages 121-125

  15. A characterization of binary search networks

    • E. Barcucci, R. Pinzani, E. Rodella, R. Sprugnoli
    Pages 126-135

  16. About the effect of the number of successful paths in an infinite tree on the recognizability by a finite automaton with Buchi conditions

    • D. Beauquier, M. Nivat, D. NiwiÅ„ski
    Pages 136-145

  17. Deterministic dequeue automata and LL(1) parsing of breadth-depth grammars

    • Luca Breveglieri, Claudio Citrini, Stefano Crespi-Reghizzi
    Pages 146-156

  18. The complexity of computing maximal word functions

    • Danilo Bruschi, Giovanni Pighizzini
    Pages 157-167

  19. Unambiguity and fewness for logarithmic space

    • Gerhard Buntrock, Birgit Jenner, Klaus-Jörn Lange, Peter Rossmanith
    Pages 168-179

  20. Differential resultants and subresultants

    • Marc Chardin
    Pages 180-189
Back to top

Keywords

About this book

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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation