JCSS, Volume 53

Volume 53, Number 1, August 1996

• Narayan Vikas:
  An O(n) Algorithm for Abelian p-Group Isomorphism and an O(n log n) Algorithm for Abelian Group Isomorphism. 1-9
  
• Jeffrey Shallit, Yuri Breitbart:
  Automaticity I: Properties of a Measure of Descriptional Complexity. 10-25
  
• Ganesh Baliga, John Case:
  Learnability: Admissible, Co-Finite, and Hypersimple Languages. 26-32
  
• Frank Drewes:
  Language Theoretic and Algorithmic Properties of d-dimensional Collages and Patterns in a Grid. 33-66
  
• Shlomo Moran, Gadi Taubenfeld, Irit Yadin:
  Concurrent Counting. 61-78
  
• Detlef Sieling:
  New Lower Bounds and Hierarchy Results for Restricted Branching Programs. 79-87
  
• Steffen Lange, Thomas Zeugmann:
  Incremental Learning from Positive Data. 88-103
  
• Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski:
  Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. 104-111
  
• Feng Gao:
  Towards Structured Parallel Computing on Architecture-Independent Parallel Algorithm Design for Distributed-Memory Architectures. 112-128
  
• Harold N. Gabow, Ying Xu:
  Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems. 129-147
  
• Paul F. Dietz:
  A Space Efficient Variant of Path Copying for Partially Persistent Sorted Sets. 148-152
  

Volume 53, Number 2, October 1996

• Manindra Agrawal, Somenath Biswas:
  Polynomial-Time Isomorphism of 1-L-Complete Sets. 155-160
  
• Christos H. Papadimitriou, Mihalis Yannakakis:
  On Limited Nondeterminism and the Complexity of the V-C Dimension. 161-170
  
• Mitsunori Ogihara, Thomas Thierauf, Seinosuke Toda, Osamu Watanabe:
  On Closure Properties of #P in the Context of PF ° #P. 171-179
  
• Tirza Hirst, David Harel:
  Taking It to the Limit: On Infinite Variants of NP-Complete Problems. 180-193
  
• Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman:
  P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility. 194-209
  
• Harry Buhrman, Leen Torenvliet:
  P-Selektive Self-Reducible Sets: A New Characterization of P. 210-217
  
• Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo:
  Pointers versus Arithmetic in PRAMs. 218-232
  

• Steven M. Kautz, Peter Bro Miltersen:
  Relative to a Random Oracle, NP Is Not Small. 235-250
  
• Gábor Tardos:
  Multi-prover Encoding Schemes and Three-prover Proof Systems. 251-260
  
• Harry Buhrman, Pekka Orponen:
  Random Strings Make Hard Instances. 261-266
  
• Manindra Agrawal:
  On the Isomorphism Conjecture for Weak Reducibilities. 267-282
  
• Kevin J. Compton, Erich Grädel:
  Logical Definability of Counting Functions. 283-297
  
• Richard Chang:
  On the Query Complexity of Clique Size and Maximum Satisfiability. 298-313
  

Volume 53, Number 3, December 1996

• Michael Mitzenmacher:
  Bounds on the Greedy Routing Algorithm for Array Networks. 317-327
  
• Eric J. Schwabe, Ian M. Sutherland:
  Improved Parity-Declustered Layouts for Disk Arrays. 328-343
  
• Margaret Reid-Miller:
  List Ranking and List Scan on the CRAY C90. 344-356
  
• Bhaskar Ghosh, S. Muthukrishnan:
  Dynamic Load Balancing by Random Matchings. 357-370
  
• Hisao Tamaki:
  Construction of the Mesh and the Torus Tolerating a Large Number of Faults. 371-379
  
• Mauro Leoncini:
  On the Parallel Complexity of Gaussian Elimination with Pivoting. 380-394
  
• Shay Halperin, Uri Zwick:
  An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM. 395-416
  
• Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran:
  Efficient Low-Contention Parallel Algorithms. 417-442
  
• Carlo Meghini, Costantino Thanos:
  An Optimal Predicate Locking Scheduler. 443-468
  
• Andreas Goerdt:
  A Threshold for Unsatisfiability. 469-486
  
• Lila Kari, Gabriel Thierrin:
  Maximal and Minimal Solutions to Language Equations. 487-496
  
• Thomas Eiter, Georg Gottlob:
  The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions. 497-512
  
• Tao Jiang, Ming Li:
  K One-Way Heads Cannot Do String-Matching. 513-524
  
• Jean R. S. Blair, Errol L. Lloyd:
  River Routing with a Generalized Model. 525-544
  
• Suresh Chari, Pankaj Rohatgi:
  On Completeness Under Random Reductions. 545-555
  
• Joost Engelfriet, Vincent van Oostrom:
  Regular Description of Context-Free Graph Languages. 556-574
  
• Jerzy W. Grzymala-Busse, Soe Than:
  Partition Triples: A Tool for Reduction of Data Sets. 575-582
  
• Sanjay Jain:
  Program Synthesis in the Presence of Infinite Number of Inaccuracies. 583-591
  

Last update Tue Feb 14 04:20:23 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page