A. Abbas, P. Genevès, C. Roisin, and N. Layaïda, Optimising SPARQL query evaluation in the presence of shex constraints, BDA 2017, pp.1-12, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01673067

M. Arenas, C. Gutierrez, and J. Pérez, Foundations of RDF databases, Reasoning Web, International Summer School on Semantic Technologies for Information Systems, pp.158-204, 2009.

M. Arenas, J. Pérez, J. Reutter, C. Riveros, and J. Sequeda, Data exchange in the relational and RDF worlds. International Workshop on Semantic Web Information Management (SWIM), 2011.

G. J. Bex, F. Neven, and J. Van-den-bussche, DTDs versus XML Schema: A practical study, WebDB, pp.79-84, 2004.

I. Boneva, R. Ciucanu, and S. Staworko, Schemas for unordered XML on a DIME, Theoretical Computer Science (TCS), vol.57, issue.2, pp.337-376, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01076329

I. Boneva, J. Lozano, and S. Staworko, Relational to RDF data exchange in presence of a shape expression schema, Alberto Mendelzon International Workshop on Foundations of Data Management, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01775199

A. Brüggemann-klein and D. Wood, One-unambiguous regular languages. Information and Computation, vol.142, pp.182-206, 1998.

L. Cardelli and G. Ghelli, TQL: a query language for semistructured data based on the ambient logic, Mathematical Structures in Computer Science, vol.14, issue.3, pp.285-327, 2004.

?. ?ebiri?, F. Goasdoué, P. Guzewicz, and I. Manolescu, Compact Summaries of Rich Heterogeneous Graphs, 2018.

?. ?ebiri?, F. Goasdoué, and I. Manolescu, A Framework for Efficient Representative Summarization of RDF Graphs, International Semantic Web Conference (ISWC), 2017.

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree automata techniques and applications, 1997.

S. Dal-zilio and D. Lugiez, XML schema, tree logic and sheaves automata, Rewriting Techniques and Applications, pp.246-263, 2003.
URL : https://hal.archives-ouvertes.fr/hal-00109288

C. C. Elgot and M. O. Rabin, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, Journal of Symbolic Logic, vol.31, issue.2, pp.169-181, 1966.

M. F. Fernandez and D. Suciu, Optimizing regular path expressions using graph schemas, International Conference on Data Engineering (ICDE), pp.14-23, 1998.

W. Gelade, W. Martens, and F. Neven, Optimizing schema languages for XML: Numerical constraints and interleaving, SIAM Journal on Computing, vol.38, issue.5, pp.2021-2043, 2009.

F. Goasdoué, P. Guzewicz, and I. Manolescu, Incremental structural summarization of RDF graphs, International Conference on Extending Database Technology (EDBT), 2019.

E. Grädel, The complexity of subclasses of logical theories, 1987.

C. Haase and P. Hofman, Tightening the complexity of equivalence problems for commutative grammars, Symposium on Theoretical Aspects of Computer Science (STACS), vol.41, pp.1-41, 2016.

A. Klarlund, T. Schwentick, and D. Suciu, XML: Model, schemas, types, logics and queries, Logics for Emerging Applications of Databases, 2003.

E. Kopczynski and A. To, Parikh images of grammars: Complexity and applications, Logic in Computer Science (LICS), pp.80-89, 2010.

J. E. Gayo, E. Prud'hommeaux, I. Boneva, and D. Kontokostas, Validating RDF data, Synthesis Lectures on the Semantic Web: Theory and Technology, vol.7, issue.1, pp.1-328, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01667426

J. E. Gayo, E. Prud'hommeaux, I. Boneva, S. Staworko, H. R. Solbrig et al., Towards an RDF validation language based on regular expression derivatives, EDBT/ICDT Workshops (GraphQ & LWDM), pp.197-204, 2015.

J. E. Gayo, E. Prud'hommeaux, H. Solbrig, and J. M. Alvarez-rodriguez, Validating and describing linked data portals using RDF Shape Expressions, Workshop on Linked Data Quality, 2015.

W. Martens, F. Neven, and T. Schwentick, Complexity of decision problems for XML schemas and chain regular expressions, SIAM Journal on Computing, vol.39, issue.4, pp.1486-1530, 2009.

W. Martens, F. Neven, T. Schwentick, and G. J. Bex, Expressiveness and complexity of XML schema, ACM Transactions on Database Systems (TODS), vol.31, issue.3, pp.770-813, 2006.

A. J. Mayer and L. J. Stockmeyer, The complexity of word problems -this time with interleaving. Information and Computation, vol.115, pp.293-311, 1994.

G. Miklau and D. Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM, vol.51, issue.1, pp.2-45, 2004.

F. Neven and T. Schwentick, XML schemas without order, 1999.

D. C. Oppen, A 2 2 2 pn upper bound on the complexity of Presburger arithmetic, Journal of Computer and System Sciences, vol.16, issue.3, pp.323-332, 1978.

R. M. Robinson, Restricted set-theoretical definitions in arithmetic, Proceedings of the, pp.238-242, 1958.

H. Seidl, T. Schwentick, and A. Muscholl, Numerical document queries, ACM Symposium on Principles of Database Systems (PODS), pp.155-166, 2003.

H. Seidl, T. Schwentick, and A. Muscholl, Counting in trees, Logic and Automata: History and Perspectives, pp.575-612, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00358327

H. Seidl, Haskell overloading is dexptime-complete, Information Processing Letters, vol.52, issue.2, pp.57-60, 1994.

S. Staworko, I. Boneva, J. E. Gayo, S. Hym, E. G. Prud'hommeaux et al., Complexity and expressiveness of ShEx for RDF, International Conference on Database Theory (ICDT), pp.195-211, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01218552

S. Staworko and P. Wieczorek, Characterizing XML twig queries with examples, International Conference on Database Theory (ICDT), pp.144-160, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01205417

M. Veanes, On computational complexity of basic problems of finite tree automata, 1997.

. W3c, RDF validation workshop report: Practical assurances for quality RDF data, 2013.

V. Weispfenning, The complexity of almost linear diophantine problems, Journal of Symbolic Computation, vol.10, issue.5, pp.395-404, 1990.

H. Zhang, Y. Duan, X. Yuan, and Y. Zhang, ASSG: adaptive structural summary for RDF graph data, International Semantic Web Conference (ISWC), pp.233-236, 2014.