JCSS, Volume 44

Volume 44, Number 1, February 1992

Edward P. F. Chan, Paolo Atzeni: Connection-Trap-Free Database Schemes. 1-22 BibTeX
Razvan Diaconescu: Contraction Algebras and Unification of (Infinite) Terms. 23-42 BibTeX
David E. Muller, Franco P. Preparata: Parallel Restructuring and Evaluation of Expressions. 43-62 BibTeX
Thomas Lengauer, Klaus W. Wagner: The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems. 63-93 BibTeX
Elias Dahlhaus, Marek Karpinski: Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. 94-102 BibTeX
Prabhakar Ragde: Processor-Time Tradeoffs in PRAM Simulations. 103-113 BibTeX
Satoshi Takahashi: Self-Similarity of Linear Cellular Automata. 114-140 BibTeX
Ravi S. Sandhu: Undecidability of Safety for the Schematic Protection Model with Cyclic Creates. 141-159 BibTeX
Thomas Herbst: Some Remarks on a Theorem of Sakarovitch. 160-165 BibTeX

Selected Papers from the 4th Annual Conference on Structure in Complexity Theory, June 19-22, 1989

Wolfgang Maass, Theodore A. Slaman: The Complexity Types of Computable Sets. 168-192 BibTeX
Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby: On the Theory of Average Case Complexity. 193-219 BibTeX
Jack H. Lutz: Almost Everywhere High Nonuniform Complexity. 220-258 BibTeX
Uriel Feige, Adi Shamir: Multi-Oracle Interactive Protocols with Constant Space Verifiers. 259-271 BibTeX
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán: Turing Machines with Few Accepting Computations and Low Sets for PP. 272-286 BibTeX
Steven Homer, Alan L. Selman: Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. 287-301 BibTeX
Ernst W. Mayr, Ashok Subramanian: The Complexity of Circuit Value and Network Stability. 302-323 BibTeX
Tak Wah Lam, Walter L. Ruzzo: Results on Communication Complexity Classes. 324-342 BibTeX
Ming Li, Paul M. B. Vitányi: Inductive Reasoning and Kolmogorov Complexity. 343-384 BibTeX

Steven Lindell: The Invariant Problem for Binary String Structures and the Parallel Complexity Theory of Queries. 385-410 BibTeX
Andrew Klapper: Distributed Event Algebras. 411-424 BibTeX
Michael Kaminski, Shlomit S. Pinter: Finite Automata on Directed Graphs. 425-446 BibTeX
Manuel Silva, Tadao Murata: B-Fairness and Structural B-Fairness in Petri Net Models of Concurrent Systems. 447-477 BibTeX
David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien: Regular Languages in NC¹. 478-499 BibTeX
Osamu Watanabe: On Polynomial Time One-Truth-Table Reducibility to a Sparse Set. 500-516 BibTeX