Mathematical Foundations of Computer Science 1988
Springer Berlin (Verlag)
978-3-540-50110-7 (ISBN)
Sparse sets, tally sets, and polynomial reducibilities.- Functional programming and combinatory algebras.- On models and algebras for concurrent processes.- String matching with constraints.- Structure of complexity classes: Separations, collapses, and completeness.- Inductive syntactical synthesis of programs from sample computations.- 3-dimensional shortest paths in the presence of polyhedral obstacles.- Robust oracle machines.- Recognizable sets with multiplicities in the tropical semiring.- Reusable specification components.- Comparing interconnection networks.- Probabilistic automata complexity of languages depends on language structure and error probability.- Breadth-first phrase structure grammars and queue automata.- Implementing abstract data structures in hardware.- Distribution of Sequential Processes.- Automata and rational expressions on planar graphs.- On maximal prefix sets of words.- Infinite behaviour of deterministic petri nets.- Testing isomorphism of outerplanar graphs in parallel.- Efficient simulations between concurrent-read concurrent-write pram models.- Multiple propositional dynamic logic of parallel programs.- The steiner tree problem and homogeneous sets.- Termination of rewriting is undecidable in the one-rvle case.- Local checking of trace synchronizability.- Edge separators for planar graphs and their applications.- A fast parallel algorithm for eigenvalue problem of jacobi matrices.- Strong and robustly strong polynomial time reducibilities to sparse sets.- Context-free-like forms for the phrase-structure grammars.- On the expressive strength of the finitely typed lambda - terms.- Hoare calculi for higher - type control siructures and their completeness in the sense of cook.- On representing CCS programs by finite petri nets.- Ataxonomy of fairness and temporal logic problems for petri nets.- Branching programs as a tool for proving lower bounds on vlsi computations and optimal algorithms for systolic arrays.- Two lower bounds for circuits over the basis (&, V, -).- Positive/Negative conditional rewriting.- On the computational complexity of codes in graphs.- Separating the eraser turing machine classes Le, NLe, co-NLe and Pe.- Compositional proofs by partial specification of processes.- Introducing negative information in relational databases.- On positive occur-checks in unification.- Two applications of fürer's counter to one-tape nondeterministic TMs.- ? 2 p -complete lexicographically first maximal subgraph problems.- Proof system for weakest prespecification and its applications.- On complexity of counting.- Design, proof and analysis of new efficient algorithms for incremental attribute evaluation.- On efficiency of interval routing algorithms.- An almost linear robinson unification algorithm.- Random boolean formulas representing any boolean function with asymptotically equal probability.- On the power of communication in alternating machines.- Classes of cnf-formulas with backtracking trees of exponential or linear average order for exact-satisfiability.- Bisections of free monoids and a new unavoidable regularity.- Failures semantics and deadlocking of modular petri nets.- A decomposition theorem for finite-valued transducers and an application to the equivalence problem.
| Erscheint lt. Verlag | 10.8.1988 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | IX, 563 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 946 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | algorithm • algorithms • Complexity • Complexity theory • Computer • Computer Science • Database • formal language • Informatik • programming • Semantics |
| ISBN-10 | 3-540-50110-X / 354050110X |
| ISBN-13 | 978-3-540-50110-7 / 9783540501107 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
