Composition of Path Transductions

摘要

We propose to study two infinite graph transformations that we respectively call bounded and unbounded path transduction. These graph transformations are based on path substitutions and graph products. When graphs are considered as automata, path transductions correspond to rational word transductions on the accepted languages. They define strict subclasses of monadic transductions and preserve the decidability of monadic second order theory. We give a generalization of the Elgot and Mezei composition theorem from rational word transductions to path transductions.