Skip to main content
SpringerLink
Log in
Book cover

STACS 93

10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993. Proceedings

  • Conference proceedings
  • © 1993

Overview

Editors:
  1. P. Enjalbert
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. A. Finkel
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. K. W. Wagner
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 665)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (73 papers)

  1. Front Matter

    Download chapter PDF

  2. Causal and distributed semantics for concurrent processes

    • Ilaria Castellani
    Pages 1-1

  3. Editorial note

    • Klaus W. Wagner
    Pages 2-4

  4. Alternation for two-way machines with sublogarithmic space

    • Burchard von Braunmühl
    Pages 5-15

  5. Separating the lower levels of the sublogarithmic space hierarchy

    • Maciej Liśkiewicz, Rüdiger Reischuk
    Pages 16-27

  6. Locating P/poly optimally in the extended low hierarchy

    • Johannes Köbler
    Pages 28-37

  7. Measure, stochasticity, and the density of hard languages

    • Jack H. Lutz, Elvira Mayordomo
    Pages 38-47

  8. Halting problem of one binary Horn clause is undecidable

    • Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier
    Pages 48-57

  9. Decidability and undecidability results for duration calculus

    • Zhou Chaochen, Michael R. Hansen, Peter Sestoft
    Pages 58-68

  10. Defining λ-typed λ-calculi by axiomatizing the typing relation

    • Philippe de Groote
    Pages 69-69

  11. The complexity of logic-based abduction

    • Thomas Eiter, Georg Gottlob
    Pages 70-79

  12. Treewidth of chordal bipartite graphs

    • T. Kloks, D. Kratsch
    Pages 80-89

  13. On paths in networks with valves

    • Ulrich Huckenbeck
    Pages 90-99

  14. Scheduling interval ordered tasks in parallel

    • S. Sunder, Xin He
    Pages 100-109

  15. An O(√n)-worst-case-time solution to the granularity problem

    • A. Pietracaprina, F. P. Preparata
    Pages 110-119

  16. The synthesis problem of Petri nets

    • Jörg Desel, Wolfgang Reisig
    Pages 120-129

  17. General refinement and recursion operators for the Petri Box calculus

    • Eike Best, Raymond Devillers, Javier Esparza
    Pages 130-140

  18. On fairness in distributed automated deduction

    • Maria Paola Bonacina, Jieh Hsiang
    Pages 141-152

  19. Divide-and-conquer algorithms on the hypercube

    • Ernst W. Mayr, Ralph Werchner
    Pages 153-162

  20. A first-order isomorphism theorem

    • Eric Allender, Jose Balcázar, Neil Immerman
    Pages 163-174
Back to top

Keywords

About this book

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 Computer Science of the Gesellschaft f}r Informatik (GI) and theSpecial Interest Group for Applied Mathematics of the Association Francaise des Sciences et Technologies de l'Information et des Syst mes (afcet). The volume includes the three invited talks which opened the three days of the symposium: "Causal and distributed semantics for concurrent processes" (I. Castellani), "Parallel architectures: design and efficient use" (B. Monien et al.), and "Transparent proofs" (L. Babai). The selection of contributed papers is organized into parts on: computational complexity, logic in computer science, efficient algorithms, parallel and distributed computation, language theory, computational geometry, automata theory, semantics and logic of programming languages, automata theory and logic, circuit complexity, omega-automata, non-classical complexity, learning theory and cryptography, and systems.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation