1,721,072 research outputs found
Decidability of the Logic of the Reflexive Sub-interval Relation over Finite Linear Orders
Get PDFAn interval temporal logic is a propositional, multimodal logic interpreted over interval structures of partial orders. The semantics of each modal operator are given in the standard way with respect to one of the natural accessibility relations defined on such interval structures. In this paper, we consider the modal operators based on the (reflexive) subinterval relation and the (reflexive) super-interval relation. We show that the satisfiability problems for the interval temporal logics featuring either or both of these modalities, interpreted over interval structures of finite linear orders, are all PSPACEcomplete. These results fill a gap in the known complexity results for interval temporal logics
What Is Spatial Logic?
Get PDFBy a spatial logic, we understand any formal language interpreted over a class of structures featuring geometrical entities and relations, broadly construed. The formal language in question may employ any logical syntax: that of first-order logic, or some fragment of first-order logic, or perhaps higher-order logic. The structures over which it is interpreted may inhabit any class of geometrical ‘spaces’: topological spaces, affine spaces, metric spaces, or perhaps a single space such a the projective plane or Euclidean 3-space. And the non-logical primitives of the language may be interpreted as any geometrical properties or relations defined over the relevant domains: topological connectedness of regions, parallelism of lines, or perhaps equidistance of two points from a third. What all these logics have in common is that the operative notion of validity depends on the underlying geometry of the structures over which their distinctively spatial primitives are interpreted. Spatial logic, then, is simply the study of the family of spatial logics, so conceived. An analogy will help elucidate this rather austere-looking definition. From our stance, spatial logic parallels the more established area of temporal logic. A temporal logic is a formal language interpreted over some class of structures based on frameworks of temporal relations, broadly construed. The language in question, though usually some modal fragment of first- or higher-order logic, may in principle employ any logical syntax; the objects over which that syntax is interpreted may include points, paths, or extended intervals over any variet
More fragments of language
No full textBy 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 transitive verbs was investigated. The present paper considers various fragments of English involving ditransitive verbs and determines their semantic complexity. © 2006 University of Notre Dame
The Syllogistic with Unity
Get PDFWe extend the language of the classical syllogisms with the sentence-forms
"At most 1 p is a q" and "More than 1 p is a q". We show that the resulting
logic does not admit a finite set of syllogism-like rules whose associated
derivation relation is sound and complete, even when reductio ad absurdum is
allowed
Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
Get PDFWe show that the finite satisfiability problem for the guarded two-variable
fragment with counting quantifiers is in EXPTIME. The method employed also
yields a simple proof of a result recently obtained by Y. Kazakov, that the
satisfiability problem for the guarded two-variable fragment with counting
quantifiers is in EXPTIME.Comment: 20 pages, 3 figure
Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
Get PDFoai:arXiv.org:0806.1636The data-complexity of both satisfiability and finite satisfiability for the
two-variable fragment with counting is NP-complete; the data-complexity of both
query-answering and finite query-answering for the two-variable guarded
fragment with counting is co-NP-complete
Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
Get PDFWe show that the satisfiability and finite satisfiability problems for the
two-variable fragment of first-order logic with counting quantifiers are both
in NEXPTIME, even when counting quantifiers are coded succinctly.Comment: 24 pages, 1 pstex_t figur
The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
Get PDFWe consider the two-variable fragment of first-order logic with one
distinguished binary predicate constrained to be interpreted as a transitive
relation. The finite satisfiability problem for this logic is shown to be
decidable, in triply exponential non-deterministic time. The complexity falls
to doubly exponential non-deterministic time if the distinguished binary
predicate is constrained to be interpreted as a partial order
Walking on Words
Get PDFAny function f with domain {1, … , m} and co-domain {1, … , n} induces a natural map from words of length n to those of length m: the ith letter of the output word (1 ≤ i ≤ m) is given by the f(i)th letter of the input word. We study this map in the case where f is a surjection satisfying the condition |f(i+1)-f(i)| ≤ 1 for 1 ≤ i < m. Intuitively, we think of f as describing a "walk" on a word u, visiting every position, and yielding a word w as the sequence of letters encountered en route. If such an f exists, we say that u generates w. Call a word primitive if it is not generated by any word shorter than itself. We show that every word has, up to reversal, a unique primitive generator. Observing that, if a word contains a non-trivial palindrome, it can generate the same word via essentially different walks, we obtain conditions under which, for a chosen pair of walks f and g, those walks yield the same word when applied to a given primitive word. Although the original impulse for studying primitive generators comes from their application to decision procedures in logic, we end, by way of further motivation, with an analysis of the primitive generators for certain word sequences defined via morphisms
Temporal prepositions and their logic
No full textA fragment of English featuring temporal prepositions and the order-denoting adjectives first and last is defined by means of a context-free grammar. The phrase-structures which this grammar assigns to the sentences it recognizes are viewed as formulas of an interval temporal logic, whose satisfaction-conditions faithfully represent the meanings of the corresponding English sentences. It is shown that the satisfiability problem for this logic is NEXPTIME-complete. The computational complexity of determining logical relationships between English sentences featuring the temporal constructions in question is thus established. © 2005 Elsevier B.V. All rights reserved
- …
