<p>See Mike Domaratzki's paper, State complexity of proportional removals</p>

<p><a href="http://dl.acm.org/citation.cfm?id=782471">http://dl.acm.org/citation.cfm?id=782471</a></p>

<p><a href="http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps">http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps</a></p>

CC BY-SA 3.0
2012-02-29T02:34:43.003Z
Excellent! theorem 6 gives a family of languages with $\Omega(e^{\sqrt{n\log n}})$ and theorem 3 gives an upper bound of $O(n e^{\sqrt{n\log n}})$, so there is little space for improvement.
didest
CC BY-SA 3.0
2012-02-29T01:55:45.167Z
2012-02-29T01:55:45.167Z
Jeffrey Shallit
<p>For any language $L$ over $\Sigma^*$, define 
$$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.</p>

<p>An exercise in Sipser's book asks to show that $L_{1/2}$ is regular whenever $L$ is. I have seen two distinct solutions, and both involve an exponential blow-up of states.</p>

<p>Question: can anyone construct a family of languages $\{L_n\}$ such that the canonical automaton for $(L_n)_{1/2}$ is significantly (say, exponentially) larger than that for $L$? My best efforts so far only increase the state size by $+1$!</p>

CC BY-SA 3.0
2012-02-28T16:56:46.723Z
you dont mention the semiobvious issue of DFA minimization. havent seen the proofs but maybe they do not take it into acct. and a DFA minimization post-run on the proof construction might simplify the DFA significantly...?
vzn
CC BY-SA 3.0
2012-02-28T18:49:21.427Z
The constructions in the proofs are abstract and it's not at all clear how to minimize them via the standard techniques.
Aryeh
CC BY-SA 3.0
2012-02-29T00:35:39.673Z
Can you post the best family of languages you've found?
didest
CC BY-SA 3.0
2012-02-29T01:38:30.273Z
this is not reqd to answer your Q but it might be helpful to sketch out the constructions. another option is to attack the problem empirically with random FSMs
vzn
<fl.formal-languages><automata-theory>
complexity of the half language
Aryeh
# complexity of the half language

(Asked by: username_0 on 2012-02-28)

For any language $L$ over $\Sigma^\*$, define
$$L\_{1/2} = \{x \in \Sigma^\* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L\_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.

An exercise in Sipser's book asks to show that $L\_{1/2}$ is regular whenever $L$ is. I have seen two distinct solutions, and both involve an exponential blow-up of states.

Question: can anyone construct a family of languages $\{L\_n\}$ such that the canonical automaton for $(L\_n)\_{1/2}$ is significantly (say, exponentially) larger than that for $L$? My best efforts so far only increase the state size by $+1$!

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: you dont mention the semiobvious issue of DFA minimization. havent seen the proofs but maybe they do not take it into acct. and a DFA minimization post-run on the proof construction might simplify the DFA significantly...?  
> **username_0**: The constructions in the proofs are abstract and it's not at all clear how to minimize them via the standard techniques.  
> **username_2**: Can you post the best family of languages you've found?  
> **username_1**: this is not reqd to answer your Q but it might be helpful to sketch out the constructions. another option is to attack the problem empirically with random FSMs  

---

## 1 answers

### Answer by username_3 on 2012-02-29. Score: 20 | Accepted answer

See Mike Domaratzki's paper, State complexity of proportional removals

<http://dl.acm.org/citation.cfm?id=782471>

<http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps>

> **Comments:**
> **username_2**: Excellent! theorem 6 gives a family of languages with $\Omega(e^{\sqrt{n\log n}})$ and theorem 3 gives an upper bound of $O(n e^{\sqrt{n\log n}})$, so there is little space for improvement.  

---

