13. STACS 1996: Grenoble, France

Claude Puech, Rüdiger Reischuk (Eds.): STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings. Lecture Notes in Computer Science 1046 Springer 1996, ISBN 3-540-60922-9

Invited Lecture

Harry Buhrman, Luc Longpré:
Compressibility and Resource Bounded Measure. 13-24
Martin Kummer:
On the Complexity of Random Strings (Extended Abstract). 25-36

Tero Harju, Juhani Karhumäki, Daniel Krob:
Remarks on Generalized Post Correspondence Problem. 39-48
Marie-Pierre Béal, Olivier Carton, Christophe Reutenauer:
Cyclic Languages and Strongly Cyclic Languages. 49-59

Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng:
Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness. 63-74
Harry Buhrman, Thomas Thierauf:
The Complexity of Generating and Checking Proffs of Membership. 75-86
Jack H. Lutz:
Observations on Measure and Lowness for Delta^P_2. 87-97
Vikraman Arvind, N. V. Vinodchandran:
Solvable Black-Box Group Problems Are Low for PP. 99-110

Volker Heun, Ernst W. Mayr:
Embedding Graphs with Bounded Treewidth into Optimal Hypercubes. 157-168
Michel Morvan, Laurent Viennot:
Parallel Comparability Graph Recognition and Modular Decomposition. 169-180
Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann:
Fault-Tolerant Shared Memory Simulations. 181-192
Piotr Indyk:
On Word-Level Parallelism in Fault-Tolerant Computing. 193-204

Janis Barzdins, Rusins Freivalds, Carl H. Smith:
Learning with Confidence. 207-218
Erika Tateishi, Osamu Maruyama, Satoru Miyano:
Extracting Best Consensus Motifs from Positive and Negative Examples. 219-230
François Denis, Cyrille D'Halluin, Rémi Gilleron:
PAC Learning with Simple Examples. 231-242
Andris Ambainis, Rusins Freivalds, Carl H. Smith:
General Inductive Inference Types Based on Linearly-Ordered Sets. 243-253

Béatrice Bérard, Paul Gastin, Antoine Petit:
On the Power of Non-Observable Actions in Timed Automata. 257-268
Michael Bertol, Volker Diekert:
Trace Rewriting: Computing Normal Forms in Time O(n log n). 269-280
Christoph Dürr, Huong Lê Thanh, Miklos Santha:
A Decision Procedure for Well-Formed Linear Quantum Cellular Automata. 281-292

Andreas Jakoby, Christian Schindelhauer:
On the Complexity of Worst Case and Expected Time in a Circuit. 295-306
Jin-yi Cai, Ashish V. Naik, D. Sivakumar:
On the Existence of Hard Sparse Sets under Weak Reductions. 307-318
Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardware. 319-330
Jin-yi Cai, Alan L. Selman:
Fine Separation of Average Time Complexity Classes. 331-343

Joseph Sifakis, Sergio Yovine:
Compositional Specification of Timed Systems (Extended Abstract). 347-359

Daniel Bleichenbacher, Ueli M. Maurer:
Optimal Tree-Based One-Time Digital Signature Schemes. 363-374
Joel Friedman, Antoine Joux, Yuval Roichman, Jacques Stern, Jean-Pierre Tillich:
The Action of a Few Random Permutations on r-Tuples and an Application to Cryptography. 375-386
Ueli M. Maurer:
A Unified and Generalized Treatment of Authentification Theory. 387-398

Igor Walukiewicz:
Monadic Second Order Logic on Tree-Like Structures. 401-413
Thomas Schwentick:
On Bijections vs. Unary Functions. 415-426
Jerzy Marcinkowski:
The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs. 427-438

Thomas Hofmeister, Hanno Lefmann:
A Combinatorial Design Approach to MAXCUT. 441-452
Arvind Gupta, Naomi Nishimura:
Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width. 453-464
Scott A. Mitchell:
A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume. 465-476

Julian C. Bradfield:
On the Expressivity of the Modal Mu-Calculus. 479-490
Beate Bollig, Ingo Wegener:
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams. 491-502
Roberto Giacobazzi:
"Optimal" Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics. 503-514

Vincent Schmitt:
Flip-Flop Nets. 517-528
Evangelos Kranakis, Danny Krizanc:
Lower Bounds for Compact Routing (Extended Abstract). 529-540

Christiane Frougny:
On the Successor Function in Non-Classical Numeration Systems. 543-553
Marie-Pierre Béal, Filippo Mignosi, Antonio Restivo:
Minimal Forbidden Words and Symbolic Dynamics. 555-566

Martin Dietzfelbinger:
Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes. 569-580
Pierre Kelsen:
Ranking and Unranking Trees Using Regular Reductions. 581-592
Dany Breslauer:
On Competitive On-Line Paging with Lookahead. 593-603
Jens Lagergren:
Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters. 605-616

Christoph Meinel, Stephan Waack:
The "log Rank" Conjecture for Modular Communication Complexity. 619-630
Andris Ambainis:
Upper Bounds on Multiparty Communication Complexity of Shifts. 631-642
Carsten Damm, Stasys Jukna, Jiri Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping. 643-654
Evripidis Bampis, Charles Delorme, Jean-Claude König:
Optimal Schedules for d-D Grid Graphs with Communication Delays (Extended Abstract). 655-666

Bernd Gärtner, Emo Welzl:
Linear Programming - Randomization and Abstract Frameworks. 669-687