Mathematical Foundations of Computer Science 1989
Springer Berlin (Verlag)
978-3-540-51486-2 (ISBN)
From specification languages to specification knowledge bases: The PTO approach.- Monadic second-order logic and context-free graph-grammars.- A thesis for bounded concurrency.- Space bounded computations : Review and new separation results.- Concurrent nondeterministic processes: Adequacy of structure and behaviour.- LEDA a library of efficient data types and algorithms.- Correctness of concurrent processes.- Understanding nets.- On the strength of temporal proofs.- Proof-theoretic characterisations of logic programming.- Algebraically closed theories.- Control flow versus logic: A denotational and a declarative model for Guarded Horn Clauses.- Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A constructive glimpse.- Parallel complexity of lexicographically first problems for tree-structured graphs.- On the power of synchronization in parallel computations.- Optimal parallel algorithms for the recognition and colouring outerplanar graphs.- Logical characterizations of nonmonotonic TMSs.- Proving correctness of constructor implementations.- Equivalence notions for concurrent systems and refinement of actions.- System simulation and the sensitivity of self-stabilization.- Polynomial-time functions generate SAT: On P-splinters.- Generalized definite tree languages.- Pinwheel scheduling with two distinct numbers.- Testing approximate symmetry in the plane is NP-hard.- Memory and algebra.- Integer relations among algebraic numbers.- An iterative metric fully abstract semantics for nondeterministic dataflow (extended abstract).- Complexity of decision problems under incomplete information.- On the nature of TELLUS.- Switching graphs and their complexity.- Pomset semantics for true concurrency with synchronization and recursion.- Oracle branching programs and Logspaceversus P.- Generalizing singly-linked list reorganizing heuristics for doubly-linked lists.- Area complexity of merging.- Logically defined subsets of IN k .- An extended Herbrand theorem for first-order theories with equality interpreted in partial algebras.- Characterization of recognizable trace languages by distributed automata.- Knuth-Morris-Pratt algorithm: An analysis.- Pushdown automata on infinite trees and omega-Kleene closure of context-free tree sets.- An imperative type hierarchy with partial products.- A coloring algorithm for interval graphs.- Finite constants: Characterizations of a new decidable set of constants.- Optimal data flow analysis via observational equivalence.- One more method for proving lower bounds on the formula complexity of boolean functions.- The Hoare-like verification system for a language with an exception handling mechanism.- On the lengths of values in a finite transducer.- On varieties of languages closed under products with counter.- On the computational efficiency of symmetric neural networks.- Constructive aspects of the omega-rule : Application to proof systems in computer science and algorithmic logic.- How to define functionals on free structures in typed ? calculus.- Concurrency, modularity, and synchronization.- On comparing probabilistic and deterministic automata complexity of languages.
| Erscheint lt. Verlag | 9.8.1989 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | X, 610 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 857 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Schlagworte | Algorithm analysis and problem complexity • Algorithmen • algorithms • Automata • Automata Theory • Automatentheorie • Complexity • Computability • Computability Theory • Computational Complexity • Databases • Distributed Computing • distributed programming • formal language • Komplexität • Parallel Computing • Parallelprogrammierung • Software Specification • Softwarespezifikation • theoretical computer science |
| ISBN-10 | 3-540-51486-4 / 3540514864 |
| ISBN-13 | 978-3-540-51486-2 / 9783540514862 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
