Skip to main content
SpringerLink
Log in

Fundamentals of Computation Theory

International Conference FCT '89, Szeged, Hungary, August 21-25, 1989. Proceedings

  • Conference proceedings
  • © 1989

Overview

Editors:
  1. J. Csirik
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. J. Demetrovics
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. F. GĂ©cseg
    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 380)

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 (47 papers)

  1. Front Matter

    Download chapter PDF

  2. On word equations and Makanin's algorithm

    • Habib Abdulrab, Jean-Pierre PĂ©cuchet
    Pages 1-12

  3. Complexity classes with complete problems between P and NP-C

    • Carme Ă€lvarez, Josep DĂ­az, Jacobo Torán
    Pages 13-24

  4. Interpretations of synchronous flowchart schemes

    • MiklĂłs Bartha
    Pages 25-34

  5. Generalized Boolean hierarchies and Boolean hierarchies over RP

    • Alberto Bertoni, Danilo Bruschi, Deborah Joseph, Meera Sitharam, Paul Young
    Pages 35-46

  6. The equational logic of iterative processes

    • Stephen L. Bloom
    Pages 47-57

  7. The distributed bit complexity of the ring: From the anonymous to the non-anonymous case

    • Hans L. Bodlaender, Shlomo Moran, Manfred K. Warmuth
    Pages 58-67

  8. The jump number problem for biconvex graphs and rectangle covers of rectangular regions

    • Andreas Brandstädt
    Pages 68-77

  9. Recent developments in the design of asynchronous circuits

    • J. A. Brzozowski, J. C. Ebergen
    Pages 78-94

  10. New simulations between CRCW PRAMs

    • Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, Tomasz Radzik
    Pages 95-104

  11. About connections between syntactical and computational complexity

    • Jean-Luc CoquidĂ©, Max Dauchet, Sophie Tison
    Pages 105-115

  12. Completeness in approximation classes

    • Pierluigi Crescenzi, Alessandro Panconesi
    Pages 116-126

  13. Separating completely complexity classes related to polynomial size Ω-Decision trees

    • Carsten Damm, Christoph Meinel
    Pages 127-136

  14. On product hierarchies of automata

    • P. Dömösi, Z. Ésik, B. Imreh
    Pages 137-144

  15. On the communication complexity of planarity

    • P. ÄŽuriš, P. Pudlák
    Pages 145-147

  16. Context-free NCE graph grammars

    • Joost Engelfriet
    Pages 148-161

  17. Dynamic data structures with finite population: A combinatorial analysis

    • J. Françon, B. Randrianarimanana, R. Schott
    Pages 162-174

  18. Iterated deterministic top-down look-ahead

    • Z. FĂĽlöp, S. Vágvölgyi
    Pages 175-184

  19. Using generating functions to compute concurrency

    • Dominique Geniet, LoĂżs Thimonier
    Pages 185-196

  20. A logic for nondeterministic functional programs extended abstract

    • Ana Gil-Luezas
    Pages 197-208
Back to top

Keywords

About this book

This volume contains the proceedings of the conference on Fundamentals of Computation Theory held in Szeged, Hungary, August 21-25, 1989. The conference is the seventh in the series of the FCT conferences initiated in 1977 in Poznan-Kornik, Poland. The papers collected in this volume are the texts of invited contributions and shorter communications falling into one of the following sections: - Efficient Computation by Abstract Devices: Automata, Computability, Probabilistic Computations, Parallel and Distributed Computing; - Logics and Meanings of Programs: Algebraic and Categorical Approaches to Semantics, Computational Logic, Logic Programming, Verification, Program Transformations, Functional Programming; - Formal Languages: Rewriting Systems, Algebraic Language Theory; - Computational Complexity: Analysis and Complexity of Algorithms, Design of Efficient Algorithms, Algorithms and Data Structures, Computational Geometry, Complexity Classes and Hierarchies, Lower Bounds.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation