Information and Computation -- 1991

Volume 90, Number 1, January 1991

• Corrado Böhm and Enrico Tronci. About systems of equations, x-separability, and left-invertibility in the lambda-calculus. Information and Computation, 90(1):1-32, January 1991. Citations. [BibTeX entry]

• Nathan Linial, Yishay Mansour, and Ronald L. Rivest. Results on learnability and the Vapnik-Chervonenkis dimension. Information and Computation, 90(1):33-49, January 1991. References and Citations. [BibTeX entry]

• Phokion G. Kolaitis. The expressive power of stratified programs. Information and Computation, 90(1):50-66, January 1991. References and Citations. [BibTeX entry]

• Dung T. Huynh. Effective entropies and data compression. Information and Computation, 90(1):67-85, January 1991. References and Citations. [BibTeX entry]

• Oscar H. Ibarra, Tao Jiang, Jik H. Chang, and Bala Ravikumar. Some classes of languages in NC^1. Information and Computation, 90(1):86-106, January 1991. References and Citations. [BibTeX entry]

• Zhaohui Luo. A higher-order calculus and theory abstraction. Information and Computation, 90(1):107-137, January 1991. References and Citations. [BibTeX entry]

Volume 90, Number 2, February 1991

• Eric Bach. Toward a theory of Pollard's rho method. Information and Computation, 90(2):139-155, February 1991. [BibTeX entry]

• Ker-I Ko. Separating the low and high hierarchies by oracles. Information and Computation, 90(2):156-177, February 1991. Citations. [BibTeX entry]

• W. F. McColl, M. S. Paterson, and B. H. Bowditch. Planar acyclic computation. Information and Computation, 90(2):178-193, February 1991. [BibTeX entry]

• Peter Dybjer. Inverse image analysis generalises strictness analysis. Information and Computation, 90(2):194-216, February 1991. Citations. [BibTeX entry]

• Mila E. Majster-Cederbaum and F. Zetzsche. Towards a foundation for semantics in complete metric spaces. Information and Computation, 90(2):217-243, February 1991. References and Citations. [BibTeX entry]

Volume 91, Number 1, March 1991

• Matthias Krause. Lower bounds for depth-restricted branching programs. Information and Computation, 91(1):1-14, March 1991. Citations. [BibTeX entry]

• Nicole Bidoit and Christine Froidevaux. General logical databases and programs: Default logic semantics and stratification. Information and Computation, 91(1):15-54, March 1991. Citations. [BibTeX entry]

• Roberto M. Amadio. Recursion over realizability structures. Information and Computation, 91(1):55-85, March 1991. References and Citations. [BibTeX entry]

• Samuel R. Buss and Louise Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86-102, March 1991. References and Citations. [BibTeX entry]

• Kirk Pruhs and Udi Manber. The complexity of controlled selection. Information and Computation, 91(1):103-127, March 1991. [BibTeX entry]

• Dan Geiger, Azaria Paz, and Judea Pearl. Axioms and algorithms for inferences involving probabilistic independence. Information and Computation, 91(1):128-141, March 1991. Citations. [BibTeX entry]

• Joachim von zur Gathen and Gadiel Seroussi. Boolean circuits versus arithmetic circuits. Information and Computation, 91(1):142-154, March 1991. References and Citations. [BibTeX entry]

Volume 91, Number 2, April 1991

• P. S. Gopalakrishnan, I. V. Ramakrishnan, and L. N. Kanal. Approximate algorithms for the knapsack problem on parallel computers. Information and Computation, 91(2):155-171, April 1991. [BibTeX entry]

• Lajos Rónyai. Computing the order of centralizers in linear groups. Information and Computation, 91(2):172-176, April 1991. [BibTeX entry]

• M. Chrobak, H. Karloff, and T. Radzik. Connectivity vs. reachability. Information and Computation, 91(2):177-188, April 1991. [BibTeX entry]

• N. G. de Bruijn. Telescopic mappings in typed lambda calculus. Information and Computation, 91(2):189-204, April 1991. References and Citations. [BibTeX entry]

• Brian A. Coan and Cynthia Dwork. Simultaneity is harder than agreement. Information and Computation, 91(2):205-231, April 1991. References and Citations. [BibTeX entry]

• Kim Guldstrand Larsen and Glynn Winskel. Using information systems to solve recursive domain equations. Information and Computation, 91(2):232-258, April 1991. Citations. [BibTeX entry]

• Stephen J. Bellantoni. Parallel random access machines with bounded memory wordsize. Information and Computation, 91(2):259-273, April 1991. Citations. [BibTeX entry]

Volume 92, Number 1, May 1991

• Richard Cole and Uzi Vishkin. Approximate parallel scheduling. II. Applications to logarithmic-time optimal parallel graph algorithms. Information and Computation, 92(1):1-47, May 1991. References and Citations. [BibTeX entry]

• Felice Cardone and Mario Coppo. Type inference with recursive types: Syntax and semantics. Information and Computation, 92(1):48-80, May 1991. References and Citations. [BibTeX entry]

• Scot W. Hornick and Franco P. Preparata. Deterministic P-RAM simulation with constant redundancy. Information and Computation, 92(1):81-96, May 1991. [BibTeX entry]

• John G. Geske, Dung T. Huynh, and Joel I. Seiferas. A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes. Information and Computation, 92(1):97-104, May 1991. [BibTeX entry]

• Arnon Avron. Simple consequence relations. Information and Computation, 92(1):105-140, May 1991. Citations. [BibTeX entry]

Volume 92, Number 2, June 1991

• Walter Cunto, Gastón H. Gonnet, J. Ian Munro, and Patricio V. Poblete. Fringe analysis for extquick: An in situ distributive external sorting algorithm. Information and Computation, 92(2):141-160, June 1991. [BibTeX entry]

• Samson Abramsky. A domain equation for bisimulation. Information and Computation, 92(2):161-218, June 1991. References and Citations. [BibTeX entry]

• Jianzhong Du, Joseph Y-T. Leung, and Gilbert H. Young. Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation, 92(2):219-236, June 1991. Citations. [BibTeX entry]

• H. Venkateswaran. Two dynamic programming algorithms for which intepreted pebbling helps. Information and Computation, 92(2):237-252, June 1991. [BibTeX entry]

• Efim Kinber and Thomas Zeugmann. One-sided error probabilistic inductive inference and reliable frequency identification. Information and Computation, 92(2):253-284, June 1991. Abstract, References, and Citations. [BibTeX entry]

Volume 93, Number 1, July 1991

Special Issue: Selections from 1989 IEEE Symposium on Logic in Computer Science

• Rohit Parikh. Preface. Information and Computation, 93(1):iii, July 1991. [BibTeX entry]

• Mitchell Wand. Type inference for record concatenation and multiple inheritance. Information and Computation, 93(1):1-15, July 1991. Abstract, References, Citations, etc. [BibTeX entry]

• Michael W. Mislove, Lawrence S. Moss, and Frank J. Oles. Non-well-founded sets modeled as ideal fixed points. Information and Computation, 93(1):16-54, July 1991. Citations, etc. [BibTeX entry]

• Eugenio Moggi. Notions of computation and monads. Information and Computation, 93(1):55-92, July 1991. Citations, etc. [BibTeX entry]

• Daniel Leivant. Finitely stratified polymorphism. Information and Computation, 93(1):93-113, July 1991. Citations, etc. [BibTeX entry]

• Yiannis N. Moschovakis. A model of concurrency with fair merge and full recursion. Information and Computation, 93(1):114-171, July 1991. Citations, etc. [BibTeX entry]

• Val Breazu-Tannen, Thierry Coquand, Carl A. Gunter, and Andre Scedrov. Inheritance as implicit coercion. Information and Computation, 93(1):172-221, July 1991. References, Citations, etc. [BibTeX entry]

Volume 93, Number 2, August 1991

• William Aiello and Johan Hastad. Relativized perfect zero knowledge is not BPP. Information and Computation, 93(2):223-240, August 1991. Citations. [BibTeX entry]

• Pierluigi Crescenzi and Alessandro Panconesi. Completeness in approximation classes. Information and Computation, 93(2):241-262, August 1991. Citations. [BibTeX entry]

• Solomon Passay and Tinko Tinchev. An essay in combinatory dynamic logic. Information and Computation, 93(2):263-332, August 1991. References and Citations. [BibTeX entry]

• H. James Hoover. Real functions, contraction mappings and P-completeness. Information and Computation, 93(2):333-349, August 1991. [BibTeX entry]

Volume 94, Number 1, September 1991

• Kim G. Larsen and Arne Skou. Bisimulation through probabilistic testing. Information and Computation, 94(1):1-28, September 1991. Citations. [BibTeX entry]

• P. C. P. Bhatt, K. Diks, T. Hagerup, V. C. Prasad, T. Radzik, and S. Saxena. Improved deterministic parallel integer sorting. Information and Computation, 94(1):29-47, September 1991. Abstract, References, and Citations. [BibTeX entry]

• Manfred Droste. Universal homogeneous event structures and domains. Information and Computation, 94(1):48-61, September 1991. References and Citations. [BibTeX entry]

• Erich Grädel. Simple sentences that are hard to decide. Information and Computation, 94(1):62-82, September 1991. [BibTeX entry]

• Anna Lubiw and András Rácz. A lower bound for the integer element distinctiveness problem. Information and Computation, 94(1):83-92, September 1991. [BibTeX entry]

• Egon Wanke. Algorithms for graph problems on BNLC structured graphs. Information and Computation, 94(1):93-122, September 1991. Abstract, References, and Citations. [BibTeX entry]

Volume 94, Number 2, October 1991

• J. W. de Bakker. Comparative semantics for flow of control in logic programming without logic. Information and Computation, 94(2):123-179, October 1991. References and Citations. [BibTeX entry]

• M. L. Tiomkin and J. A. Makowsky. Decidability of finite probablistic propositional dynamic logics. Information and Computation, 94(2):180-203, October 1991. References. [BibTeX entry]

• Stefano Berardi. Retractions on di-domains as a model for type:type. Information and Computation, 94(2):204-231, October 1991. Citations. [BibTeX entry]

• Stephan Waack and Matthias Krause. On oblivious branching programs of linear length. Information and Computation, 94(2):232-249, October 1991. References and Citations. [BibTeX entry]

Volume 95, Number 1, November 1991

• Amotz Bar-Noy, Danny Dolev, Daphne Koller, and David Peleg. Fault-tolerant critical section management in asynchronous environments. Information and Computation, 95(1):1-20, November 1991. Abstract. [BibTeX entry]

• Joost Engelfriet. Iterated stack automata and complexity classes. Information and Computation, 95(1):21-75, November 1991. References and Citations. [BibTeX entry]

• A. Apostolico and M. Crochemore. Optimal canonization of all substrings of a string. Information and Computation, 95(1):76-95, November 1991. Citations. [BibTeX entry]

• David A. Mix Barrington and Pierre McKenzie. Oracle branching programs and Logspace versus P. Information and Computation, 95(1):96-115, November 1991. References and Citations. [BibTeX entry]

Volume 95, Number 2, December 1991

• Juraj Hromkovi\v{c}. Nonlinear lower bounds on the number of processors of circuits with sublinear separators. Information and Computation, 95(2):117-128, December 1991. [BibTeX entry]

• David Haussler, Michael Kearns, Nick Littlestone, and Manfred K. Warmuth. Equivalence of models for polynomial learnability. Information and Computation, 95(2):129-161, December 1991. Citations. [BibTeX entry]

• Sanjay Jain and Arun Sharma. Learning in the presence of partial explanations. Information and Computation, 95(2):162-191, December 1991. Abstract, References, and Citations. [BibTeX entry]

• Alban Ponse. Process expressions and hoare's logic: Showing an irreconcilability of context-free recursion with scott's induction rule. Information and Computation, 95(2):192-217, December 1991. References. [BibTeX entry]

• R. Mahesh, C. Pandu Rangan, and Aravind Srinivasan. On finding the minimum bandwidth of interval graphs. Information and Computation, 95(2):218-224, December 1991. References. [BibTeX entry]

• Livio Colussi. Correctness and efficiency of the pattern matching algorithms. Information and Computation, 95(2):225-251, December 1991. Citations. [BibTeX entry]

Shortcuts: