8

Transductions of terms and words

As explained in the introduction of Section 1.7, there are no appropriate finite-state automata or finite-state transducers that work “directly” on graphs. Thus, for graphs, the role of automata and transducers is taken over by monadic second-order logic: instead of being accepted by an automaton, a set of graphs is defined by a monadic second-order sentence; and instead of being computed by a transducer, a graph transduction is defined by a definition scheme consisting of monadic second-order formulas. With respect to automata, the original motivation for this approach was Theorem 1.16 (cf. Theorem 5.82): for terms and words monadic second-order logic and finite-state automata have the same expressive power. ...

Start Free Trial

No credit card required