We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
An abstract is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)
References
REFERENCES
[1]
[1]Barendregt, H. P., van Eekelen, M. C. J. D., Glauert, J. R. W., Kennaway, J. R., Plasmeijer, M. J., and Sleep, M. R., Term graph rewriting, PARLE: Parallel Architectures and Languages Europe, Volume II, Lecture Notes in Computer Science, vol. 259, Springer-Verlag, Berlin, 1987, pp. 141–158.CrossRefGoogle Scholar
[2]
[2]Staples, J., Computation on graph-like expressions, Theoretical Computer Science, vol. 10 (1980), pp. 171–185.CrossRefGoogle Scholar
[3]
[3]Turner, D. A., A new implementation technique for applicative languages, Software-Practice and Experience, vol. 9 (1979), pp. 31–49.CrossRefGoogle Scholar
[1]
[1]Angluin, D. and Smith, C. H., Inductive inference: theory and methods, Computing Surveys, vol. 15 (1983), pp. 237–269.CrossRefGoogle Scholar
[2]
[2]Cherniavsky, J. C., Computer systems as scientific theories: a Popperian approach to testing, Proceedings of the fifth Pacific Northwest software quality conference, 1987, pp. 297–308.Google Scholar
[3]
[3]Cherniavsky, J. C., Statman, R., and Velauthapillai, M., Testing and inductive inference-abstract approaches, Technical report no. TR-5, Department of Computer Science, Georgetown University, Washington, D. C., 1987.Google Scholar
[4]
[4]Fass, L. F., Inference of skeletal automata, Technical report no. TR-2, Department of Computer Science, Georgetown University, Washington, D. C., 1984.Google Scholar
[5]
[5]Weyuker, E. J., Assessing test data adequacy through program inference, Transactions on Programming, Languages and Systems, vol. 5 (1983), pp. 641–655.CrossRefGoogle Scholar
[6]
[6]Weyuker, E. J., The evaluation of program-based software test data adequacy criteria, Communications of the Association for Computing Machinery, vol. 31 (1988), pp. 668–675.CrossRefGoogle Scholar
[1]
[1]Fenstad, J. E., General recursion theory—an axiomatic approach, Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
[2]
[2]Fitting, M., Enumeration operators and modular logic programming, Journal of Logic Programming, vol. 4 (1987), pp. 11–21.CrossRefGoogle Scholar
[3]
[3]Kleene, S. C., Countable functionals, Constructivity in mathematics (proceedings, Amsterdam, 1957; Heyting, A., editor), North-Holland, Amsterdam, 1959, pp. 81–100.Google Scholar
[4]
[4]Miller, D. A. and Nadathur, G., Higher-order logic programming, Third international conference on logic programming (proceedings, London, 1985), Lecture Notes in Computer Science, vol. 225Springer-Verlag, Berlin, 1986, pp. 448–462.CrossRefGoogle Scholar
[5]
[5]Moschovakis, Y. N., Axioms for computational theories—first draft, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 199–255.CrossRefGoogle Scholar
[6]
[6]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[1]
[1]Amir, A. and Gasarch, W. I., Polynomially terse sets (extended abstract), Structure in complexity theory (proceedings of the second annual conference, Ithaca, New York, 1987), IEEE Computer Society Press, Washington, D. C., 1987, pp. 22–27.Google Scholar
[2]
[2]Jockusch, C. G.Jr., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[1]
[1]Coquand, Thierry and Huet, Gérard, Constructions: a higher order proof system for mechanizing mathematics, EUROCAL '85, Vol. I, Lecture Notes in Computer Science, vol. 203, Springer-Verlag, Berlin, 1985, pp. 151–184.CrossRefGoogle Scholar
[2]
[2]Gentzen, Gerhard, Untersuchungen über das logische Schliessen, Mathematische Zeitschrift, vol. 39 (1934), pp. 176–218, 405–431.CrossRefGoogle Scholar
[3]
[3]Staff, Ora, Ulysses: a computer-security modeling environment, Proceedings of the eleventh national computer security conference, National Computer Security Center, 1988.Google Scholar
[4]
[4]Prawitz, Dag, Natural deduction, Almqvist & Wiksell, Stockholm, 1965.Google Scholar
Lachlan, A. H., The priority method for the construction of recursively enumerable sets, Cambridge summer school in mathematical logic, Lecture Notes in Mathematics, vol. 337, Springer-Verlag, Berlin, 1973, pp. 299–310.CrossRefGoogle Scholar
Jockusch, C. G.Jr., Genericity for recursively enumerable sets, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Mathematics, vol. 1141, Springer-Verlag, Berlin, 1985, pp. 203–232.CrossRefGoogle Scholar
Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[2]Paris, J. and Wilkie, A., On the scheme of induction for bounded arithmetic formulas, Annals of Pure and Applied Logic, vol. 35 (1987), pp. 205–303.Google Scholar
[3]
[3]Paris, J., Wilkie, A., and Woods, A., Provability of the pigeonhole principle and the existence of infinitely many primes, this Journal, vol. 53 (1988), pp. 1235–1244.Google Scholar
[4]
[4]Takeuti, G., Bounded arithmetic and truth definition, Annals of Pure and Applied Logic, vol. 39 (1988), pp. 75–104.CrossRefGoogle Scholar
Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
Kučera, A., On the use of diagonally nonrecursive functions, Logic Colloquium '87 (to appear).Google Scholar
[Mac87]
[Mac87]Mackworth, A. K., Constraint satisfaction, Encyclopedia of artificial intelligence (Shapiro, S. C. and Eckroth, D., editors), Vol. 1, Wiley, New York, 1987, pp. 205–211.Google Scholar
[LadMad882]
[LadMad88.2]Ladkin, P. B. and Maddux, R. D., On binary constraint networks, Technical Report KES.U.88.8, Kestrel Institute, Palo Alto, California, 1988.Google Scholar
[Tar41]
[Tar41]Tarski, A., On the calculus of relations, this Journal, vol. 6 (1941), pp. 73–89.Google Scholar
[1]
[1]Leblanc, H. and Roeper, P., Onrelativizing Kolmogorov's absolute probability functions (abstract), this Journal, vol. 53 (1988), pp. 1288–1289.Google Scholar
[2]
[2]Popper, K. R., The logic of scientific discovery, Hutchinson, London, and Basic Books, New York, 1959.Google Scholar
[Lei83]
[Lei83]Leivant, Daniel, Reasoning about functional programs and complexity classes associated with type disciplines, Twenty-fourth annual symposium on the foundations of computer science, IEEE Computer Society, Washington, D.C., 1983, pp. 460–469.Google Scholar
[Lei87]
[Lei87]Leivant, Daniel, Descriptive characterizations of computational complexity, Second annual conference on structure in complexity theory, IEEE Computer Society, Washington, D.C., 1987, pp. 203–217; revised version, to appear in the Journal of Computer and System Sciences.Google Scholar
[Schw76]
[Schw76]Schwichtenberg, Helmut, Definierbare Funktionen im Lambda-Kalkul mit Typen, Archit für Mathematische Logik undGrundlagenforschung, vol. 17 (1976), pp. 113–114.CrossRefGoogle Scholar
[1]
[1]Barwise, J. and Etchemendy, J., The Liar, Oxford University Press, Oxford, 1987.Google Scholar
[2]
[2]Hyttinen, T., Games and infinitary languages, Annates Academiae Scientiarum Fennicae Series A I Mathematica Dissertationes, No. 64 (1987).Google Scholar
[3]
[3]Väänänen, J., Set-theoretic definability of logics, Model-theoretic logics (Barwise, J. and Feferman, S., editors), Springer-Verlag, Berlin, 1985, pp. 599–643.Google Scholar
Ladner, R. E. [1977], Application of model theoretic games to discrete linear orders and finite automata, Information and Control, vol. 33 (1977), pp. 281–303.CrossRefGoogle Scholar
Moschovakis, Y. [1983], Abstract recursion as a foundation for the theory of algorithms, Computation and proof theory, Lecture Notes in Mathematics, vol. 1104, Springer-Verlag, Berlin, 1983, pp. 289–364.CrossRefGoogle Scholar
[1]
[1]Ash, C. J., Jockusch, C. G.Jr., and Knight, J. F., Jumps of orderings, Transactions of the American Mathematical Society (to appear).Google Scholar
[2]
[2]Kaplansky, I., Infinite Abelian groups, University of Michigan Press, Ann Arbor, Michigan, 1954.Google Scholar
[3]
[3]Richter, L. J., Degrees of structures, this Journal, vol. 46 (1981), pp. 723–731.Google Scholar
[4]
[4]Rogers, H.Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[1]
[1]Foreman, M., Potent axioms, Transactions of the American Mathematical Society, vol. 294 (1986), pp. 1–28.CrossRefGoogle Scholar
[2]
[2]Matsubara, Yo, Menas' conjecture and generic ultrapowers, Annals of Pure and Applied Logic, vol. 36 (1987), pp. 225–234.CrossRefGoogle Scholar
[1]
[1]Millar, T. S., Persistently finite theories with hyperarithmetic models, Transactions of the American Mathematical Society, vol. 278 (1983), pp. 91–99.CrossRefGoogle Scholar
[2]
[2]Millar, T. S., Decidable Ehrenfeucht theories, Recursion theory (Nerode, A. and Shore, R. A., editors), Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, 1985, pp. 311–321.CrossRefGoogle Scholar
[3]
[3]Peretyat'kin, M. G., On complete theories with a finite number of denumerable models, Algebra i Logika, vol. 12 (1973), pp. 550–576; English translation, Algebra and Logic, vol. 12 (1973), pp. 310–326.Google Scholar
[4]
[4]Reed, R. C., A decidable Ehrenfeucht theory with exactly two hyperarithmetic models, Ph.D. Thesis, University of Wisconsin, Madison, Wisconsin, 1986.Google Scholar
[1]
[1]Krol, M. D., A topological model for intuitionistic analysis with Kripke's scheme, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 24 (1978), pp. 427–436.CrossRefGoogle Scholar
[2]
[2]Moschovakis, J. R., A topological interpretation of second-order intuitionistic arithmetic, Compositio Mathematica, vol. 26 (1973), pp. 261–275.Google Scholar
[3]
[3]Scowcroft, P., A new model for intuitionistic analysis. Preliminary report, Abstracts of Papers Presented to the American Mathematical Society, vol. 9 (1988), p. 501 (abstract 88T-03-273).Google Scholar
[1]
[1]Coquand, Thierry and Huet, Gérard, The calculus of constructions, Information and Computation, vol. 76 (1988), pp. 95–120.CrossRefGoogle Scholar
[2]
[2]Coquand, Thierry and Huet, Gérard, Constructions: a higher order proof system for mechanizing mathematics, EUROCAL '85, Vol. 1, Lecture Notes in Computer Science, vol. 203, Springer-Verlag, Berlin, 1985, pp. 151–184.CrossRefGoogle Scholar
[3]
[3]Huet, Gérard, Formal structures for computation and deduction, Lecture notes, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1986.Google Scholar
[4]
[4]Huet, Gérard, Induction principles formalized in the calculus of constructions, TAPSOFT '87, Vol. 1, Lecture Notes in Computer Science, vol. 249, Springer-Verlag, Berlin, 1987, pp. 276–286.CrossRefGoogle Scholar
[5]
[5]Seldin, Jonathan P., A sequent calculus for type assignment, this Journal, vol. 42 (1977), pp. 1128.Google Scholar
[1]
[1]Martin-Löf, Per, On the meanings of the logical constants and the justification of the logical laws, Atti degli Incontri di Logica Matematica, Vol. 2 (Bernardi, C. and Pagli, P., editors), Dipartimento di Matematica, Università di Siena, Siena, 1985, pp. 203–281.Google Scholar
[2]
[2]Martin-Löf, Per, Truth of a proposition, evidence of a judgement, validity of a proof, Synthese, vol. 73 (1987), pp. 407–420.CrossRefGoogle Scholar
[1]Mayr, E. and Meyer, A., The complexity of the word problems for commutative semigroups and polynomial ideals, Advances in Mathematics, vol. 46 (1982), pp. 305–329.CrossRefGoogle Scholar
[2]
[2]McAloon, K., Petri nets and large finite sets, Theoretical Computer Science, vol. 32 (1984), pp. 173–183.CrossRefGoogle Scholar
[1]
[1]Brown, D. K. and Simpson, S. G., Which set existence axioms are needed to prove the separable Hahn-Banach theorem?Annals of Pure and Applied Logic, vol. 31 (1986), pp. 123–144.CrossRefGoogle Scholar
[2]
[2]Jockusch, C., classes and Boolean combinations of recursively enumerable sets, this Journal, vol. 39 (1974), pp. 95–96.Google Scholar
[3]
[3]Simpson, S. G., Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?, this Journal, vol. 49 (1984), pp. 783–802.Google Scholar
[4]
[4]Yu, Xiaokang, Measure theory in weak systems of second order arithmetic, Ph.D. thesis, Pennsylvania State University, University Park, Pennsylvania, 1987.Google Scholar