STACS 93 : 10th Annual Symposium on Theoretical Ascpects of Computer Science Würzburg, Germany, February 25 27, 1993 : proceedings
This volume contains the proceedings of the tenth annual Symposium on Theoretical Aspects of Computer Science (STACS '93), held in W}rzburg, February 25-27, 1993. The STACS symposia are held alternately in Germany and France, and organized jointly by the Special Interest Group for Theoretical C...
Gespeichert in:
| Körperschaft: | |
|---|---|
| Weitere Verfasser: | , , |
| Format: | Livre numérique |
| Sprache: | Anglais |
| Veröffentlicht: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Schriftenreihe: | Lecture notes in computer science
665 |
| Schlagworte: | |
| Online Zugang: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Anmerkung: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, proceedings, P. Enjalbert, A. Finkel, K.W. Wagner (eds.), 1993, Berlin, Springer, 1 vol. (XIV- 723 p.), Lecture notes in computer science, 0-387-56503-5 • STACS 93, Texte imprimé, 9783662200612 |
Inhaltsangabe:
- Causal and distributed semantics for concurrent processes
- Editorial note
- Alternation for two-way machines with sublogarithmic space
- Separating the lower levels of the sublogarithmic space hierarchy
- Locating P/poly optimally in the extended low hierarchy
- Measure, stochasticity, and the density of hard languages
- Halting problem of one binary Horn clause is undecidable
- Decidability and undecidability results for duration calculus
- Defining ?-typed ?-calculi by axiomatizing the typing relation
- The complexity of logic-based abduction
- Treewidth of chordal bipartite graphs
- On paths in networks with valves
- Scheduling interval ordered tasks in parallel
- An O(?n)-worst-case-time solution to the granularity problem
- The synthesis problem of Petri nets
- General refinement and recursion operators for the Petri Box calculus
- On fairness in distributed automated deduction
- Divide-and-conquer algorithms on the hypercube
- A first-order isomorphism theorem
- Splittings, robustness and structure of complete sets
- Defying upward and downward separation
- Counting, selecting, and sorting by query-bounded machines
- Cancellation in context-free languages: Enrichment by reduction
- Counting overlap-free binary words
- The limit set of recognizable substitution systems
- Partially commutative Lyndon words
- Parallel architectures: Design and efficient use
- Weighted closest pairs
- Rectilinear path queries in a simple rectilinear polygon
- Parallel algorithm for the matrix chain product and the optimal triangulation problems (extended abstract)
- Multi-list ranking: complexity and applications
- Exact algorithms for a geometric packing problem (extended abstract)
- A decomposition theorem for probabilistic transition systems
- Local automata and completion.-Efficient compression of wavelet coefficients for smooth and fractal-like data
- On the equivalence of two-way pushdown automata and counter machines over bounded languages
- Computability properties of low-dimensional dynamical systems
- Fixed-parameter intractability II (extended abstract)
- Limits on the power of parallel random access machines with weak forms of write conflict resolution
- On using oracles that compute values
- Multicounter automata with sublogarithmic reversal bounds
- Structured operational semantics for concurrency and hierarchy
- The complexity of verifying functional programs
- Towards the formal design of self-stabilizing distributed algorithms
- Axiomatizations of temporal logics on trace systems
- Capabilities and complexity of computations with integer division
- Extended locally definable acceptance types
- Gap-definability as a closure property
- On the logical definability of some rational trace languages
- Solving systems of set constraints using tree automata
- Complement problems and tree automata in AC-like theories (extended abstract)
- Transparent (holographic) proofs
- Computing symmetric functions with AND/OR circuits and a single MAJORITY gate
- Threshold circuits for iterated multiplication: Using AC0 for free
- Circuits with monoidal gates
- A non-probabilistic switching lemma for the Sipser function
- Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs
- On syntactic congruences for ? languages
- A polynomial time algorithm for the equivalence of two morphisms on ?-regular languages
- Locally threshold testable languages of infinite words
- Deterministic asynchronous automata for infinite traces
- Recursive automata on infinite words
- A complexity theoretic approach toincremental computation
- Precise average case complexity
- The bit probe complexity measure revisited
- Language learning with some negative information
- Language learning with a bounded number of mind changes
- Efficient sharing of many secrets
- The KIV system a tool for formal program development
- 1st Grade A system for implementation, testing and animation of graph algorithms
- The program verifier Tatzelwurm
- LEDA a library of efficient data types and algorithms
- Defining ?-typed ?-calculi by axiomatizing the typing relation.