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 BibTeX

@proceedings{DBLP:conf/stacs/1998,
  editor    = {Michel Morvan and
               Christoph Meinel and
               Daniel Krob},
  title     = {STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer
               Science, Paris, France, February 25-27, 1998, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1373},
  year      = {1998},
  isbn      = {3-540-64230-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talk

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

Algorithms and Data Structures I

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

Logic I

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

Complexity I

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

Automata and Formal Languages I

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

Complexity II

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 BibTeX
Vikraman Arvind, Richard Beigel, Antoni Lozano: The Complexity of Modular Graph Automorphism. 172-182 BibTeX
Leonid Libkin, Limsoon Wong: Unary Quantifiers, Transitive Closure, and Relations of Large Degree. 183-193 BibTeX
Peter Bürgisser: On the Structure of Valiant's Complexity Classes. 194-204 BibTeX

Algorithms and Data Structures II

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

Invited Talk

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

Algorithms and Data Structures III

Cristina Bazgan, Miklos Santha, Zsolt Tuza: On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract). 276-286 BibTeX
Klaus Jansen: The Mutual Exclusion Scheduling Problem for Permutation and Comparability Graphs. 287-297 BibTeX
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 BibTeX
Kim S. Larsen: Partially Persistent Search Trees with Transcript Operations. 309-319 BibTeX

Automata and Formal Languages II

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

Invited Talk

Torben Hagerup: Sorting and Searching on the Word RAM. 366-398 BibTeX

Algorithms and Data Structures IV

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

Logic II

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

Complexity III

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

Automata and Formal Languages III

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

Algorithms and Data Structures V

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

Complexity IV

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