0
$\begingroup$

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where

  • $f(\alpha)=\beta$,
  • $f^{-1}(\beta)=\alpha$,
  • $\forall \alpha_0,\alpha_1,\alpha_2\in G. d(\alpha_0,\alpha_1)<d(\alpha_0,\alpha_2)\leftrightarrow d(f(\alpha_0),f(\alpha_1))<d(f(\alpha_0),f(\alpha_2))$ where $d(\alpha_0,\alpha_1)$ is the Hamming distance between $\alpha_0$ and $\alpha_1$ (i.e., small perturbations of $\beta$ lead to small perturbations of $\alpha$, and vice versa), and
  • for any perturbation $\beta'$ of $\beta$ (say, by substituting a letter) we have $f^{-1}(\beta')=\alpha'$ such that
    • $\alpha'$ is a string derived from $G$ (i.e., "valid" w.r.t. $G$) and
    • $\alpha'$ is a perturbation of $\alpha$.

On a high level, I would like translate arbitrary modifications to some "dense" representation of a string $\alpha$ into "valid" modifications of $\alpha$ ("valid" means that $\alpha'\in G$).

Since arbitrary modifications of $\beta$ yield valid modifications of $\alpha$, we can say that $\beta$ is a "condensed" representation of $\alpha$, $f$ is the "condensing" operator, and $f^{-1}$ is the "de-condensing" operator.

It doesn't necessarily need to be complete such that all valid modifications of $\alpha$ can be generated but it should be sound such that only "valid modifications of $\alpha$ can be generated.

My first idea was to conceptually index each string that can be generated by $G$. For instance, if $\alpha$ has index $\beta=12$, we could generate a perturbation $\beta'=15$ and find $\alpha'$ as the string derived from $G$ with index 15. However, $\alpha'$ may be very different from $\alpha$ e.g., in terms of Hamming distance and I would need to establish an order over all strings and be able to enumerate the first $n$ strings.

Any ideas or pointers?

$\endgroup$
  • 1
    $\begingroup$ 1) The connection of title and question body are not clear to me. 2) What kind of function may $f$ be? Any restrictions? 3) Which unrestricted grammar? 4) Define "small" and "valid". $\endgroup$ – Raphael May 27 '16 at 11:31
  • $\begingroup$ a' must be valid even if β′ is not? I do not see any "condensation" then. Rather the second language seems to be intuitively less compact. At any rate, your algorithms will need some knowledge about the two languages/grammars they are dealing with. I do not think that there can be a general operation of this type. $\endgroup$ – Peter Leupold May 29 '16 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.