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

Dominique Duval

Dominique Duval 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.CTProgramming LanguagesDatabasesFormal Languages and Automata TheorySoftware Engineering

Catalog footprint

What is connected

18works
6topics
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

18 published item(s)

preprint2020arXiv

On foundational aspects of RDF and SPARQL

We consider the recommendations of the World Wide Web Consortium (W3C) about the Resource Description Framework (RDF) and the associated query language SPARQL. We propose a new formal framework based on category theory which provides clear and concise formal definitions of the main basic features of RDF and SPARQL. We propose to define the notions of RDF graphs as well as SPARQL basic graph patterns as objects of some nested categories. This allows one to clarify, in particular, the role of blank nodes. Furthermore, we consider basic SPARQL CONSTRUCT and SELECT queries and formalize their operational semantics following a novel algebraic graph transformation approach called POIM.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

AGREE -- Algebraic Graph Rewriting with Controlled Embedding (Long Version)

The several algebraic approaches to graph transformation proposed in the literature all ensure that if an item is preserved by a rule, so are its connections with the context graph where it is embedded. But there are applications in which it is desirable, for example when cloning an item, to specify different embeddings for the original and for the copy. Therefore we propose a conservative extension of these approaches where a rule can specify how the embedding of a preserved item should be changed, typically by removing certain connections.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Hilbert-Post completeness for the state and the exception effects

In this paper, we present a novel framework for studying the syntactic completeness of computational effects and we apply it to the exception effect. When applied to the states effect, our framework can be seen as a generalization of Pretnar's work on this subject. We first introduce a relative notion of Hilbert-Post completeness, well-suited to the composition of effects. Then we prove that the exception effect is relatively Hilbert-Post complete, as well as the "core" language which may be used for implementing it; these proofs have been formalized and checked with the proof assistant Coq.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Breaking a monad-comonad symmetry between computational effects

Computational effects may often be interpreted in the Kleisli category of a monad or in the coKleisli category of a comonad. The duality between monads and comonads corresponds, in general, to a symmetry between construction and observation, for instance between raising an exception and looking up a state. Thanks to the properties of adjunction one may go one step further: the coKleisli-on-Kleisli category of a monad provides a kind of observation with respect to a given construction, while dually the Kleisli-on-coKleisli category of a comonad provides a kind of construction with respect to a given observation. In the previous examples this gives rise to catching an exception and updating a state. However, the interpretation of computational effects is usually based on a category which is not self-dual, like the category of sets. This leads to a breaking of the monad-comonad duality. For instance, in a distributive category the state effect has much better properties than the exception effect. This remark provides a novel point of view on the usual mechanism for handling exceptions. The aim of this paper is to build an equational semantics for handling exceptions based on the coKleisli-on-Kleisli category of the monad of exceptions. We focus on n-ary functions and conditionals. We propose a programmer's language for exceptions and we prove that it has the required behaviour with respect to n-ary functions and conditionals.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Certified proofs in programs involving exceptions

Exception handling is provided by most modern programming languages. It allows to deal with anomalous or exceptional events which require special processing. In computer algebra, exception handling is an efficient way to implement the dynamic evaluation paradigm: for instance, in linear algebra, dynamic evaluation can be used for applying programs which have been written for matrices with coefficients in a field to matrices with coefficients in a ring. Thus, a proof system for computer algebra should include a treatement of exceptions, which must rely on a careful description of a semantics of exceptions. The categorical notion of monad can be used for formalizing the raising of exceptions: this has been proposed by Moggi and implemented in Haskell. In this paper, we provide a proof system for exceptions which involves both raising and handling, by extending Moggi's approach. Moreover, the core part of this proof system is dual to a proof system for side effects in imperative languages, which relies on the categorical notion of comonad. Both proof systems are implemented in the Coq proof assistant.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Program certification with computational effects

Dynamic evaluation is a paradigm in computer algebra which was introduced for computing with algebraic numbers. In linear algebra, for instance, dynamic evaluation can be used to apply programs which have been written for matrices with coefficients modulo some prime number to matrices with coefficients modulo some composite number. A way to implement dynamic evaluation in modern computing languages is to use the exceptions mechanism provided by the language. In this paper, we pesent a proof system for exceptions which involves both raising and handling, by extending Moggi's approach based on monads. Moreover, the core part of this proof system is dual to a proof system for the state effect in imperative languages, which relies on the categorical notion of comonad. Both proof systems are implemented in the Coq proof assistant, and they are combined in order to deal with both effects at the same time.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Transformation of Attributed Structures with Cloning (Long Version)

Copying, or cloning, is a basic operation used in the specification of many applications in computer science. However, when dealing with complex structures, like graphs, cloning is not a straightforward operation since a copy of a single vertex may involve (implicitly)copying many edges. Therefore, most graph transformation approaches forbid the possibility of cloning. We tackle this problem by providing a framework for graph transformations with cloning. We use attributed graphs and allow rules to change attributes. These two features (cloning/changing attributes) together give rise to a powerful formal specification approach. In order to handle different kinds of graphs and attributes, we first define the notion of attributed structures in an abstract way. Then we generalise the sesqui-pushout approach of graph transformation in the proposed general framework and give appropriate conditions under which attributed structures can be transformed. Finally, we instantiate our general framework with different examples, showing that many structures can be handled and that the proposed framework allows one to specify complex operations in a natural way.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Formal verification in Coq of program properties involving the global state effect

The syntax of an imperative language does not mention explicitly the state, while its denotational semantics has to mention it. In this paper we present a framework for the verification in Coq of properties of programs manipulating the global state effect. These properties are expressed in a proof system which is close to the syntax, as in effect systems, in the sense that the state does not appear explicitly in the type of expressions which manipulate it. Rather, the state appears via decorations added to terms and to equations. In this system, proofs of programs thus present two aspects: properties can be verified {\em up to effects} or the effects can be taken into account. The design of our Coq library consequently reflects these two aspects: our framework is centered around the construction of two inductive and dependent types, one for terms up to effects and one for the manipulation of decorations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Patterns for computational effects arising from a monad or a comonad

This paper presents equational-based logics for proving first order properties of programming languages involving effects. We propose two dual inference system patterns that can be instanciated with monads or comonads in order to be used for proving properties of different effects. The first pattern provides inference rules which can be interpreted in the Kleisli category of a monad and the coKleisli category of the associated comonad. In a dual way, the second pattern provides inference rules which can be interpreted in the coKleisli category of a comonad and the Kleisli category of the associated monad. The logics combine a 3-tier effect system for terms consisting of pure terms and two other kinds of effects called 'constructors/observers' and 'modifiers', and a 2-tier system for 'up-to-effects' and 'strong' equations. Each pattern provides generic rules for dealing with any monad (respectively comonad), and it can be extended with specific rules for each effect. The paper presents two use cases: a language with exceptions (using the standard monadic semantics), and a language with state (using the less standard comonadic semantics). Finally, we prove that the obtained inference system for states is Hilbert-Post complete.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Adjunctions for exceptions

An algebraic method is used to study the semantics of exceptions in computer languages. The exceptions form a computational effect, in the sense that there is an apparent mismatch between the syntax of exceptions and their intended semantics. We solve this apparent contradiction by efining a logic for exceptions with a proof system which is close to their syntax and where their intended semantics can be seen as a model. This requires a robust framework for logics and their morphisms, which is provided by categorical tools relying on adjunctions, fractions and limit sketches.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Graph rewriting with polarized cloning

We tackle the problem of graph transformation with a particular focus on node cloning. We propose a new approach to graph rewriting where nodes can be cloned zero, one or more times. A node can be cloned together with all its incident edges, with only its outgoing edges, with only its incoming edges or with none of its incident edges. We thus subsume previous works such as the sesqui-pushout, the heterogeneous pushout and the adaptive star grammars approaches. A rewrite rule is defined as a span where the right-hand and left-hand sides are graphs while the interface is a polarized graph. A polarized graph is a graph endowed with some annotations on nodes. The way a node is cloned is indicated by its polarization annotation. We use these annotations for designing graph transformation with polarized cloning. We show how a clone of a node can be built according to the different possible polarizations and define a rewrite step as a final pullback complement followed by a pushout. This is called the polarized sesqui-pushout approach. We also provide an algorithmic presentation of the proposed graph transformation with polarized cloning.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Categorical Abstract Rewriting Systems and Functoriality of Graph Transformation

Rewriting systems are often defined as binary relations over a given set of objects. This simple definition is used to describe various properties of rewriting such as termination, confluence, normal forms etc. In this paper, we introduce a new notion of abstract rewriting in the framework of categories. Then, we define the functoriality property of rewriting systems. This property is sometimes called vertical composition. We show that most of graph transformation systems are functorial and provide a counter-example of graph transformation systems which is not functorial.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

States and exceptions considered as dual effects

In this paper we consider the two major computational effects of states and exceptions, from the point of view of diagrammatic logics. We get a surprising result: there exists a symmetry between these two effects, based on the well-known categorical duality between products and coproducts. More precisely, the lookup and update operations for states are respectively dual to the throw and catch operations for exceptions. This symmetry is deeply hidden in the programming languages; in order to unveil it, we start from the monoidal equational logic and we add progressively the logical features which are necessary for dealing with either effect. This approach gives rise to a new point of view on states and exceptions, which bypasses the problems due to the non-algebraicity of handling exceptions.

0 citations0 reviewsNo code linkedOpen access