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.

  • 1
    $\begingroup$ What makes you believe that a polynomial algorithm indeed does exist for this problem? $\endgroup$ – Gamow May 23 '18 at 14:52
  • 2
    $\begingroup$ 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. link.springer.com/chapter/10.1007/978-3-319-62809-7_6 (See also books.google.com/…). $\endgroup$ – Yonatan N May 23 '18 at 15:52

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 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)$.


Your Answer

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

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