Information and Computation -- 1997

Volume 132, Number 1, January 10, 1997

• Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1-63, 10 January 1997. Abstract, References, Citations, etc. [BibTeX entry]

• Sanjay Jain and Arun Sharma. Elementary formal systems, intrinsic complexity, and procrastination. Information and Computation, 132(1):65-84, 10 January 1997. Abstract and References. [BibTeX entry]

Volume 132, Number 2, February 1, 1997

• Klaus Jansen and Sabine Öhring. Approximation algorithms for time constrained scheduling. Information and Computation, 132(2):85-108, 1 February 1997. Abstract and References. [BibTeX entry]

• Mads Tofte and Jean-Pierre Talpin. Region-based memory management. Information and Computation, 132(2):109-176, 1 February 1997. Abstract, References, Citations, etc. [BibTeX entry]

Volume 133, Number 1, February 25, 1997

• Morten Heine Sørensen. Strong normalization from weak normalization in typed lambda-calculi. Information and Computation, 133(1):35-71, 25 February 1997. Abstract and References. [BibTeX entry]

• Juraj Hromkovi\v{c}, Ralf Klasing, Walter Unger, and Hubert Wagener. Optimal algorithms for broadcast and gossip in the edge-disjoint path modes. Information and Computation, 133(1):1-33, 25 February 1997. Abstract and References. [BibTeX entry]

Volume 133, Number 2, March 15, 1997

• Steffen van Bakel and Maribel Fernández. Normalization results for typeable rewrite systems. Information and Computation, 133(2):73-116, 15 March 1997. Abstract, References, and Citations. [BibTeX entry]

• Charanjit S. Jutla. Determinization and memoryless winning strategies. Information and Computation, 133(2):117-134, 15 March 1997. Abstract and References. [BibTeX entry]

Volume 134, Number 1, April 10, 1997

• Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, and Werner Nutt. The complexity of concept languages. Information and Computation, 134(1):1-58, 10 April 1997. Abstract and References. [BibTeX entry]

• Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Steve Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Information and Computation, 134(1):59-74, 10 April 1997. Abstract and References. [BibTeX entry]

Volume 134, Number 2, May 1, 1997

• Kim G. Larsen and Yi Wang. Time-abstracted bisimulation: Implicit specifications and decidability. Information and Computation, 134(2):75-101, 1 May 1997. Abstract and References. [BibTeX entry]

• Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Information and Computation, 134(2):103-139, 1 May 1997. Abstract, References, and Citations. [BibTeX entry]

Volume 135, Number 1, May 25, 1997

• Goos Kant and Hans L. Bodlaender. Triangulating planar graphs while minimizing the maximum degree. Information and Computation, 135(1):1-14, 25 May 1997. Abstract and References. [BibTeX entry]

• Konstantin Skodinis and Egon Wanke. The bounded degree problem for eNCE graph grammars. Information and Computation, 135(1):15-35, 25 May 1997. Abstract and References. [BibTeX entry]

• Rudolf Ahlswede and Ning Cai. Models of multi-user write-efficient memories and general diametric theorems. Information and Computation, 135(1):37-67, 25 May 1997. Abstract and References. [BibTeX entry]

Volume 135, Number 2, June 15, 1997

• Nicola Leone, Pasquale Rullo, and Francesco Scarcello. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation, 135(2):69-112, 15 June 1997. Abstract and References. [BibTeX entry]

• Jerzy Tyszkiewicz. The Kolmogorov expression complexity of logics. Information and Computation, 135(2):113-135, 15 June 1997. Abstract, References, and Citations. [BibTeX entry]

Volume 136, Number 1, July 10, 1997

• Martin Strauss. Measure on P: Strength of the notion. Information and Computation, 136(1):1-23, 10 July 1997. Abstract, References, and Citations. [BibTeX entry]

• Susanne Albers and Torben Hagerup. Improved parallel integer sorting without concurrent writing. Information and Computation, 136(1):25-51, 10 July 1997. Abstract, References, Citations, etc. [BibTeX entry]

• A. J. Kfoury and A. P. Stolboushkin. An infinite pebble game and applications. Information and Computation, 136(1):53-66, 10 July 1997. Abstract and References. [BibTeX entry]

Volume 136, Number 2, August 1, 1997

• Mark Levene and George Loizou. Null inclusion dependencies in relational databases. Information and Computation, 136(2):67-108, 1 August 1997. Abstract, References, and Citations. [BibTeX entry]

• Rob van Glabbeek and Frits Vaandrager. The difference between splitting in n and n+1. Information and Computation, 136(2):109-142, 1 August 1997. Abstract and References. [BibTeX entry]

• G. Venkatesan, U. Rotics, M. S. Madanlal, J. A. Makowsky, and C. Pandu Rangan. Restrictions of minimum spanner problems. Information and Computation, 136(2):143-164, 1 August 1997. Abstract and References. [BibTeX entry]

Volume 137, Number 1, August 25, 1997

• Matt Fairtlough and Michael Mendler. Propositional lax logic. Information and Computation, 137(1):1-33, 25 August 1997. Abstract and References. [BibTeX entry]

• Benedetto Intrigila. Non-existent Statman's double fixedpoint combinator does not exist, indeed. Information and Computation, 137(1):35-40, 25 August 1997. Abstract and References. [BibTeX entry]

• Moreno Falaschi, Maurizio Gabbrielli, Kim Marriott, and Catuscia Palamidessi. Constraint logic programming with dynamic scheduling: A semantics based on closure operators. Information and Computation, 137(1):41-67, 25 August 1997. Abstract, References, and Citations. [BibTeX entry]

• Yves Lafont. Interaction combinators. Information and Computation, 137(1):69-101, 25 August 1997. Abstract, References, and Citations. [BibTeX entry]

Volume 137, Number 2, September 15, 1997

• Artur Czumaj, Friedhelm Meyer auf der Heide, and Volker Stemann. Simulating shared memory in real time: On the computation power of reconfigurable architectures. Information and Computation, 137(2):103-120, 15 September 1997. Abstract, References, and Citations. [BibTeX entry]

• Luca Aceto and Wan Fokkink. An equational axiomatization for multi-exit iteration. Information and Computation, 137(2):121-158, 15 September 1997. Abstract, References, and Citations. [BibTeX entry]

• Stephen Cook, Russell Impagliazzo, and Tomoyuki Yamakami. A tight relationship between generic oracles and type-2 complexity theory. Information and Computation, 137(2):159-170, 15 September 1997. Abstract, References, and Citations. [BibTeX entry]

Volume 138, Number 1, October 10, 1997

• Shiva P. Chaudhuri and Jaikumar Radhakrishnan. The complexity of parallel prefix problems on small domains. Information and Computation, 138(1):1-22, 10 October 1997. Abstract and References. [BibTeX entry]

• Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. Efficient learning of typical finite automata from random walks. Information and Computation, 138(1):23-48, 10 October 1997. Abstract and References. [BibTeX entry]

• Alexander Rabinovich. On schematological equivalence of partially interpreted dataflow networks. Information and Computation, 138(1):49-87, 10 October 1997. Abstract and References. [BibTeX entry]

• Paul Beame, Faith E. Fich, and Rakesh K. Sinha. Separating the power of EREW and CREW PRAMs with small communication width. Information and Computation, 138(1):89-99, 10 October 1997. Abstract and References. [BibTeX entry]

Volume 138, Number 2, November 1, 1997

• Jan Kuper. On the Jacopini technique. Information and Computation, 138(2):101-123, 1 November 1997. Abstract and References. [BibTeX entry]

• Patrice Brémond-Grégoire, Jin-Young Choi, and Insup Lee. A complete axiomatization of finite-state ACSR processes. Information and Computation, 138(2):124-159, 1 November 1997. Abstract and References. [BibTeX entry]

• M. Latteux and D. Simplot. Context-sensitive string languages and recognizable picture languages. Information and Computation, 138(2):160-169, 1 November 1997. Abstract and References. [BibTeX entry]

• Rakesh D. Barve and Philip M. Long. On the complexity of learning from drifting distributions. Information and Computation, 138(2):170-193, 1 November 1997. Abstract and References. [BibTeX entry]

• Roberto Segala. Quiescence, fairness, testing, and the notion of implementation. Information and Computation, 138(2):194-210, 1 November 1997. Abstract, References, etc. [BibTeX entry]

Volume 139, Number 1, November 25, 1997

• Yonatan Aumann, Michael A. Bender, and Lisa Zhang. Efficient execution of nondeterministic parallel programs on asynchronous systems. Information and Computation, 139(1):1-16, 25 November 1997. Abstract, References, etc. [BibTeX entry]

• Christiane Frougny. On the sequentiality of the successor function. Information and Computation, 139(1):17-38, 25 November 1997. Abstract and References. [BibTeX entry]

• Giorgio Ghelli. Termination of system F-bounded: A complete proof. Information and Computation, 139(1):39-56, 25 November 1997. Abstract and References. [BibTeX entry]

• Franco Barbanera and Stefano Berardi. The simply-typed theory of beta-conversion has no maximum extension. Information and Computation, 139(1):57-61, 25 November 1997. Abstract and References. [BibTeX entry]

• Stephen L. Bloom and Zoltán Ésik. Axiomatizing shuffle and concatenation in languages. Information and Computation, 139(1):62-91, 25 November 1997. Abstract and References. [BibTeX entry]

• Hans L. Bodlaender, Jan van Leeuwen, Richard Tan, and Dimitrios Thilikos. On interval routing schemes and treewidth. Information and Computation, 139(1):92-109, 25 November 1997. Abstract and References. [BibTeX entry]

Volume 139, Number 2, December 15, 1997

• Alexander Rabinovich. Complexity of equivalence problems for concurrent systems of finite agents. Information and Computation, 139(2):111-129, 15 December 1997. Abstract and References. [BibTeX entry]

• Symeon Bozapalidis. Positive tree representations and applications to tree automata. Information and Computation, 139(2):130-153, 15 December 1997. Abstract and References. [BibTeX entry]

• Zena M. Ariola and Jan Willem Klop. Lambda calculus with explicit recursion. Information and Computation, 139(2):154-233, 15 December 1997. Abstract, References, etc. [BibTeX entry]

• Maren Hinrichs and Gerd Wechsung. Time bounded frequency computations. Information and Computation, 139(2):234-257, 15 December 1997. Abstract and References. [BibTeX entry]

• Sergio De Agostino and Riccardo Silvestri. A worst-case analysis of the LZ2 compression algorithm. Information and Computation, 139(2):258-268, 15 December 1997. Abstract and References. [BibTeX entry]

Shortcuts: