Information and Computation -- 1996

Volume 124, Number 1, January 10, 1996

• Lance Fortnow and Nick Reingold. PP is closed under truth-table reductions. Information and Computation, 124(1):1-6, 10 January 1996. Abstract, References, and Citations. [BibTeX entry]

• Andreas Gruchalski. Computability on dI-domains. Information and Computation, 124(1):7-19, 10 January 1996. Abstract and References. [BibTeX entry]

• Gérard Cécé, Alain Finkel, and S. Purushothaman Iyer. Unreliable channels are easier to verify than perfect channels. Information and Computation, 124(1):20-31, 10 January 1996. Abstract, References, and Citations. [BibTeX entry]

• Delia Kesner, Laurence Puel, and Val Tannen. A typed pattern calculus. Information and Computation, 124(1):32-61, 10 January 1996. Abstract and References. [BibTeX entry]

• Christian Haack. A decomposition theorem for domains. Information and Computation, 124(1):62-67, 10 January 1996. Abstract and References. [BibTeX entry]

• James H. Anderson and Jae-Heon Yang. Time/contention trade-offs for multiprocessor synchronization. Information and Computation, 124(1):68-84, 10 January 1996. Abstract, References, etc. [BibTeX entry]

• P. Kosiuczenko and K. Meinke. On the power of higher-order algebraic specification methods. Information and Computation, 124(1):85-101, 10 January 1996. Abstract, References, and Citations. [BibTeX entry]

Volume 124, Number 2, February 1, 1996

• Douglas J. Howe. Proving congruence of bisimulation in functional programming languages. Information and Computation, 124(2):103-112, 1 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Chun-Kuen Ho. Beyond recursive real functions. Information and Computation, 124(2):113-126, 1 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Rachel Ben-Eliyahu and Menachem Magidor. A temporal logic for proving properties of topologically general executions. Information and Computation, 124(2):127-144, 1 February 1996. Abstract and References. [BibTeX entry]

• Campbell B. Fraser, Robert W. Irving, and Martin Middendorf. Maximal common subsequences and minimal common supersequences. Information and Computation, 124(2):145-153, 1 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Alexander Rabinovich. On schematological equivalence of dataflow networks. Information and Computation, 124(2):154-167, 1 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Hsu-Chun Yen. On the regularity of Petri net languages. Information and Computation, 124(2):168-181, 1 February 1996. Abstract and References. [BibTeX entry]

• Abbas Edalat. Power domains and iterated function systems. Information and Computation, 124(2):182-197, 1 February 1996. Abstract, References, and Citations. [BibTeX entry]

Volume 125, Number 1, February 25, 1996

• Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125(1):1-12, 25 February 1996. Abstract, References, and Citations. [BibTeX entry]

• David W. Juedes and Jack H. Lutz. Completeness and weak completeness under polynomial-size circuits. Information and Computation, 125(1):13-31, 25 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Dora Giammarresi, Antonio Restivo, Sebastian Seibert, and Wolfgang Thomas. Monadic second-order logic over rectangular pictures and recognizability by tiling systems. Information and Computation, 125(1):32-45, 25 February 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Yves Lafont and Andre Scedrov. The undecidability of second order multiplicative linear logic. Information and Computation, 125(1):46-51, 25 February 1996. Abstract, References, and Citations. [BibTeX entry]

• Judit Bar-Ilan and David Peleg. Scheduling jobs using common resources. Information and Computation, 125(1):52-61, 25 February 1996. Abstract and References. [BibTeX entry]

• Orna Kupferman and Orna Grumberg. Branching-time temporal logic and tree automata. Information and Computation, 125(1):62-69, 25 February 1996. Abstract and References. [BibTeX entry]

• Ronald V. Book and Osamu Watanabe. On random hard sets for NP. Information and Computation, 125(1):70-76, 25 February 1996. Abstract and References. [BibTeX entry]

Volume 125, Number 2, March 15, 1996

• Masami Hagiya. Preface. Information and Computation, 125(2):77, 15 March 1996. [BibTeX entry]

• Martín Abadi and Luca Cardelli. A theory of primitive objects: Untyped and first-order systems. Information and Computation, 125(2):78-102, 15 March 1996. Abstract, References, etc. [BibTeX entry]

• Franco Barbanera and Stefano Berardi. A symmetric lambda calculus for classical program extraction. Information and Computation, 125(2):103-117, 15 March 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Ursula Goltz, Roberto Gorrieri, and Arend Rensink. Comparing syntactic and semantic action refinement. Information and Computation, 125(2):118-143, 15 March 1996. Abstract, References, etc. [BibTeX entry]

• Masako Takahashi, Yohji Akama, and Sachio Hirokawa. Normal proofs and their grammar. Information and Computation, 125(2):144-153, 15 March 1996. Abstract, References, Citations, etc. [BibTeX entry]

• David A. Plaisted and Andrea Sattler-Klein. Proof lengths for equational completion. Information and Computation, 125(2):154-170, 15 March 1996. Abstract, References, and Citations. [BibTeX entry]

Volume 126, Number 1, April 10, 1996

• Wan Fokkink and Rob van Glabbeek. Ntyft/ntyxt rules reduce to ntree rules. Information and Computation, 126(1):1-10, 10 April 1996. Abstract, References, and Citations. [BibTeX entry]

• Martin Hofmann and Benjamin C. Pierce. Positive subtyping. Information and Computation, 126(1):11-33, 10 April 1996. Abstract and References. [BibTeX entry]

• Michele Boreale and Rocco De Nicola. A symbolic semantics for the pi-calculus. Information and Computation, 126(1):34-52, 10 April 1996. Abstract and References. [BibTeX entry]

• Hasan Md. Sayeed and Hosame Abu-Amara. Efficient perfectly secure message transmission in synchronous networks. Information and Computation, 126(1):53-61, 10 April 1996. Abstract and References. [BibTeX entry]

• Rajeev Alur and Gadi Taubenfeld. Contention-free complexity of shared memory algorithms. Information and Computation, 126(1):62-73, 10 April 1996. Abstract and References. [BibTeX entry]

• Gordon Plotkin. On a question of H. Friedman. Information and Computation, 126(1):74-77, 10 April 1996. Abstract, References, and Citations. [BibTeX entry]

• Toshiya Itoh. Simulating fair dice with biased coins. Information and Computation, 126(1):78-82, 10 April 1996. Abstract and References. [BibTeX entry]

• Gérard Boudol and Cosimo Laneve. The discriminating power of multiplicities in the lambda-calculus. Information and Computation, 126(1):83-102, 10 April 1996. Abstract, References, and Citations. [BibTeX entry]

• Jens Palsberg. Erratum: Efficient inference of object types. Information and Computation, 126(1):103-104, 10 April 1996. References. [BibTeX entry]

Volume 126, Number 2, May 1, 1996

• Manfred Droste. Aperiodic languages in concurrency monoids. Information and Computation, 126(2):105-113, 1 May 1996. Abstract and References. [BibTeX entry]

• Thomas Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114-122, 1 May 1996. Abstract and References. [BibTeX entry]

• Roel Bloo, Fairouz Kamareddine, and Rob Nederpelt. The Barendregt cube with definitions and generalised reduction. Information and Computation, 126(2):123-143, 1 May 1996. Abstract, References, and Citations. [BibTeX entry]

• Christophe Ringeissen. Combining decision algorithms for matching in the union of disjoint equational theories. Information and Computation, 126(2):144-160, 1 May 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Shiva Chaudhuri. Sensitive functions and approximate problems. Information and Computation, 126(2):161-168, 1 May 1996. Abstract and References. [BibTeX entry]

Volume 127, Number 1, May 25, 1996

• Vladimir V. V'yugin. Bayesianism: An algorithmic analysis. Information and Computation, 127(1):1-10, 25 May 1996. Abstract, References, and Citations. [BibTeX entry]

• Pietro Di Gianantonio. Real number computability and domain theory. Information and Computation, 127(1):11-25, 25 May 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Luca Aceto, Rob van Glabbeek, Wan Fokkink, and Anna Ingólfsdóttir. Axiomatizing prefix iteration with silent steps. Information and Computation, 127(1):26-40, 25 May 1996. Abstract, References, and Citations. [BibTeX entry]

• Walter Vogler. The limit of Split_n-language equivalence. Information and Computation, 127(1):41-61, 25 May 1996. Abstract, References, and Citations. [BibTeX entry]

Volume 127, Number 2, June 15, 1996

• Moshe Y. Vardi. Editor's foreword. Information and Computation, 127(2):64, 15 June 1996. [BibTeX entry]

• Moshe Y. Vardi. In memoriam: {Paris C.\ Kanellakis} (1953-1995). Information and Computation, 127(2):65, 15 June 1996. [BibTeX entry]

• Andrew M. Pitts. Relational properties of domains. Information and Computation, 127(2):66-90, 15 June 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Parosh Aziz Abdulla and Bengt Jonsson. Verifying programs with unreliable channels. Information and Computation, 127(2):91-101, 15 June 1996. Abstract, References, etc. [BibTeX entry]

• John Mitchell and Ramesh Viswanathan. Standard ML-NJ weak polymorphism and imperative constructs. Information and Computation, 127(2):102-116, 15 June 1996. Abstract, References, etc. [BibTeX entry]

• Gerd G. Hillebrand, Paris C. Kanellakis, and Harry G. Mairson. Database query languages embedded in the typed lambda calculus. Information and Computation, 127(2):117-144, 15 June 1996. Abstract, References, etc. [BibTeX entry]

• Stephen Brookes. Full abstraction for a shared-variable parallel language. Information and Computation, 127(2):145-163, 15 June 1996. Abstract, References, etc. [BibTeX entry]

• André Joyal, Mogens Nielsen, and Glynn Winskel. Bisimulation from open maps. Information and Computation, 127(2):164-185, 15 June 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Marcelo P. Fiore. A coinduction principle for recursive data types based on bisimulation. Information and Computation, 127(2):186-198, 15 June 1996. Abstract, References, Citations, etc. [BibTeX entry]

Volume 128, Number 1, July 10, 1996

• Nancy Lynch and Frits Vaandrager. Forward and backward simulations, II: Timing-based systems. Information and Computation, 128(1):1-25, 10 July 1996. Abstract, References, and Citations. [BibTeX entry]

• Ian A. Mason, Scott F. Smith, and Carolyn L. Talcott. From operational semantics to domain theory. Information and Computation, 128(1):26-47, 10 July 1996. Abstract, References, and Citations. [BibTeX entry]

• Joe Kilian and Hava T. Siegelmann. The dynamic universality of sigmoidal neural networks. Information and Computation, 128(1):48-56, 10 July 1996. Abstract. [BibTeX entry]

• George Varghese and Nancy A. Lynch. A tradeoff between safety and liveness for randomized coordinated attack. Information and Computation, 128(1):57-71, 10 July 1996. Abstract and References. [BibTeX entry]

Volume 128, Number 2, August 1, 1996

• John Case, Sanjay Jain, and Arun Sharma. Machine induction without revolutionary changes in hypothesis size. Information and Computation, 128(2):73-86, 1 August 1996. Abstract and References. [BibTeX entry]

• Kathleen Romanik and Jeffrey Scott Vitter. Using Vapnik-Chervonenkis dimension to analyze the testing complexity of program segments. Information and Computation, 128(2):87-108, 1 August 1996. Abstract and References. [BibTeX entry]

• David Harel and Eli Singerman. More on nonregular PDL: Finite models and Fibonacci-like programs. Information and Computation, 128(2):109-118, 1 August 1996. Abstract and References. [BibTeX entry]

• Yenjo Han and Thomas Thierauf. Restricted information from nonadaptive queries to NP. Information and Computation, 128(2):119-125, 1 August 1996. Abstract and References. [BibTeX entry]

• Mark Changizi. Self-monitoring machines and an omega^omega hierarchy of loops. Information and Computation, 128(2):127-138, 1 August 1996. Abstract and References. [BibTeX entry]

Volume 129, Number 1, August 25, 1996

• Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 25 August 1996. Abstract, References, Citations, etc. [BibTeX entry]

• Birgit Jenner, Pierre McKenzie, and Denis Thérien. Logspace and logtime leaf languages. Information and Computation, 129(1):21-33, 25 August 1996. Abstract, References, and Citations. [BibTeX entry]

• Mads Dam. Model checking mobile processes. Information and Computation, 129(1):35-51, 25 August 1996. Abstract, References, and Citations. [BibTeX entry]

• Kalvis Aps{\=\i}tis, R\=usi\c{n}\v{s} Freivalds, and Carl H. Smith. On duality in learning and the selection of learning terms. Information and Computation, 129(1):53-62, 25 August 1996. Abstract, References, etc. [BibTeX entry]

• Svetlana Anoulova, Paul Fischer, Stefan Pölt, and Hans Ulrich Simon. Probably almost Bayes decisions. Information and Computation, 129(1):63-71, 25 August 1996. Abstract and References. [BibTeX entry]

Volume 129, Number 2, September 15, 1996

• Zhang Mingyi. A new research into default logic. Information and Computation, 129(2):73-85, 15 September 1996. Abstract and References. [BibTeX entry]

• Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, and Douglas R. Stinson. Visual cryptography for general access structures. Information and Computation, 129(2):86-106, 15 September 1996. Abstract, References, and Citations. [BibTeX entry]

• Luca Aceto and Anna Ingólfsdóttir. CPO models for compact GSOS languages. Information and Computation, 129(2):107-141, 15 September 1996. Abstract and References. [BibTeX entry]

Volume 130, Number 1, October 10, 1996

• Stephen Fenner, Lance Fortnow, and Lide Li. Gap-definability as a closure property. Information and Computation, 130(1):1-17, 10 October 1996. Abstract and References. [BibTeX entry]

• Sanjay Jain and Arun Sharma. Computational limits on team identification of languages. Information and Computation, 130(1):19-60, 10 October 1996. Abstract and References. [BibTeX entry]

• Thomas Wilke and Haiseung Yoo. Computing the Rabin index of a regular language of infinite words. Information and Computation, 130(1):61-70, 10 October 1996. Abstract, References, and Citations. [BibTeX entry]

• Parosh Aziz Abdulla and Bengt Jonsson. Undecidable verification problems for programs with unreliable channels. Information and Computation, 130(1):71-90, 10 October 1996. Abstract and References. [BibTeX entry]

• Carsten Damm and Markus Holzer. Inductive counting for width-restricted branching programs. Information and Computation, 130(1):91-99, 10 October 1996. Abstract, References, Citations, etc. [BibTeX entry]

Volume 130, Number 2, November 1, 1996

• Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, and Martin Tompa. Time-space tradeoffs for undirected graph traversal by graph automata. Information and Computation, 130(2):101-129, 1 November 1996. Abstract, References, and Citations. [BibTeX entry]

• Farn Wang. Parametric timing analysis for real-time systems. Information and Computation, 130(2):131-150, 1 November 1996. Abstract, References, etc. [BibTeX entry]

• Raffaele Giancarlo and Roberto Grossi. On the construction of classes of suffix trees for square matrices: Algorithms and applications. Information and Computation, 130(2):151-182, 1 November 1996. Abstract, References, and Citations. [BibTeX entry]

• Véronique Bruyère and Clelia De Felice. Any lifting of a trace coding is a word coding. Information and Computation, 130(2):183-193, 1 November 1996. Abstract and References. [BibTeX entry]

Volume 131, Number 1, November 25, 1996

• F. Ferrucci, G. Pacini, G. Satta, M. I. Sessa, G. Tortora, M. Tucci, and G. Vitiello. Symbol-relation grammars: A formalism for graphical languages. Information and Computation, 131(1):1-46, 25 November 1996. Abstract and References. [BibTeX entry]

• Lila Kari and Gabriel Thierrin. Contextual insertions/deletions and computability. Information and Computation, 131(1):47-61, 25 November 1996. Abstract and References. [BibTeX entry]

• Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation, 131(1):63-79, 25 November 1996. Abstract and References. [BibTeX entry]

• Claudia Bertram-Kretzberg and Thomas Hofmeister. Multiple product modulo arbitrary numbers. Information and Computation, 131(1):81-93, 25 November 1996. Abstract and References. [BibTeX entry]

Volume 131, Number 2, December 15, 1996

• Diana Rooß and Klaus W. Wagner. On the power of DNA-computing. Information and Computation, 131(2):95-109, 15 December 1996. Abstract and References. [BibTeX entry]

• Carlo Blundo, Alfredo De Santis, and Ugo Vaccaro. Randomness in distribution protocols. Information and Computation, 131(2):111-139, 15 December 1996. Abstract, References, and Citations. [BibTeX entry]

• Davide Sangiorgi. Bisimulation for higher-order process calculi. Information and Computation, 131(2):141-178, 15 December 1996. Abstract and References. [BibTeX entry]

• M. Agrawal and V. Arvind. A note on decision versus search for graph automorphism. Information and Computation, 131(2):179-189, 15 December 1996. Abstract and References. [BibTeX entry]

Shortcuts: