M. Arenas, P. Barceló, L. Libkin, and F. Murlak, Foundations of Data Exchange
DOI : 10.1017/CBO9781139060158

A. Balmin, Y. Papakonstantinou, and V. Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems, vol.29, issue.4, pp.710-751, 2004.
DOI : 10.1145/1042046.1042050

G. J. Bex, W. Gelade, W. Martens, and F. Neven, Simplifying XML schema, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, pp.731-744, 2009.
DOI : 10.1145/1559845.1559922

G. J. Bex, W. Gelade, F. Neven, and S. Vansummeren, Learning deterministic regular expressions for the inference of schemas from XML data, World Wide Web Conference (WWW), pp.825-834, 2008.

A. Brüggemann-klein and D. Wood, Deterministic regular languages, International Symposium on Theoretical Aspects of Computer Science (STACS), pp.173-184, 1992.
DOI : 10.1007/3-540-55210-3_182

A. Brüggemann-klein and D. Wood, One-Unambiguous Regular Languages, Information and Computation, vol.142, issue.2, pp.182-206, 1998.
DOI : 10.1006/inco.1997.2695

H. Chen and L. Chen, Inclusion Test Algorithms for One-Unambiguous Regular Expressions, International Colloquium on Theoretical Aspects of Computing (ICTAC), pp.96-110, 2008.
DOI : 10.1007/978-3-540-85762-4_7

D. Colazzo, G. Ghelli, and C. Sartiani, Efficient inclusion for a class of XML types with interleaving and counting, Information Systems, vol.34, issue.7, pp.643-656, 2009.
DOI : 10.1016/j.is.2008.10.001

URL : https://hal.archives-ouvertes.fr/inria-00535983

D. Fallside and P. Walmsley, XML Schema Part 0: Primer (second edition). World Wide Web Consortium, 2004.

W. Gelade, M. Gyssens, and W. Martens, Regular Expressions with Counting: Weak versus Strong Determinism, SIAM Journal on Computing, vol.41, issue.1, pp.160-190, 2012.
DOI : 10.1137/100814196

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.
DOI : 10.1137/070697367

W. Gelade and F. Neven, Succinctness of the Complement and Intersection of Regular Expressions, ACM Transactions on Computational Logic, vol.13, issue.1, pp.1-19, 2012.
DOI : 10.1145/2071368.2071372

URL : https://hal.archives-ouvertes.fr/hal-00226864

B. Groz, S. Maneth, and S. Staworko, Deterministic regular expressions in linear time, Proceedings of the 31st symposium on Principles of Database Systems, PODS '12, pp.49-60, 2012.
DOI : 10.1145/2213556.2213566

URL : https://hal.archives-ouvertes.fr/inria-00618451

J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2007.

D. Hovland, Regular Expressions with Numerical Constraints and Automata with Counters, International Colloquium on Theoretical Aspects of Computing (IC- TAC), pp.231-245, 2009.
DOI : 10.1007/978-3-642-03466-4_15

N. D. Jones, Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences, vol.11, issue.1, pp.68-85, 1975.
DOI : 10.1016/S0022-0000(75)80050-X

P. Kilpeläinen, Checking determinism of XML Schema content models in optimal time, Information Systems, vol.36, issue.3, pp.596-617, 2011.
DOI : 10.1016/j.is.2010.10.001

P. Kilpeläinen and R. Tuhkanen, One-unambiguity of regular expressions with numeric occurrence indicators, Information and Computation, vol.205, issue.6, pp.890-916, 2007.
DOI : 10.1016/j.ic.2006.12.003

C. Konrad and F. Magniez, Validating XML documents in the streaming model with external memory, International Conference on Database Theory (ICDT), pp.34-45, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00580814

K. Losemann, W. Martens, and M. Niewerth, Descriptional Complexity of Deterministic Regular Expressions, Mathematical Foundations of Computer Science (MFCS), pp.643-654, 2012.
DOI : 10.1007/978-3-642-32589-2_56

S. Maneth, A. Berlea, T. Perst, and H. Seidl, XML type checking with macro tree transducers, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '05, pp.283-294, 2005.
DOI : 10.1145/1065167.1065203

W. Martens and F. Neven, On the complexity of typechecking top-down XML transformations, Theoretical Computer Science, vol.336, issue.1, pp.153-180, 2005.
DOI : 10.1016/j.tcs.2004.10.035

T. Milo, D. Suciu, and V. Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, vol.66, issue.1, pp.66-97, 2003.
DOI : 10.1016/S0022-0000(02)00030-2

F. Neven and T. Schwentick, On the complexity of XPath containment in the presence of disjunction, DTDs, and variables, Logical Methods in Computer Science, vol.2, issue.3, 2006.
DOI : 10.2168/LMCS-2(3:1)2006

L. Segoufin and V. Vianu, Validating streaming XML documents, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '02, pp.53-64, 2002.
DOI : 10.1145/543613.543622

P. Van-emde and . Boas, The convenience of tilings, Complexity, Logic and Recursion Theory, pp.331-363, 1997.

P. T. Wood, Containment for XPath Fragments under DTD Constraints, International Conference on Database Theory (ICDT), pp.297-311, 2003.
DOI : 10.1007/3-540-36285-1_20