We prove ExpTime-membership of the satisfiability problem for loosely ∀-guarded first-order formulas with a bounded number of variables and an unbounded number of constants. Guarded fragments with constants are interesting by themselves and because of their connection to hybrid logic.

The guarded fragment with transitive guards, [GF+TG], is an extension of the guarded fragment of first-order logic, GF, in which certain predicates are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. Moreover, we show that the problem is in 2E. This result is optimal since the satisfiability problem for GF is 2E-complete 1719–1742). We also show (...) that the satisfiability problem for two-variable [GF+TG] is N-hard in contrast to GF with bounded number of variables for which the satisfiability problem is E-complete. (shrink)

Abstract State Machines (ASMs) provide a formal method for transparent design and specification of complex dynamic systems. They combine advantages of informal and formal methods. Applications of this method motivate a number of computability and decidability problems connected to ASMs. Such problems result for example from the area of verifying properties of ASMs. Their high expressive power leads rather directly to undecidability respectively uncomputability results for most interesting problems in the case of unrestricted ASMs. Consequently, it is rather natural to (...) ask whether there exist expressive classes of ASMs for which we can prove positive decidability and computability results. In this work, we introduce such a class of ASMs. The concept is similar to the one of the guarded fragment of first-order logic. We analyze the expressive power of this class and prove that it is stronger than Datalog LITE and the guarded fragment of first-order fixed point logic. Some decidability and computability results have been proven in earlier works. (shrink)

We show that the loosely guarded and packed fragments of first-order logic have the finite model property. We use a construction of Herwig and Hrushovski. We point out some consequences in temporal predicate logic and algebraic logic.

We show that the loosely guarded and packed fragments of first-order logic have the finite model property. We use a construction of Herwig and Hrushovski. We point out some consequences in temporal predicate logic and algebraic logic.

We prove ExpTime-membership of the satisfiability problem for loosely ∀-guarded first-order formulas with a bounded number of variables and an unbounded number of constants. Guarded fragments with constants are interesting by themselves and because of their connection to hybrid logic.

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails (...) in restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

In this paper, we introduce a variant of second-order propositional modal logic interpreted on general (or Henkin) frames, \(SOPML^{\mathcal {H}}\), and present a decidable fragment of this logic, \(SOPML^{\mathcal {H}}_{dec}\), that preserves important expressive capabilities of \(SOPML^{\mathcal {H}}\). \(SOPML^{\mathcal {H}}_{dec}\) is defined as a _modal loosely guarded fragment_ of \(SOPML^{\mathcal {H}}\). We demonstrate the expressive power of \(SOPML^{\mathcal {H}}_{dec}\) using examples in which modal operators obtain (a) the epistemic interpretation, (b) the dynamic interpretation. \(SOPML^{\mathcal {H}}_{dec}\) partially satisfies the principle (...) of non-Fregean logic: two different _atomic_ propositions with the same truth value can have different contents. In \(SOPML^{\mathcal {H}}_{dec}\), we also define _relating connectives_ and show that the _weak Boethius’ Thesis_ built using these connectives is a valid formula of \(SOPML^{\mathcal {H}}_{dec}\). (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails (...) in restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

We show that the satisfiability problem for the monodic guarded, loosely guarded, and packed fragments of first-order temporal logic with equality is 2Exptime-complete for structures with arbitrary first-order domains, over linear time, dense linear time, rational number time, and some other classes of linear flows of time. We then show that for structures with finite first-order domains, these fragments are also 2Exptime-complete over real number time and hence over most of the commonly used linear flows of (...) time, including the natural numbers, integers, rationals, and any first-order definable class of linear flows of time. (shrink)

In the 1970s Codd introduced the relational algebra, with operators selection, projection, union, difference and product, and showed that it is equivalent to first-order logic. In this paper, we show that if we replace in Codd’s relational algebra the product operator by the “semijoin” operator, then the resulting “semijoin algebra” is equivalent to the guarded fragment of first-order logic. We also define a fixed point extension of the semijoin algebra that corresponds to μGF.

In the 1970s Codd introduced the relational algebra, with operators selection, projection, union, difference and product, and showed that it is equivalent to first-order logic. In this paper, we show that if we replace in Codd’s relational algebra the product operator by the “semijoin” operator, then the resulting “semijoin algebra” is equivalent to the guarded fragment of first-order logic. We also define a fixed point extension of the semijoin algebra that corresponds to μGF.

Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) (...) of first-order logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself. (shrink)

Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) (...) of first-order logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself. (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are algorithmically solvable (...) for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

The Guarded Negation Fragment (GNFO) is a fragment of first-order logic that contains all positive existential formulas, can express the first-order translations of basic modal logic and of many description logics, along with many sentences that arise in databases. It has been shown that the syntax of GNFO is restrictive enough so that computational problems such as validity and satisfiability are still decidable. This suggests that, in spite of its expressive power, GNFO formulas are amenable to novel optimizations. In (...) this article we study the model theory of GNFO formulas. Our results include effective preservation theorems for GNFO, effective Craig Interpolation and Beth Definability results, and the ability to express the certain answers of queries with respect to a large class of GNFO sentences within very restricted logics. (shrink)

Guarded fragments of first-order logic were recently introduced by Andreka, van Benthem and Nemeti; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all (...) other known decidable fragments of first-order logic. Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is EXPTIME-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment. It is also shown that some natural, modest extensions of the guarded fragments are undecidable. (shrink)

We explore the finite model theory of the characterisation theorems for modal and guarded fragments of first-order logic over transition systems and relational structures of width two. A new construction of locally acyclic bisimilar covers provides a useful analogue of the well known tree-like unravellings that can be used for the purposes of finite model theory. Together with various other finitary bisimulation respecting model transformations, and Ehrenfeucht–Fraïssé game arguments, these covers allow us to upgrade finite approximations for full (...) bisimulation equivalence towards approximations for elementary equivalence. These techniques are used to prove several ramifications of the van Benthem–Rosen characterisation theorem of basic modal logic for refinements of ordinary bisimulation equivalence, both in the sense of classical and of finite model theory. (shrink)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results (...) support this claim.) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

Against the background of worldwide, intentional or unintentional everyday violations of human dignity and the epochal need to experience oneself as a human being in one’s specific way of being, this article attempts to pursue the question of human dignity and its concealment. On the one hand, it seeks to ask whether human dignity has become obsolete due to social and epochal developments and preconditions and whether it can only appear and be experienced as antiquated in the context of a (...) technological language or an administered world. On the other hand, it asks whether ethical and anthropological thinking have not sufficiently experienced, thought, and conceptualized man. From the context of these perspectives that determine the question of dignity, Heidegger’s article seeks to take up Heidegger’s repeated search for an original ethics based on Heraclitus’ fragment 119, and from this point of view to ask for a perhaps deeper and more adequate understanding of human dignity. At the centre of this is Heidegger’s thesis that human dignity is based on the protection of the unhidden and, ever before, the hiddenness of all beings. Without wanting to ignore the difficulty and complexity of Heidegger’s thinking, the author seeks to find access to this understanding of our dignity based on the experience of personal encounters. (shrink)

The present paper offers a libertarian reading of one of the most important Chinese novels of the twentieth century, The Travels of Laocan, written by Chinese entrepreneur Liu E between 1903 and 1906. I start with an exposition of the ideas associated with the concept of “Asian values,” the evident cultural unviability of this notion, and how “Asian authoritarianism” has been rationalized and justified on the basis of a Hobbesian conception of human nature. Next, I examine Liu E’s life and (...) career as an entrepreneur in a highly interventionist society. Finally, I focus on his magnum opus, The Travels of Laocan, a fictionalized autobiography that explains Liu E’s philosophical and libertarian ideas. (shrink)

We expand first order models with a tolerance relation on thedomain. Intuitively, two elements stand in this relation if they arecognitively close for the agent who holds the model. This simplenotion turns out to be very powerful. It leads to a semanticcharacterization of the guarded fragment of Andréka, van Benthemand Németi, and highlights the strong analogies between modallogic and this fragment. Viewing the resulting logic – tolerance logic– dynamically it is a resource-conscious information processingalternative to classical first order logic. (...) The differences areindicated by several examples. (shrink)

To articulate the past historically does not mean to recognize it “the way it really was”. It means to seize hold of a memory as it flashes up at a moment of danger. Ever since the advent of the May Fourth Movement in 1919, which marked a turning point in the process of intellectual modernization in the Republic of China, voices were raised against Confucian mores because they were considered cannibalistic, and against the influence they exerted upon the freedom and (...) mobility of women,2 who were reduced to a secondary position in society. Although the fact remains that many so-called “vulgar” traditionalists were the real pioneers of women’s rights in the late Qing and early Republican period,3... (shrink)

El presente artículo tiene como objetivo mostrar, a través de los textos confucianos y de sus intérpretes, cuál ha sido la posición de la mujer en la filosofía china clásica. Se analizará el papel que en las Analectas de Confucio, en los textos rituales, en el “Clásico de Poesía” y en Mencio juega la mujer, así como las interpretaciones que sobre estos pasajes, en ocasiones demasiado escuetos para posicionarse claramente sobre ellos, han realizado los comentaristas, desde la Antigüedad hasta finales (...) de la Época Imperial. Un examen atento mostrará que el confucianismo, a pesar de no preocuparse excesivamente de la cuestión, supo desafiar la “concience collective” y resaltar el papel de la mujer en la historia y en la sociedad. Finalmente, a través de una breve comparación con lo que la filosofía clásica occidental tiene que decir sobre la cuestión del género, se concluirá con unas observaciones sobre el papel del confucianismo en las sociedades modernas asiáticas y su relevancia para la formación de un discurso feminista autóctono. (shrink)

From classical antiquity to contemporary times, challenging situations of dilemmatic or paradoxical nature continue to fascinate both scholars and the casual reader. Although Western literature provides a fruitful source of philosophical discussion on the circumstances under which a morally competent agent faces incompatible moral requirements, Sinology has rarely accepted the idea of moral dilemmas in Chinese philosophy in general and Confucianism in particular. The present paper explores moral and morally motivated dilemmas in Liu Xiang’s 劉向 Lienü Zhuan 列女傳 and the (...) philosophical strategies employed for their resolution within the framework of the Confucian tradition, emphasizing similarities with Western traditions such as Greek tragedy or Thomistic philosophy. (shrink)

Name der Zeitschrift: Nietzsche-Studien Jahrgang: 43 Heft: 1 Seiten: 189-191.

Name der Zeitschrift: Nietzsche-Studien Jahrgang: 43 Heft: 1 Seiten: 192-194.

La actual crisis pedagógica que vive Occidente, constatada por todos aquellos educadores que deben enfrentarse diariamente a unos estándares cada vez más bajos y al consecuente perjuicio en lo que a la autoridad del profesorado se refiere, fue ya profetizada en su momento por Hannah Arendt (“The Crisis in Education”). La educación es uno de los factores más importantes para definir la calidad de vida de un país y, desde esta perspectiva, una crisis educativa es una crisis en todos los (...) ámbitos sociales, económicos y, en última instancia, políticos. El presente artículo intenta exponer cómo la educación y el conocimiento fueron concebidos en la antigüedad a través de dos modelos, Grecia y China, para mostrar así en qué medida los autores clásicos pueden todavía enseñarnos con sentido común a afrontar los problemas metodológicos actuales. Mediante una exposición comparativa, se analizarán las teorías clásicas griegas, así como la epistemología y pedagogía en el confucianismo clásico y tempranomedieval, destacando cómo estos autores confrontaron relativismo, opinión y acumulación vacía de conoci-miento, frente a la búsqueda de la verdad y la selección cuidadosa y científica de saber. En última instancia, destacaremos la necesidad de recuperar nuestra tradición clásica para mantener un nivel educativo adecuado. (shrink)