Research Catalog

Title

STACS 96 : 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996 : proceedings / Claude Puech, Rüdiger Reischuk, eds.

Author

Annual Symposium on Theoretical Aspects of Computer Science (13th : 1996 : Grenoble, France)

Publication

Berlin ; New York : Springer, ©1996.

Items in the Library & Off-site

Details

Additional Authors

• Puech, Claude.
• Reischuk, Rüdiger.

Description

xii, 690 pages : illustrations; 24 cm

Summary

"This book constitutes the refereed proceedings of the 13th Symposium on Theoretical Aspects of Computer Science, STACS 96, held in Grenoble, France in February 1996. The 52 revised papers presented were selected from a total of 185 submissions; also included are three invited papers. The volume addresses all current aspects of theoretical computer science and is organized in sections on complexity theory, automata theory, parallel algorithms, learning, parallel and distributed systems, cryptography, logic and database theory, algorithms, semantics and program verification, and communication complexity."--PUBLISHER'S WEBSITE.

Series Statement

Lecture notes in computer science ; 1046

Uniform Title

Lecture notes in computer science ; 1046.

Subject

• Computer science > Congresses
• Computer science
• Fundamentele informatica
• Programming languages (Electronic computers) > Semantics > Congresses
• Parallel programming (Computer science) > Congresses
• Informatique > Congrès

Genre/Form

Conference papers and proceedings.

Bibliography (note)

• Includes bibliographical references and index.

Contents

New Trends in Quantum Computing / G. Brassard -- Compressibility and Resource Bounded Measure / H. Buhrman and L. Longpre -- On the Complexity of Random Strings / M. Kummer -- Remarks on Generalized Post Correspondence Problem / T. Harju, J. Karhumaki and D. Krob -- Cyclic Languages and Strongly Cyclic Languages / M.-P. Beal, O. Carton and C. Reutenauer -- Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness / K. Ambos-Spies, E. Mayordomo, Y. Wang and X. Zheng -- The Complexity of Generating and Checking Proofs of Membership / H. Buhrman and T. Thierauf -- Observations on Measures and Lowness for [actual symbol not reproducible] / J. H. Lutz -- Solvable Black-Box Group Problems Are Low for PP / V. Arvind and N. V. Vinodchandran -- Languages Recognized by Finite Aperiodic Groupoids / M. Beaudry -- Star-Height of an IN-Rational Series / F. Bassino -- An Aperiodic Set of Wang Cubes / K. Culik II and J. Kari -- Lyndon Factorization of Infinite Words / G. Melancon -- Embedding Graphs with Bounded Treewidth into Optimal Hypercubes / V. Heun and E. W. Mayr -- Parallel Comparability Graph Recognition and Modular Decomposition / M. Morvan and L. Viennot -- Fault-Tolerant Shared Memory Simulations / P. Berenbrink, F. Meyer auf der Heide and V. Stemann -- On Word-Level Parallelism in Fault-Tolerant Computing / P. Indyk -- Learning with Confidence / J. Barzdins, R. Freivalds and C. H. Smith -- Extracting Best Consensus Motifs from Positive and Negative Examples / E. Tateishi, O. Maruyama and S. Miyano -- PAC Learning with Simple Examples / F. Denis, C. D'Halluin and R. Gilleron -- General Inductive Inference Types Based on Linearly-Ordered Sets / A. Ambainis, R. Freivalds and C. H. Smith -- On the Power of Non-observable Actions in Timed Automata / B. Berard, P. Gastin and A. Petit -- Trace Rewriting: Computing Normal Forms in Time O (n log n) / M. Bertol and V. Diekert -- A Decision Procedure for Well-Formed Linear Quantum Cellular Automata / C. Durr, H. Le Thanh and M. Santha -- On the Complexity of Worst Case and Expected Time in a Circuit / A. Jacoby and C. Schindelhauer -- On the Existence of Hard Sparse Sets under Weak Reductions / J.-Y. Cai, A. V. Naik and D. Sivakumar -- Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardness / A. E. Andreev, A. E. F. Clementi and J. D. P. Rolim -- Fine Separation of Average Time Complexity Classes / J.-Y. Cai and A. L. Selman -- Compositional Specification of Timed Systems / J. Sifakis and S. Yovine -- Optimal Tree-Based One-time Digital Signature Schemes / D. Bleichenbacher and U. M. Maurer -- The Action of a Few Random Permutations on r-Tuples and an Application to Cryptography / J. Friedman, A. Joux, Y. Roichman, J. Stern and J.-P. Tillich -- A Unified and Generalized Treatment of Authentication Theory / U. M. Maurer -- Monadic Second Order Logic on Tree-Like Structures / I. Walukiewicz -- On Bijections vs. Unary Functions / T. Schwentick -- The 3 Frenchmen Methods Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs / J. Marcinkowski -- A Combinatorial Design Approach to MAXCUT / T. Hofmeister and H. Lefmann -- Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width / A. Gupta and N. Nishimura -- A Characterization of the Quadrilateral Meshes of a Surface which Admit a Compatible Hexahedral Mesh of Enclosed Volume / S. A. Mitchell -- On the Expressivity of the Modal Mu-Calculus / J. C. Bradfield -- Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams / B. Bollig and I. Wegener -- "Optimal" Collecting Semantics for Analysis in a Hierarchy of Logic Program Semantics / R. Giacobazzi -- Flip-Flop Nets / V. Schmitt -- Lower Bounds for Compact Routing / E. Kranakis and D. Krizanc -- On the Successor Function in Non-classical Numeration Systems / C. Frougny -- Minimal Forbidden Words and Symbolic Dynamics / M.-P. Beal and F. Mignosi -- Universal Hashing and k-wise Independent Random Variables via Integer Arithmetic without Primes / M. Dietzfelbinger -- Ranking and Unranking Trees Using Regular Reductions / P. Kelsen -- On Competitive On-Line Paging with Lookahead / D. Breslauer -- Hypothesis Testing in Perfect Phylogeny for a Bounded Number of Characters / J. Lagergren -- The "log Rank" Conjecture for Modular Communication Complexity / C. Meinel and S. Waack -- Upper Bounds on Multiparty Communication Complexity of Shifts / A. Ambainis -- Some Bounds on Multiparty Communication Complexity of Pointer Jumping / C. Damm, S. Jukna and J. Sgall -- Optimal Schedules for d-D Grid Graphs with Communication Delays / E. Bampis, C. Delorme and J.-C. Konig -- Linear Programming -- Randomization and Abstract Frameworks / B. Gartner and E. Welzl.

ISBN

• 3540609229
• 9783540609223

LCCN

96006926

OCLC

• ocm34245696
• 34245696
• SCSB-9168026

Owning Institutions

Princeton University Library