39 found
Order:
  1.  14
    Modal Logic.Yde Venema, Alexander Chagrov & Michael Zakharyaschev - 2000 - Philosophical Review 109 (2):286.
    Modern modal logic originated as a branch of philosophical logic in which the concepts of necessity and possibility were investigated by means of a pair of dual operators that are added to a propositional or first-order language. The field owes much of its flavor and success to the introduction in the 1950s of the “possible-worlds” semantics in which the modal operators are interpreted via some “accessibility relation” connecting possible worlds. In subsequent years, modal logic has received attention as an attractive (...)
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   71 citations  
  2. Canonical Formulas for K4. Part I: Basic Results.Michael Zakharyaschev - 1992 - Journal of Symbolic Logic 57 (4):1377-1402.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  3.  7
    Canonical Formulas for K4. Part II: Cofinal Subframe Logics.Michael Zakharyaschev - 1996 - Journal of Symbolic Logic 61 (2):421-449.
    Related Works: Part I: Michael Zakharyaschev. Canonical Formulas for $K4$. Part I: Basic Results. J. Symbolic Logic, Volume 57, Issue 4 , 1377--1402. Project Euclid: euclid.jsl/1183744119 Part III: Michael Zakharyaschev. Canonical Formulas for K4. Part III: The Finite Model Property. J. Symbolic Logic, Volume 62, Issue 3 , 950--975. Project Euclid: euclid.jsl/1183745306.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  4.  18
    Decidable Fragments of First-Order Temporal Logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
    In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of first-order temporal logics and of two-sorted (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  5.  40
    A Modal Logic Framework for Reasoning About Comparative Distances and Topology.Mikhail Sheremet, Frank Wolter & Michael Zakharyaschev - 2010 - Annals of Pure and Applied Logic 161 (4):534-559.
    We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  6.  7
    Advances in Modal Logic.Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev - 2002 - Bulletin of Symbolic Logic 8 (1):95-97.
  7.  22
    Products of 'Transitive' Modal Logics.David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2005 - Journal of Symbolic Logic 70 (3):993-1021.
    We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4,K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  8. Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
    The paper considers the set ML 1 of first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in ML 1 , which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  4
    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 expanding (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  10.  48
    Temporalising Tableaux.Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev - 2004 - Studia Logica 76 (1):91 - 134.
    As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  86
    The Undecidability of the Disjunction Property of Propositional Logics and Other Related Problems.Alexander Chagrov & Michael Zakharyaschev - 1993 - Journal of Symbolic Logic 58 (3):967-1002.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  12.  8
    G. E. Hughes and M. J. Cresswell. A New Introduction to Modal Logic. Routledge, London and New York1996, X + 421 Pp. [REVIEW]Michael Zakharyaschev - 1997 - Journal of Symbolic Logic 62 (4):1483-1484.
  13.  18
    Speaking About Transitive Frames in Propositional Languages.Yasuhito Suzuki, Frank Wolter & Michael Zakharyaschev - 1998 - Journal of Logic, Language and Information 7 (3):317-339.
    This paper is a comparative study of the propositional intuitionistic (non-modal) and classical modal languages interpreted in the standard way on transitive frames. It shows that, when talking about these frames rather than conventional quasi-orders, the intuitionistic language displays some unusual features: its expressive power becomes weaker than that of the modal language, the induced consequence relation does not have a deduction theorem and is not protoalgebraic. Nevertheless, the paper develops a manageable model theory for this consequence and its extensions (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  14.  3
    Axiomatizing the Monodic Fragment of First-Order Temporal Logic.Frank Wolter & Michael Zakharyaschev - 2002 - Annals of Pure and Applied Logic 118 (1-2):133-145.
    It is known that even seemingly small fragments of the first-order temporal logic over the natural numbers are not recursively enumerable. In this paper we show that the monodic fragment is an exception by constructing its finite Hilbert-style axiomatization. We also show that the monodic fragment with equality is not recursively axiomatizable.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  15.  5
    Kripke Completeness of Strictly Positive Modal Logics Over Meet-Semilattices with Operators.Stanislav Kikot, Agi Kurucz, Yoshihito Tanaka, Frank Wolter & Michael Zakharyaschev - 2019 - Journal of Symbolic Logic 84 (2):533-588.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  17
    A Logic for Metric and Topology.Frank Wolter & Michael Zakharyaschev - 2005 - Journal of Symbolic Logic 70 (3):795 - 828.
    We propose a logic for reasoning about metric spaces with the induced topologies. It combines the 'qualitative' interior and closure operators with 'quantitative' operators 'somewhere in the sphere of radius r.' including or excluding the boundary. We supply the logic with both the intended metric space semantics and a natural relational semantics, and show that the latter (i) provides finite partial representations of (in general) infinite metric models and (ii) reduces the standard '∈-definitions' of closure and interior to simple constraints (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  3
    Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
    The paper considers the set $\mathscr{M}\mathscr{L}_1$ of first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in $\mathscr{M}\mathscr{L}_1$, which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  18.  25
    Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables.Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev - 2005 - Bulletin of Symbolic Logic 11 (3):428-438.
    We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those (...)
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  19.  6
    Products of ‘Transitive’ Modal Logics.David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2005 - Journal of Symbolic Logic 70 (3):993-1021.
    We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4,K4] with product frames of arbitrary finite or infinite depth can be decidable. In particular, if.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  22
    Axiomatizing Distance Logics.Oliver Kutz, Holger Sturm, Nobu-Yuki Suzuki, Frank Wolter & Michael Zakharyaschev - 2002 - Journal of Applied Non-Classical Logics 12 (3-4):425-439.
    In [STU 00, KUT 03] we introduced a family of ‘modal' languages intended for talking about distances. These languages are interpreted in ‘distance spaces' which satisfy some of the standard axioms of metric spaces. Among other things, we singled out decidable logics of distance spaces and proved expressive completeness results relating classical and modal languages. The aim of this paper is to axiomatize the modal fragments of the semantically defined distance logics of [KUT 03] and give a new proof of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  21.  38
    The Greatest Extension of S4 Into Which Intuitionistic Logic is Embeddable.Michael Zakharyaschev - 1997 - Studia Logica 59 (3):345-358.
    This paper gives a characterization of those quasi-normal extensions of the modal system S4 into which intuitionistic propositional logic Int is embeddable by the Gödel translation. It is shown that, as in the normal case, the set of quasi-normal modal companions of Int contains the greatest logic, M*, for which, however, the analog of the Blok-Esakia theorem does not hold. M* is proved to be decidable and Halldén-complete; it has the disjunction property but does not have the finite model property.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  3
    Islands of Tractability for Relational Constraints: Towards Dichotomy Results for the Description of Logic EL.Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2010 - In Lev Beklemishev, Valentin Goranko & Valentin Shehtman (eds.), Advances in Modal Logic, Volume 8. CSLI Publications. pp. 271-291.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  5
    A Sufficient Condition For The Finite Model Property Of Modal Logics Above K4.Michael Zakharyaschev - 1993 - Logic Journal of the IGPL 1 (1):13-21.
  24.  5
    Topology, Connectedness, and Modal Logic.Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter & Michael Zakharyaschev - 2008 - In Carlos Areces & Robert Goldblatt (eds.), Advances in Modal Logic, Volume 7. CSLI Publications. pp. 151-176.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  58
    A Tableau Decision Algorithm for Modalized ALC with Constant Domains.Carsten Lutz, Holger Sturm, Frank Wolter & Michael Zakharyaschev - 2002 - Studia Logica 72 (2):199-232.
    The aim of this paper is to construct a tableau decision algorithm for the modal description logic K ALC with constant domains. More precisely, we present a tableau procedure that is capable of deciding, given an ALC-formula with extra modal operators (which are applied only to concepts and TBox axioms, but not to roles), whether is satisfiable in a model with constant domains and arbitrary accessibility relations. Tableau-based algorithms have been shown to be practical even for logics of rather high (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  26.  13
    Canonical Formulas for Modal and Superintuitionistic Logics: A Short Outline.Michael Zakharyaschev - 1997 - In M. de Rijke (ed.), Advances in Intensional Logic. Kluwer Academic Publishers. pp. 195--248.
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  27.  9
    Canonical Formulas for K4. Part III: The Finite Model Property.Michael Zakharyaschev - 1997 - Journal of Symbolic Logic 62 (3):950-975.
    Related Works: Part I: Michael Zakharyaschev. Canonical Formulas for $K4$. Part I: Basic Results. J. Symbolic Logic, Volume 57, Issue 4 , 1377--1402. Project Euclid: euclid.jsl/1183744119 Part II: Michael Zakharyaschev. Canonical Formulas for K4. Part II: Cofinal Subframe Logics. J. Symbolic Logic, Volume 61, Issue 2 , 421--449. Project Euclid: euclid.jsl/1183745008.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  28. Advances in Modal Logic.Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.) - 1998 - CSLI Publications.
    No categories
     
    Export citation  
     
    Bookmark   1 citation  
  29.  15
    Review: G. E. Hughes, M. J. Cresswell, A New Introduction to Modal Logic. [REVIEW]Michael Zakharyaschev - 1997 - Journal of Symbolic Logic 62 (4):1483-1484.
  30.  11
    A New Solution to a Problem of Hosoi and Ono.Michael Zakharyaschev - 1994 - Notre Dame Journal of Formal Logic 35 (3):450-457.
    This paper gives a new, purely semantic proof of the following theorem: if an intermediate propositional logic L has the disjunction property then a disjunction free formula is provable in L iff it is provable in intuitionistic logic. The main idea of the proof is to use the well-known semantic criterion of the disjunction property for "simulating" finite binary trees (which characterize the disjunction free fragment of intuitionistic logic) by general frames.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  5
    Canonical Formulas for K4. Part III: The Finite Model Property.Michael Zakharyaschev - 1997 - Journal of Symbolic Logic 62 (3):950-975.
    Related Works: Part I: Michael Zakharyaschev. Canonical Formulas for $K4$. Part I: Basic Results. J. Symbolic Logic, Volume 57, Issue 4, 1377--1402. Project Euclid: euclid.jsl/1183744119 Part II: Michael Zakharyaschev. Canonical Formulas for K4. Part II: Cofinal Subframe Logics. J. Symbolic Logic, Volume 61, Issue 2, 421--449. Project Euclid: euclid.jsl/1183745008.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  32.  21
    Multi-Dimensional Modal Logic, Maarten Marx and Yde Venema.Michael Zakharyaschev - 2000 - Journal of Logic, Language and Information 9 (1):128-131.
  33.  7
    A Logic For Metric And Topology.Frank Wolter & Michael Zakharyaschev - 2005 - Journal of Symbolic Logic 70 (3):795-828.
    In this paper we devise some technical tools for dealing with problems connected with the philosophical view usually called mathematical instrumentalism. These tools are interesting in their own right, independently of their philosophical consequences. For example, we show that even though the fragment of Peano's Arithmetic known as IΣ₁ is a conservative extension of the equational theory of Primitive Recursive Arithmetic, IΣ₁ has a super-exponential speed-up over PRA. On the other hand, theories studied in the Program of Reverse Mathematics that (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  34.  8
    Philadelphia, PA, USA May 18–20, 2011.Anjolina G. de Oliveira, Ruy de Queiroz, Rajeev Alur, Max Kanovich, John Mitchell, Vladimir Voevodsky, Yoad Winter & Michael Zakharyaschev - 2012 - Bulletin of Symbolic Logic 18 (1).
  35.  2
    A Note on Relativised Products of Modal Logics.Agi Kurucz & Michael Zakharyaschev - 2003 - In Philippe Balbiani, Nobu-Yuki Suzuki, Frank Wolter & Michael Zakharyaschev (eds.), Advances in Modal Logic, Volume 4. CSLI Publications. pp. 221-242.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  36. Mathematical Problems From Applied Logic I.Dov M. Gabbay, Sergei S. Goncharov & Michael Zakharyaschev - 2007 - Studia Logica 87 (2-3):363-367.
     
    Export citation  
     
    Bookmark  
  37. Advances in Modal Logic, Vol. 1.Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev - 2000 - Studia Logica 65 (3):440-442.
  38. Dynamic Description Logics.Frank Wolter & Michael Zakharyaschev - 2000 - In Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke & Heinrich Wansing (eds.), Advances in Modal Logic, Volume 2. CSLI Publications. pp. 449-463.
    No categories
     
    Export citation  
     
    Bookmark  
  39. Advances in Modal Logic, Volume 2.Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke & Heinrich Wansing (eds.) - 2001 - Center for the Study of Language and Inf.
    Modal Logic, originally conceived as the logic of necessity and possibility, has developed into a powerful mathematical and computational discipline. It is the main source of formal languages aimed at analyzing complex notions such as common knowledge and formal provability. Modal and modal-like languages also provide us with families of restricted description languages for relational and topological structures; they are being used in many disciplines, ranging from artificial intelligence, computer science and mathematics via natural language syntax and semantics to philosophy. (...)
     
    Export citation  
     
    Bookmark