Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Dartois, Luc"'
Deterministic two-way transducers capture the class of regular functions. The efficiency of composing two-way transducers has a direct implication in algorithmic problems related to reactive synthesis, where transformation specifications are converte
Externí odkaz:
http://arxiv.org/abs/2406.11488
The class of regular transformations has several equivalent characterizations such as functional MSO transductions, deterministic two-way transducers, streaming string transducers, as well as regular transducer expressions (RTE). For algorithmic appl
Externí odkaz:
http://arxiv.org/abs/2202.04340
Autor:
Carton, Olivier, Dartois, Luc
Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperiodicity for these transducers and we show that aperiodic transducers c
Externí odkaz:
http://arxiv.org/abs/2103.15651
FO transductions, aperiodic deterministic two-way transducers, as well as aperiodic streaming string transducers are all equivalent models for first order definable functions. In this paper, we solve the long standing open problem of expressions capt
Externí odkaz:
http://arxiv.org/abs/2101.07130
Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in
Externí odkaz:
http://arxiv.org/abs/1702.07157
We introduce a logic, called LT, to express properties of transductions, i.e. binary relations from input to output (finite) words. In LT, the input/output dependencies are modelled via an origin function which associates to any position of the outpu
Externí odkaz:
http://arxiv.org/abs/1701.03670
Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following mod
Externí odkaz:
http://arxiv.org/abs/1606.00234
Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable functions. This result has recently been lifted to FO definable functions,
Externí odkaz:
http://arxiv.org/abs/1506.04059
Autor:
Dartois, Luc, Paperman, Charles
We investigate the decidability of the definability problem for fragments of first order logic over finite words enriched with modular predicates. Our approach aims toward the most generic statements that we could achieve, which successfully covers t
Externí odkaz:
http://arxiv.org/abs/1401.6576
We consider the four fragments FO2, the intersection of Sigma2 and FO2, the intersection of Pi2 and FO2, and Delta2 of first-order logic FO[<] over finite and infinite words. For all four fragments, we give characterizations in terms of rankers. In p
Externí odkaz:
http://arxiv.org/abs/1005.0505