Topics in the theory of computation: selected papers of the International Conference on ’’Foundations of Computation Theory’’, FCT ’83, Borgholm, Sweden, August 21-27, 1983’

This volume contains nine selected papers presented at the Borgholm conference. They were chosen on the basis of their immediate relevance to the most fundamental aspects of the theory of computation and the newest developments in this area. These papers, which have been extended and refereed, fall into eight categories: 1. Constructive Mathematics in Models of Computation and Programming; 2. Abstract Calculi and Denotational Semantics; 3. Theory of Machines, Computations and Languages; 4. Nondeterminism, Concurrency and Distributed Computing; 5. Abstract Algebras, Logics and Combinatorics in Computation Theory; 6. General Computability and Decidability; 7. Computational and Arithmetic Complexity; 8. Analysis of Algorithms and Feasible Computing. Content: Advisory Editors Page ii Edited by Page iii Copyright page Page iv Preface Pages v-vi Marek Karpinski, Jan van Leeuwen Conference Commitees “Foundations of Computation Theory- 1983” Borgholm, Sweden, August 21-27, 1983 Pages vii-viii Input Driven Languages are Recognized in log n Space Original Research Article Pages 1-19 Burchard von Braunmühl, Rutger Verbeek Constructive Mathematics as a Programming Logic I: Some Principles of Theory Original Research Article Pages 21-37 Robert L. Constable Space and Reversal Complexity of Probabilistic One-Way Turing Machines Original Research Article Pages 39-50 Rūsiņš Freivalds Recurring Dominoes: Making the Highly Undecidable Highly Understandable Original Research Article Pages 51-71 David Harel A New Transformational Approach to Partial Correctness Proof Calculi for Algol 6 8-Like Programs with Finite Modes and Simple Sideeffects Original Research Article Pages 73-102 H. Langmaack Effective Determination of the Zeros of p-Adic Exponential Functions Original Research Article Pages 103-109 Angus Macintyre The Logic of Games and its Applications Original Research Article Pages 111-139 Rohit Parikh A Fast Parallel Construction of Disjoint Paths in Networks Original Research Article Pages 141-153 Eli Shamir, Eli Upfal Descriptional Complexity for Classes of Ianov-Schemes Original Research Article Pages 155-186 Peter Trum, Detlef Wotschke Author Index Page 187 This volume contains nine selected papers presented at the Borgholm conference. They were chosen on the basis of their immediate relevance to the most fundamental aspects of the theory of computation and the newest developments in this area. These papers, which have been extended and refereed, fall into eight categories: 1. Constructive Mathematics in Models of Computation and Programming; 2. Abstract Calculi and Denotational Semantics; 3. Theory of Machines, Computations and Languages; 4. Nondeterminism, Concurrency and Distributed Computing; 5. Abstract Algebras, Logics and Combinatorics in Computation Theory; 6. General Computability and Decidability; 7. Computational and Arithmetic Complexity; 8. Analysis of Algorithms and Feasible Computing