Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures.In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global winning strategy.As applications of this technique it is shown that • — Graph Connectivity is not expressible in existential monadic (...) second-order logic , even in the presence of a built-in linear order,• — Graph Connectivity is not expressible in MonNP even in the presence of arbitrary built-in relations of degree n0, and• — the presence of a built-in linear order gives MonNP more expressive power than the presence of a built-in successor relation. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the latter (...) is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size (...) of the input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees. (shrink)

The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted towards favoring (...) the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win. (shrink)

In this paper, I have proposed a compositional semantic analysis of exception NPs from which three core properties of exception constructions could be derived. I have shown that this analysis overcomes various empirical and conceptual shortcomings of prior proposals of the semantics of exception sentences. The analysis was first formulated for simple exception NPs, where the EP-complement was considered a set-denoting term and the EP-associate was a monadic quantifier. It was then generalized in two steps: first, in order to (...) account for quantified EP-complements, and second, in order to account for polyadic quantifiers as the EP-associates. An additional assumption that was made in several places was that EPs may operate at the level of implications. The consequences of this assumption, though, still have to be investigated. (shrink)

This volume presents the proceedings of the Computer Science Logic Workshop CSL '92, held in Pisa, Italy, in September/October 1992. CSL '92 was the sixth of the series and the first one held as Annual Conference of the European Association for Computer Science Logic (EACSL). Full versions of the workshop contributions were collected after their presentation and reviewed. On the basis of 58 reviews, 26 papers were selected for publication, and appear here in revised final form. Topics covered in the (...) volume include: Turing machines, linear logic, logic of proofs, optimization problems, lambda calculus, fixpoint logic, NP-completeness, resolution, transition system semantics, higher order partial functions, evolving algebras, functional logic programming, inductive definability, semantics of C, classes for a functional language, NP-optimization problems, theory of types and names, sconing and relators, 3-satisfiability, Kleene's slash, negation-complete logic programs, polynomial-time oracle machines, and monadic second-order properties. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr’s views. Unlike the usual formulation (in which the post-measurement state is a unit vector in Hilbert space), our version actually opens the possibility of admitting a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify this (...) theory, or introduce unusual and controversial interpretative rules and/or ontologies). To that effect, we recall a remarkable phenomenon in the theory of Schrödinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schrödinger’s Cat type) becomes exponentially sensitive to tiny perturbations of the potential as ħ→0. We show that this instability emerges also from the textbook wkb approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation). Numerical simulations show that adiabatically arising perturbations may (quite literally) cause the collapse of the wave-function in the classical limit. Thus, at least in the context of a simple mathematical model, we combine the technical and conceptual virtues of decoherence (which fails to solve the measurement problem but launches the key idea that perturbations may come from the environment) with those of dynamical collapse models à la grw (which do solve the measurement problem but are ad hoc), without sharing their drawbacks: single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), and no modification of quantum mechanics is needed. (shrink)

Through reading the early work of Walter Benjamin—up to and including the Trauerspiel, author Monad Rrenban elicits a cohesive conception of the wild, inforgettable form, philosophy, as inherent in everything. This book, distinct in its analysis and depth of analysis, elaborates the wild, unforgettable form—philosophy in relation to language, the discipline and the practice of philosophy, criticism, and the politics of death.

In this paper we extend Mundici’s functor Γ to the category of monadic MV-algebras. More precisely, we define monadic ℓ -groups and we establish a natural equivalence between the category of monadic MV-algebras and the category of monadic ℓ -groups with strong unit. Some applications are given thereof.

In the following paper I would like to try to expound on a concept quite important in the philosophy of Leibniz – that of the “Monas Dominans”. In particular, I would like to approach this subject in the first place by means of considerations of a “historical-genetic” nature, while in the second part of my work I propose to put forward some possible interpretations of it. In both cases I will try to compare my ideas with those of recent studies (...) on this theme. The difficulties are numerous; first of all, the texts published to date in which Leibniz introduces and presents his doctrine of the “Monas Dominans” are relatively few, especially if compared to the space given to other elements of his philosophical system; secondly, if on the one hand the general intention put forward by Leibniz through the introduction of this doctrine is clear enough (the Monas Dominans renders “One” in the Machine the “corporeal substance”, that is the “Animal”, as found in the letter to De Volder of June 1703 to which scholars often make reference), on the other hand, when one tries to clarify its details and consider its implications one immediately runs into the same difficulties already pointed out in other studies (regarding, for example, the definition of “corporeal substance”, the relationship between the “Monas dominans” and the “innumerable subordinate monads” that form the “Organic Machine”, etc.). A primary idea I will try to present in this work regards the highlighting in the work of Leibniz of a close correlation between the appearance of the expression “organism” and that of the expression “Monas Dominans”. (shrink)

Monadic MV-algebras are an algebraic model of the predicate calculus of the Łukasiewicz infinite valued logic in which only a single individual variable occurs. GMV-algebras are a non-commutative generalization of MV-algebras and are an algebraic counterpart of the non-commutative Łukasiewicz infinite valued logic. We introduce monadic GMV-algebras and describe their connections to certain couples of GMV-algebras and to left adjoint mappings of canonical embeddings of GMV-algebras. Furthermore, functional MGMV-algebras are studied and polyadic GMV-algebras are introduced and discussed.

In this paper, we are concerned with the development of a general set theory using the single axiom version of Leśniewski’s mereology. The specification of mereology, and further of Tarski’s geometry of solids will rely on the Calculus of Inductive Constructions (CIC). In the first part, we provide a specification of Leśniewski’s mereology as a model for an atomless Boolean algebra using Clay’s ideas. In the second part, we interpret Leśniewski’s mereology in monadic second-order logic using names and develop (...) a full version of mereology referred to as CIC-based Monadic Mereology (λ-MM) allowing an expressive theory while involving only two axioms. In the third part, we propose a modeling of Tarski’s solid geometry relying on λ-MM. It is intended to serve as a basis for spatial reasoning. All parts have been proved using a translation in type theory. (shrink)

In spite of their materialist aspirations, both classical and neoclassical economic theories rely on non-material notions of value to explain market activity. André Orléan calls this commitment of orthodox economics "the substance hypothesis." In this essay, I show how the substance hypothesis mirrors Gottfried Wilhelm Leibniz's account of monads, which he called the "true atoms of nature." I argue that value is the atom of economic nature in orthodox economic theories. Like monads, it is a fantasy. The atom of economic (...) nature that governs our actual, material lives, I argue, is money. (shrink)

We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism.

D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.

We show that monadic intuitionistic quantifiers admit the following temporal interpretation: “always in the future” (for$\forall $) and “sometime in the past” (for$\exists $). It is well known that Prior’s intuitionistic modal logic${\sf MIPC}$axiomatizes the monadic fragment of the intuitionistic predicate logic, and that${\sf MIPC}$is translated fully and faithfully into the monadic fragment${\sf MS4}$of the predicate${\sf S4}$via the Gödel translation. To realize the temporal interpretation mentioned above, we introduce a new tense extension${\sf TS4}$of${\sf S4}$and provide a full (...) and faithful translation of${\sf MIPC}$into${\sf TS4}$. We compare this new translation of${\sf MIPC}$with the Gödel translation by showing that both${\sf TS4}$and${\sf MS4}$can be translated fully and faithfully into a tense extension of${\sf MS4}$, which we denote by${\sf MS4.t}$. This is done by utilizing the relational semantics for these logics. As a result, we arrive at the diagram of full and faithful translations shown in Figure 1 which is commutative up to logical equivalence. We prove the finite model property (fmp) for${\sf MS4.t}$using algebraic semantics, and show that the fmp for the other logics involved can be derived as a consequence of the fullness and faithfulness of the translations considered. (shrink)

We introduce the equational notion of a monadic bounded algebra (MBA), intended to capture algebraic properties of bounded quantification. The variety of all MBA's is shown to be generated by certain algebras of two-valued propositional functions that correspond to models of monadic free logic with an existence predicate. Every MBA is a subdirect product of such functional algebras, a fact that can be seen as an algebraic counterpart to semantic completeness for monadic free logic. The analysis involves (...) the representation of MBA's as powerset algebras of certain directed graphs with a set of "marked" points. It is shown that there are only countably many varieties of MBA's, all are generated by their finite members, and all have finite equational axiomatisations classifying them into fourteen kinds of variety. The universal theory of each variety is decidable. Finitely generated MBA's are shown to be finite, with the free algebra on r generators having exactly $2^{3.2^{r.} } ^{2^{{\rm{2}}^{{\rm{r - 1}}} } } $ elements. An explicit procedure is given for constructing this freely generated algebra as the powerset algebra of a certain marked graph determined by the number r. (shrink)

We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$.

We investigate monadic fragments of Intuitionistic Control Logic, which is obtained from Intuitionistic Propositional Logic by extending language of IPL by a constant distinct from intuitionistic constants. In particular we present the complete description of purely negational fragment and show that most of monadic fragments are finite.

This article discusses the final development of Gottfried Wilhelm Leibniz’s metaphysics: the theory of monads. It examines Leibniz’s arguments for monads as mindlike “simple substances,” his description of the properties of monads, and the distinction he draws among different types of monads. The remainder of the article focuses on two problems that attend Leibniz’s claim that reality ultimately consists solely of monads and their internal states (perceptions and appetitions). The first problem is whether a relation among monads can account for (...) the supposed unity of a living body or corporeal substance; the second is whether the metaphysics of monads supports a plausible explanation of the reality of matter. With regard to the second problem, the article explores Leibniz’s thesis that monads are, in two senses, “requisites” of matter. It concludes with reflections on the limits of his attempt to explain the physical world in terms of monads alone. (shrink)

In this new work, Richard T. W. Arthur offers a fresh interpretation of Leibniz's theory of substance. He goes against a long trend of idealistic interpretations of Leibniz's thought by instead taking seriously Leibniz's claim of introducing monads to solve the problem of the composition of matter and motion.

The genesis for this volume was in the bombing of Japan during World War II, where the author, as a young boy, watched the bombers overhead, speculating about the lives of the pilots and their relationship with those huddled on the ground._ From this disturbing diorama, Professor Hiroshi Kojima, the translator of Martin Buber into Japanese, unfolds a new approach to Buber's “I-Thou” relation, drawing upon insights from Husserl, Heidegger, and others in the tradition of continental philosophy to extend and (...) deepen Buber's thought. In chapters that reflect upon a wide range of phenomena—from religion, science, and technology, to imagination, embodiment, and power—Professor Kojima articulates a conception of what it means to be a human being that stands as an alternative to atomism and alienation of the modern world. Analyses of haiku and other aspects of Japanese culture demonstrate how Kojima's theory can illuminate the spiritual traditions of both East and West. Original in its thought and revealing in its insight into Japanese thought and culture, _Monad and Thou__ represents the life's work of one of Japan's great thinkers. (shrink)

Let ( * X, * T) be the nonstandard extension of a Hausdorff space (X, T). After Wattenberg [6], the monad m(x) of a near-standard point x in * X is defined as m(x) = μ T (st(x)). Consider the relation $R_{\mathrm{ns}} = \{\langle x, y \rangle \mid x, y \in \mathrm{ns} (^\ast X) \text{and} y \in m(x)\}.$ Frank Wattenberg in [6] and [7] investigated the possibilities of extending the domain of R ns to the whole of * X. Wattenberg's (...) extensions of R ns were required to be equivalence relations, among other things. Because the nontrivial ways of constructing such extensions usually produce monadic relations, the said condition practically limits (to completely regular spaces) the class of spaces for which such extensions are possible. Since symmetry and transitivity are not, after all, characteristics of the kind of nearness that is obtained in a general topological space, it may be expected that if these two requirements are relaxed, then a monadic extension of R ns to * X should be possible in any topological space. A study of such extensions of R ns is the purpose of the present paper. We call a binary relation $W \subseteq ^\ast X \times ^\ast X$ an infinitesimal on * X if it is monadic and reflexive on * X. We prove, among other things, that the existence of an infinitesimal on * X that extends R ns is equivalent to the condition that the space (X, T) be regular. (shrink)

We investigate the monadic logic of trees with ω + 1 levels, the monadic topology of the product space ω λ and a strengthening of monadic logic for trees with ω levels.

The variety MBA of monadic bounded algebras consists of Boolean algebras with a distinguished element E, thought of as an existence predicate, and an operator ∃ reflecting the properties of the existential quantifier in free logic. This variety is generated by a certain class FMBA of algebras isomorphic to ones whose elements are propositional functions. We show that FMBA is characterised by the disjunction of the equations ∃E = 1 and ∃E = 0. We also define a weaker notion (...) of "relatively functional" algebra, and show that every member of MBA is isomorphic to a relatively functional one. (shrink)

In this paper we extend Mundici’s functor Γ to the category of monadic MV-algebras. More precisely, we define monadic ℓ-groups and we establish a natural equivalence between the category of monadic MV-algebras and the category of monadic ℓ-groups with strong unit. Some applications are given thereof.

In this paper, we investigate universal and existential quantifiers on NM-algebras. The resulting class of algebras will be called monadic NM-algebras. First, we show that the variety of monadic NM-algebras is algebraic semantics of the monadic NM-predicate logic. Moreover, we discuss the relationship among monadic NM-algebras, modal NM-algebras and rough approximation spaces. Second, we introduce and investigate monadic filters in monadic NM-algebras. Using them, we prove the subdirect representation theorem of monadic NM-algebras, and (...) characterize simple and subdirectly irreducible monadic NM-algebras. Finally, we present the monadic NM-logic and prove its completeness with respect to monadic NM-algebras. These results constitute a crucial first step for providing an algebraic foundation for the monadic NM-predicate logic. (shrink)

In this paper, we introduce the variety of algebras, which we call monadic \-rough Heyting algebras. These algebras constitute an extension of monadic Heyting algebras and in \ case they coincide with monadic 3-valued Łukasiewicz–Moisil algebras. Our main interest is the characterization of simple and subdirectly irreducible monadic \-rough Heyting algebras. In order to this, an Esakia-style duality for these algebras is developed.

One of the main obstacles for panpsychism, the view that consciousness is fundamental and ubiquitous, is the difficulty of explaining how simple subjects could combine to form complex subjects. Known as the subject combination problem, it poses a possibly insurmountable challenge to the view. In this paper, I will assume that this challenge cannot be overcome and instead present a version of panpsychism that completely avoids talk of combination. Inspired by Gottfried Wilhelm Leibniz’s metaphysics of monads, I will focus on (...) a relational explanation of how simple subjects could constitute complex experiences, without them having to combine in virtue of their subjectivity. I call this view monadic panpsychism. Additionally, my proposal will not rely on emergence and so it will circumvent problems commonly faced by emergentist accounts. As I will argue, monadic panpsychism is preferable to combinatory and emergentist panpsychism because it faces a significantly less worrisome set of objections. Apart from being unaffected by the seemingly insuperable issue of subject combination, I will demonstrate that monadic panpsychism also has tools to address other kinds of the combination problem. That alone justifies the need for a new formulation of panpsychism, one which faces unique difficulties but also offers unique solutions. (shrink)

Epistemic monadic Boolean algebras are obtained by enriching monadic Boolean algebras with a knowledge operator. Epistemic monadic logic as the monadic fragment of first-order epistemic logic is introduced for talking about knowing things. A Halmos-style representation of epistemic monadic Boolean algebras is established. Relativizations of epistemic monadic algebras are given for modelling updates. These logics are semantically complete.

Aiming for applications in monadic second-order model theory, we study first-order theories without definable pairing functions. Our main results concern forking-properties of sequences of indiscernibles. These turn out to be very well-behaved for the theories under consideration.

It is generally assumed that there are two types of genericity, called characterizing statements and kind reference in Krifka et al. (1995). Characterizing statements express generalizations about sets of entities or situations, cf. (1); kind reference involves reference to an entity that is related to specimens, cf. (2).

Büchi, J. R. The monadic second order theory of [omega symbol]₁.--Büchi, J. R. and Siefkes, D. Axiomatization of the monadic second order theory of [omega symbol]₁.

We consider a deterministic rewrite system for combinatory logic over combinators , and . Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalizing term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda-expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if (...) they represent the same lambda-expression (up to --equivalence). The problem of minimizing the number of reduction steps over equivalent combinator expressions (i.e., the problem of finding the "fastest running" combinator representation for a specific lambda-expression) is proved to be NP-complete by reduction from the "Hitting Set" problem. (shrink)

A monadic formula Ψ (Y) is a selector for a formula φ (Y) in a structure M if there exists a unique subset P of μ which satisfies Ψ and this P also satisfies φ. We show that for every ordinal α ≥ ωω there are formulas having no selector in the structure (α, <). For α ≤ ω₁, we decide which formulas have a selector in (α, <), and construct selectors for them. We deduce the impossibility of a (...) full generalization of the Büchi-Landweber solvability theorem from (ω, <) to (ωw, <). We state a partial extension of that theorem to all countable ordinals. To each formula we assign a selection degree which measures "how difficult it is to select". We show that in a countable ordinal all non-selectable formulas share the same degree. (shrink)

Husserl's transcendental phenomenology is not a mere egology, but gets its concrete accomplishment only as a phenomenology of 'transcendental intersubjectivity'. However, the subjective centers of any transcendentality and thus of every constitution — even of intersubjectivity itself — have to be such unities as Leibniz' 'monads', that is, individually concrete subjects producing all their representations of one another completely out of themselves, respectively. Thus the problem arises, how the genuine transcendental status of each monadic subject in all its constitutive (...) achievements could be maintained so that they develop their own intentional lives in a universal mutual accordance, without presupposing again a supra-monadic ground for their 'harmony', i.e. a higher-levelled ordering unity. I shall argue that th peculiar Husserlian 'transcendental monadology' is inevitably bound to this intrinsic paradox which can at best be reduced to a mere postulate but never be resolved. (shrink)

This paper argues that donkey pronouns should be construed as definite articles, followed by an NP sister which has undergone deletion in the phonology. So Every man who owns a donkey beats it is claimed to share a Logical Form with Every man who owns a donkey beats the donkey, which means the same. There is independent evidence for assimilating pronouns to determiners, and for NP-deletion; so this theory explains E-type anaphora without postulating any special entity (`E-type pronoun') for the (...) purpose. Since NP-deletion, like other ellipsis, requires an antecedent, this theory also explains the requirement for a "formal link" between donkey pronoun and antecedent, which standard E-type theories find difficult to account for. Other empirical advantages of this theory include its ability to explain the pattern of strict and sloppy identity displayed by donkey sentences with phonologically reduced continuations. It is shown that Bach-Peters sentences, quantificational subordination, and paycheck sentences can also be dealt with on the present approach. (shrink)

We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other.

We define and study monadic MV-algebras as pairs of MV-algebras one of which is a special case of relatively complete subalgebra named m-relatively complete. An m-relatively complete subalgebra determines a unique monadic operator. A necessary and sufficient condition is given for a subalgebra to be m-relatively complete. A description of the free cyclic monadic MV-algebra is also given.

In our paper, monadic modal pseudocomplemented De Morgan algebras are considered following Halmos’ studies on monadic Boolean algebras. Hence, their topological representation theory is used successfully. Lattice congruences of an mmpM is characterized and the variety of mmpMs is proven semisimple via topological representation. Furthermore and among other things, the poset of principal congruences is investigated and proven to be a Boolean algebra; therefore, every principal congruence is a Boolean congruence. All these conclusions contrast sharply with known results (...) for monadic De Morgan algebras. Finally, we show that the above results for mmpM are verified for monadic tetravalent modal algebras. (shrink)

Daniel Garber presents a study of Leibniz's conception of the physical world, elucidating his puzzling metaphysics of monads, mind-like simple substances.

We present the design goals and metatheory of the Monadic Hybrid Calculus, a new formal system that has the same power as the Monadic Predicate Calculus. MHC allows quantification, including relative quantification, in a straightforward way without the use of bound variables, using a simple adaptation of modal logic notation. Thus “all Greeks are mortal” can be written as [G]M. MHC is also ‘hybrid’ in that it has individual constants, which allow us to formulate statements about particular individuals. (...) Thus “Socrates is Athenian and mortal” can be formalised as s.For our proof system, we use a simple adaptation of Beth-style tableaus. The availability of individual constants eliminates the need for labelled deduction.We discuss first the pragmatic and pedagogical advantages of MHC. Then we present the metatheory: formal syntax, semantics, proof rules, soundness, completeness and expressive equivalence with the Monadic Predicate Calculus. (shrink)