Information and Computation -- 1989

Volume 80, Number 1, January 1989

• Leen Torenvliet and Peter van Emde Boas. Simplicity, immunity, relativizations and nondeterminism. Information and Computation, 80(1):1-17, January 1989. References and Citations. [BibTeX entry]

• Hans Kleine Büning and Ulrich Löwen. Optimizing propositional calculus formulas with regard to questions of deducibility. Information and Computation, 80(1):18-43, January 1989. [BibTeX entry]

• Miklos Santha. Relativized Arthur-Merlin versus Merlin-Arthur games. Information and Computation, 80(1):44-49, January 1989. [BibTeX entry]

• P.-L. Curien and A. Obtu{\l}owicz. Partiality, Cartesian closedness and toposes. Information and Computation, 80(1):50-95, January 1989. Citations. [BibTeX entry]

Volume 80, Number 2, February 1989

• J. W. Klop and R. C. de Vrijer. Unique normal forms for lambda calculus with surjective pairing. Information and Computation, 80(2):97-113, February 1989. Citations. [BibTeX entry]

• Joost Engelfriet. The power to two-way deterministic checking stack automata. Information and Computation, 80(2):114-120, February 1989. References. [BibTeX entry]

• Gilles Bernot. Correctness proofs for abstract implementation. Information and Computation, 80(2):121-151, February 1989. Citations. [BibTeX entry]

• Vijay V. Vazirani. NC algorithms for computing the number of perfect matchings in K_{3,3}-free graphs and related problems. Information and Computation, 80(2):152-164, February 1989. References and Citations. [BibTeX entry]

• Patrick Cousot and Radhia Cousot. A language independent proof of the soundness and completeness of generalized Hoare logic. Information and Computation, 80(2):165-191, February 1989. [BibTeX entry]

Volume 80, Number 3, March 1989

• Howard J. Karloff and Walter L. Ruzzo. The iterated mod problem. Information and Computation, 80(3):193-204, March 1989. References and Citations. [BibTeX entry]

• Patrick W. Dymond and Stephen A. Cook. Complexity theory of parallel time and hardware. Information and Computation, 80(3):205-226, March 1989. References and Citations. [BibTeX entry]

• J. Ross Quinlan and Ronald L. Rivest. Inferring decision trees using the minimum description length principle. Information and Computation, 80(3):227-248, March 1989. Citations. [BibTeX entry]

• Sara Porat and Nissim Francez. Fairness in context-free grammars under every choice-strategy. Information and Computation, 80(3):249-268, March 1989. References. [BibTeX entry]

• Birgit Jenner, Bernd Kirsig, and Klaus-Jörn Lange. The logarithmic alternation hierarchy collapses: A \sum^{\cal{L}}_2 = A{\Pi}^{\cal{L}}_2. Information and Computation, 80(3):269-287, March 1989. Citations. [BibTeX entry]

Volume 81, Number 1, April 1989

• Jerzy Tiuryn. A simplified proof of DDL < DL. Information and Computation, 81(1):1-12, April 1989. References. [BibTeX entry]

• M. C. Browne, E. M. Clarke, and O. Grumberg. Reasoning about networks with many identical finite state processes. Information and Computation, 81(1):13-31, April 1989. Citations. [BibTeX entry]

• Alan Gibbons and Wojciech Rytter. Optimal parallel algorithm for dynamic expression evaluation and context-free recognition. Information and Computation, 81(1):32-45, April 1989. References and Citations. [BibTeX entry]

• Aviezri S. Fraenkel. The use and usefulness of numeration systems. Information and Computation, 81(1):46-61, April 1989. Citations. [BibTeX entry]

• Ker-I Ko. Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation, 81(1):62-87, April 1989. Citations. [BibTeX entry]

• Joost Engelfriet and George Leih. Linear graph grammars: Power and complexity. Information and Computation, 81(1):88-121, April 1989. References and Citations. [BibTeX entry]

Volume 81, Number 2, May 1989

• Thierry Coquand, Carl Gunter, and Glynn Winskel. Domain theoretic models of polymorphism. Information and Computation, 81(2):123-167, May 1989. References and Citations. [BibTeX entry]

• V. Michele Abrusci and Gianfranco Mascari. A logic of recursion. Information and Computation, 81(2):168-226, May 1989. References. [BibTeX entry]

• Robin Milner. A complete axiomatisation for observational congruence of finite-state behaviors. Information and Computation, 81(2):227-247, May 1989. Citations. [BibTeX entry]

Volume 81, Number 3, June 1989

• Robert S. Streett and E. Allen Emerson. An automata theoretic decision procedure for the propositional mu-calculus. Information and Computation, 81(3):249-264, June 1989. References and Citations. [BibTeX entry]

• G. Sénizergues. Church-Rosser controller rewriting systems and equivalence problems for deterministic context-free languages. Information and Computation, 81(3):265-279, June 1989. References. [BibTeX entry]

• Sorin Istrail. An arithmetical hierarchy in propositional dynamic logic. Information and Computation, 81(3):280-289, June 1989. [BibTeX entry]

• Karel Hrbacek. Convex powerdomains II. Information and Computation, 81(3):290-317, June 1989. References and Citations. [BibTeX entry]

• Don Coppersmith, Prabhakar Raghavan, and Martin Tompa. Parallel graph algorithms that are efficient on average. Information and Computation, 81(3):318-333, June 1989. References. [BibTeX entry]

• Richard Cole and Uzi Vishkin. Faster optimal parallel prefix sums and list ranking. Information and Computation, 81(3):334-352, June 1989. References and Citations. [BibTeX entry]

• H.-J. Stoss and W. Schnitzlein. Linear-time simulation of multihead Turing machines. Information and Computation, 81(3):353-363, June 1989. Citations. [BibTeX entry]

• Dan E. Willard and John H. Reif. Parallel processing can be harmful: The unusual behavior of interpolation search. Information and Computation, 81(3):364-379, June 1989. Citations. [BibTeX entry]

Volume 82, Number 1, July 1989

• Jean-Pierre Jouannaud and Emmanuel Kounalis. Automatic proofs by induction in theories without constructors. Information and Computation, 82(1):1-33, July 1989. References and Citations. [BibTeX entry]

• Jin-Yi Cai and Lane A. Hemachandra. Enumerative counting is hard. Information and Computation, 82(1):34-44, July 1989. References and Citations. [BibTeX entry]

• Dan E. Willard. Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems. Information and Computation, 82(1):45-64, July 1989. Citations. [BibTeX entry]

• Manfred Droste. Recursive domain equations for concrete data structures. Information and Computation, 82(1):65-80, July 1989. Citations. [BibTeX entry]

• Nancy A. Lynch and Eugene W. Stark. A proof of the Kahn principle for input/output automata. Information and Computation, 82(1):81-92, July 1989. Abstract, References, and Citations. [BibTeX entry]

• Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, July 1989. Citations. [BibTeX entry]

Volume 82, Number 2, August 1989

• A. Bertoni, G. Mauri, and N. Sabadini. Membership problems for regular and context-free trace languages. Information and Computation, 82(2):135-150, August 1989. Citations. [BibTeX entry]

• Margaret Montenyohl and Mitchell Wand. Incorporating static analysis in a combinator-based compiler. Information and Computation, 82(2):151-184, August 1989. Abstract, References, and Citations. [BibTeX entry]

• László Babai and Shlomo Moran. Proving properties of interactive proofs by a generalized counting technique. Information and Computation, 82(2):185-197, August 1989. [BibTeX entry]

• André Arnold and Anne Dicky. An algebraic characterization of transition system equivalences. Information and Computation, 82(2):198-229, August 1989. Citations. [BibTeX entry]

Volume 82, Number 2, September 1989

• Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82(3):231-246, September 1989. References and Citations. [BibTeX entry]

• Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261, September 1989. Citations. [BibTeX entry]

• Richard J. Anderson, Ernst W. Mayr, and Manfred K. Warmuth. Parallel approximation algorithms for bin packing. Information and Computation, 82(3):262-277, September 1989. Abstract, References, and Citations. [BibTeX entry]

• F. A. Stomp, W. P. de Roever, and R. T. Gerth. The upsilon calculus as an assertion-language for fairness arguments. Information and Computation, 82(3):278-322, September 1989. Citations. [BibTeX entry]

• R\=usi\c{n}\v{s} Freivalds, Carl H. Smith, and Mahendran Velauthapillai. Trade-off among parameters effecting inductive inference. Information and Computation, 82(3):323-349, September 1989. Abstract, References, and Citations. [BibTeX entry]

• Foto Afrati, Christos H. Papadimitriou, and George Papageorgiou. Corrigendum: The complexity of cubical graphs. Information and Computation, 82(3):350-353, September 1989. References. [BibTeX entry]

Volume 83, Number 1, October 1989

• Jonathan S. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83(1):1-20, October 1989. Citations. [BibTeX entry]

• Toshiya Itoh and Shigeo Tsujii. Structure of parallel multipliers for a class of fields GF(2^m). Information and Computation, 83(1):21-40, October 1989. References. [BibTeX entry]

• M. Nivat and A. Saoudi. Automata on infinite objects and their applications to logic and programming. Information and Computation, 83(1):41-64, October 1989. References. [BibTeX entry]

• Bernd Voigt and Ingo Wegener. Minimal polynomials for the conjunction of functions on disjoint variables can be very simple. Information and Computation, 83(1):65-79, October 1989. [BibTeX entry]

• R. Ahlswede and Z. Zhang. Coding for write-efficient memory. Information and Computation, 83(1):80-97, October 1989. References and Citations. [BibTeX entry]

• Alok Aggarwal, Heather Booth, Joseph O'Rourke, Subhash Suri, and Chee K. Yap. Finding minimal convex nested polygons. Information and Computation, 83(1):98-110, October 1989. Abstract, References, and Citations. [BibTeX entry]

• Vladimir Estivill-Castro and Derick Wood. A new measure of presortedness. Information and Computation, 83(1):111-119, October 1989. Citations. [BibTeX entry]

Volume 83, Number 2, November 1989

• Neil Immerman and Dexter Kozen. Definability with bounded number of bound variables. Information and Computation, 83(2):121-139, November 1989. Abstract, References, and Citations. [BibTeX entry]

• A. Arnold and S. Brlek. Optimal word chains for the Thue-Morse word. Information and Computation, 83(2):140-151, November 1989. [BibTeX entry]

• Pierre America, Jaco de Bakker, Joost N. Kok, and Jan Rutten. Denotational semantics of a parallel object-oriented language. Information and Computation, 83(2):152-205, November 1989. References and Citations. [BibTeX entry]

• Michiel H. M. Smid, Mark H. Overmars, Leen Torenvliet, and Peter van Emde Boas. Maintaining multiple representations of dynamic data structures. Information and Computation, 83(2):206-233, November 1989. [BibTeX entry]

• F. E. Fich, M. Li, P. Ragde, and Y. Yesha. On the power of concurrent-write PRAMs with read-only memory. Information and Computation, 83(2):234-244, November 1989. [BibTeX entry]

• Yongkyun Cho and Seymour Ginsburg. Decision problems of object histories. Information and Computation, 83(2):245-263, November 1989. References. [BibTeX entry]

Volume 83, Number 3, December 1989

• Steven M. German, Edmund M. Clarke, and Joseph Y. Halpern. Reasoning about procedures as parameters in the language L4. Information and Computation, 83(3):265-359, December 1989. Abstract, References, and Citations. [BibTeX entry]

Shortcuts: