12
$\begingroup$

This sub-problem is motivated by Algorithm to test whether a language is regular.

Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to determine whether $L_1 = L_2$.

Is this decidable? If yes, can anyone suggest an algorithm for this? If not, can anyone suggest a semi-algorithm (one that returns "equal", "not equal", or "I'm not sure"; where we want it to return "not sure" as rarely as possible).

Motivation: A solution to this sub-problem would be helpful for solving Algorithm to test whether a language is regular


Algebraic form. Here's one possible definition of what I mean by a representation of a language in algebraic form. Such a language is given by

$$L = \{E : S\}$$

where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

  • Each of $x,y,z,\dots$ is a word-expression. (These represent variables that can take on any word in $\Sigma^*$.)

  • Each of $x^r,y^r,z^r,\dots$ is a word-expression. (Here $x^r$ represents the reverse of the string $x$.)

  • Each of $a,b,c,\dots$ is a word-expression. (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)

  • Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.

  • The concatenation of word-expressions is a word-expression.

  • Each of $m,n,p,q,\dots$ is a length-variable. (These represent variables that can take on any natural number.)

  • Each of $|x|,|y|,|z|,\dots$ is a length-variable. (These represent the length of a corresponding word.)

My goal is something rich enough to capture many of the examples we see in textbook exercises. (Feel free to suggest modifications to this formalization if it makes the equality-testing problem easier while still remaining expressive enough to capture many of the examples we see in textbooks.)


Some easier cases. If the original problem is too hard, here are some sub-cases that would still be interesting:

  • If $L_1,L_2$ are two languages specified in "algebraic" form as above, and $L_1\ne L_2$, let $d(L_1,L_2)$ denote the length of the shortest word that is an element of one of $L_1,L_2$ but not the other. Can we upper-bound $d(L_1,L_2)$ as a function of the length of the descriptions of $L_1,L_2$? Is it guaranteed to always be polynomial? at most singly-exponential?

    Motivation: If we could prove it is always polynomial, this might help us exhibit a witness that $L_1 \ne L_2$.

  • If we omit the reversal operation (we do not allow $x^r,y^r,\dots$), does the problem become easier?

$\endgroup$
  • $\begingroup$ Are those algebraic form languages and context free languages the same ? $\endgroup$ – François Jun 19 '15 at 16:40
  • $\begingroup$ @FrançoisG., no. For instance, $\{w^\eta w^\eta : w \in \Sigma^*, \eta \in \mathbb{N}\}$ is not context-free but has an algebraic form. (I don't know whether every context-free language has an algebraic form expression; I don't see any reason to expect this to be true.) I know that testing equality of two context-free languages is undecidable. I don't know how hard the first sub-case (at the end of the question) is if $L_1,L_2$ are two context-free languages. $\endgroup$ – D.W. Jun 19 '15 at 17:27
  • 1
    $\begingroup$ I don't see how to express Dyck languages in this framework. $\endgroup$ – Raphael Oct 30 '16 at 19:40

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.