<p>The Myhill-Nerode theorem characterizes regular/recognizable languages as those that have finitely many &quot;quotients&quot;, and <a href="https://www.cs.cornell.edu/%7Ekozen/Papers/mn.pdf" rel="noreferrer">it works for trees</a> — more precisely, a tree language is regular iff there are finitely many languages of the form <span class="math-container">$\{t \mid C[t/x] ∈ L\}$</span> where the &quot;context&quot; <span class="math-container">$C$</span> is like a tree over the same ranked alphabet, except that exactly one of its leaves is the free variable <span class="math-container">$x$</span>.</p>
<p>Your <span class="math-container">$f^{-1}(L)$</span> can be written as a union of quotients of a regular tree language, which is therefore a finite union of regular tree languages, so it is regular. I don't know about the name of the operation though.</p>

CC BY-SA 4.0
2022-11-03T00:39:18.560Z
2022-11-03T00:39:18.560Z
Lê Thành Dũng 'Tito' Nguyễn
<p>Related to <a href="https://cstheory.stackexchange.com/questions/43787/regular-tree-languages-are-closed-under-quotient">my previous question</a> but this time I have a better idea of what I'm actually asking.</p>

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

<p><span class="math-container">$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 \}$</span>.</p>

<p>That is, if <span class="math-container">$f$</span> is a symbol in our ranked alphabet, we take the <span class="math-container">$i$</span>th component of all trees in <span class="math-container">$L$</span> that have <span class="math-container">$f$</span> as their root.</p>

<p>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.</p>

<p>I'm wondering:</p>

<ol>
<li>Does this operation have a name already? Has it been studied?</li>
<li>If so, are recognizable tree languages closed under this operation?</li>
</ol>

<p>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 <a href="http://tata.gforge.inria.fr/" rel="nofollow noreferrer">TATA</a> book, but they seem to be more about projecting out the nth tuple of a relation, not about projecting to the <span class="math-container">$i$</span>th argument of a symbol.</p>

<lo.logic><fl.formal-languages><automata-theory><tree><grammars>
Notion of "quotient" or "inverse" for recognizable tree languages?
Joey Eremondi
# Notion of "quotient" or "inverse" for recognizable tree languages?

(Asked by: username_0 on 2019-04-27)

Related to [my previous question](https://cstheory.stackexchange.com/questions/43787/regular-tree-languages-are-closed-under-quotient) 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](http://tata.gforge.inria.fr/) 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.

**Tags:** lo.logic, fl.formal-languages, automata-theory, tree, grammars


---

## 1 answers

### Answer by username_1 on 2022-11-03. Score: 5

The Myhill-Nerode theorem characterizes regular/recognizable languages as those that have finitely many "quotients", and [it works for trees](https://www.cs.cornell.edu/%7Ekozen/Papers/mn.pdf) — more precisely, a tree language is regular iff there are finitely many languages of the form $\{t \mid C[t/x] ∈ L\}$ where the "context" $C$ is like a tree over the same ranked alphabet, except that exactly one of its leaves is the free variable $x$.

Your $f^{-1}(L)$ can be written as a union of quotients of a regular tree language, which is therefore a finite union of regular tree languages, so it is regular. I don't know about the name of the operation though.


---

