R. Lemma-2 and . Satisfiability, ? RE is a regular expression that does not contain blanks)

. Proof, . Re-path, N. Satisfiability-is-in, S. Abiteboul, D. Quass et al., since each blank in the regular expression R can be mapped (assigned) to p terms, where p denotes the number of terms appearing as predicates in G. If the number of blanks in R is x, then there are (p x ) possible assignments (mappings) in all The Lorel query language for semistructured data, Journal on Digital Libraries, vol.1, pp.1-68, 1997.

A. , A. V. Hopcroft, J. E. And-ullman, and J. D. , The Design and Analysis of Computer Algorithms, 1974.

A. , N. Demri, S. And-de-rijke, and M. , A modal perspective on path constraints, Journal of Logic and Computation, vol.13, pp.1-18, 2003.

B. , J. De-moor, A. Lex, W. And-ganter, and B. , Simple conceptual graphs revisited: Hypergraphs and conjunctive types for efficient projection algorithms, Proceedings of the 11th International Conference on Conceptual Structures (ICCS'03), pp.229-242, 2003.

D. Beckett, Turtle -terse RDF triple language, 2006.

B. , D. And-guha, and R. V. , RDF vocabulary description language 1.0: RDF schema, p.23, 2003.

B. , P. Davidson, S. Hillebrand, G. And-suciu, and D. , A query language and optimization techniques for unstructured data, Proceedings of the ACM SIGMOD International Conference on the Management of Data, pp.505-516, 1996.

C. , J. J. And-klyne, and G. , RDF concepts and abstract syntax, 2004.

C. , M. P. And-mendelzon, and A. , Graphlog: a visual formalism for real life recursion, Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp.404-416, 1990.

C. , O. Dieng, R. And-hébert, and C. , A conceptual graph model for W3C resource description framework, Proceedings of the International Conference on Conceptual Structures, pp.468-482, 2000.

C. , I. F. Mendelzon, A. O. And-wood, and P. T. , A graphical query language supporting recursion, Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data, pp.323-330, 1987.

C. , I. F. Mendelzon, A. O. And-wood, and P. T. , Recursive queries without recursion, Proceedings of Second International Conference on Expert Database Systems, pp.355-368, 1988.

D. Moor, O. And-david, and E. , Universal regular path queries, Higher-Order and Symbolic Computation, pp.15-35, 2003.

G. , C. Hurtado, C. And-mendelzon, and A. , Foundations of semantic web databases, ACM Symposium on Principles of Database Systems (PODS), pp.95-106, 2004.

H. , P. Broekstra, J. Eberhart, A. And, and R. Volz, A comparison of RDF query languages, Proceedings of the 3rd International Semantic Web Conference (ICWC) (Hiroshima (JP), pp.502-517, 2004.

L. , Y. A. Rothamel, T. , Y. , F. Stoller et al., Parametric regular path queries, Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp.219-230, 2004.

M. , A. O. And-wood, and P. , Finding regular simple paths in graph databases, SIAM Journal on Computing, vol.24, issue.6, pp.1235-1258, 1995.

M. , E. Swick, R. And-brickley, and D. , Resource description framework (RDF), 2004.

M. , M. And-chein, and M. , Conceptual graphs: Fundamental notions. Revue d'intelligence artificielle 6, pp.365-406, 1992.

M. , M. And-chein, and M. , Polynomial algorithms for projection and matching, Proceedings of the 7th Annual Workshop on Conceptual Structures: Theory and Implementation, pp.239-251, 1993.

P. , J. Arenas, M. And-gutierrez, and C. , Semantics and complexity of SPARQL, Proceedings 5th International Semantic Web Conference, pp.30-43, 2006.

E. Prud-'hommeaux and A. And-seaborne, SPARQL query language for RDF. Working draft, p.3, 2006.

I. Unité-de-recherche and I. Rhône, Alpes 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rocquencourt : Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex (France) Unité de recherche, 2004.

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399