Input strictly local tree transducers (Q782595)

The contribution investigates input strictly local tree transducers. To this end, the authors first generalize the concept of strictly locally testable from strings to trees and then define the input strictly local tree-to-tree functions. Using the canonical linear deterministic bottom-up tree transducers of [\textit{S. Friese} et al., Lect. Notes Comput. Sci. 6224, 185--196 (2010; Zbl 1250.68155)], the contribution also provides a characterization of those input strictly local tree-to-tree functions by means of a subclass of the mentioned tree transducers, called input strictly local tree transducers. The characterization yields a decision procedure for checking whether a tree-to-tree function \(f\) is input strictly local provided that \(f\) is itself represented as a linear deterministic bottom-up tree transducer. In other words, the contribution establishes a tree-transducer normal form for those input strictly local tree-to-tree functions, which follows the original definition very closely. The investigation is generally motivated from observations in phonology and morphology, but no detailed account is presented. An example from the area of syntax (wh-movement) is provided, but it does not have the locality property considered in the contribution; it nevertheless illustrates the power of the involved tree transducers. The writing is generally clear and examples are provided whenever expected by the reader. Full detailed proof details of all major statements are also provided. Anyone with some background on locality and some experience in tree automata theory should be able to easily appreciate the full contents of the contribution. For the entire collection see [Zbl 1435.68034].