Search

We study the existence of finite characterisations for modal formulas. A finite characterisation of a modal formula φ is a finite collection of positive and negative examples that distinguishes φ from every other, non-equivalent modal formula, where an example is a finite pointed Kripke structure. This definition can be restricted to specific frame classes and to fragments of the modal language: a modal fragment ℒ admits finite characterisations with respect to a frame class ℱ if every formula φ ∈ ℒ has a finite characterisation with respect to ℒ consisting of examples that are based on frames in ℱ. Finite characterisations are useful for illustration, interactive specification and debugging of formal specifications, and their existence is a precondition for exact learnability with membership queries. We show that the full modal language admits finite characterisations with respect to a frame class ℱ only when the modal logic of ℱ is locally tabular. We then study which modal fragments, freely generated by some set of connectives, admit finite characterisations. Our main result is that the positive modal language without the truth-constants ⊤ and ⊥ admits finite characterisations w.r.t. the class of all frames. This result is essentially optimal: finite characterisability fails when the language is extended with the truth constant ⊤ or ⊥ or with all but very limited forms of negation. [ABSTRACT FROM AUTHOR]

Vector spaces contain a number of general structures that invite analysis in modal languages. The resulting logical systems provide an interesting counterpart to the much better-studied modal logics of topological spaces. In this programmatic paper, we investigate issues of definability and axiomatization using standard techniques for modal and hybrid languages. The analysis proceeds in stages. We first present a modal analysis of commutative groups that establishes our main techniques, next we introduce a new modal logic of linear dependence and independence in vector spaces and, finally, we study a modal logic for describing full-fledged vector spaces. While still far from covering every basic aspect of linear algebra, our discussion identifies several leads for more systematic research. [ABSTRACT FROM AUTHOR]

We give sound and complete axiomatizations for XPath with data tests by ‘equality’ or ‘inequality’, and containing the single ‘child’ axis. This data-aware logic predicts over data trees, which are tree-like structures whose every node contains a label from a finite alphabet and a data value from an infinite domain. The language allows us to compare data values of two nodes but cannot access the data values themselves (i.e. there is no comparison by constants). Our axioms are in the style of equational logic, extending the axiomatization of data-oblivious XPath, by B. ten Cate, T. Litak and M. Marx. We axiomatize the full logic with tests by ‘equality’ and ‘inequality’, and also a simpler fragment with ‘equality’ tests only. Our axiomatizations apply both to node expressions and path expressions. The proof of completeness relies on a novel normal form theorem for XPath with data tests. [ABSTRACT FROM AUTHOR]

We introduce a new hybrid modal logic HSML for reasoning about sabotage-style graph games with edge deletions and provide a complete Hilbert-style axiomatization. We extend the completeness analysis to protocol models with restrictions on available edge deletions and clarify the connections between HSML-style logics of edge deletions and recent modal logics for stepwise point deletion from graphs. [ABSTRACT FROM AUTHOR]

Modal logic with propositional quantifiers (i.e. second-order propositional modal logic (⁠|$\textsf {SOPML}$|⁠)) has been considered since the early time of modal logic. Its expressive power and complexity are high, and its van Benthem–Rosen theorem and Goldblatt–Thomason theorem have been proved by ten Cate (2006, J. Philos. Logic , 35, 209–223). However, the Sahlqvist theory of |$\textsf {SOPML}$| has not been considered in the literature. In the present paper, we fill in this gap. We develop the Sahlqvist correspondence theory for |$\textsf {SOPML}$|⁠ , which covers and properly extends existing Sahlqvist formulas in basic modal logic. We define the class of Sahlqvist formulas for |$\textsf {SOMPL}$| step by step in a hierarchical way, each formula of which is shown to have a first-order correspondent over Kripke frames effectively computable by an algorithm |$\textsf {ALBA}^{\textsf {SOMPL}}$|⁠. In addition, we show that certain |$\varPi _2$| -rules correspond to |$\varPi _2$| -Sahlqvist formulas in |$\textsf {SOMPL}$|⁠ , which further correspond to first-order conditions, and that even for very simple |$\textsf {SOMPL}$| Sahlqvist formulas, they could already be non-canonical. [ABSTRACT FROM AUTHOR]

This paper proposes different ways of modally defining properties related to the concept of balance in signed social networks where relations can be either positive or negative. The motivation is to be able to formally reason about the social phenomenon of group polarization based on balance theory. The starting point is a recently developed basic modal logic that axiomatizes the class of social networks that are balanced up to a certain degree. This property is not modally definable but can be captured using a deduction rule. In this work, we examine different possibilities for extending this basic language to define frame properties such as balance and related properties such as non-overlapping positive and negative relations and collective connectedness as axioms. Furthermore, we define the property of full balance rather than balanced-up-to-a-degree. We look into the complexity of the model checking problem and show a non-compactness result of the extended language. Along the way, we provide axioms for weak balance. We also look at a full hybrid extension and reason about network changes with dynamic modalities. Then, to explore the measures of how far a network is from polarization, we consider variations of measures in relation to balance. [ABSTRACT FROM AUTHOR]

The celebrated van Benthem characterization theorem states that on Kripke structures modal logic is the bisimulation-invariant fragment of first-order logic. In this paper, we prove an analogue of the van Benthem characterization theorem for models based on descriptive general frames. This is an important class of general frames for which every modal logic is complete. These frames can be represented as Stone spaces equipped with a 'continuous' binary relation. The proof of our theorem generalizes Rosen's proof of the van Benthem theorem for finite frames and uses as an essential technique a new notion of descriptive unravelling. We also develop a basic model theory for descriptive general frames and show that in many ways it behaves like the model theory of finite structures. In particular, we prove the failure of the compactness theorem, of the Beth definability theorem, of the Craig interpolation theorem and of the upward Löwenheim–Skolem theorem. 1 [ABSTRACT FROM AUTHOR]

In this article, we start with a two-player game that models communication under adverse circumstances in everyday life and study it from the perspective of a modal logic of graphs, where links can be deleted locally according to definitions available to the adversarial player. We first introduce a new language, semantics and some typical validities. We then formulate a new type of first-order translation for this modal logic and prove its correctness. Then, a novel notion of bisimulation is proposed that leads to a characterization theorem for the logic as a fragment of first-order logic, and a further investigation is made of its expressive power against hybrid modal languages. Next, we discuss how to axiomatize this logic of link deletion, using dynamic-epistemic logics as a contrast. Finally, we show that our new modal logic lacks both the tree model property and the finite model property and that its satisfiability problem is undecidable. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a logical approach to the important notion of closeness, which has not received much attention in the literature. Our notion of closeness is based on the so-called proximity intervals , which will be used to decide the elements that are close to each other. Some of the intuitions of this definition are explained on the basis of examples. We prove the decidability of the recently introduced multimodal logic for closeness and, then, we show some capabilities of the logic with respect to expressivity in order to denote particular positions of the proximity intervals. [ABSTRACT FROM AUTHOR]

Bull's theorem states that all axiomatic extensions of the modal logic S4.3 have the finite model property. We show that this fails for hybrid logic, by defining an axiomatic extension of the hybrid companion of S4.3, which has only infinite Kripke models. In contrast, by considering hybrid algebraic semantics or, dually, semantics based on two-sorted general frames, we are able to prove analogues of Bull's theorem for two hybrid languages. [ABSTRACT FROM AUTHOR]

It is a landmark theorem of McKinsey and Tarski that if we interpret modal diamond as closure (and hence modal box as interior), then S4 is the logic of any dense-in-itself metrizable space. The McKinsey-Tarski Theorem relies heavily on a metric that gives rise to the topology. We give a new and more topological proof of the theorem, utilizing Bing’s Metrization Theorem. [ABSTRACT FROM AUTHOR]

Relation-changing modal logics (RC for short) are extensions of the basic modal logic with dynamic operators that modify the accessibility relation of a model during the evaluation of a formula. These languages are equipped with dynamic modalities that are able e.g. to delete, add and swap edges in the model, both locally and globally. We study the satisfiability problem for some of these logics. We first show that they can be translated into hybrid logic. As a result, we can transfer some results from hybrid logics to RC. We discuss in particular decidability for some fragments. We then show that satisfiability is, in general, undecidable for all the languages introduced, via translations from memory logics. [ABSTRACT FROM AUTHOR]

The paper considers modal logics of products of neighbourhood frames. The n-product of modal logics is the logic of all products of neighbourhood frames of the corresponding logics. We find the n-product of any two pretransitive Horn axiomatizable logics. As a corollary, we find the d-logic of products of topological spaces from some classes of topological spaces. [ABSTRACT FROM AUTHOR]

This article models collective decision making scenarios by using a priority-based aggregation procedure, the so-called lexicographic method, to represent a form of reliability-based 'deliberation'. More precisely, it considers agents with a preference ordering over a set of objects and a reliability ordering over the agents themselves, providing a logical framework describing the way in which the public and simultaneous announcement of the individual preferences leads to individual preference upgrade. The main results are the definitions of this lexicographic upgrade for diverse types of reliability relations (in particular, the preorder and total preorder cases), a sound and complete axiom system for a language describing the effects of such upgrades, and the definitions for non-public variations. [ABSTRACT FROM AUTHOR]

Coalgebraic modal logic serves as a unifying framework to study a wide range of modal logics beyond the relational realm, including probabilistic and graded logics as well as conditional logics and logics based on neighbourhoods and games. Coalgebraic predicate logic (CPL), a generalization of a neighbourhood-based first-order logic introduced by Chang, has been identified as a natural first-order extension of coalgebraic modal logic, which in particular coincides with the standard first-order correspondence language when instantiated to Kripke-style relational modal operators. Here, we generalize to the CPL setting the classical van Benthem/Rosen theorem stating that both over arbitrary and over finite models, modal logic is precisely the bisimulation-invariant fragment of first-order logic. As instances of this generic result, we obtain corresponding characterizations for, e.g. conditional logic, neighbourhood logic (i.e. classical modal logic) and monotone modal logic. [ABSTRACT FROM AUTHOR]

Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A well-known example from the literature on intuitionistic logic is the class of Medvedev frames $${\langle W, R\rangle}$$ where W is the set of nonempty subsets of some nonempty finite set S, and xRy iff $${x\supseteq y}$$ , or more liberally, where $${\langle W, R\rangle}$$ is isomorphic as a directed graph to $${\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle}$$ . Prucnal (Stud Logica 38(3):247-262, 1979) proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those y such that $${x\not= y}$$ ), or a complement modality (for quantifying over those y such that $${x\not\supseteq y}$$ ). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable-which would answer the open question of whether Medvedev's (Sov Math Dokl 7:857-860, 1966) 'logic of finite problems' is decidable-or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frame-incomplete logics. [ABSTRACT FROM AUTHOR]

We introduce a new Gentzen-style framework of grafted hypersequents that combines the formalism of nested sequents with that of hypersequents. To illustrate the potential of the framework, we present novel calculi for the modal logics K5 and KD5, as well as for extensions of the modal logics K and KD with the axiom for shift reflexivity. The latter of these extensions is also known as SDL+ in the context of deontic logic. All our calculi enjoy syntactic cut-elimination and can be used in backwards proof search procedures of optimal complexity. The tableaufication of the calculi for K5 and KD5 yields simplified prefixed tableau calculi for these logic reminiscent of the simplified tableau system for S5, which might be of independent interest. [ABSTRACT FROM AUTHOR]

Following a result by De Rijke for modal logic, it is shown that the basic weak entailment model-theoretic language with absurdity is the maximal model-theoretic language having (i) the finite occurrence property, (ii) preservation under relevant directed bisimulations and (iii) the finite depth property. This can be seen as a generalized preservation theorem characterizing propositional weak entailment formulas among formulas of other model-theoretic languages. [ABSTRACT FROM AUTHOR]

The celebrated theorem proved by Goldblatt and Thomason in 1974 gives necessary and sufficient conditions for an elementary class of Kripke frames to be modally definable. Here we obtain a local analogue of this result, which deals with modal definability of classes of pointed frames. Furthermore, we generalize it to the case of n-frames, which are frames with n distinguished worlds. For talking about n-frames, we generalize modal formulas to modal expressions. While a modal formula is evaluated at a single world of a model, a modal expression with n individual variables is evaluated at an n-tuple of worlds, just as a first-order formula with n free variables. We introduce operations on n-frames that preserve validity of modal expressions, and show that closure under these operations is a necessary and sufficient condition for an elementary class of n-frames to be modally definable. We also discuss the relationship between modal expressions and hybrid logic and leave open questions. [ABSTRACT FROM AUTHOR]

In this paper we develop the theoretical foundations to exploit symmetries in modal logics. We generalize the notion of symmetries of propositional formulas in conjunctive normal form to modal formulas using the framework provided by coinductive modal models introduced in [5]. Hence, the results apply to a wide class of modal logics including, for example, hybrid logics. We present two graph constructions that enable the reduction of symmetry detection in modal formulas to the graph automorphism detection problem, and we evaluate the graph constructions on modal benchmarks. [ABSTRACT FROM AUTHOR]

We study dynamic modal operators that can change the accessibility relation of a model during the evaluation of a formula. In particular, we extend the basic modal language with modalities that are able to delete, add or swap an edge between pairs of elements of the domain. We define a generic framework to characterize this kind of operations. First, we investigate relation-changing modal logics as fragments of classical logics. Then, we use the new framework to get a suitable notion of bisimulation for the logics introduced, and we investigate their expressive power. Finally, we show that the complexity of the model checking problem for the particular operators introduced is PSPACE-complete, and we study two subproblems of model checking: formula complexity and program complexity. [ABSTRACT FROM AUTHOR]

In this article, we discuss a well-known self-referential paradox in epistemic game theory, the Brandenburger–Keisler paradox. We approach the paradox from two different perspectives, non-well-founded set theory and paraconsistent logic, and provide models in which the paradox is solved. [ABSTRACT FROM AUTHOR]

It is a celebrated result of McKinsey and Tarski [28] that S4 is the logic of the closure algebra Χ+ over any dense-in-itself separable metrizable space. In particular, S4 is the logic of the closure algebra over the reals R, the rationals Q, or the Cantor space C. By [5], each logic above S4 that has the finite model property is the logic of a subalgebra of Q+, as well as the logic of a subalgebra of C+. This is no longer true for R, and the main result of [5] states that each connected logic above S4 with the finite model property is the logic of a subalgebra of the closure algebra R+.In this paper we extend these results to all logics above S4. Namely, for a normal modal logic L, we prove that the following conditions are equivalent: (i) L is above S4, (ii) L is the logic of a subalgebra of Q+, (iii) L is the logic of a subalgebra of C+. We introduce the concept of a well-connected logic above S4 and prove that the following conditions are equivalent: (i) L is a well-connected logic, (ii) L is the logic of a subalgebra of the closure algebra $\xi _2^ + $ over the infinite binary tree, (iii) L is the logic of a subalgebra of the closure algebra ${\bf{L}}_2^ + $ over the infinite binary tree with limits equipped with the Scott topology. Finally, we prove that a logic L above S4 is connected iff L is the logic of a subalgebra of R+, and transfer our results to the setting of intermediate logics.Proving these general completeness results requires new tools. We introduce the countable general frame property (CGFP) and prove that each normal modal logic has the CGFP. We introduce general topological semantics for S4, which generalizes topological semantics the same way general frame semantics generalizes Kripke semantics. We prove that the categories of descriptive frames for S4 and descriptive spaces are isomorphic. It follows that every logic above S4 is complete with respect to the corresponding class of descriptive spaces. We provide several ways of realizing the infinite binary tree with limits, and prove that when equipped with the Scott topology, it is an interior image of both C and R. Finally, we introduce gluing of general spaces and prove that the space obtained by appropriate gluing involving certain quotients of L2 is an interior image of R. [ABSTRACT FROM PUBLISHER]

We investigate dynamic modal operators that can change the model during evaluation. We define the logic SL by extending the basic modal language with the modality, which is a diamond operator that in addition has the ability to invert pairs of related elements in the domain while traversing an edge of the accessibility relation. SL is very expressive: it fails to have the finite and the tree model property. We show that SL is equivalent to a fragment of first-order logic by providing a satisfiability preserving translation. In addition, we provide an equivalence preserving translation from SL to the hybrid logic H(:,↓ ). We also define a suitable notion of bisimulation for SL and investigate its expressive power, showing that it lies strictly between the basic modal logic and H(:,↓ ). We finally show that its model checking problem is PSpace-complete and its satisfiability problem is undecidable. [ABSTRACT FROM PUBLISHER]

Hybrid logic is an extension of modal logic which allows us to refer explicitly to points of the model in the syntax of formulas. It is easy to justify interest in hybrid logic on applied grounds, with the usefulness of the additional expressive power. For example, when reasoning about time one often wants to build up a series of assertions about what happens at a particular instant, and standard modal formalisms do not allow this. What is less obvious is that the route hybrid logic takes to overcome this problem often actually improves the behaviour of the underlying modal formalism. For example, it becomes far simpler to formulate proof-systems for hybrid logic, and completeness results can be proved of a generality that is simply not available in modal logic. That is, hybridization is a systematic way of remedying a number of known deficiencies of modal logic. First-order hybrid logic is obtained by adding first-order machinery to propositional hybrid logic, or equivalently, by adding hybrid-logical machinery to first-order modal logic. In this short paper we introduce first-order hybrid logic and we give a survey of work in the area. [ABSTRACT FROM AUTHOR]

We prove the undecidability of Core XPath 1.0 (CXP) [G. Gottlob and C. Koch, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS ’02 (Copenhagen, July 2002). IEEE CS Press (2002) 189–202.] extended with an Inflationary Fixed Point (IFP) operator. More specifically, we prove that the satisfiability problem of this language is undecidable. In fact, the fragment of CXP+IFP containing only the self and descendant axes is already undecidable. [ABSTRACT FROM PUBLISHER]

In previous works, we presented a modification of the usual possible world semantics by introducing an independent temporal structure in each world and using accessibility functions to represent the relation among them. Different properties ofthe accessibility functions (being injective, surjective, increasing, etc.) have been considered and axiomatic systems (called functional) which define these properties have been given. Only a few ofthese systems have been proved tobe complete. The aim ofthis paper is to make a progress in the study ofcompleteness for functional systems. For this end, we use indexes as names for temporal flows and give new proofs of completeness. Specifically, we focus our attention on the system which defines injectivity, because the system which defines this property without using indexes was proved to be incomplete in previous works. The only system considered which remains incomplete is the one which defines surjectivity, even ifwe consider a sequence ofnatural extensions ofthe previous one (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex (computationally) it is to use these logics to actually test whether a given graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal (NP) complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic. [ABSTRACT FROM PUBLISHER]

In Artificial Intelligence there is a need for reasoning about continuous processes, where assertions refer to time intervals rather than time points. Taking our lead from van Benthem's treatment of interval temporal structures and Halpern and Shoham's work on intervals, we present a interval temporal logic with two binary relations, precedence and inclusion. We study the logic in its full generality without making any assumptions about the underlying nature of time, be it discrete or dense, linear or branching. We identify two general classes of interval temporal structures, minimal interval structures and van Benthem minimal interval structures. We show that in our interval temporal language, the two classes in fact have the same logic. We go on to prove that the logic of minimal interval structures is complete and decidable, possessing the finite model property, and that the satisfiability problem is PSPACE-complete. In order to establish the complexity result we extend the tableau method introduced by Horrocks et al., which treats transitive and inverse relations only, to also incorporate interaction between relations. We go on to identify some important limitations in the expressive power of our logic, before concluding the paper by raising a number of interesting questions that follow from our work. [ABSTRACT FROM AUTHOR]

We define for every Kripke complete modal logic L its hybrid companion LH and investigate which properties transfer from L to LH. For a specific class of logics, we present a satisfiability-preserving translation from LH to L. We prove that for this class of logics, complexity, (uniform) interpolation, and finite axiomatization transfer from L to LH. We also provide examples showing that, in general, none of complexity, decidability, the finite model property or the Beth property transfer. [ABSTRACT FROM PUBLISHER]