Regular languages viewed from a graph-theoretic perspective

In this paper, we consider the graph G ( L | w ), resp. the directed graph G → ( L | w ), associated with an arbitrary language L ⊆ Σ ⁎ and an arbitrary string w ∈ Σ ⁎. The clique number of L is then defined as the supremum of the clique numbers of the graphs G ( L | w ) where w ranges over all strings in Σ ⁎. The maximum in- or outdegree of L is defined analogously. We characterize regular languages with an infinite clique number and determine tight upper bounds in the finite case. We obtain analogous results for the maximum indegree and the maximum outdegree of a regular language. As an application, we consider the problem of determining the maximum activity level of a prefix-closed regular language — a parameter that is related to the computational complexity of parsing techniques utilizing unbounded regular lookahead. Finally, we determine the computational complexity of various problems arising from our graph-theoretic approach.

Authors

• Marius Konitzer
• Hans Ulrich Simon

Keywords

• Regular language
• Lookahead DFA
• Clique number
• Maximum degree
• Computational complexity