8
$\begingroup$

I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$

For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\mathcal L$, then $bd\in\mathcal L$.

The motivation of this property comes from a non-commutative version of quantum logic. Intuitively, one can interpret the words of such a language as "all possible ways of achieving the same result" in this context.

$\endgroup$

1 Answer 1

9
$\begingroup$

We discussed your question with @M.Monet in the case of regular languages. It turns out that, unless we're mistaken, your condition is precisely equivalent to saying that the language is recognized by a bideterministic automaton. An automaton is bideterministic if it is deterministic (so in particular has a unique initial state), if it has a unique final state, and if the reverse of the automaton is also deterministic. (The notion exists under different names, e.g., injective automata, zero-reversible acceptors...) I will call a language bideterministic if it is accepted by such an automaton. It is known that not all languages are bideterministic, but that if a language is bideterministic then the minimal deterministic automaton for the language will be bideterministic. See for instance Pin, On reversible automata, https://hal.science/hal-00019977.

What follows is a proof of the fact that a regular language satisfies your condition iff it is bideterministic. I don't know whether this characterization has been stated before somewhere in the literature on bideterministic automata.

Let me first show that a language $L$ accepted by a bideterministic automaton $A$ satisfies your condition. Assume that $ac \in L$, let $q_0$ be the initial state of $A$, $q_f$ the final state, and $q$ the state reached between $a$ and $c$. Further assume that $ad \in L$. Hence there is a path $\pi'$ labeled $d$ from $q$ to $q_f$. Now assume $bc \in L$. We know that the run of $bc$ in the automaton must be reaching state $q$ between $b$ and $c$, as otherwise we have two reverse paths when reading the reverse of $c$ backwards from $q_f$ that lead to two different states, and this would violate the reverse determinism requirement. Thus, there is a path $\pi$ labeled $b$ from $q_0$ to $q$. We conclude from $\pi$ and $\pi'$ that the word $bd$ is also accepted by the automaton so your requirement is satisfied.

To show a converse, let $L$ be a regular language. Let us consider its minimal deterministic automaton, and assume that we have trimmed the minimal automaton: call $A$ the result. Let me first show that if $A$ has two final states then $L$ does not satisfy your condition. We prove this by contradiction. Let $q_f$ and $q_f'$ be two different final states. As $A$ is minimal, the language recognized from $q_f$ and $q_f'$ must be different (Myhill–Nerode): up to exchanging them, we assume without loss of generality that there is a word $d$ such that $d$ is accepted from $q_f$ and $d$ is not accepted from $q_f'$. Now, as $A$ is minimal, $q_f$ and $q_f'$ are accessible. Hence, let $a$ be a word going from the initial state to $q_f$, and let $b$ be a word going from the initial state to $q_f'$. Now, take $c = \epsilon$. We know that $ac = a$ and $bc = b$ are both accepted, and $ad$ is accepted (because reading $a$ from the initial state leads to $q_f$ from which we accept $d$). Hence your condition would imply that $bd$ is accepted. But this is a contradiction: reading $b$ from the initial state leads to $q_f'$ from which we reject $d$ by assumption.

Hence, $A$ must have a single final state $q_f$. Let me show that the reverse of $A$ must be deterministic. The proof is by contradiction and is similar to the previous paragraph. Assume that there is a violation of reverse determinism, i.e., a state $q$ and letter $x$ for which there are two distinct predecessors $q_1$ and $q_2$. As $A$ is minimal, we know that the language accepted from $q_1$ and $q_2$ cannot be the same. So, up to exchanging $q_1$ and $q_2$, without loss of generality assume that there is a word $d$ which is accepted from $q_1$ and rejected from $q_2$. Now, $A$ is trimmed so $q$ is co-accessible. Hence, let $c'$ be a word accepted from $q$: thus the word $c = xc'$ is accepted from both $q_1$ and $q_2$. As $A$ is trimmed, $q_1$ and $q_2$ are accessible, so let $a$ be a word going from the initial state to $q_1$, and $b$ be a word going from the initial state to $q_2$. We can now see that $ac$ is accepted (via $q_1$) and $bc$ is accepted (via $q_2$) and $ad$ is accepted (via $q_1$) but $bd$ is rejected (the run goes via $q_2$ from which we reject $d$. So we have a contradiction. This together with the previous paragraph establishes the reverse direction of the equivalence.

$\endgroup$

Your Answer

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

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