Information and Computation, Volume 138

Volume 138, Number 1, October 10, 1997

Shiva Chaudhuri, Jaikumar Radhakrishnan: The Complexity of Parallel Prefix Problems on Small Domains. 1-22
Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie: Efficient Learning of Typical Finite Automata from Random Walks. 23-48
Alexander Moshe Rabinovich: On Schematological Equivalence of Partially Interpreted Dataflow Networks. 49-87
Paul Beame, Faith E. Fich, Rakesh K. Sinha: Separating the Power of EREW and CREW PRAMs with Small Communication Width. 89-99

Jan Kuper: On the Jacopini Technique. 101-123
Patrice Brémond-Grégoire, Jin-Young Choi, Insup Lee: A Complete Axiomatization of Finite-State ACSR Processes. 124-159
Michel Latteux, David Simplot: Context-Sensitive String Languages and Eecognizable Picture Languages. 160-169
Rakesh D. Barve, Philip M. Long: On the Complexity of Learning from Drifting Distributions. 170-193
Roberto Segala: Quiescence, Fairness, Testing, and the Notion of Implementation. 194-210