Tenth and final Meeting
- Christof Loeding (LIAFA)
-
Title: Deterministic Transducers over Infinite Terms (Slides)
- Abstract:
We introduce top-down deterministic transducers with rational lookahead (transducer for short) working on infinite
terms. Infinite terms can be used to describe other types of infinite objects (e.g., graphs) by attaching a semantics of
correct arity to each symbol the term is built from and then evaluating the term according to this semantics. In this
sense, transducers can be used to transform various kinds of infinite objects by applying them to the terms representing
these objects.
On the other hand, each infinite term can be obtained by unfolding a (possibly infinite) graph. To this respect, interpreting
the term is equivalent to solving the graph seen as an equational system. For this reason, we investigate how
transducers on infinite terms can be compared with transformations of graphs, namely monadic second-order (MSO)
transductions of graphs.
Our main result is an equivalence of the expressive power of (certain) MSO transductions and transducers. More
precisely, we show that for each transducer T there is an MSO transduction M such that unfold(M(G)) = T(unfold(G)) for
any graph G. Reciprocally, we show that if an MSO transduction M 'preserves bisimilarity of graphs', then there is a
transducer T such that for any graph G, unfold(T(G)) = unfold(M(G)).