Journal of the ACM Bibliography

Selected papers that cite this one

• Ganesh Baliga and John Case. Learnability: Admissible, co-finite, and hypersimple languages. Journal of Computer and System Sciences, 53(1):26-32, August 1996.

• Ganesh Baliga, John Case, and Sanjay Jain. The synthesis of language learners. Accepted for publication in Information and Computation. Final manuscript received for publication June 25, 1998.

• Ganesh Baliga, John Case, and Sanjay Jain. Language learning with some negative information. Journal of Computer and System Sciences, 51(2):273-285, October 1995.

• Ganesh Baliga, John Case, Sanjay Jain, and Mandayam Suraj. Machine learning of higher-order programs. The Journal of Symbolic Logic, 59(2):486-500, June 1994.

• Ganesh Baliga, Sanjay Jain, and Arun Sharma. Learning from multiple sources of inaccurate data. SIAM Journal on Computing, 26(4):961-990, August 1997.

• Leonard J. Bass. A note on the intersection of complexity classes of functions. SIAM Journal on Computing, 1(4):288-289, December 1972.

• Leonard Bass and Paul Young. Ordinal hierarchies and naming complexity classes. Journal of the ACM, 20(4):668-686, October 1973.

• Sanat K. Basu. On classes of computable functions. In Conference Record of ACM Symposium on Theory of Computing, pages 55-59, Marina del Rey, California, 5-7 May 1969.

• Victor L. Bennison and Robert I. Soare. Some lowness properties and computational complexity sequences. Theoretical Computer Science, 6(3):233-254, June 1978.

• Manuel Blum. On effective procedures for speeding up algorithms. In Conference Record of ACM Symposium on Theory of Computing, pages 43-53, Marina del Rey, California, 5-7 May 1969.

• Manuel Blum. On the size of machines. Information and Control, 11(3):257-265, September 1967.

• Manuel Blum. On effective procedures for speeding up algorithms. Journal of the ACM, 18(2):290-305, April 1971.

• P. van Emde Boas. Some applications of the McCreight-Meyer algorithm in abstract complexity theory. Theoretical Computer Science, 7(1):79-98, August 1978.

• A. Borodin. Computational complexity and the existence of complexity gaps. Journal of the ACM, 19(1):158-174, January 1972.

• A. Borodin. Complexity classes of recursive functions and the existence of complexity gaps. In Conference Record of ACM Symposium on Theory of Computing, pages 67-78, Marina del Rey, California, 5-7 May 1969.

• John Case. Pseudo-extending computable functions. Information and Control, 56(1/2):100-111, January/February 1983.

• John Case, Sanjay Jain, Steffen Lange, and Thomas Zeugmann. Incremental concept learning for bounded data mining. Accepted for publication in Information and Computation. Final manuscript received for publication November 6, 1998.

• John Case, Sanjay Jain, and Arun Sharma. Anomalous learning helps succinctness. Theoretical Computer Science, 164(1-2):13-28, 10 September 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.

• Gregory J. Chaitin. On the simplicity and speed of programs for computing infinite sets of natural numbers. Journal of the ACM, 16(3):407-422, July 1969.

• Keh-Jiann Chen. Tradeoffs in the inductive inference of nearly minimal size programs. Information and Control, 52(1):68-86, January 1982.

• Robert L. Constable. The operator gap. Journal of the ACM, 19(1):175-183, January 1972.

• Robert L. Constable and Allan B. Borodin. Subrecursive programming languages, part I: Efficiency and program structure. Journal of the ACM, 19(3):526-568, July 1972.

• Robert P. Daley. An example of information and computation resource trade-off. Journal of the ACM, 20(4):687-695, October 1973.

• Robert P. Daley. Busy beaver sets: Characterizations and applications. Information and Control, 52(1):52-67, January 1982.

• Robert P. Daley and Carl H. Smith. On the complexity of inductive inference. Information and Control, 69(1-3):12-40, April/May/June 1986.

• Anna-Maria Emde and Britta Schinzel. Aggregating inductive expertise on partial recursive functions. Information and Computation, 96(2):139-167, February 1992.

• Stephen A. Fenner. Almost weakly 2-generic sets. The Journal of Symbolic Logic, 59(3):868-887, September 1994.

• Rusins Freivalds and Sanjay Jain. Kolmogorov numberings and minimal identification. Theoretical Computer Science, 188(1-2):175-194, 30 November 1997.

• Mark Fulk and Sanjay Jain. Learning in the presence of inaccurate information. Theoretical Computer Science, 161(1-2):235-261, 15 July 1996.

• Mark Fulk and Sanjay Jain. Approximate inference and scientific method. Information and Computation, 114(2):179-191, 1 November 1994.

• John Gill and Manuel Blum. On almost everywhere complex recursive functions. Journal of the ACM, 21(3):425-435, July 1974.

• J. Hartmanis. On the complexity of undecidable problems in automata theory. Journal of the ACM, 16(1):160-167, January 1969.

• J. Hartmanis and J. E. Hopcroft. An overview of the theory of computational complexity. Journal of the ACM, 18(3):444-475, July 1971.

• Sanjay Jain. Program synthesis in the presence of infinite number of inaccuracies. Journal of Computer and System Sciences, 53(3):583-591, December 1996.

• Sanjay Jain and Arun Sharma. On aggregating teams of learning machines. Theoretical Computer Science, 137(1):85-108, 9 January 1995.

• Sanjay Jain and Arun Sharma. The structure of intrinsic complexity of learning. The Journal of Symbolic Logic, 62(4):1187-1201, December 1997.

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

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

• Sanjay Jain and Arun Sharma. The intrinsic complexity of language identification. Journal of Computer and System Sciences, 52(3):393-402, June 1996.

• S. Jain and A. Sharma. Prudence in vacillatory language identification. Mathematical Systems Theory, 28(3):267-279, May/June 1995.

• Sanjay Jain and Arun Sharma. Learning with the knowledge of an upper bound on program size. Information and Computation, 102(1):118-166, January 1993.

• Sanjay Jain and Arun Sharma. Learning in the presence of partial explanations. Information and Computation, 95(2):162-191, December 1991.

• Sanjay Jain, Arun Sharma, and Mahendran Velauthapillai. Finite identification of functions by teams with success ratio 1/2 and above. Information and Computation, 121(2):201-213, September 1995.

• Marek Karpinski and Rutger Verbeek. There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator. Information and Control, 67(1-3):158-162, October/November/December 1985.

• L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes. Journal of the ACM, 19(2):296-308, April 1972.

• Steffen Lange and Thomas Zeugmann. Incremental learning from positive data. Journal of Computer and System Sciences, 53(1):88-103, August 1996.

• Leonid A. Levin. Computational complexity of functions. Theoretical Computer Science, 157(2):267-271, 5 May 1996.

• E. M. McCreight and A. R. Meyer. Classes of computable functions defined by bounds on computation: Preliminary report. In Conference Record of ACM Symposium on Theory of Computing, pages 79-88, Marina del Rey, California, 5-7 May 1969.

• Léa Meyer. Probabilistic language learning under monotonicity constraints. Theoretical Computer Science, 185(1):81-128, 10 October 1997.

• Albert R. Meyer. Program size in restricted programming languages. Information and Control, 21(4):382-394, November 1972.

• Eliana Minicozzi. Some natural properties of strong-identification in inductive inference. Theoretical Computer Science, 2(3):345-360, September 1976.

• Robert Moll. An operator embedding theorem for complexity classes of recursive functions. Theoretical Computer Science, 1(3):193-198, February 1976.

• David Pager. On the efficiency of algorithms. Journal of the ACM, 17(4):708-714, October 1970.

• Kenneth W. Regan. Diagonalization, uniformity, and fixed-point theorems. Information and Computation, 98(1):1-40, May 1992.

• Kenneth W. Regan. Linear time and memory-efficient computation. SIAM Journal on Computing, 25(1):133-168, February 1996.

• Joel I. Seiferas and Albert R. Meyer. Characterizations of realizable space complexities. Annals of Pure and Applied Logic, 73(2):171-190, 1 June 1995.

• Robert I. Soare. Computational complexity of recursively enumerable sets. Information and Control, 52(1):8-18, January 1982.

• R. Verbeek and K. Weihrauch. Data representation and computational complexity. Theoretical Computer Science, 7(1):99-116, August 1978.

• David G. Willis. Computational complexity and probability constructions. Journal of the ACM, 17(2):241-259, April 1970.

• Paul R. Young. Toward a theory of enumerations. Journal of the ACM, 16(2):328-348, April 1969.

• Paul R. Young. Speed-ups by changing the order in which sets are enumerated (preliminary version). In Conference Record of ACM Symposium on Theory of Computing, pages 89-92, Marina del Rey, California, 5-7 May 1969.

Selected references

• J. Hartmanis and R. E. Stearns. Computational complexity of recursive sequences. In Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pages 82-90, Princeton, New Jersey, 11-13 November 1964. IEEE.

Shortcuts: