Results for 'decidability'

556 found
Order:
See also
  1. More on The Decidability of Mereological Theories.Hsing-Chien Tsai - 2011 - Logic and Logical Philosophy 20 (3):251-265.
    Quite a few results concerning the decidability of mereological theories have been given in my previous paper. But many mereological theories are still left unaccounted for. In this paper I will refine a general method for proving the undecidability of a theory and then by making use of it, I will show that most mereological theories that are strictly weaker than CEM are finitely inseparable and hence undecidable. The same results might be carried over to some extensions of those (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  2.  17
    On the Decidability of Implicational Ticket Entailment.Katalin Bimbó & J. Michael Dunn - 2013 - Journal of Symbolic Logic 78 (1):214-236.
    The implicational fragment of the logic of relevant implication, $R_\to$ is known to be decidable. We show that the implicational fragment of the logic of ticket entailment, $T_\to$ is decidable. Our proof is based on the consecution calculus that we introduced specifically to solve this 50-year old open problem. We reduce the decidability problem of $T_\to$ to the decidability problem of $R_\to$. The decidability of $T_\to$ is equivalent to the decidability of the inhabitation problem of implicational (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  3.  56
    Decidability of General Extensional Mereology.Hsing-Chien Tsai - 2013 - Studia Logica 101 (3):619-636.
    The signature of the formal language of mereology contains only one binary predicate P which stands for the relation “being a part of”. Traditionally, P must be a partial ordering, that is, ${\forall{x}Pxx, \forall{x}\forall{y}((Pxy\land Pyx)\to x=y)}$ and ${\forall{x}\forall{y}\forall{z}((Pxy\land Pyz)\to Pxz))}$ are three basic mereological axioms. The best-known mereological theory is “general extensional mereology”, which is axiomatized by the three basic axioms plus the following axiom and axiom schema: (Strong Supplementation) ${\forall{x}\forall{y}(\neg Pyx\to \exists z(Pzy\land \neg Ozx))}$ , where Oxy means ${\exists (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  4.  52
    A Comprehensive Picture of the Decidability of Mereological Theories.Hsing-Chien Tsai - 2013 - Studia Logica 101 (5):987-1012.
    The signature of the formal language of mereology contains only one binary predicate which stands for the relation “being a part of” and it has been strongly suggested that such a predicate must at least define a partial ordering. Mereological theories owe their origin to Leśniewski. However, some more recent authors, such as Simons as well as Casati and Varzi, have reformulated mereology in a way most logicians today are familiar with. It turns out that any theory which can be (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  5.  76
    Propositional Interval Neighborhood Logics: Expressiveness, Decidability, and Undecidable Extensions.Davide Bresolin, Valentin Goranko, Angelo Montanari & Guido Sciavicco - 2009 - Annals of Pure and Applied Logic 161 (3):289-304.
    In this paper, we investigate the expressiveness of the variety of propositional interval neighborhood logics , we establish their decidability on linearly ordered domains and some important subclasses, and we prove the undecidability of a number of extensions of PNL with additional modalities over interval relations. All together, we show that PNL form a quite expressive and nearly maximal decidable fragment of Halpern–Shoham’s interval logic HS.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  6.  27
    On the Decidability of Axiomatized Mereotopological Theories.Hsing-Chien Tsai - 2015 - Notre Dame Journal of Formal Logic 56 (2):287-306.
    The signature of the formal language of mereotopology contains two predicates $P$ and $C$, which stand for “being a part of” and “contact,” respectively. This paper will deal with the decidability issue of the mereotopological theories which can be formed by the axioms found in the literature. Three main results to be given are as follows: all axiomatized mereotopological theories are separable; all mereotopological theories up to $\mathbf{ACEMT}$, $\mathbf{SACEMT}$, or $\mathbf{SACEMT}^{\prime}$ are finitely inseparable; all axiomatized mereotopological theories except $\mathbf{SAX}$, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  6
    Decidability and Specker Sequences in Intuitionistic Mathematics.Mohammad Ardeshir & Rasoul Ramezanian - 2009 - Mathematical Logic Quarterly 55 (6):637-648.
    A bounded monotone sequence of reals without a limit is called a Specker sequence. In Russian constructive analysis, Church's Thesis permits the existence of a Specker sequence. In intuitionistic mathematics, Brouwer's Continuity Principle implies it is false that every bounded monotone sequence of real numbers has a limit. We claim that the existence of Specker sequences crucially depends on the properties of intuitionistic decidable sets. We propose a schema about intuitionistic decidability that asserts “there exists an intuitionistic enumerable set (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  22
    Decidability of an Xstit Logic.Gillman Payette - 2014 - Studia Logica 102 (3):577-607.
    This paper presents proofs of completeness and decidability of a non-temporal fragment of an Xstit logic. This shows a distinction between the non-temporal fragments of Xstit logic and regular stit logic since the latter is undecidable. The proof of decidability is via the finite model property. The finite model property is shown to hold by constructing a filtration. However, the set that is used to filter the models isn’t simply closed under subformulas, it has more complex closure conditions. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  4
    Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
    We study concepts of decidability for subsets of Euclidean spaces ℝk within the framework of approximate computability . A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  27
    An Elementary System as and its Semi‐Completeness and Decidability.Qin Jun - 1992 - Mathematical Logic Quarterly 38 (1):305-320.
    The author establishes an elementary system AS which contains functions +, ≐ and a constant 0 and then proves the semi-completeness and the decidability of AS, using the theory of systems of inequalities.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  11.  12
    On the Decidability Status of Fuzzy A ℒ C with General Concept Inclusions.Franz Baader, Stefan Borgwardt & Rafael Peñaloza - 2015 - Journal of Philosophical Logic 44 (2):117-146.
    The combination of Fuzzy Logics and Description Logics has been investigated for at least two decades because such fuzzy DLs can be used to formalize imprecise concepts. In particular, tableau algorithms for crisp Description Logics have been extended to reason also with their fuzzy counterparts. It has turned out, however, that in the presence of general concept inclusion axioms this extension is less straightforward than thought. In fact, a number of tableau algorithms claimed to deal correctly with fuzzy DLs with (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  8
    The Decidability of the Class and the Axiom of Foundation.Dorella Bellè & Franco Parlamento - 2001 - Notre Dame Journal of Formal Logic 42 (1):41-53.
    We show that the Axiom of Foundation, as well as the Antifoundation Axiom AFA, plays a crucial role in determining the decidability of the following problem. Given a first-order theory T over the language , and a sentence F of the form with quantifier-free in the same language, are there models of T in which F is true? Furthermore we show that the Extensionality Axiom is quite irrelevant in that respect.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  13.  7
    On Decidability of a Logic for Order of Magnitude Qualitative Reasoning with Bidirectional Negligibility.Joanna Golinska-Pilarek - 2012 - In Luis Farinas del Cerro, Andreas Herzig & Jerome Mengin (eds.), Logics in Artificial Intelligence. Springer. pp. 255--266.
    Qualitative Reasoning (QR) is an area of research within Artificial Intelligence that automates reasoning and problem solving about the physical world. QR research aims to deal with representation and reasoning about continuous aspects of entities without the kind of precise quantitative information needed by conventional numerical analysis techniques. Order-of-magnitude Reasoning (OMR) is an approach in QR concerned with the analysis of physical systems in terms of relative magnitudes. In this paper we consider the logic OMR_N for order-of-magnitude reasoning with the (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  5
    Comparing First Order Theories of Modules Over Group Rings II: Decidability: Decidability.Carlo Toffalori & S. Cittadini - 2002 - Mathematical Logic Quarterly 48 (4):483-498.
    We consider R-torsionfree modules over group rings RG, where R is a Dedekind domain and G is a finite group. In the first part of the paper [4] we compared the theory T of all R-torsionfree RG-modules and the theory T0 of RG-lattices , and we realized that they are almost always different. Now we compare their behaviour with respect to decidability, when RG-lattices are of finite, or wild representation type.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15. Decidability of Mereological Theories.Hsing-Chien Tsai - 2009 - Logic and Logical Philosophy 18 (1):45-63.
    Mereological theories are theories based on a binary predicate ‘being a part of’. It is believed that such a predicate must at least define a partial ordering. A mereological theory can be obtained by adding on top of the basic axioms of partial orderings some of the other axioms posited based on pertinent philosophical insights. Though mereological theories have aroused quite a few philosophers’ interest recently, not much has been said about their meta-logical properties. In this paper, I will look (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  16.  13
    Decidability of ∀*∀‐Sentences in Membership Theories.Eugenio G. Omodeo, Franco Parlamento & Alberto Policriti - 1996 - Mathematical Logic Quarterly 42 (1):41-58.
    The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo-Fraenkel which is already complete with respect to the ∀*∀ class of sentences. NP-hardness and NP-completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  17.  20
    Decidability and Generalized Quantifiers.Andreas Baudisch (ed.) - 1980 - Akademie Verlag.
  18.  11
    Decidability of ∃*∀∀-Sentences in HF.D. Bellè & F. Parlamento - 2008 - Notre Dame Journal of Formal Logic 49 (1):55-64.
    Let HF be the collection of the hereditarily finite well-founded sets and let the primitive language of set theory be the first-order language which contains binary symbols for equality and membership only. As announced in a previous paper by the authors, "Truth in V for ∃*∀∀-sentences is decidable," truth in HF for ∃*∀∀-sentences of the primitive language is decidable. The paper provides the proof of that claim.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  36
    A Note on the Decidability of de Finetti's Coherence.Francesco Corielli - 1995 - Theory and Decision 38 (1):121-129.
  20.  9
    Decidability in the Constructive Theory of Reals as an Ordered ℚ‐Vectorspace.Miklós Erdélyi-Szabó - 1997 - Mathematical Logic Quarterly 43 (3):343-354.
    We show that various fragments of the intuitionistic/constructive theory of the reals are decidable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  28
    On the Decidability of the Real Field with a Generic Power Function.Gareth Jones & Tamara Servi - 2011 - Journal of Symbolic Logic 76 (4):1418-1428.
    We show that the theory of the real field with a generic real power function is decidable, relative to an oracle for the rational cut of the exponent of the power function. We also show the existence of generic computable real numbers, hence providing an example of a decidable o-minimal proper expansion of the real field by an analytic function.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  22.  13
    Decidability of the Equational Theory of the Continuous Geometry CG(\Bbb {F}).John Harding - 2013 - Journal of Philosophical Logic 42 (3):461-465.
    For $\Bbb {F}$ the field of real or complex numbers, let $CG(\Bbb {F})$ be the continuous geometry constructed by von Neumann as a limit of finite dimensional projective geometries over $\Bbb {F}$ . Our purpose here is to show the equational theory of $CG(\Bbb {F})$ is decidable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  23.  10
    A Note on the Decidability of Exponential Terms.Paola D'Aquino & Giuseppina Terzo - 2007 - Mathematical Logic Quarterly 53 (3):306-310.
    In this paper we prove, modulo Schanuel's Conjecture, that there are algorithms which decide if two exponential polynomials in π are equal in ℝ and if two exponential polynomials in π and i coincide in ℂ.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  24.  11
    Relative Decidability and Definability in Henselian Valued Fields.Joseph Flenner - 2011 - Journal of Symbolic Logic 76 (4):1240-1260.
    Let (K, v) be a henselian valued field of characteristic 0. Then K admits a definable partition on each piece of which the leading term of a polynomial in one variable can be computed as a definable function of the leading term of a linear map. The main step in obtaining this partition is an answer to the question, given a polynomial f(x) ∈ K[x], what is v(f(x))? Two applications are given: first, a constructive quantifier elimination relative to the leading (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  25.  28
    Deducibility and Decidability.R. R. Rockingham Gill - 1990 - Routledge.
    The classic results obtained by Gödel, Tarski, Kleene, and Church in the early thirties are the finest flowers of symbolic logic. They are of fundamental importance to those investigations of the foundations of mathematics via the concept of a formal system that were inaugurated by Frege, and of obvious significance to the mathematical disciplines, such as computability theory, that developed from them. Derived from courses taught by the author over several years, this new exposition presents all of the results with (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  26. Issues of Decidability and Tractability.Witold Marciszewski (ed.) - 2006 - University of Białystok.
  27. Recursive Functions and Metamathematics Problems of Completeness and Decidability, Gödel's Theorems.Roman Murawski - 1999
     
    Export citation  
     
    Bookmark  
  28. Three Concepts of Decidability for General Subsets of Uncountable Spaces.Matthew W. Parker - 2003 - Theoretical Computer Science 351 (1):2-13.
    There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  29.  11
    Some Effects of Ash–Nerode and Other Decidability Conditions on Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 55 (1):51-65.
    With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  30.  77
    Completeness and Decidability Results for Some Propositional Modal Logics Containing “Actually” Operators.Dominic Gregory - 2001 - Journal of Philosophical Logic 30 (1):57-78.
    The addition of "actually" operators to modal languages allows us to capture important inferential behaviours which cannot be adequately captured in logics formulated in simpler languages. Previous work on modal logics containing "actually" operators has concentrated entirely upon extensions of KT5 and has employed a particular modeltheoretic treatment of them. This paper proves completeness and decidability results for a range of normal and nonnormal but quasi-normal propositional modal logics containing "actually" operators, the weakest of which are conservative extensions of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  31.  59
    Decidability for Some Justification Logics with Negative Introspection.Thomas Studer - 2013 - Journal of Symbolic Logic 78 (2):388-402.
    Justification logics are modal logics that include justifications for the agent's knowledge. So far, there are no decidability results available for justification logics with negative introspection. In this paper, we develop a novel model construction for such logics and show that justification logics with negative introspection are decidable for finite constant specifications.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  32. Absolute Decidability and Mathematical Modality.Hasen Khudairi - manuscript
    This paper aims to contribute to the analysis of the nature of mathematical modality, and to the applications of the latter to unrestricted quantification and absolute decidability. Rather than countenancing the interpretational type of mathematical modality as a primitive, I argue that the interpretational type of mathematical modality is a species of epistemic modality. I argue, then, that the framework of multi-dimensional intensional semantics ought to be applied to the mathematical setting. The framework permits of a formally precise account (...)
    No categories
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  33.  6
    Non-Primitive Recursive Decidability of Products of Modal Logics with Expanding Domains.David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2006 - Annals of Pure and Applied Logic 142 (1):245-268.
    We show that—unlike products of ‘transitive’ modal logics which are usually undecidable—their ‘expanding domain’ relativisations can be decidable, though not in primitive recursive time. In particular, we prove the decidability and the finite expanding product model property of bimodal logics interpreted in two-dimensional structures where one component—call it the ‘flow of time’—is • a finite linear order or a finite transitive tree and the other is composed of structures like • transitive trees/partial orders/quasi-orders/linear orders or only finite such structures (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  34. Decidability and ℵ0-Categoricity of Theories of Partially Ordered Sets.James H. Schmerl - 1980 - Journal of Symbolic Logic 45 (3):585 - 611.
    This paper is primarily concerned with ℵ 0 -categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ 0 -categoricity. Among the latter are the following. Corollary 3.3. For every countable ℵ 0 -categorical U there is a linear order of A such that $(\mathfrak{U}, is ℵ 0 -categorical. Corollary 6.7. Every ℵ 0 -categorical theory of a partially ordered set of finite width has a decidable theory. (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  35.  49
    Axiomatisation and Decidability Off Andp in Cyclical Time.Mark Reynolds - 1994 - Journal of Philosophical Logic 23 (2):197 - 224.
    We present a Hilbert style axiomatisation for the set of formulas in the temporal language with F and P which are valid over non-transitive cyclical flows of time. We also give a simpler axiomatisation using the slightly controversial 'irreflexivity rule' and go on to prove the decidability of any temporal logic over cyclical time provided it uses only connectives with first-order tables.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  36.  5
    Deductive Systems and the Decidability Problem for Hybrid Logics.Michal Zawidzki - 2014 - Cambridge University Press.
    This book stands at the intersection of two topics: the decidability and computational complexity of hybrid logics, and the deductive systems designed for them. Hybrid logics are here divided into two groups: standard hybrid logics involving nominals as expressions of a separate sort, and non-standard hybrid logics, which do not involve nominals but whose expressive power matches the expressive power of binder-free standard hybrid logics.The original results of this book are split into two parts. This division reflects the division (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  37.  28
    Decidability of Logics Based on an Indeterministic Metric Tense Logic.Yan Zhang & Kai Li - 2015 - Studia Logica 103 (6):1123-1162.
    This paper presents two general results of decidability concerning logics based on an indeterministic metric tense logic, which can be applied to, among others, logics combining knowledge, time and agency. We provide a general Kripke semantics based on a variation of the notion of synchronized Ockhamist frames. Our proof of the decidability is by way of the finite frame property, applying subframe transformations and a variant of the filtration technique.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  38.  36
    Completeness and Decidability of Tense Logics Closely Related to Logics Above K.Frank Wolter - 1997 - Journal of Symbolic Logic 62 (1):131-158.
    Tense logics formulated in the bimodal propositional language are investigated with respect to Kripke-completeness (completeness) and decidability. It is proved that all minimal tense extensions of modal logics of finite width (in the sense of K. Kine) as well as all minimal tense extensions of cofinal subframe logics (in the sense of M. Zakharyaschev) are complete. The decidability of all finitely axiomatizable minimal tense extensions of cofinal subframe logics is shown. A number of variations and extensions of these (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  39.  38
    Decidability Ofstit Theory with a Single Agent Andrefref Equivalence.Ming Xu - 1994 - Studia Logica 53 (2):259 - 298.
    The purpose of this paper is to prove the decidability ofstit theory (a logic of seeing to it that) with a single agent andRefref Equivalence. This result is obtained through an axiomatization of the theory and a proof that it has thefinite model property. A notion ofcompanions to stit formulas is introduced and extensively used in the proof.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  40. Decidability of Cylindric Set Algebras of Dimension Two and First-Order Logic with Two Variables.Maarten Marx & Szabolcs Mikulás - 1999 - Journal of Symbolic Logic 64 (4):1563-1572.
    The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse 2 ). The new proof also shows the known results that the universal theory of Pse 2 is decidable and that every finite Pse 2 can be represented on a (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  41.  15
    Decidability, Partial Decidability and Sharpness Relation for L-Subsets.Giangiacomo Gerla - 1987 - Studia Logica 46 (3):227-238.
    If X is set and L a lattice, then an L-subset or fuzzy subset of X is any map from X to L, [11]. In this paper we extend some notions of recursivity theory to fuzzy set theory, in particular we define and examine the concept of almost decidability for L-subsets. Moreover, we examine the relationship between imprecision and decidability. Namely, we prove that there exist infinitely indeterminate L-subsets with no more precise decidable versions and classical subsets whose (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  42.  21
    Decidability Results for Metric and Layered Temporal Logics.Angelo Montanari & Alberto Policriti - 1996 - Notre Dame Journal of Formal Logic 37 (2):260-282.
    We study the decidability problem for metric and layered temporal logics. The logics we consider are suitable to model time granularity in various contexts, and they allow one to build granular temporal models by referring to the "natural scale" in any component of the model and by properly constraining the interactions between differently-grained components. A monadic second-order language combining operators such as temporal contextualization and projection, together with the usual displacement operator of metric temporal logics, is considered, and the (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  43.  31
    Decidability in Intuitionistic Type Theory is Functionally Decidable.Silvio Valentini - 1996 - Mathematical Logic Quarterly 42 (1):300-304.
    In this paper we show that the usual intuitionistic characterization of the decidability of the propositional function B prop [x : A], i. e. to require that the predicate ∨ ¬ B) is provable, is equivalent, when working within the framework of Martin-Löf's Intuitionistic Type Theory, to require that there exists a decision function ψ: A → Boole such that = Booletrue) ↔ B). Since we will also show that the proposition x = Booletrue [x: Boole] is decidable, we (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  44.  9
    Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.
    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) (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  45.  1
    Decidability of a Hybrid Duration Calculus.Thomas Bolander, Jens Ulrik Hansen & Michael R. Hansen - 2007 - Electronic Notes in Theoretical Computer Science 174 (3):113-133.
    We present a logic which we call Hybrid Duration Calculus. HDC is obtained by adding the following hybrid logical machinery to the Restricted Duration Calculus : nominals, satisfaction operators, down-arrow binder, and the global modality. RDC is known to be decidable, and in this paper we show that decidability is retained when adding the hybrid logical machinery. Decidability of HDC is shown by reducing the satisfiability problem to satisfiability of Monadic Second-Order Theory of Order. We illustrate the increased (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  46.  16
    Decidability for ℤ[G]‐Modules When G is Cyclic of Prime Order.Carlo Toffalori - 1996 - Mathematical Logic Quarterly 42 (1):369-378.
    We consider the decision problem for modules over a group ring ℤ[G], where G is a cyclic group of prime order. We show that it reduces to the same problem for a class of certain abelian structures, and we obtain some partial decidability results for this class.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  9
    On the Decidability of the Theories of the Arithmetic and Hyperarithmetic Degrees as Uppersemilattices.James S. Barnes - 2017 - Journal of Symbolic Logic 82 (4):1496-1518.
    We establish the decidability of the${{\rm{\Sigma }}_2}$theory of both the arithmetic and hyperarithmetic degrees in the language of uppersemilattices, i.e., the language with ≤, 0, and$\sqcup$. This is achieved by using Kumabe-Slaman forcing, along with other known results, to show given finite uppersemilattices${\cal M}$and${\cal N}$, where${\cal M}$is a subuppersemilattice of${\cal N}$, that every embedding of${\cal M}$into either degree structure extends to one of${\cal N}$iff${\cal N}$is an end-extension of${\cal M}$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  48.  7
    Decidability and Definability with Circumscription.John S. Schlipf - 1987 - Annals of Pure and Applied Logic 35 (2):173-191.
    We consider McCarthy's notions of predicate circumscription and formula circumscription. We show that the decision problems “does θ have a countably infinite minimal model” and “does φ hold in every countably infinite minimal model of θ” are complete Σ 1 2 and complete π 1 2 over the integers, for both forms of circumscription. The set of structures definable as first order definable subsets of countably infinite minimal models is the set of structures which are Δ 1 2 over the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  49.  11
    Decidability Problems in Languages with Henkin Quantifiers.Michał Krynicki & Marcin Mostowski - 1992 - Annals of Pure and Applied Logic 58 (2):149-172.
    Krynicki, M. and M. Mostowski, Decidability problems in languages with Henkin quantifiers, Annals of Pure and Applied Logic 58 149–172.We consider the language L with all Henkin quantifiers Hn defined as follows: Hnx1…xny1…yn φ iff f1…fnx1. ..xn φ, ...,fn). We show that the theory of equality in L is undecidable. The proof of this result goes by interpretation of the word problem for semigroups.Henkin quantifiers are strictly related to the function quantifiers Fn defined as follows: Fnx1…xny1…yn φ iff fx1…xn (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  50.  4
    Decidability of the Theory of Modules Over Prüfer Domains with Dense Value Groups.Lorna Gregory, Sonia L'Innocente & Carlo Toffalori - 2019 - Annals of Pure and Applied Logic 170 (12):102719.
    We provide algebraic conditions ensuring the decidability of the theory of modules over effectively given Prüfer (in particular Bézout) domains whose localizations at maximal ideals have dense value groups. For Bézout domains, these conditions are also necessary.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 556