<p>A language $L$ is said to be <em>commutative</em> if the following property holds:</p>

<blockquote>
  <p>for every  word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on
  $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm a_{\sigma(n)}$ is
  also in $L$.</p>
</blockquote>

<p>Now, my understanding of your question is the following: </p>

<blockquote>
  <p>given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether
  the language accepted by $\mathcal{A}$ is a <em>commutative language</em>.</p>
</blockquote>

<p>There is a polynomial algorithm to answer this question. 
Indeed a language is commutative if and only if its <a href="https://en.wikipedia.org/wiki/Syntactic_monoid" rel="noreferrer">syntactic monoid</a> is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$. </p>

<p>Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.</p>

CC BY-SA 4.0
2018-05-28T18:01:37.120Z
2018-05-28T18:01:37.120Z
J.-E. Pin
<p>I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.</p>

<p>Would appreciate any help.</p>

CC BY-SA 4.0
2018-05-23T14:52:57.557Z
What makes you believe that a polynomial algorithm indeed does exist for this problem?
Gamow
CC BY-SA 4.0
2018-05-23T15:52:33.290Z
Does “the same letters” refer to the same *set* of letters or the same *multiset* of letters? Assuming a multiset, this paper seems to establish your result for finite alphabets. https://link.springer.com/chapter/10.1007/978-3-319-62809-7_6 (See also https://books.google.com/books?id=ob0tDwAAQBAJ&pg=PA107&lpg=PA107&dq=dfa+%E2%80%9Cclosed+under+permutation%E2%80%9D&source=bl&ots=tccG50rM9u&sig=TRJXiJPlaQK8opKwnPr5mNI5RpM&hl=en&sa=X&ved=2ahUKEwjakPv6lpzbAhXqHTQIHXy4Dc8Q6AEwAXoECAUQAQ#v=onepage&q=dfa%20%E2%80%9Cclosed%20under%20permutation%E2%80%9D&f=false).
Yonatan N
<ds.algorithms><automata-theory><regular-language>
Existence of an algorithm
Axx
# Existence of an algorithm

(Asked by: username_0 on 2018-05-23)

I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.

Would appreciate any help.

**Tags:** ds.algorithms, automata-theory, regular-language

> **Comments:**
> **username_1**: What makes you believe that a polynomial algorithm indeed does exist for this problem?  
> **username_2**: Does “the same letters” refer to the same *set* of letters or the same *multiset* of letters? Assuming a multiset, this paper seems to establish your result for finite alphabets. https://link.springer.com/chapter/10.1007/978-3-319-62809-7_6 (See also https://books.google.com/books?id=ob0tDwAAQBAJ&pg=PA107&lpg=PA107&dq=dfa+%E2%80%9Cclosed+under+permutation%E2%80%9D&source=bl&ots=tccG50rM9u&sig=TRJXiJPlaQK8opKwnPr5mNI5RpM&hl=en&sa=X&ved=2ahUKEwjakPv6lpzbAhXqHTQIHXy4Dc8Q6AEwAXoECAUQAQ#v=onepage&q=dfa%20%E2%80%9Cclosed%20under%20permutation%E2%80%9D&f=false).  

---

## 1 answers

### Answer by username_3 on 2018-05-28. Score: 11

A language $L$ is said to be *commutative* if the following property holds:

> for every word $a\_1 \dotsm a\_n \in L$ and any permutation $\sigma$ on
> $\{1, \ldots, n\}$, the word $a\_{\sigma(1)} \dotsm a\_{\sigma(n)}$ is
> also in $L$.

Now, my understanding of your question is the following:

> given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether
> the language accepted by $\mathcal{A}$ is a *commutative language*.

There is a polynomial algorithm to answer this question.
Indeed a language is commutative if and only if its [syntactic monoid](https://en.wikipedia.org/wiki/Syntactic_monoid) is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$.

Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.


---

