本文中，我们对理论计算机科学中的下界问题及其意义进行了简要的综述，并阐述了作者在ω-自动机转换的状态复杂性和形式语言中starheight问题上的两项研究工作。 在ω-自动机转换上，我们首先提出了一种证明自动机状态转换复杂性下界的技巧，即full自动机技巧，然后将这种技巧应用到非确定ω-自动机的求补操作上。具体地，我们证明了一个Buchi自动机求补的Ω((0.76n)~n)的下界，并且证明了这个下界对于几乎所有ω-自动机的求补和确定化操作都有效。我们也证明了一个广义Buchi自动机求补的(Ω(nk))~n的下界，而这个下界对于Streett自动机的求补也有效。该项工作发表在了欧洲顶级的ICALP理论会议上，并获得最佳学生论文奖。 关于star height问题，我们引入了split游戏，一种逻辑中Ehrenfeucht-Fra(?)ssé游戏的变种，并证明了这种游戏能用于分析广义正则表达式的表达能力。我们也把split游戏推广到了广义ω-正则表达式。为了理解这种游戏如何能被用来攻克著名的困难的star height 2问题，我们提出并且解决了star height 2问题在ω-语言理论中的一个类似的但较为容易驾驭的变种，即omega power问题。实际上，我们证明了omega power算子和布尔算子以及连接算子一起无法表达整个ω-正则语言类。这项工作已被著名的Theoretical Computer Science杂志接受。