Foundations of Computation Theory : Proceedings of the 1983 International FCT-Conference Borgholm, Sweden, August 21-27, 1983 / edited by M. Karpinski.

Format:

Book

Contributor:

Karpinski, M., Editor.

Series:

Lecture Notes in Computer Science, 0302-9743 ; 158

Language:

English

Subjects (All):

Computers.

Computation by Abstract Devices.

Local Subjects:

Computation by Abstract Devices.

Physical Description:

1 online resource (XIV, 522 p.)

Edition:

1st ed. 1983.

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1983.

Language Note:

English

Summary:

Foundations of Computation is a free textbook for a one-semester course in theoretical computer science. It has been used for several years in a course at Hobart and William Smith Colleges. The course has no prerequisites other than introductory computer programming. The first half of the course covers material on logic, sets, and functions that would often be taught in a course in discrete mathematics. The second part covers material on automata, formal languages and grammar that would ordinarily be encountered in an upper level course in theoretical computer science.

Contents:

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.

Notes:

Bibliographic Level Mode of Issuance: Monograph

CC BY-ND

ISBN:

9783540386827

3540386823

OCLC:

1000322544