2
$\begingroup$

Related to my previous question but this time I have a better idea of what I'm actually asking.

I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, bottom-up automata etc.):

$f^{-i}(L) = \{ t \mid \exists s_1 \ldots s_n \ldotp f(s_1, \ldots, s_{i-1}, t, s_{i+1} \ldots, s_n) \in L \}$.

That is, if $f$ is a symbol in our ranked alphabet, we take the $i$th component of all trees in $L$ that have $f$ as their root.

This seems reminiscent of the notion of quotient in formal language theory, or of projections in the set-constraint literature. Notably, it's not a homomorphism, since we're only applying it at the root, not over the entire tree.

I'm wondering:

  1. Does this operation have a name already? Has it been studied?
  2. If so, are recognizable tree languages closed under this operation?

It seems like a simple-enough property, but I'd rather not have to figure out all the theory myself if it's already been studied. I've found some things about projection in the TATA book, but they seem to be more about projecting out the nth tuple of a relation, not about projecting to the $i$th argument of a symbol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.