Foundations of Computation Theory: Proceedings of the 1983 International FCT-Conference Borgholm, Sweden, August 21-27, 1983 (Lecture Notes in Computer Science, 158)

Experiments, powerdomains and fully abstract models for applicative multiprogramming....Pages 1-13 Deterministic dynamic logic of recursive programs is weaker than dynamic logic....Pages 14-25 Reversal-bounded and visit-bounded realtime computations....Pages 26-39 Input-driven languages are recognized in log n space....Pages 40-51 How to search in history....Pages 52-63 Comstructive matnkmatics as a programming logic I: Some principles of theory....Pages 64-77 The classification of problems which have fast parallel algorithms....Pages 78-93 A fair calculus of communicating systems....Pages 94-105 Two way finite state generators....Pages 106-114 A complete set of axioms for a theory of communicating sequential processes....Pages 115-126 The consensus problem in unreliable distributed systems (a brief survey)....Pages 127-140 Methods in the analysis of algorithms : Evaluations of a recursive partitioning process....Pages 141-158 Space and reversal complexity of probabilistic one-way turing machines....Pages 159-170 Pseudorandom number generation and space complexity....Pages 171-176 Recurring dominoes: Making the highly undecidable highly understandable (preliminary report)....Pages 177-194 Propositional dynamic logic of flowcharts....Pages 195-206 Fast triangulation of simple polygons....Pages 207-218 On containment problems for finite-turn languages....Pages 219-231 On languages generated by semigroups....Pages 232-240 Aspects of programs with finite modes....Pages 241-254 Estimating a probability using finite memory....Pages 255-269 The greedy and Delauney triangulations are not bad in the average case and minimum weight geometric triangulation of multi-connected polygons is NP-complete....Pages 270-284 Decision problems for exponential rings: The p-adic case....Pages 285-289 Functional behavior of nondeterministic programs....Pages 290-301 A single source shortest path algorithm for graphs with separators....Pages 302-309 Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus)....Pages 310-327 Finding dominators....Pages 328-334 Characterizing composability of abstract implementations....Pages 335-346 Propositional logics of programs: New directions....Pages 347-359 A new probabilistic model for the study of algorithmic properties of random graph problems....Pages 360-367 On diagonalization methods and the structure of language classes....Pages 368-380 A new solution for the Byzantine generals problem....Pages 382-393 Modular decomposition of automata (survey)....Pages 394-412 A kernel language for algebraic specification and implementation extended abstract....Pages 413-427 A fast construction of disjoint paths in communication networks....Pages 428-438 A tight Ω(loglog n)-bound on the time for parallel Ram's to compute nondegenerated boolean functions....Pages 439-444 The identification of propositions and types in Martin-Löf's type theory: A programming example....Pages 445-456 Remarks on searching labyrinths by automata....Pages 457-464 Metrical and ordered properties of powerdomains....Pages 465-474 Economy of description for program schemes extended abstract....Pages 475-486 On approximate string matching....Pages 487-495 Deterministic context-free dynamic logic is more expressive than deterministic dynamic logic of regular programs....Pages 496-504 A note on powerdomains and modality....Pages 505-514 Reasoning with fairness constraints....Pages 515-517