Information Technology Reference
In-Depth Information
(a) With the
H
average time curve.
(b) Without the
H
average time curve.
Fig. 4.
Average time for computing
Safe
(
u
),
LSafe
(
u
)and
Reach
(
u
) and overall com-
putation for 15 random trees
6.2 VPAs Resulting from XPath Translation
Our second benchmark is based on VPAs obtained from queries over XML doc-
uments expressed in the XPath language, and then translated into VPAs. This
translation was performed by the QuiXProc tool, as described in [GN11]. This
family of XPath expressions yields VPAs of linear size increase (VPA with id
i
has 16+11
i
states), and looks for some complex patterns in the tree. In Figure 4
we report the time used by our algorithm on randomly generated trees, for this
family of VPAs. This shows that for real-world VPAs, the size of
H
is outside
the hardness threshold exhibited in Figure 3. For instance, for the VPA with id
9andsize
is computed in about 120s. Moreover, Figure 4b shows
the eciency of our online algorithm (less than 0.8s).
|
Q
|
= 115,
H
Acknowledgements.
We thank Gregoire Sutre for useful discussions, and the
QuiXProc team for translating XPath expressions of our benchmark to VPAs.
We also thank one of the reviewers who helped us to improve the presentation
of this article. The second author is supported by a grant from FRIA. This work
was also partially supported by CNRS SOSP project.
References
[AEM04]
Alur, R., Etessami, K., Madhusudan, P.: A temporal logic of nested calls
and returns. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS,
vol. 2988, pp. 467-481. Springer, Heidelberg (2004)
[AM04]
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proc. STOC,
pp. 202-211. ACM Press (2004)
[AM09]
Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56,
1-43 (2009)
[BYFJ05]
Bar-Yossef, Z., Fontoura, M., Josifovski, V.: Buffering in query evaluation
over XML streams. In: Proc. PODS, pp. 216-227. ACM Press (2005)
