Format:
Online-Ressource (IX, 562 S.)
Edition:
Online-Ausg. Berlin [u.a.] Springer 2006 Springer lecture notes archive
ISBN:
9783540459262
Series Statement:
Lecture notes in computer science 324
Content:
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 -- A taxonomy 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.
Content:
This volume contains 11 invited lectures and 42 communications presented at the 13th Conference on Mathematical Foundations of Computer Science, MFCS '88, held at Carlsbad, Czechoslovakia, August 29 - September 2, 1988. Most of the papers present material from the following four fields: - complexity theory, in particular structural complexity, - concurrency and parellelism, - formal language theory, - semantics. Other areas treated in the proceedings include functional programming, inductive syntactical synthesis, unification algorithms, relational databases and incremental attribute evaluation.
Note:
Literaturangaben
Additional Edition:
ISBN 354050110X
Additional Edition:
ISBN 038750110X
Additional Edition:
ISBN 9783540501107
Additional Edition:
Erscheint auch als Druck-Ausgabe Mathematical foundations of computer science 1988 Berlin [u.a.] : Springer, 1988 ISBN 354050110X
Additional Edition:
ISBN 038750110X
Language:
English
Keywords:
Konferenzschrift
URL:
Volltext
(lizenzpflichtig)
URL:
Volltext
(lizenzpflichtig)
URL:
Volltext
(lizenzpflichtig)
