Abstract
We introduce a path-based cyclic proof system for first-order $\mu $-calculus, the extension of first-order logic by second-order quantifiers for least and greatest fixed points of definable ...monotone functions. We prove soundness of the system and demonstrate it to be as expressive as the known trace-based cyclic systems of Dam and Sprenger. Furthermore, we establish cut-free completeness of our system for the fragment corresponding to the modal $\mu $-calculus.
We set up a generic framework for proving completeness results for variants of the modal mu-calculus, using tools from coalgebraic modal logic. We illustrate the method by proving two new ...completeness results: for the graded mu-calculus (which is equivalent to monadic second-order logic on the class of unranked tree models), and for the monotone modal mu-calculus.
Besides these main applications, our result covers the Kozen–Walukiewicz completeness theorem for the standard modal mu-calculus, as well as the linear-time mu-calculus and modal fixpoint logics on ranked trees. Completeness of the linear-time mu-calculus is known, but the proof we obtain here is different and places the result under a common roof with Walukiewicz' result.
Our approach combines insights from the theory of automata operating on potentially infinite objects, with methods from the categorical framework of coalgebra as a general theory of state-based evolving systems. At the interface of these theories lies the notion of a coalgebraic modal one-step language. One of our main contributions here is the introduction of the novel concept of a disjunctive basis for a modal one-step language. Generalizing earlier work, our main general result states that in case a coalgebraic modal logic admits such a disjunctive basis, then soundness and completeness at the one-step level transfer to the level of the full coalgebraic modal mu-calculus.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We show characterisation results for normalisation, head-normalisation, and strong normalisation for λ μ using intersection types. We reach these results for a strict notion of type assignment for λ ...μ that is the natural restriction of the domain-based system of van Bakel et al. (2011) for λ μ by limiting the type inclusion relation to just intersection elimination. We show that this system respects β μ-equality, by showing both soundness and completeness results. We then define a notion of reduction on derivations that corresponds to cut-elimination, and show that this is strongly normalisable.
We use this strong normalisation result to show an approximation result, and through that a characterisation of head-normalisation. Using the approximation result, we show that there is a very strong relation between the system of van Bakel et al. (2011) and ours.
We then introduce a notion of type assignment that eliminates ω as an assignable type, and show, using the strong normalisation result for derivation reduction, that all terms typeable in this system are strongly normalisable as well, and show that all strongly normalisable terms are typeable.
We conclude by adding type variables to our system, and show that system essentially is that of van Bakel (2010b).
We introduce a new game-theoretic semantics (GTS) for the modal mu-calculus. Our so-called bounded GTS replaces parity games with alternative evaluation games where only finite paths arise; infinite ...paths are not needed even when the considered transition system is infinite. The novel games offer alternative approaches to various constructions in the framework of the mu-calculus. While our main focus is introducing the new GTS, we also consider some applications to demonstrate its uses. For example, we consider a natural model transformation procedure that reduces model checking games to checking a single, fixed formula in the constructed models. We also use the GTS to identify new alternative variants of the mu-calculus, including close variants of the logic with PTime model checking; variants with iteration limited to finite ordinals; and other systems where the semantic or syntactic specification of the mu-calculus has been modified in a natural way suggested by the GTS.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Backward type inference for XML queries Im, Hyeonseung; Genevès, Pierre; Gesbert, Nils ...
Theoretical computer science,
07/2020, Volume:
823
Journal Article
Peer reviewed
Open access
Although XQuery is a statically typed, functional query language for XML data, some of its features such as upward and horizontal XPath axes are typed imprecisely. The main reason is that while the ...XQuery data model allows us to navigate upwards and between siblings from a given XML node, the type model, e.g., regular tree types, can describe only the subtree structure of the given node. To alleviate this limitation, precise forward type inference systems for XQuery were recently proposed using an extended regular type language that can describe not only a given XML node but also its context. In this paper, as a different approach, we propose a novel backward type inference system for XQuery, based on a type language extended with logical formulas. Our backward type inference system provides an exact typing result for XPath axes and a sound typing result for XQuery expressions.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The modal mu-calculus is a very expressive formalism extending basic modal logic with least and greatest fixpoint operators. In the seminal paper introducing the formalism in the shape known today, ...Kozen also proposed an elegant axiom system, and he proved a partial completeness result with respect to the Kripke-style semantics of the logic. The problem of proving Kozen's axiom system complete for the full language remained open for about a decade, until it was finally resolved by Walukiewicz. In this paper we develop a framework that will let us clarify and simplify parts of Walukiewicz' proof.
Our main contribution is to take the automata-theoretic viewpoint, already implicit in Walukiewicz' proof, much more seriously by bringing automata explicitly into the proof theory. Thus we further develop the theory of modal parity automata as a mathematical framework for proving results about the modal mu-calculus. Once the connection between automata and derivations is in place, large parts of the completeness proof can be reformulated as purely automata-theoretic theorems. From a conceptual viewpoint, our automata-theoretic approach lets us distinguish two key aspects of the mu-calculus: the one-step dynamics encoded by the modal operators, and the combinatorics involved in dealing with nested fixpoints. This “deconstruction” allows us to work with these two features in a largely independent manner.
More in detail, prominent roles in our proof are played by two classes of modal automata: next to the disjunctive automata that are known from the work of Janin & Walukiewicz, we introduce here the class of semi-disjunctive automata that roughly correspond to the fragment of the mu-calculus for which Kozen proved completeness. We will establish a connection between the proof theory of Kozen's system, and two kinds of games involving modal automata: a satisfiability game involving a single modal automaton, and a consequence game relating two such automata. In the key observations on these games we bring the dynamics and combinatorics of parity automata together again, by proving some results that witness the nice behaviour of disjunctive and semi-disjunctive automata in these games. As our main result we prove that every formula of the modal mu-calculus provably implies the translation of a disjunctive automaton; from this the completeness of Kozen's axiomatization is immediate.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In the present paper, the algorithmic correspondence theory developed in Conradie and Palmigiano 9 is extended to mu-calculi with a non-classical base. We focus in particular on the language of ...bi-intuitionistic modal mu-calculus. We enhance the algorithm ALBA introduced in Conradie and Palmigiano 9 so as to guarantee its success on the class of recursive mu-inequalities, which we introduce in this paper. Key to the soundness of this enhancement are the order-theoretic properties of the algebraic interpretation of the fixed point operators. We show that, when restricted to the Boolean setting, the recursive mu-inequalities coincide with the “Sahlqvist mu-formulas” defined in van Benthem, Bezhanishvili and Hodkinson 22.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Parameterised Boolean Equation Systems (PBESs) can be used to represent many different kinds of decision problems. Most notably, model checking and equivalence problems can be encoded in a PBES. ...Traditional techniques to solve PBESs, such as instantiation techniques, cannot deal with PBESs with an infinite data domain. We propose an approach that can solve PBESs with infinite data by computing the bisimulation quotient of the underlying graph structure. Furthermore, we show how this technique can be improved by repeatedly searching for finite proofs. We also apply knowledge of intermediate solutions in an early termination heuristic. Unlike existing approaches, our technique is not restricted to subfragments of PBESs. Compared to similar procedures that operate on behavioural models, our technique is also more general: it is not restricted to model checking with finite action sets. Experimental results show that our ideas work well in practice and support a wider range of models and properties than state-of-the-art techniques.
•Parameterised Boolean equation systems (PBES) can encode model checking problems.•A normal form for PBESs facilitates symbolic approaches such as partition refinement.•Symbolic partition refinement for PBESs enables infinite-state model checking.•The setting of PBESs allows several optimisations to the standard algorithm.•Symbolic partition refinement for PBESs is more scalable than existing techniques.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
