26 found
Order:
See also
Valentin Goranko
Stockholm University
  1.  59
    Modal Logic with Names.George Gargov & Valentin Goranko - 1993 - Journal of Philosophical Logic 22 (6):607 - 636.
    We investigate an enrichment of the propositional modal language L with a "universal" modality ■ having semantics x ⊧ ■φ iff ∀y(y ⊧ φ), and a countable set of "names" - a special kind of propositional variables ranging over singleton sets of worlds. The obtained language ℒ $_{c}$ proves to have a great expressive power. It is equivalent with respect to modal definability to another enrichment ℒ(⍯) of ℒ, where ⍯ is an additional modality with the semantics x ⊧ ⍯φ (...)
    Download  
     
    Export citation  
     
    Bookmark   29 citations  
  2.  23
    Elementary Canonical Formulae: Extending Sahlqvist’s Theorem.Valentin Goranko & Dimiter Vakarelov - 2006 - Annals of Pure and Applied Logic 141 (1):180-217.
    We generalize and extend the class of Sahlqvist formulae in arbitrary polyadic modal languages, to the class of so called inductive formulae. To introduce them we use a representation of modal polyadic languages in a combinatorial style and thus, in particular, develop what we believe to be a better syntactic approach to elementary canonical formulae altogether. By generalizing the method of minimal valuations à la Sahlqvist–van Benthem and the topological approach of Sambin and Vaccaro we prove that all inductive formulae (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  3.  32
    Hierarchies of Modal and Temporal Logics with Reference Pointers.Valentin Goranko - 1996 - Journal of Logic, Language and Information 5 (1):1-24.
    We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and (...)
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  4.  70
    A Road Map of Interval Temporal Logics and Duration Calculi.Valentin Goranko, Angelo Montanari & Guido Sciavicco - 2004 - Journal of Applied Non-Classical Logics 14 (1-2):9-54.
    We survey main developments, results, and open problems on interval temporal logics and duration calculi. We present various formal systems studied in the literature and discuss their distinctive features, emphasizing on expressiveness, axiomatic systems, and (un)decidability results.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  57
    The Craig Interpolation Theorem for Prepositional Logics with Strong Negation.Valentin Goranko - 1985 - Studia Logica 44 (3):291 - 317.
    This paper deals with, prepositional calculi with strong negation (N-logics) in which the Craig interpolation theorem holds. N-logics are defined to be axiomatic strengthenings of the intuitionistic calculus enriched with a unary connective called strong negation. There exists continuum of N-logics, but the Craig interpolation theorem holds only in 14 of them.
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  6.  24
    Modal Logics for Parallelism, Orthogonality, and Affine Geometries.Philippe Balbiani & Valentin Goranko - 2002 - Journal of Applied Non-Classical Logics 12 (3-4):365-397.
    We introduce and study a variety of modal logics of parallelism, orthogonality, and affine geometries, for which we establish several completeness, decidability and complexity results and state a number of related open, and apparently difficult problems. We also demonstrate that lack of the finite model property of modal logics for sufficiently rich affine or projective geometries (incl. the real affine and projective planes) is a rather common phenomenon.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  7.  27
    From Linear to Branching-Time Temporal Logics: Transfer of Semantics and Definability.Valentin Goranko & Alberto Zanardo - 2007 - Logic Journal of the IGPL 15 (1):53-76.
    This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for possible paths. We then consider (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  51
    Axiomatizations with Context Rules of Inference in Modal Logic.Valentin Goranko - 1998 - Studia Logica 61 (2):179-197.
    A certain type of inference rules in modal logics, generalizing Gabbay's Irreflexivity rule, is introduced and some general completeness results about modal logics axiomatized with such rules are proved.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  9.  52
    The Basic Algebra of Game Equivalences.Valentin Goranko - 2003 - Studia Logica 75 (2):221-238.
    We give a complete axiomatization of the identities of the basic game algebra valid with respect to the abstract game board semantics. We also show that the additional conditions of termination and determinacy of game boards do not introduce new valid identities. En route we introduce a simple translation of game terms into plain modal logic and thus translate, while preserving validity both ways game identities into modal formulae. The completeness proof is based on reduction of game terms to a (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  24
    Optimal Decision Procedures for Satisfiability in Fragments of Alternating-Time Temporal Logics.Valentin Goranko & Steen Vester - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. College Publications. pp. 234-253.
    We consider several natural fragments of the alternating-time temporal logics ATL* and ATL with restrictions on the nesting between temporal operators and strategic quantifiers. We develop optimal decision procedures for satisfiability in these fragments, showing that they have much lower complexities than the full languages. In particular, we prove that the satisfiability problem for state formulae in the full `strategically flat' fragment of ATL* is PSPACE-complete, whereas the satisfiability problems in the flat fragments of ATL and ATL$^{+}$ are $\Sigma^P_3$-complete. We (...)
    Download  
     
    Export citation  
     
    Bookmark  
  11.  14
    Algorithmic Correspondence and Completeness in Modal Logic. IV. Semantic Extensions of SQEMA.Willem Conradie & Valentin Goranko - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):175-211.
    In a previous work we introduced the algorithm \SQEMA\ for computing first-order equivalents and proving canonicity of modal formulae, and thus established a very general correspondence and canonical completeness result. \SQEMA\ is based on transformation rules, the most important of which employs a modal version of a result by Ackermann that enables elimination of an existentially quantified predicate variable in a formula, provided a certain negative polarity condition on that variable is satisfied. In this paper we develop several extensions of (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  40
    Temporal Logics with Reference Pointers and Computation Tree Logics.Valentin Goranko - 2000 - Journal of Applied Non-Classical Logics 10 (3):221-242.
    A complete axiomatic system CTL$_{rp}$ is introduced for a temporal logic for finitely branching $\omega^+$-trees in a temporal language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL$^{*}$ into CTL$_{rp}$. In particular, that yields a complete axiomatization for the translations of all valid CTL$^{*}$-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a way more expressive medium for reasoning (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  13.  16
    Sahlqvist Formulas Unleashed in Polyadic Modal Languages.Valentin Goranko & Dimiter Vakarelov - 2002 - In Frank Wolter, Heinrich Wansing, Maarten de Rijke & Michael Zakharyaschev (eds.), Advances in Modal Logic, Volume 3. World Scientific. pp. 221-240.
    We propose a generalization of Sahlqvist formulae to polyadic modal languages by representing modal polyadic languages in a combinatorial style and thus, in particular, developing what we believe to be the right approach to Sahlqvist formulae at all. The class of polyadic Sahlqvist formulae PSF defined here expands essentially the so far known one. We prove first-order definability and canonicity for the class PSF.
    Download  
     
    Export citation  
     
    Bookmark  
  14.  20
    Modal Definability in Enriched Languages.Valentin Goranko - 1989 - Notre Dame Journal of Formal Logic 31 (1):81-105.
    The paper deals with polymodal languages combined with standard semantics defined by means of some conditions on the frames. So, a notion of "polymodal base" arises which provides various enrichments of the classical modal language. One of these enrichments, viz. the base £(R,-R), with modalities over a relation and over its complement, is the paper's main paradigm. The modal definability (in the spirit of van Benthem's correspondence theory) of arbitrary and ~-elementary classes of frames in this base and in some (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  15.  17
    Classes and Theories of Trees Associated with a Class of Linear Orders.Valentin Goranko & Ruaan Kellerman - 2011 - Logic Journal of the IGPL 19 (1):217-232.
    Given a class of linear order types C, we identify and study several different classes of trees, naturally associated with C in terms of how the paths in those trees are related to the order types belonging to C. We investigate and completely determine the set-theoretic relationships between these classes of trees and between their corresponding first-order theories. We then obtain some general results about the axiomatization of the first-order theories of some of these classes of trees in terms of (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  14
    Algorithmic Correspondence and Completeness in Modal Logic. V. Recursive Extensions of SQEMA.Willem Conradie, Valentin Goranko & Dimitar Vakarelov - 2010 - Journal of Applied Logic 8 (4):319-333.
    The previously introduced algorithm \sqema\ computes first-order frame equivalents for modal formulae and also proves their canonicity. Here we extend \sqema\ with an additional rule based on a recursive version of Ackermann's lemma, which enables the algorithm to compute local frame equivalents of modal formulae in the extension of first-order logic with monadic least fixed-points \mffo. This computation operates by transforming input formulae into locally frame equivalent ones in the pure fragment of the hybrid mu-calculus. In particular, we prove that (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  14
    Modal Logic and Universal Algebra I: Modal Axiomatizations of Structures.Valentin Goranko & Dimiter Vakarelov - 2000 - In Michael Zakharyaschev, Krister Segerberg, Maarten de Rijke & Heinrich Wansing (eds.), Advances in Modal Logic, Volume 2. CSLI Publications. pp. 265-292.
    We study the general problem of axiomatizing structures in the framework of modal logic and present a uniform method for complete axiomatization of the modal logics determined by a large family of classes of structures of any signature.
    Download  
     
    Export citation  
     
    Bookmark  
  18.  26
    Hyperboolean Algebras and Hyperboolean Modal Logic.Valentin Goranko & Dimiter Vakarelov - 1999 - Journal of Applied Non-Classical Logics 9 (2):345-368.
    Hyperboolean algebras are Boolean algebras with operators, constructed as algebras of complexes (or, power structures) of Boolean algebras. They provide an algebraic semantics for a modal logic (called here a {\em hyperboolean modal logic}) with a Kripke semantics accordingly based on frames in which the worlds are elements of Boolean algebras and the relations correspond to the Boolean operations. We introduce the hyperboolean modal logic, give a complete axiomatization of it, and show that it lacks the finite model property. The (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  19.  92
    Logic for Physical Space: From Antiquity to Present Days.Marco Aiello, Guram Bezhanishvili, Isabelle Bloch & Valentin Goranko - 2012 - Synthese 186 (3):619-632.
    Since the early days of physics, space has called for means to represent, experiment, and reason about it. Apart from physicists, the concept of space has intrigued also philosophers, mathematicians and, more recently, computer scientists. This longstanding interest has left us with a plethora of mathematical tools developed to represent and work with space. Here we take a special look at this evolution by considering the perspective of Logic. From the initial axiomatic efforts of Euclid, we revisit the major milestones (...)
    Download  
     
    Export citation  
     
    Bookmark  
  20.  42
    Refutation Systems in Modal Logic.Valentin Goranko - 1994 - Studia Logica 53 (2):299 - 324.
    Complete deductive systems are constructed for the non-valid (refutable) formulae and sequents of some propositional modal logics. Thus, complete syntactic characterizations in the sense of Lukasiewicz are established for these logics and, in particular, purely syntactic decision procedures for them are obtained. The paper also contains some historical remarks and a general discussion on refutation systems.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  21.  29
    The Modal Logic of the Countable Random Frame.Valentin Goranko & Bruce Kapron - 2003 - Archive for Mathematical Logic 42 (3):221-243.
    We study the modal logic M L r of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e. the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give a sound and complete axiomatization of M L r and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  28
    Strategic Commitment and Release in Logics for Multi-Agent Systems.Thomas Ågotnes, Valentin Goranko & Wojciech Jamroga - manuscript
    In this paper we analyze how the semantics of the Alternating-time Temporal Logic ATL$^*$ deals with agents' commitments to strategies in the process of formula evaluation. In (\acro{atl}$^*$), one can express statements about the strategic ability of an agent (or a coalition of agents) to achieve a goal $\phi$ such as: ``agent $i$ can choose a strategy such that, if $i$ follows this strategy then, no matter what other agents do, $\phi$ will always be true''. However, strategies in \acro{atl} are (...)
    Download  
     
    Export citation  
     
    Bookmark  
  23.  48
    Tableaux-Based Decision Method for Single-Agent Linear Time Synchronous Temporal Epistemic Logics with Interacting Time and Knowledge.Mai Ajspur & Valentin Goranko - 2013 - In Kamal Lodaya (ed.), Logic and its Applications. Springer. pp. 80--96.
    Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with interactions between time and (...)
    Download  
     
    Export citation  
     
    Bookmark  
  24.  44
    Model-Checking CTL* Over Flat Presburger Counter Systems.Stéphane Demri, Alain Finkel, Valentin Goranko & Govert van Drimmelen - 2010 - Journal of Applied Non-Classical Logics 20 (4):313-344.
    This paper concerns model-checking of fragments and extensions of CTL* on infinite-state Presburger counter systems, where the states are vectors of integers and the transitions are determined by means of relations definable within Presburger arithmetic. In general, reachability properties of counter systems are undecidable, but we have identified a natural class of admissible counter systems (ACS) for which we show that the quantification over paths in CTL* can be simulated by quantification over tuples of natural numbers, eventually allowing translation of (...)
    Download  
     
    Export citation  
     
    Bookmark  
  25.  19
    Proving Unprovability in Some Normal Modal Logics.Valentin Goranko - 1991 - Bulletin of the Section of Logic 20 (1):23-29.
    This note considers deductive systems for the operator a of unprovability in some particular propositional normal modal logics. We give thus complete syntactic characterization of these logics in the sense of Lukasiewicz: for every formula  either `  or a  (but not both) is derivable. In particular, purely syntactic decision procedure is provided for the logics under considerations.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  26.  18
    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.
    Download  
     
    Export citation  
     
    Bookmark