Workshop
Starting on
Ending on
Location
IRISA Rennes
Room
Lipari
Speaker
Vincent Ghigo ( LaBRI/Univ. Bordeaux)
Main department
Title: On the equivalence between generating functions computed by memory transducers and enumerating functions produced by indexed grammars
Abstract: We consider the sequences of natural integers that can be computed by a deterministic transducer, with input in a arbitrary structure, output in natural integers and with memory the set of stacks of stacks of the structure. We show, by constructive proofs, that these sequences are, exactly, the counting sequences of formal languages generated by unambiguous context-free indexed grammars, with indexes in the structure. This general theorem applies, notably, to the structure of natural integers endowed with the decrement operation, showing that the polynomial recurrences count exactly the index-languages.