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 invi...
Saved in:
| Corporate Author: | |
|---|---|
| Other Authors: | , |
| Format: | Livre numérique |
| Language: | Anglais |
| Published: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Series: | Lecture notes in computer science
1200 |
| Subjects: | |
| Online Access: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Note: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27-March 1, 1997, proceedings, Rüdiger Reischuk, Michel Morvan (eds.), 1997, Berlin, Springer, 1 vol. (XIII-611 p.), Lecture notes in computer science, 3-540-62616-6 • STACS 97, Texte imprimé, 9783662186329 |
Table of Contents:
- 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
- Thecomplexity 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.