Paper Info
Title
Regular languages viewed from a graph-theoretic perspective.
Abstract
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.
Year
DOI
Venue
2017
10.1016/j.ic.2016.06.012
Inf. Comput.
Keywords
Field
DocType
Regular language,Lookahead DFA,Clique number,Maximum degree,Computational complexity
Discrete mathematics,Combinatorics,Clique graph,Clique,Directed graph,Infimum and supremum,Regular graph,Degree (graph theory),Regular language,Mathematics,Computational complexity theory
Journal
Volume
Issue
ISSN
253
P3
0890-5401
Citations 
PageRank 
References 
0
0.34
9
Authors
2
Name
Order
Citations
PageRank
Marius Konitzer120.74
Hans-Ulrich Simon2567104.52