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$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.