Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees
verfasst von : Hao Yuan, Patrick Eugster
Erschienen in: Programming Languages and Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The context-free language (CFL) reachability problem is well known and studied in computer science, as a fundamental problem underlying many important static analyses such as points-to-analysis. Solving the CFL reachability problem in the general case is very hard. Popular solutions resorting to a graph traversal exhibit a time complexity of
O
(
k
3
n
3
) for a grammar of size
k
. For Dyck CFLs, a particular class of CFLs, this complexity can be reduced to
O
(
kn
3
). Only recently the first subcubic algorithm was proposed by Chaudhuri, dividing the complexity of predating solutions by a factor of log
n
.
In this paper we propose an effective algorithm for solving the CFL reachability problem for Dyck languages when the considered graph is a bidirected tree with specific constraints. Our solution pre-processes the graph in
O
(
n
log
n
log
k
) time in a space of
O
(
n
log
n
), after which any Dyck-CFL reachability query can be answered in
O
(1) time, while a naïve online algorithm will require
O
(
n
) time to answer a query or require
O
(
n
2
) to store the pre-computed results for all pairs of nodes.