# Learning a regular language with a specified closure property

Consider an alphabet $$\Sigma$$, and a partial transformation function $$f:S\to\Sigma^\ast$$ defined on some subset $$S\subseteq\Sigma^\ast$$. Let $$S_f$$ denote the set of strings $$s\in S$$ such that $$f^n(s)\in S$$ for all $$n\geq0$$, and let $$f^\infty(s)$$ denote this sequence of strings starting at $$s$$. (In other words, $$\overline{S_f}$$ is the set of strings that eventually reach a string in $$\overline S$$, and conversely, $$S_f$$ is the maximal set of strings that is closed under $$f$$.)

Now, suppose that $$\varepsilon\in S_f$$; that it is computable in polynomial time whether $$s\in S_f$$ for any $$s\in\Sigma^\ast$$; and that for all regular languages $$L\subseteq S$$, $$f(L)\subseteq\Sigma^\ast$$ is also a regular language, computable in linear time as a function from one NFA to another.

Then, is there generally an algorithm faster than brute force to find a regular language $$L_\varepsilon\subseteq S_f$$ such that $$\varepsilon\in L_\varepsilon$$ and $$f(L_\varepsilon)\subseteq L_\varepsilon$$, assuming that such a language exists? For instance, can the problem be reduced to a series of SAT problems of reasonable size?

Given a hypothesis language $$L$$, it's not difficult to test whether $$f(L)\setminus L$$ is empty, or to find a counterexample if it isn't. So I first thought of modifying the standard L* algorithm for this purpose. However, this isn't much better than brute force, since for any string in $$S_f\setminus f^\infty(\varepsilon)$$, we must make a judgment call on whether to include that string in our language (ensuring that our decisions respect $$f$$), and picking these at random usually won't allow the algorithm to terminate, so we'll have to branch through exponentially many choices up to the size of the actual language.

Then, I looked into algorithms for finding separating DFAs, since in this case, we have $$f^\infty(\varepsilon)\subseteq L_\varepsilon\subseteq S_f$$, so our DFA will separate $$f^\infty(\varepsilon)$$ from $$\overline{S_f}$$. Chen et al. (2009) outline a natural extension of the L* algorithm for learning a separating DFA from language-inclusion queries, but the algorithm doesn't terminate if either the positive or negative language isn't regular. Oncina & García (1993) are a bit closer, with an algorithm for learning a (not necessarily minimal) DFA from a set of positive and negative examples, but it's unclear how to proceed once a candidate DFA is found that isn't closed under $$f$$. Perhaps this could be combined with the exponential branching as before, but it's unclear how much faster it would be than the standard L* approach.

Is there any way in general to improve on these brute-force approaches? Or is there any literature on this problem for any particular kind of function $$f$$?