default search action
13. STACS 1996: Grenoble, France
Claude Puech, Rüdiger Reischuk:
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
Complexity Theory I
Automata Theory I
- 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
Complexity Theory II
- 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
Automata Theory II
Parallel Algorithms
- 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
Learning
- Erika Tateishi, Osamu Maruyama, Satoru Miyano:
Extracting Best Consensus Motifs from Positive and Negative Examples. 219-230 - Andris Ambainis, Rusins Freivalds, Carl H. Smith:
General Inductive Inference Types Based on Linearly-Ordered Sets. 243-253
Parallel and Distributed Systems I
- Béatrice Bérard, Paul Gastin, Antoine Petit:
On the Power of Non-Observable Actions in Timed Automata. 257-268 - Christoph Dürr, Huong Lê Thanh, Miklos Santha:
A Decision Procedure for Well-Formed Linear Quantum Cellular Automata. 281-292
Complexity Theory III
- 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
Invited Lecture
- Joseph Sifakis, Sergio Yovine:
Compositional Specification of Timed Systems (Extended Abstract). 347-359
Cryptography
- 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
Logic and Data Base Theory
- Jerzy Marcinkowski:
The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs. 427-438
Algorithms I
- 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
Semantics and Program Verification
- 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
Parallel and Distributed Systems II
Automata Theory III
- Marie-Pierre Béal, Filippo Mignosi, Antonio Restivo:
Minimal Forbidden Words and Symbolic Dynamics. 555-566
Algorithms II
- Martin Dietzfelbinger:
Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes. 569-580
Communication Complexity
- Christoph Meinel, Stephan Waack:
The "log Rank" Conjecture for Modular Communication Complexity. 619-630 - 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
Invited Lecture
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2015-03-06 02:54 CET by the dblp team