Foundations of Computation Theory: Proceedings of the 1983 International FCT-Conference Borgholm, Sweden, August 21–27, 1983

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