24

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$!

Community
  • 1
Aryeh
  • 10,494
  • 1
  • 27
  • 51
  • 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...? – vzn Feb 28 '12 at 16:56
  • 5
    The constructions in the proofs are abstract and it's not at all clear how to minimize them via the standard techniques. – Aryeh Feb 28 '12 at 18:49
  • Can you post the best family of languages you've found? – didest Feb 29 '12 at 00:35
  • 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 Feb 29 '12 at 01:38

1 Answers1

20

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

Jeffrey Shallit
  • 6,986
  • 33
  • 38
  • 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. – didest Feb 29 '12 at 02:34