Distributed tree processing devices

Abstract

Distributed tree processing devices, like regular tree grammars, top-down tree automata and transducers, and bottom-up tree automata and transducers are considered. The concept of distribution lies in that the set of rewriting rules are distributed among n sets, called components. The components work on deriving a sentential form such that they cooperate with each other concerning cooperation strategies. We develop a technical toolkit for studying distributed tree processing devices. We mainly consider the -ç strategy which means that a component should work on a sentential form as far as it can. We show that in general the above distributed tree processing devices with -÷ cooperation strategy are more powerful than the ordinary ones with respect to generating capacity.