Complexity and structure in formal language theory
K.-J. Lange · 2002
Some connections between formal languages and complexity are reviewed. Families of formal languages are treated with complexity theoretical methods. In particular, the concept of unambiguity, common to both areas, is treated in detail. Some new results on deterministic families of formal languages and on complexities of operations on formal languages are indicated.>