24
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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...? $\endgroup$ – vzn Feb 28 '12 at 16:56
  • 5
    $\begingroup$ The constructions in the proofs are abstract and it's not at all clear how to minimize them via the standard techniques. $\endgroup$ – Aryeh Feb 28 '12 at 18:49
  • $\begingroup$ Can you post the best family of languages you've found? $\endgroup$ – Diego de Estrada Feb 29 '12 at 0:35
  • $\begingroup$ 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 $\endgroup$ – vzn Feb 29 '12 at 1:38
20
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Diego de Estrada Feb 29 '12 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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