JCSS, Volume 44

Volume 44, Number 1, February 1992

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

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

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