http://openproblemgarden.org/op/star_height_problem Comments for "Star height problem" en http://openproblemgarden.org/op/star_height_problem#comment-7116 <p>See the referenced Wikipedia article. </p> Fri, 30 Dec 2011 03:16:18 +0100 Robert Samal comment 7116 at http://openproblemgarden.org http://openproblemgarden.org/op/star_height_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/lawrence_eggan_c">Lawrence Eggan C.</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/theoretical_computer_science">Theoretical Comp. Sci.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; The <a href="http://en.wikipedia.org/wiki/Star_height_problem">star height problem</a> in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? </div> </tr></td> </table> </td> </tr> </table> Lawrence Eggan C. formal language Kleene stars regular expressions regular languages Theoretical Computer Science http://openproblemgarden.org/op/star_height_problem#comment Wed, 28 Dec 2011 22:06:02 +0100 porton 37368 at http://openproblemgarden.org