11
$\begingroup$

(This is a simpler rephrasing of an earlier question I have since deleted.)

Definitions

For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer reads any number of characters (including 0) from the input tape and outputs any number of characters (including 0) to the output tape. These two tapes need not have the same alphabet. Like an NFA, when the input tape is exhausted, the transducer can either reject or accept the input, depending on what state it ends in.

A given transducer $T : A^* \rightarrow B^*$ induces a rational relation $\simeq_T$, where for two words $a \in A^*, b \in B^*$, we have $a \simeq_T b$ if and only if there is a path of $T$ that takes $a$ as input, outputs $b$, and accepts.

A rational function is a rational relation that is also a partial function over $A^*$; that is, for any word $a \in A^*$, there is at most a single $b \in B^*$ such that $a \simeq_T b$. In this case we can write the rational function as $f_T$, where $f_T(a) = b$. Note that the domain and range of a rational function are both always regular languages.

A function over words is length-preserving if $\forall a \in A^*$, $|f(a)| = |a|$.

The density of a language $L$ is a function $\rho_L : \mathbb{N} \rightarrow \mathbb{N}$ where $\rho_L(n)$ is the number of words of length $n$ in $L$.

Question

Let $A, B$ be alphabets. Let $L \subseteq A^*$ be a regular language with $\rho_L(n) \leq |B|^n$. Does there always exist a rational, length-preserving, injective function $f : L \rightarrow B^*$ (that is total over $L$)?

Notes

  • Both conditions on $L$ are necessary for $f$ to exist: if $L$ is not regular, no rational function can have $L$ as its domain and be total over it; if $\rho_L(n) > |B|^n$, then $f$ can't possibly be injective and length-preserving. So the question is asking whether these conditions are also sufficient for $f$ to exist.
  • According to [1], such a rational length-preserving bijection between regular languages exists as long as there exists a regular language over $B^*$ with the same density as $L$. So, the problem reduces to constructing a regular language $L' \subseteq B^*$ such that $\rho_L = \rho_{L'}$, given that $\rho_L(n) \leq |B|^n$.

[1]: Béal, Marie-Pierre; Lombardy, Sylvain; Sakarovitch, Jacques, Conjugacy and equivalence of weighted automata and functional transducers, Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 58-69 (2006). ZBL1185.68381.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Just stating a few obvious things in case other users ask themselves the same question: dropping any of the hypothesis on the function (regular, injective, and length-preserving) makes the result trivial. For $f$ not regular, take any injections $f_n:\{u\in L:|u|=n\}\to |B|^n$ and $f=\bigcup_n f_n$. For $f$ not injective, take an automaton for $L$ and build the transducer that outputs $a$ at each transition, hence mapping $u$ to $a^{|u|}$. For $f$ not length-preserving, take $k$ such that $|A|\le |B|^k$ and then map distinct letters of $A$ to distinct words of length $k$ on $B$. $\endgroup$
    – xavierm02
    Jun 18, 2022 at 10:42
  • $\begingroup$ So the only remaining way to weaken the statement to get a (possibly) easier to prove one is to ask for $A$ to have exactly $|B|^n$ words of length $n$. In this setting, we can try building an injective / surjective function $g:|B|^n\to L$ instead but I'm not sure how to do that. $\endgroup$
    – xavierm02
    Jun 18, 2022 at 10:47
  • $\begingroup$ Do you know whether the answer is negative if you require the rational function to be computed by a deterministic transducer? $\endgroup$
    – Neal Young
    Jun 19, 2022 at 1:53
  • $\begingroup$ @NealYoung You at least need to be able to read/output multiple characters at once: letting $A = \{x, y, z, w\}$ and $B = \{x,y\}$, the language $$L = (x(x+y+z+w))^*$$ seems to require as much, since you have to map to $$f(L) = ((x+y)(x+y))^*$$ and that seems to require reading pairs of characters at once. Not sure if that's what you're asking for though. $\endgroup$
    – Jake
    Jun 19, 2022 at 4:04

1 Answer 1

Reset to default
6
$\begingroup$

It turns out the answer is "no": in [2] the authors show that a regular language $L$ exists with density $\rho_L(n) \leq |B|^n$ such that no regular language over $B$ has the same density; therefore, the injective rational length-preserving function cannot exist.

[2]: Béal, Marie-Pierre; Perrin, Dominique, On the generating sequences of regular languages on (k) symbols, J. ACM 50, No. 6, 955-980 (2003). ZBL1325.68125.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.