Information and Computation, Volume 108

Volume 108, Number 1, 1994

Sauro Tulipani: Decidability of the Existential Theory of Infinite Terms with Subterm Relation. 1-33
Hans L. Bodlaender, Shlomo Moran, Manfred K. Warmuth: The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case. 34-50
Gérard Boudol: Lambda-Calculi for (Strict) Parallel Functions. 51-127
Frank S. de Boer, Catuscia Palamidessi: Embedding as a Tool for Language Comparison. 128-157
Rafail E. Krichevsky: Occam's Razor, Partially Specified Boolean Functions, String Matching, and Independent Sets. 158-174

Takeshi Shinohara: Rich Classes Inferable from Positive Data: Length-Bounded Elementary Formal Systems. 175-186
Ricardo A. Baeza-Yates, Gaston H. Gonnet: Fast String Matching with Mismatches. 187-199
Johan Håstad, Ingo Wegener, Norbert Wurm, Sang-Zin Yi: Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC⁰. 200-211
Nick Littlestone, Manfred K. Warmuth: The Weighted Majority Algorithm. 212-261
Danilo Bruschi, Giovanni Pighizzini, Nicoletta Sabadini: On the Existence of Minimum Asynchronous Automata and on the Equivalence Problem for Unambiguous Regular Trace Languages. 262-285