Fundamentals of Computation Theory

1. Front Matter

   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

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.

• RP
• Turing machine
• algorithms
• automata
• calculus
• complexity
• computability
• formal language
• formal languages
• grammars
• logic
• petri net
• program transformation
• semantics
• turing degree
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics