<p>1) Here is a paper that studies your question in the case of <em>finite</em> 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)$:</p>

<blockquote>
  <p>Palioudakis A., Cho DJ., Goč D., Han YS., Ko SK., Salomaa K. (2015) <a href="https://doi.org/10.1007/978-3-319-19225-3_19" rel="nofollow noreferrer">The State Complexity of Permutations on Finite Languages over Binary Alphabets.</a> In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118. </p>
</blockquote>

<p>See <a href="https://cs.uwaterloo.ca/~shallit/DC2015/cho.pdf" rel="nofollow noreferrer">slides here</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2017-09-20T06:27:29.847Z
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.
Raj.R
CC BY-SA 3.0
2017-09-19T18:05:53.900Z
2017-09-19T18:05:53.900Z
Joshua Grochow
<p>Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA. 
Let $C$ be <em>some</em> class of acyclic DFAs.</p>

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

<p>Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.</p>

<p>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$. </p>

<p>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$.</p>

<p>Is there some references for study of these kind? are similar questions for CFL studied?</p>

<p>Thank you.</p>

CC BY-SA 3.0
2017-09-18T20:39:51.340Z
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?
András Salamon
CC BY-SA 3.0
2017-09-19T05:09:41.547Z
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.
Raj.R
CC BY-SA 3.0
2017-09-19T07:38:04.907Z
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?
reinierpost
CC BY-SA 3.0
2017-09-19T07:42:20.640Z
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)$?
Danny
CC BY-SA 3.0
2017-09-19T07:48:52.990Z
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?
Danny
CC BY-SA 3.0
2017-09-19T10:01:35.627Z
By deformation, I mean the complexity of DFA/NFA is reduced w.r.t some measure. Only deformation by permutations (reordering) are allowed. Eg, abc -->cba, bac, cab,bca, acb are valid. Yes all permutations are allowed but L' is defined w.r.t one permutation. So one can define different L' from L. Also as one can not apply all permutation uniformly to all lengths, can it be done for some given particular length. I am looking for set of functions $f$.
Raj.R
CC BY-SA 3.0
2017-09-19T10:07:42.467Z
You might also notice that for example the languages $L_k=\{w\in\Sigma^*:\; |w| \mod k=0\}$ are regular and each $L_k$ has an DFA of size $k$. Permutations are length-preserving and thus $f(L_K)=L_k$ for each allowed function $f$, wich means that there are regular languages where this "deformation" does not help.
Danny
CC BY-SA 3.0
2017-09-19T10:35:45.907Z
You are correct, w.r.t state complexity reordering will not help. But, is the DFA mentioned  already simple enough? As DFA is defined by  a cycle of length $k$.
Raj.R
CC BY-SA 3.0
2017-09-19T10:44:41.027Z
I am not sure if I understand your question, but since $f(L_k)=L_k$, you can take whatever complexity measure you want and it stays the same.
Danny
CC BY-SA 3.0
2017-09-19T10:50:40.067Z
Also you can take each regular length-language, i.e., languages $L$ where for each $n$ you have $\Sigma^n\subseteq L$ or $\Sigma^n\cap L=\emptyset$.
Danny
CC BY-SA 3.0
2017-09-19T11:03:34.600Z
I need to update the question as it needs more information.  Either L is already easy or some reordering of L becomes easy. In $L_k$ w.r.t DFA structure of $L_k$, $L_k$ is already easy in some sense. Thanks!
Raj.R
CC BY-SA 3.0
2017-09-19T11:13:18.250Z
I don't think that the question is senseful in this form.
Danny
CC BY-SA 3.0
2017-09-19T14:54:53.820Z
What about this example: given $L = \{w w^r \}$ we apply a reordering of the letters in each word in $L$ and we get $L' = \{ 0^{2n} 1^{2m} \} $ which is regular?
Marzio De Biasi
CC BY-SA 3.0
2017-09-20T06:20:12.860Z
All strings of given length needs to be reordered using single permutation. In your example this is not the case.
Raj.R
<reference-request><automata-theory><regular-language><context-free>
Deformation of finite regular languages
Raj.R
# Deformation of finite regular languages

(Asked by: username_0 on 2017-09-18)

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.

**Tags:** reference-request, automata-theory, regular-language, context-free
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_3**: 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)$?  
> **username_3**: 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?  
> **username_0**: By deformation, I mean the complexity of DFA/NFA is reduced w.r.t some measure. Only deformation by permutations (reordering) are allowed. Eg, abc -->cba, bac, cab,bca, acb are valid. Yes all permutations are allowed but L' is defined w.r.t one permutation. So one can define different L' from L. Also as one can not apply all permutation uniformly to all lengths, can it be done for some given particular length. I am looking for set of functions $f$.  
> **username_3**: You might also notice that for example the languages $L_k=\{w\in\Sigma^*:\; |w| \mod k=0\}$ are regular and each $L_k$ has an DFA of size $k$. Permutations are length-preserving and thus $f(L_K)=L_k$ for each allowed function $f$, wich means that there are regular languages where this "deformation" does not help.  
> **username_0**: You are correct, w.r.t state complexity reordering will not help. But, is the DFA mentioned  already simple enough? As DFA is defined by  a cycle of length $k$.  
> **username_3**: I am not sure if I understand your question, but since $f(L_k)=L_k$, you can take whatever complexity measure you want and it stays the same.  
> **username_3**: Also you can take each regular length-language, i.e., languages $L$ where for each $n$ you have $\Sigma^n\subseteq L$ or $\Sigma^n\cap L=\emptyset$.  
> **username_0**: I need to update the question as it needs more information.  Either L is already easy or some reordering of L becomes easy. In $L_k$ w.r.t DFA structure of $L_k$, $L_k$ is already easy in some sense. Thanks!  
> **username_3**: I don't think that the question is senseful in this form.  
> **username_4**: What about this example: given $L = \{w w^r \}$ we apply a reordering of the letters in each word in $L$ and we get $L' = \{ 0^{2n} 1^{2m} \} $ which is regular?  
> **username_0**: All strings of given length needs to be reordered using single permutation. In your example this is not the case.  

---

## 1 answers

### Answer by username_5 on 2017-09-19. Score: 3

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.](https://doi.org/10.1007/978-3-319-19225-3_19) In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118.

See [slides here](https://cs.uwaterloo.ca/~shallit/DC2015/cho.pdf).

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.

> **Comments:**
> **username_0**: 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.  

---

