9. STACS 1992: Cachan, France

Invited Lecture

• Marie-Claude Gaudel:
  Structuring and Modularizing Algebraic Specifications: The PLUSS Specification Language, Evolutions and Perspectives. 3-18
  

Parallel Algorithms 1

• Arvind Gupta, Naomi Nishimura:
  The Parallel Complexity of Tree Embedding Problems (Extended Abstract). 21-32
  
• Anne Condon:
  A Theory of Strict P-completeness. 33-44
  
• Torben Hagerup:
  Fast and Optimal Simulations between CRCW PRAMs. 45-56
  

Logic and Semantics

• Eric Nassor, Guy Vidal-Naquet:
  Suitability of the Propositional Temporal Logic to Express Properties of Real-Time Systems. 59-70
  
• Michel Billaud:
  Axiomatizations of Backtracking. 71-82
  
• Roger Villemaire:
  Joining k- and l-Recognizable Sets of Natural Numbers. 83-94
  

Parallel Algorithms 2

• Friedhelm Meyer auf der Heide, Hieu Thien Pham:
  On the Performance of Networks with Multiple Busses. 97-108
  
• Venkatesh Radhakrishnan, Harry B. Hunt III, Richard Edwin Stearns:
  Efficient Algorithms for Solving Systems of Linear Equations and Path Problems. 109-119
  
• Lawrence L. Larmore, Wojciech Rytter:
  Efficient Sublinear Time Parallel Algorithms for Dynamic Programming and Context-Free Recognition. 121-132
  

Computational Geometry

• Franco P. Preparata, Jeffrey Scott Vitter:
  A Simplified Technique for Hidden-Line Elimination in Terrains. 135-146
  
• Bala Kalyanasundaram, Kirk Pruhs:
  A Competitive Analysis of Nearest Neighbor Based Algorithms for Searching Unknown Scenes (Preliminary Version). 147-157
  

Automate and Languages

• Bruno Bogaert, Sophie Tison:
  Equality and Disequality Constraints on Direct Subterms in Tree Automata. 161-171
  
• Anne Brüggemann-Klein, Derick Wood:
  Deterministic Regular Languages. 173-184
  

Structural Complexity 1

• Ming-Jye Sheu, Timothy J. Long:
  The Extended Low Hierarchy Is an Infinite Hierarchy. 187-198
  
• Ulrich Hertrampf:
  Locally Definable Acceptance Types for Polynomial Time Machines. 199-207
  
• Klaus Ambos-Spies, André Nies:
  The Theory of the Polynomial Many-One Degrees of Recursive Sets is Undecidable. 209-218
  

Computational Geometry and Learning Theory

• Frank Bartling, Klaus Hinrichs:
  A Plane-Sweep Algorithm for Finding a Closest Pair Among Convex Planar Objects. 221-232
  
• Jean-Marc Robert, Godfried T. Toussaint:
  Linear Approximation of Simple Objects. 233-244
  
• Shyam Kapur, Gianfranco Bilardi:
  Language Learning without Overgeneralization. 245-256
  

Invited Lecture

• Torben Hagerup:
  The Log-Star Revolution. 259-278
  

Complexity and Communication

• Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack:
  Separating Counting Communication Complexity Classes. 281-292
  
• Xaver Gubás, Juraj Hromkovic, Juraj Waczulík:
  A Nonlinear Lower Bound on the Practical Combinational Complexity. 293-302
  

Structural Complexity 2

• Jorge Castro, Carlos Seara:
  Characterizations of Some Complexity Classes Between Theta^p_2 and Delta^p_2. 305-317
  
• Ronald V. Book, Jack H. Lutz, Klaus W. Wagner:
  On Complexity Classes and Algorithmically Random Languages (Extended Abstract). 319-328
  
• Krzysztof Lorys:
  New Time Hierarchy Results for Deterministic TMs. 329-336
  

Distributed Systems

• Birgit Pfitzmann, Michael Waidner:
  Unconditional Byzantine Agreement for any Number of Faulty Processors. 339-350
  
• Ralf Klasing, Burkhard Monien, Regine Peine, Elena Stöhr:
  Broadcasting in Butterfly and DeBruijn Networks. 351-362
  
• Claire Diehl, Claude Jard:
  Interval Approximations of Message Causality in Distributed Executions. 363-374
  

Complexity

• Viggo Kann:
  On the Approximability of the Maximum Common Subgraph Problem. 377-388
  
• Walter Unger:
  The Complexity of Colouring Circle Graphs (Extended Abstract). 389-400
  
• Johannes Köbler, Uwe Schöning, Jacobo Torán:
  Graph Isomorphism is Low for PP. 401-411
  

Algorithms 1

• Hans L. Bodlaender, Ton Kloks:
  A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs. 415-423
  
• Norbert Blum:
  On Locally Optimal Alignments in Genetic Sequences. 425-436
  

Cryptography

• Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung:
  Secure Commitment Against A Powerful Adversary. 439-448
  
• Alfredo De Santis, Giuseppe Persiano:
  Communication Efficient Zero-Knowledge Proofs of Knowledge (With Applications to Electronic Cash). 449-460
  

Algorithms 2

• Kenneth L. Clarkson, Kurt Mehlhorn, Raimund Seidel:
  Four Results on Randomized Incremental Constructions. 463-474
  
• Bruno Becker, Paolo Giulio Franciosa, Stephan Gschwind, Thomas Ohler, Gerald Thiemt, Peter Widmayer:
  Enclosing Many Boxes by an Optimal Pair of Boxes. 475-486
  

VLSI

• Michael Kaufmann, Paul Molitor, Wolfgang Vogelgesang:
  Performance Driven k-Layer Wiring. 489-500
  
• Bernd Becker:
  Synthesis for Testability: Binary Decision Diagrams. 501-512
  

Invited Lecture

• Georges Hansel, Dominique Perrin, Imre Simon:
  Compression and Entropy. 515-528
  

Words and Rewriting

• Karel Culik II, Juhani Karhumäki:
  Iterative Devices Generating Infinite Words. 531-543
  
• Clelia de Felice:
  On the Factorization Conjecture. 545-556
  
• Thomas Deiß:
  Conditional Seme-Thue Systems for Presenting Monoids. 557-565
  

Algorithms 3

• Micha Sharir, Emo Welzl:
  A Combinatorial Bound for Linear Programming and Related Problems. 569-579
  
• Svante Carlsson, Jyrki Katajainen, Jukka Teuhola:
  In-place Linear Probing Sort. 581-587
  
• Maxime Crochemore, Thierry Lecroq, Artur Czumaj, Leszek Gasieniec, Stefan Jarominek, Wojciech Plandowski, Wojciech Rytter:
  Speeding Up Two String-Matching Algorithms. 589-600
  

Systems

• Michel Billaud:
  The ANIGRAF System. 603-604
  
• Jean-Marc Champarnaud:
  A Programming Language for Symbolic Computation of Regular Languages, Automata and Semigroups. 605-606
  
• Hélène Collavizza:
  Mu-SPEED: A System for the Specification and Verification of Microprocessors. 607-608
  
• Miltos D. Grammatikakis, Jung-Sing Jwo:
  A Discrete Event Simulator of Communication Algorithms in Interconnection Networks. 609-610
  
• Hervé Le Verge:
  Alpha du Centaur: An Environment for the Design of Systolic Arrays. 611-612
  
• Eric Madelaine, Didier Vergamini:
  Verification of Communicating Processes by Means of Automata Reduction and Abstraction. 613-614
  
• Paul G. Spirakis, Basil Tampakas, Marina Papatriantafilou, K. Konstantoulis, K. Vlaxodimitropoulos, V. Antonopoulos, P. Kazazis, T. Metallidou, D. Spartiotis:
  Distributed System Simulator (DSS). 615-616
  
• Huimin Lin:
  An Interactive Proof Tool for Process Algebras. 617-618
  
• Peter Bachmann, Thomas Drescher, Sabine Nieke:
  SPECI90: A Term Rewriting and Narrowing System. 619-620
  

Last update Thu May 24 04:44:44 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page