5 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…