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

Improve this question
$\endgroup$
4
  • 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, 2012 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, 2012 at 18:49
  • $\begingroup$ Can you post the best family of languages you've found? $\endgroup$
    – didest
    Feb 29, 2012 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, 2012 at 1:38

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • 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$
    – didest
    Feb 29, 2012 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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