Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA. Let $C$ be some class of acyclic DFAs.

Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\sigma$ to a string $w$ of length $n$ by permuting symbols of $w$ according to $\sigma$ and we denote the new string by $\sigma(w)$.

Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.

What interesting classes $C$ one can define s.t for any finite regular language $L$, either $L$ has a DFA in the class $C$ (L is recognized by a DFA which satisfies properties of class C) or there is a permutation $\sigma$ such that $L(\sigma)$ has a DFA in the class $C$.

Effect of permutation, an example: $L =\{ww | w \in \{0,1\}^n\}$ has only acyclic DFA of size $\Omega(2^n)$ but there is a $\sigma$ such that $L(\sigma) =\{w_1^2w_2^2\cdots w_n^2 | w \in \{0,1\}^n\}$ has $O(n)$ size DFA. I refer $L(\sigma)$ as a deformation of $L$.

Is there some references for study of these kind? are similar questions for CFL studied?

Thank you.

  • 2
    $\begingroup$ I'm confused. A finite automaton is supposed to accept any word in a language, reject the words not in a language, and the order does not matter. Maybe you meant something different? $\endgroup$ Sep 18 '17 at 20:39
  • $\begingroup$ Sometimes order does matter. For eg, $w \in L$ but $w^r \notin L$. Also, I edited the question as I am looking for deformation w.r.t reordering. $\endgroup$
    – Raj.R
    Sep 19 '17 at 5:09
  • $\begingroup$ Can you define defomation more precisely? Must a deformation be a reordering of the characters in the strings? Are all reorderings allowed? Does $\mbox{sorted}(L)$ qualify? $\endgroup$ Sep 19 '17 at 7:38
  • $\begingroup$ So you are interested in functions $f:\Sigma^*\to\Sigma^*$ such that for each symbol $a\in\Sigma$, the number of occurrences of $a$ is equal in $w$ and $f(w)$, i.e., $f$ permutes the symbols in $w$. And now you are looking for a function $f$ with this property, such that the minimal automaton for each regular language $L$ is significantly larger than a minimal automaton for $f(L)$? $\endgroup$
    – Danny
    Sep 19 '17 at 7:42
  • $\begingroup$ Also do you want to have a set of functions $f_L$ (so the function depends on the language), or are you interested in one function $f$ which is used for all regular languages? $\endgroup$
    – Danny
    Sep 19 '17 at 7:48

1) Here is a paper that studies your question in the case of finite languages $L$, and shows that if a finite language $L$ can be decided by an $n$-state DFA, then any permutation of $L$ can be decided by an $m$-state DFA for some $m \leq \frac13 (n^2 + n + 1)$:

Palioudakis A., Cho DJ., Goč D., Han YS., Ko SK., Salomaa K. (2015) The State Complexity of Permutations on Finite Languages over Binary Alphabets. In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118.

See slides here.

2) You might be interested in studies of read-once (algebraic) branching programs. Technically, this is a setting where the order of the input matters, but many of the results in this area apply regardless of how the input is ordered. While ro(A)BPs are slightly stronger than DFAs, they are closely related.

  • $\begingroup$ Thank you for the reference. This paper studies state complexity of $L'=\{\sigma(w) \mid \sigma \in S_n \& w \in L\}$ where $L \subseteq \Sigma^n$ and L has a $\bf{chain}$ DFA and for general L where $L$ does not have a chain DFA, question (upper bound) is still open (end of sec. 1 in journal version). Also I am looking for the complexity of $L'(\sigma)=\{\sigma(w) \mid w \in L\}$ where $\sigma$ is fixed. Is it possible for any $L$ there is a permutation $\sigma$ which makes $L'(\sigma)$ is easy. $\endgroup$
    – Raj.R
    Sep 20 '17 at 6:27

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