<p>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 <em>bideterministic automaton</em>. 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 <em>bideterministic</em> 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, <em>On reversible automata</em>, <a href="https://hal.science/hal-00019977" rel="nofollow noreferrer">https://hal.science/hal-00019977</a>.</p>
<p>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.</p>
<p>Let me first show that a language <span class="math-container">$L$</span> accepted by a bideterministic automaton <span class="math-container">$A$</span> satisfies your condition. Assume that <span class="math-container">$ac \in L$</span>, let <span class="math-container">$q_0$</span> be the initial state of <span class="math-container">$A$</span>, <span class="math-container">$q_f$</span> the final state, and <span class="math-container">$q$</span> the state reached between <span class="math-container">$a$</span> and <span class="math-container">$c$</span>. Further assume that <span class="math-container">$ad \in L$</span>. Hence there is a path <span class="math-container">$\pi'$</span> labeled <span class="math-container">$d$</span> from <span class="math-container">$q$</span> to <span class="math-container">$q_f$</span>. Now assume <span class="math-container">$bc \in L$</span>. We know that the run of <span class="math-container">$bc$</span> in the automaton must be reaching state <span class="math-container">$q$</span> between <span class="math-container">$b$</span> and <span class="math-container">$c$</span>, as otherwise we have two reverse paths when reading the reverse of <span class="math-container">$c$</span> backwards from <span class="math-container">$q_f$</span> that lead to two different states, and this would violate the reverse determinism requirement. Thus, there is a path <span class="math-container">$\pi$</span> labeled <span class="math-container">$b$</span> from <span class="math-container">$q_0$</span> to <span class="math-container">$q$</span>. We conclude from <span class="math-container">$\pi$</span> and <span class="math-container">$\pi'$</span> that the word <span class="math-container">$bd$</span> is also accepted by the automaton so your requirement is satisfied.</p>
<p>To show a converse, let <span class="math-container">$L$</span> be a regular language. Let us consider its minimal deterministic automaton, and assume that we have trimmed the minimal automaton: call <span class="math-container">$A$</span> the result. Let me first show that if <span class="math-container">$A$</span> has two final states then <span class="math-container">$L$</span> does not satisfy your condition. We prove this by contradiction. Let <span class="math-container">$q_f$</span> and <span class="math-container">$q_f'$</span> be two different final states. As <span class="math-container">$A$</span> is minimal, the language recognized from <span class="math-container">$q_f$</span> and <span class="math-container">$q_f'$</span> must be different (<a href="https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem#Use_and_consequences" rel="nofollow noreferrer">Myhill–Nerode</a>): up to exchanging them, we assume without loss of generality that there is a word <span class="math-container">$d$</span> such that <span class="math-container">$d$</span> is accepted from <span class="math-container">$q_f$</span> and <span class="math-container">$d$</span> is not accepted from <span class="math-container">$q_f'$</span>. Now, as <span class="math-container">$A$</span> is minimal, <span class="math-container">$q_f$</span> and <span class="math-container">$q_f'$</span> are accessible. Hence, let <span class="math-container">$a$</span> be a word going from the initial state to <span class="math-container">$q_f$</span>, and let <span class="math-container">$b$</span> be a word going from the initial state to <span class="math-container">$q_f'$</span>. Now, take <span class="math-container">$c = \epsilon$</span>. We know that <span class="math-container">$ac = a$</span> and <span class="math-container">$bc = b$</span> are both accepted, and <span class="math-container">$ad$</span> is accepted (because reading <span class="math-container">$a$</span> from the initial state leads to <span class="math-container">$q_f$</span> from which we accept <span class="math-container">$d$</span>). Hence your condition would imply that <span class="math-container">$bd$</span> is accepted. But this is a contradiction: reading <span class="math-container">$b$</span> from the initial state leads to <span class="math-container">$q_f'$</span> from which we reject <span class="math-container">$d$</span> by assumption.</p>
<p>Hence, <span class="math-container">$A$</span> must have a single final state <span class="math-container">$q_f$</span>. Let me show that the reverse of <span class="math-container">$A$</span> 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 <span class="math-container">$q$</span> and letter <span class="math-container">$x$</span> for which there are two distinct predecessors <span class="math-container">$q_1$</span> and <span class="math-container">$q_2$</span>. As <span class="math-container">$A$</span> is minimal, we know that the language accepted from <span class="math-container">$q_1$</span> and <span class="math-container">$q_2$</span> cannot be the same. So, up to exchanging <span class="math-container">$q_1$</span> and <span class="math-container">$q_2$</span>, without loss of generality assume that there is a word <span class="math-container">$d$</span> which is accepted from <span class="math-container">$q_1$</span> and rejected from <span class="math-container">$q_2$</span>. Now, <span class="math-container">$A$</span> is trimmed so <span class="math-container">$q$</span> is co-accessible. Hence, let <span class="math-container">$c'$</span> be a word accepted from <span class="math-container">$q$</span>: thus the word <span class="math-container">$c = xc'$</span> is accepted from both <span class="math-container">$q_1$</span> and <span class="math-container">$q_2$</span>. As <span class="math-container">$A$</span> is trimmed, <span class="math-container">$q_1$</span> and <span class="math-container">$q_2$</span> are accessible, so let <span class="math-container">$a$</span> be a word going from the initial state to <span class="math-container">$q_1$</span>, and <span class="math-container">$b$</span> be a word going from the initial state to <span class="math-container">$q_2$</span>. We can now see that <span class="math-container">$ac$</span> is accepted (via <span class="math-container">$q_1$</span>) and <span class="math-container">$bc$</span> is accepted (via <span class="math-container">$q_2$</span>) and <span class="math-container">$ad$</span> is accepted (via <span class="math-container">$q_1$</span>) but <span class="math-container">$bd$</span> is rejected (the run goes via <span class="math-container">$q_2$</span> from which we reject <span class="math-container">$d$</span>. So we have a contradiction. This together with the previous paragraph establishes the reverse direction of the equivalence.</p>

CC BY-SA 4.0
2024-06-25T17:01:21.460Z
2024-06-30T11:34:06.107Z
2024-06-30T11:34:06.107Z
Antoine Amarilli 'a3nm'
<p>I am looking for occurrences in literature of the following property of a formal language <span class="math-container">$\mathcal L$</span> over an alphabet <span class="math-container">$\Sigma$</span></p>
<p>For any quadruple of words <span class="math-container">$a,b,c,d\in\Sigma^*$</span>, if <span class="math-container">$ac,bc,ad\in\mathcal L$</span>, then <span class="math-container">$bd\in\mathcal L$</span>.</p>
<p>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 &quot;all possible ways of achieving the same result&quot; in this context.</p>

<reference-request><fl.formal-languages>
A split-consistency property of a formal language
Gejza Jenča
# A split-consistency property of a formal language

(Asked by: username_0 on 2024-06-01)

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.

**Tags:** reference-request, fl.formal-languages

---

## 1 answers

### Answer by username_1 on 2024-06-25. Score: 9

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](https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem#Use_and_consequences)): 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.


---

