13 citations · 30 across the 13 of their papers we have counts for
18 papers
Deciding the Common Fragment of CTL with Past and LTL
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
A central goal of language theory is to compare formalisms by understanding their relative expressive power. One challenging question in this direction is the problem of determinin…
Minimization of Streaming Transducers
Christian Bianchini, Gabriele Puppis
We provide general criteria for the existence of minimal models of streaming transducers, namely devices that read an input word and produce an output value by iteratively updating…
Automaton-based Characterisations of First Order Logic over Infinite Trees
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
We study the expressive power of First-Order Logic (\FO) over (unordered) infinite trees, with the aim of identifying robust characterisations in terms of branching-time specificat…
An Automaton-based Characterisation of First-Order Logic over Infinite Trees
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
In this paper, we study First Order Logic (FO) over (unordered) infinite trees and its connection with branching-time temporal logics. More specifically, we provide an automata-the…
Finite-valued Streaming String Transducers
Emmanuel Filiot, Ismaël Jecker, Christof Löding +3
A transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, one-way transducers, it is known since the 80s that finite valuednes…
The Logic of Prefixes and Suffixes is Elementary under Homogeneity
Dario Della Monica, Angelo Montanari, Gabriele Puppis +1
In this paper, we study the finite satisfiability problem for the logic BE under the homogeneity assumption. BE is the cornerstone of Halpern and Shoham's interval temporal logic,…
One-way resynchronizability of word transducers
Sougata Bose, S. N. Krishna, Anca Muscholl +1
The origin semantics for transducers was proposed in 2014, and led to various characterizations and decidability results that are in contrast with the classical semantics. In this…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
On Synthesis of Resynchronizers for Transducers
Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl +2
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 latt…
Equivalence of finite-valued streaming string transducers is decidable
Anca Muscholl, Gabriele Puppis
In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transduce…
Origin-equivalence of two-way word transducers is in PSPACE
Sougata Bose, Anca Muscholl, Vincent Penelle +1
We consider equivalence and containment problems for word transductions. These problems are known to be undecidable when the transductions are relations between words realized by n…
One-way definability of two-way word transducers
Félix Baschenis, Olivier Gauwin, Anca Muscholl +1
Functional transductions realized by two-way transducers (or, equally, by streaming transducers or MSO transductions) are the natural and standard notion of "regular" mappings from…
An algebraic approach to MSO-definability on countable linear orderings
Olivier Carton, Thomas Colcombet, Gabriele Puppis
We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability…
Untwisting two-way transducers in elementary time
Félix Baschenis, Olivier Gauwin, Anca Muscholl +1
Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings…
A decidable weakening of Compass Logic based on cone-shaped cardinal directions
Angelo Montanari, Gabriele Puppis, Pietro Sala
We introduce a modal logic, called Cone Logic, whose formulas describe properties of points in the plane and spatial relationships between them. Points are labelled by proposition…
Inference From Visible Information And Background Knowledge
Michael Benedikt, Pierre Bourhis, Balder ten Cate +2
We provide a wide-ranging study of the scenario where a subset of the relations in a relational vocabulary are visible to a user --- that is, their complete contents are known ---…
Logics with rigidly guarded data tests
Gabriele Puppis, Thomas Colcombet, Clemens Ley
The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we…
Decidability of the interval temporal logic ABBar over the natural numbers
A. Montanari, G. Puppis, P. Sala +1
In this paper, we focus our attention on the interval temporal logic of the Allen's relations "meets", "begins", and "begun by" (ABBar for short), interpreted over natural numbers.…