Foundations of Computation Theory [electronic resource] : Proceedings of the 1983 International FCT-Conference Borgholm, Sweden, August 21–27, 1983 / edited by Marek Karpinski.

Experiments, powerdomains and fully abstract models for applicative multiprogramming -- Deterministic dynamic logic of recursive programs is weaker than dynamic logic -- Reversal-bounded and visit-bounded realtime computations -- Input-driven languages are recognized in log n space -- How to search in history -- Comstructive matnkmatics as a programming logic I: Some principles of theory -- The classification of problems which have fast parallel algorithms -- A fair calculus of communicating systems -- Two way finite state generators -- A complete set of axioms for a theory of communicating sequential processes -- The consensus problem in unreliable distributed systems (a brief survey) -- Methods in the analysis of algorithms : Evaluations of a recursive partitioning process -- Space and reversal complexity of probabilistic one-way turing machines -- Pseudorandom number generation and space complexity -- Recurring dominoes: Making the highly undecidable highly understandable (preliminary report) -- Propositional dynamic logic of flowcharts -- Fast triangulation of simple polygons -- On containment problems for finite-turn languages -- On languages generated by semigroups -- Aspects of programs with finite modes -- Estimating a probability using finite memory -- The greedy and Delauney triangulations are not bad in the average case and minimum weight geometric triangulation of multi-connected polygons is NP-complete -- Decision problems for exponential rings: The p-adic case -- Functional behavior of nondeterministic programs -- A single source shortest path algorithm for graphs with separators -- Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus) -- Finding dominators -- Characterizing composability of abstract implementations -- Propositional logics of programs: New directions -- A new probabilistic model for the study of algorithmic properties of random graph problems -- On diagonalization methods and the structure of language classes -- A new solution for the Byzantine generals problem -- Modular decomposition of automata (survey) -- A kernel language for algebraic specification and implementation extended abstract -- A fast construction of disjoint paths in communication networks -- A tight ?(loglog n)-bound on the time for parallel Ram's to compute nondegenerated boolean functions -- The identification of propositions and types in Martin-Löf's type theory: A programming example -- Remarks on searching labyrinths by automata -- Metrical and ordered properties of powerdomains -- Economy of description for program schemes extended abstract -- On approximate string matching -- Deterministic context-free dynamic logic is more expressive than deterministic dynamic logic of regular programs -- A note on powerdomains and modality -- Reasoning with fairness constraints.