N. Alon, R. Yuster, and U. Zwick, Color-coding, J. ACM, vol.42, issue.4, pp.844-856, 1995.

R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter et al., Foundations of modern query languages for graph databases, ACM Comput. Surv, vol.50, issue.5, p.40, 2017.

M. Arenas, S. Conca, and J. Pérez, Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard, pp.629-638, 2012.

E. M. Arkin, C. H. Papadimitriou, and M. Yannakakis, Modularity of cycles and paths in graphs, J. ACM, vol.38, issue.2, pp.255-274, 1991.

G. Bagan, A. Bonifati, and B. Groz, A trichotomy for regular simple path queries on graphs, Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp.261-272, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00806448

C. L. Barrett, R. Jacob, and M. V. Marathe, Formal-language-constrained path problems, SIAM J. Comput, vol.30, issue.3, pp.809-837, 2000.

A. Bielefeldt, J. Gonsior, and M. Krötzsch, Practical linked data access via SPARQL: the case of Wikidata, Proceedings of LDOW Workshop, 2018.

A. Bonifati, W. Martens, and T. Timm, An analytical study of large SPARQL query logs, J, vol.11, issue.2, pp.149-161, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01979692

A. Bonifati, W. Martens, and T. Timm, Navigating the maze of Wikidata query logs, The World Wide Web Conference, pp.127-138, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02096714

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput, vol.17, issue.5, pp.935-938, 1988.

N. Immerman, Descriptive Complexity, 1999.

R. Jin, H. Hong, H. Wang, N. Ruan, and Y. Xiang, Computing label-constraint reachability in graph databases, SIGMOD Conference, pp.123-134, 2010.

T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas, Directed tree-width, J. Comb. Theory, Ser. B, vol.82, issue.1, pp.138-154, 2001.

A. Koschmieder and U. Leser, Regular path queries on large graphs, pp.177-194, 2012.

A. S. Lapaugh and C. H. Papadimitriou, The even-path problem for graphs and digraphs, Networks, vol.14, issue.4, pp.507-513, 1984.

U. Leser, A query language for biological networks, p.39, 2005.

K. Losemann and W. Martens, The complexity of regular expressions and property paths in SPARQL, ACM Trans. Database Syst. (TODS), vol.38, issue.4, p.24, 2013.

W. Martens and T. Trautner, Evaluation and enumeration problems for regular path queries, ICDT, in: LIPIcs, vol.98, p.21, 2018.

A. O. Mendelzon and P. T. Wood, Finding regular simple paths in graph databases, SIAM J. Comput, vol.24, issue.6, pp.1235-1258, 1995.

Z. P. Nedev, Finding an even simple path in a directed planar graph, SIAM J. Comput, vol.29, pp.685-695, 1999.

Z. P. Nedev and P. T. Wood, A polynomial-time algorithm for finding regular simple paths in outerplanar graphs, J. Algorithms, vol.35, issue.2, pp.235-259, 2000.

F. Olken, Graph data management for molecular biology, Omics. J. Integr. Biol, vol.7, issue.1, pp.75-78, 2003.

C. H. Papadimitriou, Computational Complexity, 1994.

M. Perles, M. Rabin, and E. Shamir, The theory of definite automata, IEEE Trans. Electron. Comput. EC, vol.12, issue.3, pp.233-243, 1963.

N. Robertson and P. D. Seymour, Graph minors XIII. The disjoint paths problem, J. Comb. Theory, Ser. B, vol.63, issue.1, pp.65-110, 1995.

W. L. Ruzzo, J. Simon, and M. Tompa, Space-bounded hierarchies and probabilistic computations, J. Comput. Syst. Sci, vol.28, issue.2, pp.216-230, 1984.

A. Schrijver, Finding k disjoint paths in a directed planar graph, SIAM J. Comput, vol.23, issue.4, pp.780-788, 1994.

M. P. Schützenberger, On finite monoids having only trivial subgroups, Inf. Control, vol.8, issue.2, pp.190-194, 1965.

C. B. Ward and N. M. Wiegand, Complexity results on labeled shortest path problems from wireless routing metrics, Comput. Netw, vol.54, issue.2, pp.208-217, 2010.