Prefix and equality languages of rational functions are co-context-free (Q1124356)

The authors show that for every two rational (partial) functions F and G, the complement of their prefix language Pref(F,G) \(=\) \(\{\) w \(\in\) Dom(F) \(\cap\) Dom(G)\(| F(w)\leq\) G(w) \(\vee\) G(w) \(\leq\) F(w)\(\}\) is a one- counter language. In the above, ``\(\leq ''\) is the usual prefix order relation on strings and the concepts of the rational function and one- counter language are in the sense of \textit{J. Berstel} [Transductions and Context-Free Languages (Stuttgart, 1979; Zbl 0424.68040)]. Some consequences concerning equality languages, fixed-point languages and recursively enumerable languages are easily deduced. The general method of proof is not entirely new [see, e.g., \textit{J. Berstel}; Inf. Process. Lett 22, 7-9 (1986; Zbl 0584.68082)].