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

Invited Lecture

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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