The Rational Index: A Complexity Measure for Languages
Luc Boasson, Bruno Courcelle, Maurice Nivat · SIAM Journal on Computing · 1981
With every language L we associate an increasing function called its rational index. We obtain this function by comparing L with rational languages of increasing complexity. We show that the rational indices of two languages related by a rational transduction are polynomially related. From this, we can define new rational cones of languages in terms of rational indices. We then focus our attention on the rational index of context-free languages and raise several questions closely related to the open problems concerning the subcones of the family of context-free languages.