Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T03:23:19.603Z Has data issue: false hasContentIssue false
  • English
  • Français

The Logic of Choice

Published online by Cambridge University Press:  12 March 2014

Andreas Blass  and
Yuri Gurevich
Andreas Blass
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Mi 48109-1109, E-mail: [email protected]
Yuri Gurevich
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052 (on leave of absence from)Department of Eecs, University of Michigan, Ann Arbor, Michigan E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 3 , September 2000 , pp. 1264 - 1310
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

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

Abiteboul, Serge, Simon, Eric, and Vianu, Victor [1990], Non-deterministic languages to express deterministic transformations, Proceedings of ACM symposium on principles of database systems.Google Scholar
Abiteboul, Serge and Vianu, Victor [1991], Nondeterminism in logic-based languages, Annals of Mathematics and Artificial Intelligence, vol. 3, pp. 151–186.CrossRefGoogle Scholar
Asm [∞], ASM web site, the Michigan web site on abstract state machines, http://www.eecs.umich.edu/gasm/, maintained by James K. Huggins..Google Scholar
Börger, Egon, Grädel, Erich, and Gurevich, Yuri [1996], The classical decision problem, Perspectives in Mathematical Logic, Springer Verlag.Google Scholar
Caicedo, Xavier [1995], Hilbert's ε-symbol in the presence of generalized quantifiers, Quantifiers: Logics, models and computation, volume II (Krynicki, M.et al., editors), Kluwer Publishers, pp. 63–78.Google Scholar
Del Castillo, Giuseppe, Gurevich, Yuri, and Stroetmann, Karl [1998], Typed abstract state machines, ASM Web Site.Google Scholar
Church, Alonzo [1936], An unsohable problem of elementary number theory, American Journal of Mathematics, vol. 58, pp. 345–363, [Davis 1965, pages 88–107].CrossRefGoogle Scholar
Davis, Martin [1965], The undecidable: Basic papers on undecidable propositions, unsohable problems and computable functions, Raven Press, New York.Google Scholar
Ebbinghaus, Heinz-Dieter and Flum, Jörg [1995], Finite model theory, Springer.Google Scholar
Fagin, Ron [1974], Generalized first-order spectra and polynomial time recognizable sets, Complexity of computation (Karp, R.M., editor), SIAM-AMS Proceedings, vol. 7, pp. 43–73.Google Scholar
Garey, Michael R. and Johnson, David S. [1979], Computers and intractability: a guide to the theory ofNP completeness, Freeman.Google Scholar
Greenlaw, Raymond, Hoover, H. James, and Ruzzo, Walter L. [1995], Limits to parallel computation: P-completeness theory, Oxford University Press.CrossRefGoogle Scholar
Gurevich, Yuri [1984], Toward logic tailored for computational complexity, Computation and proof theory (Logic Colloquium 1983) (Richter, M.et al., editors), Lecture Notes in Mathematics, vol. 1104, Springer Verlag, pp. 175–216.Google Scholar
Gurevich, Yuri [1988], Logic and the challenge of computer science, Current trends in theoretical computer science (Börger, E., editor), Computer Science Press, pp. 1–57.Google Scholar
Gurevich, Yuri [1991], Evolving algebras: An attempt to discover semantics, Bulletin of European Association for Theoretical Computer Science, vol. 43, pp. 264–284, A slightly revised version appeared in G. Rozenberg and A. Salomaa, editors, “Current Trends in Theoretical Computer Science”, World Scientific, 1993, 266–292.Google Scholar
Gurevich, Yuri [1995], Evolving algebra 1993: Lipari guide, Specification and validation methods (Börger, E., editor), Oxford University Press, See also “May 1997 Draft of the ASM Guide”, Technical Report CSE-TR-336-97, EECS Department, University of Michigan, 1997. Found at http://www.eecs.umich.edu/gasm/, pp. 9–36.Google Scholar
Gurevich, Yuri [1997], A guide to abstract state machines, unpublished notes.Google Scholar
Hilbert, David and Bernays, Paul [1939], Grundlagen der Mathematik, Volume 2, Springer Verlag.Google Scholar
Kleene, Stephen Cole [1952], Introduction to metamathematics, D. Van Nostrand, New York, reprinted by Wolters-Noordhoff, Groningen and North-Holland, Amsterdam in 1971.Google Scholar
Leisenring, A. C. [1969], Mathematical logic and Hubert's ε-symbol, Macdonald Technical and Scientific, London.Google Scholar
Moschovakis, Yiannis N. [1974], Elementary induction on abstract structures, North-Holland, Amsterdam.Google Scholar
Moschovakis, Yiannis N. [1980], Descriptive set theory, North Holland, Amsterdam.Google Scholar
Otto, Martin [1998], Epsilon-logic is more expressive than first-order logic over finite structures, to appear.Google Scholar
Päppinghaus, Peter and Wirsing, Martin [1983], Nondeterministic three-valued logic: Isotonic and guarded truth-functions, Studia Logica, vol. XLII.1, pp. 1–22.Google Scholar
Rescher, Nicholas [1969], Many-valued logics, McGraw-Hill, New York.Google Scholar
Trakhtenbrot, Boris A. [1950], Impossibility of an algorithm for the decision problem on finite classes, Doklady Akad. Nauk, vol. 70, pp. 569–572.Google Scholar
Turing, Alan M. [1936], On computable numbers, with an application to the Entscheidungsproblem, Proceedings of London Mathematical Society, vol. 2, no. 42, pp. 230–236, and no. 43 (1936), 544–546. [Davis 1965, pages, 115–153.].Google Scholar