Author name cluster

Vincent Penelle

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

MFCS Conference 2019 Conference Paper

On Synthesis of Resynchronizers for Transducers

Sougata Bose
Shankara Narayanan Krishna
Anca Muscholl
Vincent Penelle
Gabriele Puppis

We study two formalisms that allow to compare transducers over words under origin semantics: rational and regular resynchronizers, and show that the former are captured by the latter. We then consider some instances of the following synthesis problem: given transducers T_1, T_2, construct a rational (resp. regular) resynchronizer R, if it exists, such that T_1 is contained in R(T_2) under the origin semantics. We show that synthesis of rational resynchronizers is decidable for functional, and even finite-valued, one-way transducers, and undecidable for relational one-way transducers. In the two-way setting, synthesis of regular resynchronizers is shown to be decidable for unambiguous two-way transducers. For larger classes of two-way transducers, the decidability status is open.

Details

Highlights Conference 2014 Conference Abstract

Rewriting Higher-Order Stack Trees

Vincent Penelle

Higher-order pushdown systems and ground tree rewriting systems can be seen as extensions of suffix word rewriting systems. Both classes generate infinite graphs with interesting logical properties. Indeed, the satisfaction of any formula written in monadic second order logic (respectively first order logic with reachability predicates) can be decided on such a graph. We unify both models by introducing the notion of stack trees, whose nodes are labelled by higher-order stacks, and define the corresponding class of higher-order closed tree rewriting systems. These graphs retain the decidability properties of ground tree rewriting graphs while generalising the pushdown hierarchy of graphs.

PDF Details