Zobrazeno 1 - 10
of 107
pro vyhledávání: '"PUPPIS, GABRIELE"'
Autor:
Filiot, Emmanuel, Jecker, Ismaël, Puppis, Gabriele, Löding, Christof, Muscholl, Anca, Winter, Sarah
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 valuedness entails decidability of the equivalence problem. This decidability r
Externí odkaz:
http://arxiv.org/abs/2405.08171
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, and features modal operators corresponding to the prefix (a.k.a. "Begi
Externí odkaz:
http://arxiv.org/abs/2304.11483
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 paper we add a further decidability result for characterizing transduc
Externí odkaz:
http://arxiv.org/abs/2101.08011
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 different perspective, that is, we consider a dynamic version of the p
Externí odkaz:
http://arxiv.org/abs/2002.07049
Autor:
Bose, Sougata, Krishna, Shankara Narayanan, Muscholl, Anca, Penelle, Vincent, Puppis, Gabriele
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
Externí odkaz:
http://arxiv.org/abs/1906.08688
Autor:
Muscholl, Anca, Puppis, Gabriele
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 transducers is decidable.
Externí odkaz:
http://arxiv.org/abs/1902.06973
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 non-deterministic transducers, and become decidable when restricting to
Externí odkaz:
http://arxiv.org/abs/1807.08053
Publikováno v:
Logical Methods in Computer Science, Volume 14, Issue 4 (December 7, 2018) lmcs:3697
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 words to words. It was shown in 2013 that it is decidable if such a t
Externí odkaz:
http://arxiv.org/abs/1706.01668
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 in monadic second-order (MSO) logic. We also provide three logical app
Externí odkaz:
http://arxiv.org/abs/1702.05342