STACS 97 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997 Proceedings /

This book constitutes the refereed proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, STACS 97, held in Lübeck, Germany, in February/March 1997. The 46 revised full papers included were carefully selected from a total of 139 submissions; also included are three inv...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
Άλλοι συγγραφείς: Reischuk, Rüdiger (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt), Morvan, Michel (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt)
Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
Γλώσσα:English
Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
Έκδοση:1st ed. 1997.
Σειρά:Lecture Notes in Computer Science, 1200
Θέματα:
Διαθέσιμο Online:Full Text via HEAL-Link
Πίνακας περιεχομένων:
  • Unifying models
  • Predecessor queries in dynamic integer sets
  • Semi-dynamic shortest paths and breadth-first search in digraphs
  • Greibach normal form transformation, revisited
  • Translating regular expressions into small ?-free nondeterministic finite automata
  • Memory management for Union-Find algorithms
  • Fast online multiplication of real numbers
  • The operators min and max on the polynomial hierarchy
  • Resource-bounded kolmogorov complexity revisited
  • Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
  • Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes
  • MODp-tests, almost independence and small probability spaces
  • Hybrid diagrams: A deductive-algorithmic approach to hybrid system verification
  • Temporal logics for the specification of performance and reliability
  • Efficient scaling-invariant checking of timed bisimulation
  • Gossiping and broadcasting versus computing functions in networks
  • On the descriptive and algorithmic power of parity ordered binary decision diagrams
  • A reducibility concept for problems defined in terms of ordered binary decision diagrams
  • On the classification of computable languages
  • A conditional-logical approach to minimum cross-entropy
  • Undecidability results on two-variable logics
  • Methods and applications of (max,+) linear algebra
  • Regular expressions and context-free grammars for picture languages
  • Measuring nondeterminism in pushdown automata
  • On polynomially D verbose sets
  • A downward translation in the polynomial hierarchy
  • Strict sequential P-completeness
  • An unambiguous class possessing a complete set
  • Deadlock-free interval routing schemes
  • Power consumption in packet radio networks
  • The complexity of generating test instances
  • Efficient constructions of Hitting Sets for systems of linear functions
  • Protocols for collusion-secure asymmetric fingerprinting
  • Minimal transition systems for history-preserving bisimulation
  • On ergodic linear cellular automata over Zm
  • Intrinsic universality of a 1-dimensional reversible Cellular Automaton
  • The computational complexity of some problems of linear algebra
  • Algebraic and logical characterizations of deterministic linear time classes
  • Finding the k shortest paths in parallel
  • Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
  • Distance approximating spanning trees
  • A better upper bound on the bisection width of de Bruijn networks
  • An information-theoretic treatment of random-self-reducibility
  • Equivalence of measures of complexity classes
  • Better algorithms for minimum weight vertex-connectivity problems
  • RNC-approximation algorithms for the steiner problem
  • Pattern matching in trace monoids
  • Removing ?-transitions in timed automata
  • Probabilistic proof systems - A survey.