Buch, Englisch, Band 900, 651 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1007 g
12th Annual Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 2-4, 1995. Proceedings
Buch, Englisch, Band 900, 651 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1007 g
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-540-59042-2
Verlag: Springer Berlin Heidelberg
Besides three invited talks, the book contains revised versions of 53 research papers selected from a total of 180 submissions. The contributions address all current aspects of theoretical computer science; they are organized in sections on complexity theory, automata theory, algorithms, logic, theory of parallel computing, communication theory, graph theory and databases, and computational geometry.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Prozedurale Programmierung
- Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
Weitere Infos & Material
On the synthesis of strategies in infinite games.- Finding the maximum with linear error probabilities: a sequential analysis approach.- Completeness and weak completeness under polynomial-size circuits.- Communication complexity of key agreement on small ranges.- Pseudorandom generators and the frequency of simplicity.- Classes of bounded counting type and their inclusion relations.- Lower bounds for depth-three circuits with equals and mod-gates.- On realizing iterated multiplication by small depth threshold circuits.- A random NP-complete problem for inversion of 2D cellular automata.- On the subword equivalence problem for infinite words.- On the separators on an infinite word generated by a morphism.- Systolic tree ?-languages.- Structural complexity of ?-automata.- Algorithms explained by symmetries.- Generalized scans and tri-diagonal systems.- Two-dimensional pattern matching in linear time and small space.- On-line and dynamic algorithms for shortest path problems.- On compact representations of propositional circumscription.- A set-theoretic translation method for (poly)modal logics.- On the synthesis of discrete controllers for timed systems.- A fully abstract semantics for causality in the ?-calculus.- On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks.- Exploiting storage redundancy to speed up randomized shared memory simulations.- Interval routing schemes.- A packet routing protocol for arbitrary networks.- A family of tag systems for paperfolding sequences.- Growing context-sensitive languages and Church-Rosser languages.- Deterministic generalized automata.- Optimal simulation of automata by neural nets.- Concurrent process equivalences: Some decision problems.- Optimallower bounds on the multiparty communication complexity.- Simultaneous messages vs. communication.- Coding and strong coding in trace monoids.- On codings of traces.- Finding largest common embeddable subtrees.- The ?t-coloring problem.- Expander properties in random regular graphs with edge faults.- Dynamic analysis of the sizes of relations.- On slender context-free languages.- Partial derivatives of regular expressions and finite automata constructions.- Dependence orders for computations of concurrent automata.- On the undecidability of deadlock detection in families of nets.- On the average running time of odd-even merge sort.- Optimal average case sorting on arrays.- Normal numbers and sources for BPP.- Lower bounds on learning decision lists and trees.- Line segmentation of digital curves in parallel.- Computability of convex sets.- Enumerating extreme points in higher dimensions.- The number of views of piecewise-smooth algebraic objects.- On the structure of log-space probabilistic complexity classes.- Resource-bounded instance complexity.- On the sparse set conjecture for sets with low density.- Beyond PNP=NEXP.- Malign distributions for average case circuit complexity.- A possible code in the genetic code.
