2 results
Emmanuel Filiot ; Olivier Gauwin ; Nathan Lhote.
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, star-free expressions, aperiodic (finite) […]
Published on December 19, 2019
Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier ; Frédéric Servais.
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 depends only on the size of T and on the height […]
Published on April 4, 2019