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.
2
$\begingroup$
$\endgroup$
-
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
11
$\begingroup$
$\endgroup$
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)$.
