Switch to: References

Citations of:

Fluted formulas and the limits of decidability

William C. Purdy

Journal of Symbolic Logic 61 (2):608-620 (1996)

Add citations

You must login to add citations.

The fluted fragment with transitive relations.Ian Pratt-Hartmann & Lidia Tendera - 2022 - Annals of Pure and Applied Logic 173 (1):103042.details The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, (...) Download Export citation Bookmark
More Fragments of Language.Ian Pratt-Hartmann & Allan Third - 2006 - Notre Dame Journal of Formal Logic 47 (2):151-177.details By a fragment of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language and equipped with a semantics commanding the general assent of its native speakers. By the semantic complexity of such a fragment, we understand the computational complexity of deciding whether any given set of sentences in that fragment represents a logically possible situation. In earlier papers by the first author, the semantic complexity of various fragments of English involving at most (...) Download Export citation Bookmark 5 citations
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.details Fluted logic is the restriction of pure predicate logic to formulas in which variables play no essential role. Although fluted logic is significantly weaker than pure predicate logic, it is of interest because it seems closely to parallel natural logic, the logic that is conducted in natural language. It has been known since 1969 that if conjunction in fluted formulas is restricted to subformulas of equal arity, satisfiability is decidable. However, the decidability of sublogics lying between this restricted (homogeneous) fluted (...) Download Export citation Bookmark 2 citations
Inexpressiveness of First-Order Fragments.William C. Purdy - 2006 - Australasian Journal of Logic 4 (5):1-12.details It is well-known that first-order logic is semi-decidable. Therefore, first-order logic is less than ideal for computational purposes (computer science, knowledge engineering). Certain fragments of first-order logic are of interest because they are decidable. But decidability is gained at the cost of expressiveness. The objective of this paper is to investigate inexpressiveness of fragments that have received much attention. Download Export citation Bookmark 1 citation
Axiomatizing the monodic fragment of first-order temporal logic.Frank Wolter & Michael Zakharyaschev - 2002 - Annals of Pure and Applied Logic 118 (1-2):133-145.details It is known that even seemingly small fragments of the first-order temporal logic over the natural numbers are not recursively enumerable. In this paper we show that the monodic fragment is an exception by constructing its finite Hilbert-style axiomatization. We also show that the monodic fragment with equality is not recursively axiomatizable. Download Export citation Bookmark 11 citations

1