A zero-one law for logic with a fixed-point operator
dc.contributor.author | Blass, Andreas | en_US |
dc.contributor.author | Gurevich, Yuri | en_US |
dc.contributor.author | Kozen, Dexter | en_US |
dc.date.accessioned | 2006-04-07T18:56:56Z | |
dc.date.available | 2006-04-07T18:56:56Z | |
dc.date.issued | 1985 | en_US |
dc.identifier.citation | Blass, Andreas, Gurevich, Yuri, Kozen, Dexter (1985)."A zero-one law for logic with a fixed-point operator." Information and Control 67(1-3): 70-90. <http://hdl.handle.net/2027.42/25540> | en_US |
dc.identifier.uri | http://www.sciencedirect.com/science/article/B7MFM-4G30C9W-1D/2/a01d36a023a8f585cd209f883c13951c | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/25540 | |
dc.description.abstract | The logic obtained by adding the least-fixed-point operator to first-order logic was proposed as a query language by Aho and Ullman (in "Proc. 6th ACM Sympos. on Principles of Programming Languages," 1979, pp. 110-120) and has been studied, particularly in connection with finite models, by numerous authors. We extend to this logic, and to the logic containing the more powerful iterative-fixed-point operator, the zero-one law proved for first-order logic in (Glebskii, Kogan, Liogonki, and Talanov (1969), Kibernetika 2, 31-42; Fagin (1976), J. Symbolic Logic 41, 50-58). For any sentence [phi] of the extend logic, the proportion of models of [phi] among all structures with universe {1,2,..., n} approaches 0 or 1 as n tends to infinity. We also show that the problem of deciding, for any [phi], whether this proportion approaches 1 is complete for exponential time, if we consider only [phi]'s with a fixed finite vocabulary (or vocabularies of bounded arity) and complete for double-exponential time if [phi] is unrestricted. In addition, we establish some related results. | en_US |
dc.format.extent | 1154047 bytes | |
dc.format.extent | 3118 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | en_US |
dc.title | A zero-one law for logic with a fixed-point operator | en_US |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | en_US |
dc.subject.hlbsecondlevel | Science (General) | en_US |
dc.subject.hlbsecondlevel | Information and Library Science | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.subject.hlbtoplevel | Social Sciences | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109 USA | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109 USA | en_US |
dc.contributor.affiliationother | IBM Research, Yorktown Heights, New York 10598 USA | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/25540/1/0000082.pdf | en_US |
dc.identifier.source | Information and Control | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.