Proceedings / STACS 96: 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22 - 24, 1996 - Puech, Claude (Lecture notes in computer science, 1996)
New trends in quantum computing -- Compressibility and resource bounded measure -- On the complexity of random strings -- Remarks on generalized Post Correspondence Problem -- Cyclic languages and strongly cyclic languages -- Resource-bounded balanced genericity, stochasticity and weak randomness -- The complexity of generating and checking proofs of membership -- Observations on measure and lowness for ? 2 P -- Solvable black-box group problems are low for PP -- Languages recognized by finite aperiodic groupoids -- Star-height of an N-rational series -- An aperiodic set of Wang cubes -- Lyndon factorization of infinite words -- Embedding graphs with bounded treewidth into optimal hypercubes -- Parallel comparability graph recognition and modular decomposition -- Fault-tolerant shared memory simulations -- On word-level parallelism in fault-tolerant computing -- Learning with confidence -- Extracting best consensus motifs from positive and negative examples -- PAC learning with simple examples -- General inductive inference types based on linearly-ordered sets -- On the power of non-observable actions in timed automata -- Trace rewriting: Computing normal forms in time O(n log n) -- A decision procedure for well-formed linear quantum cellular automata -- On the complexity of worst case and expected time in a circuit -- On the existence of hard sparse sets under weak reductions -- Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness -- Fine separation of average time complexity classes -- Compositional specification of timed systems -- Optimal tree-based one-time digital signature schemes -- The action of a few random permutations on r-tuples and an application to cryptography -- A unified and generalized treatment of authentication theory -- Monadic second order logic on tree-like structures -- On bijections vs. unary functions -- The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs -- A combinatorial design approach to MAXCUT -- Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width -- A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume -- On the expressivity of the modal mu-calculus -- Read-once projections and formal circuit verification with binary decision diagrams -- “Optimal” collecting semantics for analysis in a hierarchy of logic program semantics -- Flip-flop nets -- Lower bounds for compact routing -- On the successor function in non-classical numeration systems -- Minimal forbidden words and symbolic dynamics -- Universal hashing and k-wise independent random variables via integer arithmetic without primes -- Ranking and unranking trees using regular reductions -- On competitive on-line paging with lookahead -- Hypothesis testing in perfect phylogeny for a bounded number of characters -- The “log rank” conjecture for modular communication complexity -- Upper bounds on multiparty communication complexity of shifts -- Some bounds on multiparty communication complexity of pointer jumping -- Optimal schedules for d-D grid graphs with communication delays -- Linear programming — Randomization and abstract frameworks.
Literaturangaben
Keywords: Konferenzschrift -- 1996 -- Grenoble; Theoretische Informatik