equal
deleted
inserted
replaced
486 exponential $w.r.t$ the number of characters, |
486 exponential $w.r.t$ the number of characters, |
487 but will eventually level off when the string $s$ is long enough, |
487 but will eventually level off when the string $s$ is long enough, |
488 as suggested by the finiteness bound proof. |
488 as suggested by the finiteness bound proof. |
489 And unfortunately we have concrete examples |
489 And unfortunately we have concrete examples |
490 where such regexes grew exponentially large before levelling off: |
490 where such regexes grew exponentially large before levelling off: |
491 $(a ^ * + (a + aa) ^ * + (a + aa + aaa) ^ * + \ldots + |
491 $(a ^ * + (aa) ^ * + (aaa) ^ * + \ldots + |
492 (a+ aa + aaa+\ldots \underbrace{a \ldots a}_{\text{n a's}})^*$ will already have a maximum |
492 (\underbrace{a \ldots a}_{\text{n a's}})^*$ will already have a maximum |
493 size that is exponential on the number $n$. |
493 size that is exponential on the number $n$. |
494 %TODO: give out a graph showing how the size of the regex grows and levels off at a size exponential to the original regex |
494 %TODO: give out a graph showing how the size of the regex grows and levels off at a size exponential to the original regex |
495 |
495 |
496 |
496 |
497 While the tight upper bound will definitely be a lot lower than |
497 While the tight upper bound will definitely be a lot lower than |
501 This suggests stronger simplifications that keep the tight bound polynomial. |
501 This suggests stronger simplifications that keep the tight bound polynomial. |
502 |
502 |
503 %---------------------------------------------------------------------------------------- |
503 %---------------------------------------------------------------------------------------- |
504 % SECTION 5 |
504 % SECTION 5 |
505 %---------------------------------------------------------------------------------------- |
505 %---------------------------------------------------------------------------------------- |
506 \section{a stronger version of simplification} |
506 \section{A Stronger Version of Simplification} |
507 %TODO: search for isabelle proofs of algorithms that check equivalence |
507 %TODO: search for isabelle proofs of algorithms that check equivalence |
508 |
508 |
509 |
509 |