9. STACS 1992: Cachan, France

Alain Finkel, Matthias Jantzen (Eds.): STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings. Lecture Notes in Computer Science 577 Springer 1992, ISBN 3-540-55210-3 BibTeX

@proceedings{DBLP:conf/stacs/1992,
  editor    = {Alain Finkel and
               Matthias Jantzen},
  title     = {STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer
               Science, Cachan, France, February 13-15, 1992, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {577},
  year      = {1992},
  isbn      = {3-540-55210-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Lecture

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

Parallel Algorithms 1

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

Logic and Semantics

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

Parallel Algorithms 2

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

Computational Geometry

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

Automate and Languages

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

Structural Complexity 1

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

Computational Geometry and Learning Theory

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

Invited Lecture

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

Complexity and Communication

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

Structural Complexity 2

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

Distributed Systems

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

Complexity

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

Algorithms 1

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

Cryptography

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

Algorithms 2

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

VLSI

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

Invited Lecture

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

Words and Rewriting

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

Algorithms 3

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

Systems

Michel Billaud: The ANIGRAF System. 603-604 BibTeX
Jean-Marc Champarnaud: A Programming Language for Symbolic Computation of Regular Languages, Automata and Semigroups. 605-606 BibTeX
Hélène Collavizza: Mu-SPEED: A System for the Specification and Verification of Microprocessors. 607-608 BibTeX
Miltos D. Grammatikakis, Jung-Sing Jwo: A Discrete Event Simulator of Communication Algorithms in Interconnection Networks. 609-610 BibTeX
Hervé Le Verge: Alpha du Centaur: An Environment for the Design of Systolic Arrays. 611-612 BibTeX
Eric Madelaine, Didier Vergamini: Verification of Communicating Processes by Means of Automata Reduction and Abstraction. 613-614 BibTeX
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 BibTeX
Huimin Lin: An Interactive Proof Tool for Process Algebras. 617-618 BibTeX
Peter Bachmann, Thomas Drescher, Sabine Nieke: SPECI90: A Term Rewriting and Narrowing System. 619-620 BibTeX