Foundations of Computation Theory

Contenu
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.