Information and Computation -- 1998

Volume 140, Number 1, January 10, 1998

• Daniel Leivant. Preface. Information and Computation, 140(1):1, 10 January 1998. Special Issue from the workshop on Logic and Computational Complexity (LCC), Indiana University, October 1994. [BibTeX entry]

• Douglas Cenzer and Jeffrey B. Remmel. Complexity and categoricity. Information and Computation, 140(1):2-25, 10 January 1998. Abstract and References. [BibTeX entry]

• Erich Grädel and Yuri Gurevich. Metafinite model theory. Information and Computation, 140(1):26-81, 10 January 1998. Abstract and References. [BibTeX entry]

• Jan Krají\v{c}ek and Pavel Pudlák. Some consequences of cryptographical conjectures for S^1_2 and EF. Information and Computation, 140(1):82-94, 10 January 1998. Abstract and References. [BibTeX entry]

Volume 140, Number 2, February 1, 1998

• Mads Dam. Proving properties of dynamic process networks. Information and Computation, 140(2):95-114, 1 February 1998. Abstract, References, etc. [BibTeX entry]

• Ron van der Meyden. Common knowledge and update in finite environments. Information and Computation, 140(2):115-157, 1 February 1998. Abstract and References. [BibTeX entry]

• Steven H. Low and Nicholas F. Maxemchuk. A collusion problem and its solution. Information and Computation, 140(2):158-182, 1 February 1998. Abstract and References. [BibTeX entry]

• Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, and Tami Tamir. On chromatic sums and distributed resource allocation. Information and Computation, 140(2):183-202, 1 February 1998. Abstract, References, and Citations. [BibTeX entry]

• Aaron Feigelson and Lisa Hellerstein. Conjunctions of unate DNF formulas: Learning and structure. Information and Computation, 140(2):203-228, 1 February 1998. Abstract and References. [BibTeX entry]

• Anne Brüggemann-Klein and Derick Wood. One-unambiguous regular languages. Information and Computation, 140(2):229-253, 1 February 1998. Abstract and References. [BibTeX entry]

• Endre Boros, Toshihide Ibaraki, and Kazuhisa Makino. Error-free and best-fit extensions of partially defined Boolean functions. Information and Computation, 140(2):254-283, 1 February 1998. Abstract, References, and Citations. [BibTeX entry]

Volume 141, Number 1, February 25, 1998

• Gerhard Buntrock and Friedrich Otto. Growing context-sensitive languages and Church-Rosser languages. Information and Computation, 141(1):1-36, 25 February 1998. Abstract, References, etc. [BibTeX entry]

• Kazuo Iwama and Chuzo Iwamoto. A canonical form of vector machines. Information and Computation, 141(1):37-65, 25 February 1998. Abstract and References. [BibTeX entry]

• Wolfgang Maass and Manfred K. Warmuth. Efficient learning with virtual threshold gates. Information and Computation, 141(1):66-83, 25 February 1998. Abstract and References. [BibTeX entry]

Volume 141, Number 2, March 15, 1998

• Javed A. Aslam and Scott E. Decatur. General bounds on statistical query learning and PAC learning with noise via hypothesis boosting. Information and Computation, 141(2):85-118, 15 March 1998. Abstract, References, and Citations. [BibTeX entry]

• Roberto Segala, Rainer Gawlick, Jørgen Søgaard-Andersen, and Nancy Lynch. Liveness in timed and untimed systems. Information and Computation, 141(2):119-171, 15 March 1998. Abstract and References. [BibTeX entry]

• Marc Bezem, Jan Willem Klop, and Vincent van Oostrom. Diagram techniques for confluence. Information and Computation, 141(2):172-204, 15 March 1998. Abstract and References. [BibTeX entry]

Volume 142, Number 1, April 10, 1998

• Jean-Pierre Jouannaud. Preface. Information and Computation, 142(1):1, 10 April 1998. [BibTeX entry]

• Dexter Kozen. Set constraints and logic programming. Information and Computation, 142(1):2-25, 10 April 1998. Abstract, References, and Citations. [BibTeX entry]

• Spiro Michaylov. Repeated redundant inequalities in constraint logic programming. Information and Computation, 142(1):26-39, 10 April 1998. Abstract and References. [BibTeX entry]

• Witold Charatonik. Set constraints in some equational theories. Information and Computation, 142(1):40-75, 10 April 1998. Abstract and References. [BibTeX entry]

• Rolf Backofen and Ralf Treinen. How to win a game with features. Information and Computation, 142(1):76-101, 10 April 1998. Abstract and References. [BibTeX entry]

• Christopher Lynch. Local simplification. Information and Computation, 142(1):102-126, 10 April 1998. Abstract and References. [BibTeX entry]

Volume 142, Number 2, May 1, 1998

• Viliam Geffert. Bridging across the log(n) space frontier. Information and Computation, 142(2):127-158, 1 May 1998. Abstract, References, etc. [BibTeX entry]

• Mikkel Thorup. All structured programs have small tree-width and good register allocation. Information and Computation, 142(2):159-181, 1 May 1998. Abstract and References. [BibTeX entry]

• Anne Brüggemann-Klein and Derick Wood. One-unambiguous regular languages. Information and Computation, 142(2):182-206, 1 May 1998. Abstract and References. [BibTeX entry]

• Helmut Veith. Succinct representation, leaf languages, and projection reductions. Information and Computation, 142(2):207-236, 1 May 1998. Abstract, References, etc. [BibTeX entry]

• Yves Lafont. Erratum to ``{I}nteraction combinators'' Information and Computation, 142(2):237, 1 May 1998. References. [BibTeX entry]

Volume 143, Number 1, May 25, 1998

• Paula Severi. Type inference for pure type systems. Information and Computation, 143(1):1-23, 25 May 1998. Abstract and References. [BibTeX entry]

• Beate Bollig and Ingo Wegener. Completeness and non-completeness results with respect to read-once projections. Information and Computation, 143(1):24-33, 25 May 1998. Abstract and References. [BibTeX entry]

• Davide Sangiorgi. An interpretation of typed objects into typed pi-calculus. Information and Computation, 143(1):34-73, 25 May 1998. Abstract and References. [BibTeX entry]

• Franco Montagna. Investigations on measure-one identification of classes of languages. Information and Computation, 143(1):74-107, 25 May 1998. Abstract and References. [BibTeX entry]

Volume 143, Number 2, June 15, 1998

• Daniel Leivant. Preface. Information and Computation, 143(2):109, 15 June 1998. Part 2 of a Special Issue from the workshop on Logic and Computational Complexity (LCC), Indiana University, October 1994. [BibTeX entry]

• Serge Abiteboul, Christos H. Papadimitriou, and V. Vianu. Reflective relational machines. Information and Computation, 143(2):110-136, 15 June 1998. Abstract, References, etc. [BibTeX entry]

• Robert L. Constable. A note on complexity measures for inductive classes in constructive type theory. Information and Computation, 143(2):137-153, 15 June 1998. Abstract and References. [BibTeX entry]

• Anuj Dawar. A restricted second order logic for finite structures. Information and Computation, 143(2):154-174, 15 June 1998. Abstract and References. [BibTeX entry]

• Jean-Yves Girard. Light linear logic. Information and Computation, 143(2):175-204, 15 June 1998. Abstract and References. [BibTeX entry]

• Hajime Ishihara, Bakhadyr Khoussainov, and Anil Nerode. Computable Kripke models and intermediate logics. Information and Computation, 143(2):205-230, 15 June 1998. Abstract and References. [BibTeX entry]

• Steven Lindell. A constant-space sequential model of computation for first-order logic. Information and Computation, 143(2):231-250, 15 June 1998. Abstract and References. [BibTeX entry]

Volume 144, Number 1, July 10, 1998

• Amihood Amir, Gary Benson, and Martin Farach. Optimal parallel two dimensional text searching on a CREW PRAM. Information and Computation, 144(1):1-17, 10 July 1998. Abstract and References. [BibTeX entry]

• Jaap-Henk Hoepman. Self-stabilizing ring-orientation using constant space. Information and Computation, 144(1):18-39, 10 July 1998. Abstract and References. [BibTeX entry]

• F. Gire and H. K. Hoang. An extension of fixpoint logic with a symmetry-based choice construct. Information and Computation, 144(1):40-65, 10 July 1998. Abstract and References. [BibTeX entry]

• Moti Frances and Ami Litman. Optimal mistake bound learning is hard. Information and Computation, 144(1):66-82, 10 July 1998. Abstract and References. [BibTeX entry]

Volume 144, Number 2, August 1, 1998

• Marco Bernardo, Lorenzo Donatiello, and Roberto Gorrieri. A formal approach to the integration of performance aspects in the modeling and analysis of concurrent systems. Information and Computation, 144(2):83-154, 1 August 1998. Abstract and References. [BibTeX entry]

• Thomas Eiter, Toshihide Ibaraki, and Kazuhisa Makino. Double Horn functions. Information and Computation, 144(2):155-190, 1 August 1998. Abstract, References, and Citations. [BibTeX entry]

Volume 145, Number 1, August 25, 1998

• Frank Drewes and Joost Engelfriet. Decidability of the finiteness of ranges of tree transductions. Information and Computation, 145(1):1-50, 25 August 1998. Abstract and References. [BibTeX entry]

• Juha Honkala. On number systems with finite degree of ambiguity. Information and Computation, 145(1):51-63, 25 August 1998. Abstract and References. [BibTeX entry]

• Chrysafis Hartonas and Matthew Hennessy. Full abstractness for a functional/concurrent language with higher-order value-passing. Information and Computation, 145(1):64-106, 25 August 1998. Abstract and References. [BibTeX entry]

Volume 145, Number 2, September 15, 1998

• Claudio Hermida and Bart Jacobs. Structural induction and coinduction in a fibrational setting. Information and Computation, 145(2):107-152, 15 September 1998. Abstract and References. [BibTeX entry]

• Roberto Giacobazzi and Francesco Ranzato. Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements. Information and Computation, 145(2):153-190, 15 September 1998. Abstract, References, and Citations. [BibTeX entry]

• Flavio Corradini. On performance congruences for process algebras. Information and Computation, 145(2):191-230, 15 September 1998. Abstract and References. [BibTeX entry]

Volume 146, Number 1, October 10, 1998

• Carlo Blundo, Alfredo De Santis, Amir Herzberg, Shay Kutten, Ugo Vaccaro, and Moti Yung. Perfectly secure key distribution for dynamic conferences. Information and Computation, 146(1):1-23, 10 October 1998. Abstract and References. [BibTeX entry]

• Wan Fokkink and Chris Verhoef. A conservative look at operational semantics with variable binding. Information and Computation, 146(1):24-54, 10 October 1998. Abstract and References. [BibTeX entry]

• Alexis Maciel and Denis Thérien. Threshold circuits of small majority-depth. Information and Computation, 146(1):55-83, 10 October 1998. Abstract, References, and Citations. [BibTeX entry]

Volume 146, Number 2, November 1, 1998

• Paolo Ferragina and Fabrizio Luccio. Dynamic dictionary matching in external memory. Information and Computation, 146(2):85-99, 1 November 1998. Abstract and References. [BibTeX entry]

• G. W. Hamilton. Usage counting analysis for lazy functional languages. Information and Computation, 146(2):100-137, 1 November 1998. Abstract and References. [BibTeX entry]

• Sven-Olof Nyström and Bengt Jonsson. A fully abstract semantics for concurrent constraint programming. Information and Computation, 146(2):138-180, 1 November 1998. Abstract and References. [BibTeX entry]

Volume 147, Number 1, November 25, 1998

• Robert Nieuwenhuis. Decidability and complexity analysis by basic paramodulation. Information and Computation, 147(1):1-21, 25 November 1998. Abstract, References, etc. [BibTeX entry]

• Luca Cabibbo. The expressive power of stratified logic programs with value invention. Information and Computation, 147(1):22-56, 25 November 1998. Abstract, References, etc. [BibTeX entry]

• Michael Benedikt, Timothy Griffin, and Leonid Libkin. Verifiable properties of database transactions. Information and Computation, 147(1):57-88, 25 November 1998. Abstract and References. [BibTeX entry]

• Nader H. Bshouty, Sally A. Goldman, and H. David Mathias. Noise-tolerant parallel learning of geometric concepts. Information and Computation, 147(1):89-110, 25 November 1998. Abstract and References. [BibTeX entry]

Volume 147, Number 2, December 15, 1998

• Sebastian Maneth. The generating power of total deterministic tree transducers. Information and Computation, 147(2):111-144, 15 December 1998. Abstract and References. [BibTeX entry]

• C. Lautemann, T. Schwentick, and I. A. Stewart. Positive versions of polynomial time. Information and Computation, 147(2):145-170, 15 December 1998. Abstract and References. [BibTeX entry]

• Maria Paola Bonacina and Jieh Hsiang. On the modelling of search in theorem proving -- towards a theory of strategy analysis. Information and Computation, 147(2):171-208, 15 December 1998. Abstract and References. [BibTeX entry]

• Stephen Ponzio. The combinatorics of effective resistances and resistive inverses. Information and Computation, 147(2):209-223, 15 December 1998. Abstract and References. [BibTeX entry]

Shortcuts: