Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Gauwin, Olivier"'
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 1 (February 13, 2020) lmcs:5640
We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such t
Externí odkaz:
http://arxiv.org/abs/1907.09563
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 2 (April 4, 2019) lmcs:3763
We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that
Externí odkaz:
http://arxiv.org/abs/1707.00527
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
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 4 (December 19, 2019) lmcs:3653
Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic. The robust subclass of aperiodic languages is defined by: counter-free automata,
Externí odkaz:
http://arxiv.org/abs/1705.03726
Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decid
Externí odkaz:
http://arxiv.org/abs/1701.02502
Autor:
Gauwin, Olivier
L'intérêt croissant pour les technologies Web génère de nouveaux défis. Le format XML s'est imposé comme une référence pour le stockage et l'échange de données. Certains documents XML ont acquis une taille telle, qu'il est inefficace voire
Externí odkaz:
http://www.theses.fr/2009LIL10054/document
Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characteriz
Externí odkaz:
http://arxiv.org/abs/1301.5197
An automaton is universal if it accepts every possible input. We study the notion of u-universality, which asserts that the automaton accepts every input starting with u. Universality and u-universality are both EXPTIME-hard for non-deterministic tre
Externí odkaz:
http://arxiv.org/abs/1205.2841
Publikováno v:
In Theoretical Computer Science 3 May 2015 578:100-125
Publikováno v:
In Computer Networks 2 June 2014 65:232-254