15. STACS 1998: Paris, France

Michel Morvan, Christoph Meinel, Daniel Krob (Eds.): STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings. Lecture Notes in Computer Science 1373 Springer 1998, ISBN 3-540-64230-7

Invited Talk

Richard M. Karp:
Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms. 1-2

Jeannette Janssen, Danny Krizanc, Lata Narayanan, Sunil M. Shende:
Distributed Online Frequency Assignment in Cellular Networks. 3-13
Mikkel Thorup:
Floats, Integers, and Single Source Shortest Paths. 14-24
Michel Habib, Christophe Paul, Laurent Viennot:
A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata. 25-38

Julian C. Bradfield:
Simplifying the Modal Mu-Calculus Alternation Hierarchy. 39-49
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
On Disguised Double Horn Functions and Extensions. 50-60
Stéphane Demri, Ph. Schnoebelen:
The Complexity of Propositional Linear Temporal Logics in Simple Cases (Extended Abstract). 61-72

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
Searching Constant Width Mazes Captures the AC⁰ Hierarchy. 73-83
Lance Fortnow, Sophie Laplante:
Nearly Optimal Language Compression Using Extractors. 84-93
Joel Spencer, Katherine St. John:
Random Sparse Bit Strings at the Threshold of Adjacency. 94-104
Martin Sauerhoff:
Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract). 105-115

Jacques Mazoyer, Ivan Rapaport:
Inducing an Order on Cellular Automata by a Grouping Operation. 116-127
Giovanni Manzini, Luciano Margara:
Attractors of D-dimensional Linear Cellular Automata. 128-138
Carlo Mereghetti, Giovanni Pighizzini:
Optimal Simulations Between Unary Automata. 139-149
Alexandru Mateescu:
Shuffle of omega-Words: Algebraic Aspects (Extended Abstract). 150-160

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). 161-171
Vikraman Arvind, Richard Beigel, Antoni Lozano:
The Complexity of Modular Graph Automorphism. 172-182
Leonid Libkin, Limsoon Wong:
Unary Quantifiers, Transitive Closure, and Relations of Large Degree. 183-193
Peter Bürgisser:
On the Structure of Valiant's Complexity Classes. 194-204

Detlef Sieling:
On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization (Extended Abstract). 205-215
Joan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, Mahesh Viswanathan:
Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract). 216-226
Jan Behrens, Stephan Waack:
Equivalence Test and Ordering Transformation for Parity-OBDDs of Different Variable Ordering. 227-237
Clemens Gröpl, Hans Jürgen Prömel, Anand Srivastav:
Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract). 238-248

Serge Vaudenay:
Provable Security for Block Ciphers by Decorrelation. 249-275

Cristina Bazgan, Miklos Santha, Zsolt Tuza:
On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract). 276-286
Klaus Jansen:
The Mutual Exclusion Scheduling Problem for Permutation and Comparability Graphs. 287-297
Nader H. Bshouty, Lynn Burroughs:
Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. 298-308
Kim S. Larsen:
Partially Persistent Search Trees with Transcript Operations. 309-319

Damian Niwinski, Igor Walukiewicz:
Relating Hierarchies of Word and Tree Automata. 320-331
Howard Straubing:
Languages Defined With Modular Counting Quantifiers (Extended Abstract). 332-343
Matthias Jantzen:
Hierarchies of Principal Twist-Closed Trios. 344-355
Taoufik Safer:
Radix Representations of Algebraic Number Fields and Finite Automata. 356-365

Mohamadou Diallo, Afonso Ferreira, Andrew Rau-Chaplin:
Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram. 399-409
Christine Rüb:
On Batcher's Merge Sorts as Parallel Sorting Algorithms. 410-420
Jens Gustedt:
Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel. 421-431
Anders Dessmark, Andrzej Lingas, Hans Olsson, Hiroaki Yamamoto:
Optimal Broadcasting in Almost Trees and Partial k-trees. 432-443

Thomas Schwentick, Klaus Barthelmann:
Local Normal Forms for First-Order Logic with Applications to Games and Automata. 444-454
Zoltán Ésik:
Axiomatizing the Equational Theory of Regular Tree Languages (Extended Anstract). 455-465
Angelo Monti, Adriano Peron:
A Logical Characterization of Systolic Languages. 466-476
Jochen Meßner, Jacobo Torán:
Optimal Proof Systems for Propositional Logic and Complete Sets. 477-487

Maria J. Serna, Luca Trevisan, Fatos Xhafa:
The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. 488-498
Sergei Ivanov, Michel de Rougemont:
Interactive Protocols on the Reals. 499-510
Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung:
Result-Indistinguishable Zero-Knowledge Proofs: Increased Power and Constant-Round Protocols. 511-521
Sergio De Agostino, Riccardo Silvestri:
Bounded Size Dictionary Compression: SC^k-Completeness and NC Algorithms. 522-532

Raphaël Meyer, Antoine Petit:
Expressive Completeness of LTrL on Finite Traces: An Algebraic Proof. 533-543
Anna E. Frid:
On Uniform DOL Words. 544-554
Kamal Lodaya, Pascal Weil:
Series-Parallel Posets: Algebra, Automata and Languages. 555-565

Rainer Kemp:
On the Expected Number of Nodes at Level k in 0-balanced Trees. 566-576
Martin Charles Golumbic, Haim Kaplan:
Cell Flipping in Permutation Diagrams. 577-586
Marius Dorkenoo, Marie-Christine Eglin-Leclerc, Eric Rémila:
Construction of Non-intersecting Colored Flows Through a Planar Cellular Figure. 587-595

Cristian Calude, Peter Hertling, Bakhadyr Khoussainov, Yongge Wang:
Recursively Enumerable Reals and Chaitin Omega Numbers. 596-606
Sven Kosub, Heinz Schmitz, Heribert Vollmer:
Uniformly Defining Complexity Classes of Functions. 607-617
Denis Lapoire:
Recognizability Equals Monadic Second-Order Definability for Sets of Graphs of Bounded Tree-Width. 618-628