Dando continuidad al desarrollo de la semántica GS, se ha planteado estudiar la Complejidad Computacional y Descriptiva de la Programación en Lógica Rebatible a través de la semántica declarativa definida. En este sentido se estudiaron diferentes problemas de decisión y se calculó su complejidad computacional. Asimismo se avanzó en el estudio de la Complejidad de Datos, de los Programas y la Combinada. Este análisis es el punto de partida para el estudio en marcha de la expresividad de la teoría.