BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yde Venema

Yde Venema appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer Sciencemath.LO

Catalog footprint

What is connected

7works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2016arXiv

Completeness of Flat Coalgebraic Fixpoint Logics

Modal fixpoint logics traditionally play a central role in computer science, in particular in artificial intelligence and concurrency. The mu-calculus and its relatives are among the most expressive logics of this type. However, popular fixpoint logics tend to trade expressivity for simplicity and readability, and in fact often live within the single variable fragment of the mu-calculus. The family of such flat fixpoint logics includes, e.g., LTL, CTL, and the logic of common knowledge. Extending this notion to the generic semantic framework of coalgebraic logic enables covering a wide range of logics beyond the standard mu-calculus including, e.g., flat fragments of the graded mu-calculus and the alternating-time mu-calculus (such as alternating-time temporal logic ATL), as well as probabilistic and monotone fixpoint logics. We give a generic proof of completeness of the Kozen-Park axiomatization for such flat coalgebraic fixpoint logics.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Expressiveness of the modal mu-calculus on monotone neighborhood structures

We characterize the expressive power of the modal mu-calculus on monotone neighborhood structures, in the style of the Janin-Walukiewicz theorem for the standard modal mu-calculus. For this purpose we consider a monadic second-order logic for monotone neighborhood structures. Our main result shows that the monotone modal mu-calculus corresponds exactly to the fragment of this second-order language that is invariant for neighborhood bisimulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Monadic Second-Order Logic and Bisimulation Invariance for Coalgebras

Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. Similar to well-known results for monadic second-order logic over trees, we provide a translation of this logic into a class of automata, relative to the class of coalgebras that admit a tree-like supporting Kripke frame. We then consider invariance under behavioral equivalence of formulas; more in particular, we investigate whether the coalgebraic mu-calculus is the bisimulation-invariant fragment of monadic second-order logic. Building on recent results by the third author we show that in order to provide such a coalgebraic generalization of the Janin-Walukiewicz Theorem, it suffices to find what we call an adequate uniform construction for the functor. As applications of this result we obtain a partly new proof of the Janin-Walukiewicz Theorem, and bisimulation invariance results for the bag functor (graded modal logic) and all exponential polynomial functors. Finally, we consider in some detail the monotone neighborhood functor, which provides coalgebraic semantics for monotone modal logic. It turns out that there is no adequate uniform construction for this functor, whence the automata-theoretic approach towards bisimulation invariance does not apply directly. This problem can be overcome if we consider global bisimulations between neighborhood models: one of our main technical results provides a characterization of the monotone modal mu-calculus extended with the global modalities, as the fragment of monadic second-order logic for the monotone neighborhood functor that is invariant for global bisimulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Uniform Interpolation for Coalgebraic Fixpoint Logic

We use the connection between automata and logic to prove that a wide class of coalgebraic fixpoint logics enjoys uniform interpolation. To this aim, first we generalize one of the central results in coalgebraic automata theory, namely closure under projection, which is known to hold for weak-pullback preserving functors, to a more general class of functors, i.e.; functors with quasi-functorial lax extensions. Then we will show that closure under projection implies definability of the bisimulation quantifier in the language of coalgebraic fixpoint logic, and finally we prove the uniform interpolation theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Weak MSO: Automata and Expressiveness Modulo Bisimilarity

We prove that the bisimulation-invariant fragment of weak monadic second-order logic (WMSO) is equivalent to the fragment of the modal $μ$-calculus where the application of the least fixpoint operator $μp.φ$ is restricted to formulas $φ$ that are continuous in $p$. Our proof is automata-theoretic in nature; in particular, we introduce a class of automata characterizing the expressive power of WMSO over tree models of arbitrary branching degree. The transition map of these automata is defined in terms of a logic $\mathrm{FOE}_1^\infty$ that is the extension of first-order logic with a generalized quantifier $\exists^\infty$, where $\exists^\infty x. ϕ$ means that there are infinitely many objects satisfying $ϕ$. An important part of our work consists of a model-theoretic analysis of $\mathrm{FOE}_1^\infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Completeness for the coalgebraic cover modality

We study the finitary version of the coalgebraic logic introduced by L. Moss. The syntax of this logic, which is introduced uniformly with respect to a coalgebraic type functor, required to preserve weak pullbacks, extends that of classical propositional logic with a so-called coalgebraic cover modality depending on the type functor. Its semantics is defined in terms of a categorically defined relation lifting operation. As the main contributions of our paper we introduce a derivation system, and prove that it provides a sound and complete axiomatization for the collection of coalgebraically valid inequalities. Our soundness and completeness proof is algebraic, and we employ Pattinson's stratification method, showing that our derivation system can be stratified in countably many layers, corresponding to the modal depth of the formulas involved. In the proof of our main result we identify some new concepts and obtain some auxiliary results of independent interest. We survey properties of the notion of relation lifting, induced by an arbitrary but fixed set functor. We introduce a category of Boolean algebra presentations, and establish an adjunction between it and the category of Boolean algebras. Given the fact that our derivation system involves only formulas of depth one, it can be encoded as a endo-functor on Boolean algebras. We show that this functor is finitary and preserves embeddings, and we prove that the Lindenbaum-Tarski algebra of our logic can be identified with the initial algebra for this functor.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Generalized powerlocales via relation lifting

This paper introduces an endofunctor $\VT$ on the category of frames, parametrized by an endofunctor $\T$ on the category $\Set$ that satisfies certain constraints. This generalizes Johnstone's construction of the Vietoris powerlocale, in the sense that his construction is obtained by taking for $\T$ the finite covariant power set functor. Our construction of the $\T$-powerlocale $\VT \bbL$ out of a frame $\bbL$ is based on ideas from coalgebraic logic and makes explicit the connection between the Vietoris construction and Moss's coalgebraic cover modality. We show how to extend certain natural transformations between set functors to natural transformations between $\T$-powerlocale functors. Finally, we prove that the operation $\VT$ preserves some properties of frames, such as regularity, zero-dimensionality, and the combination of zero-dimensionality and compactness.

0 citations0 reviewsNo code linkedOpen access