. Proof, We prove this result via a log-space reduction from the complement of the reachability problem in directed acyclic graphs (DAGs) This problem asks, given a DAG G = (V, E), a source node s, and a target node t, whether t is reachable from s by a directed path. The DAG reachability problem is wellknown to be NL-complete [29]

?. For-each-vertex-v-i, v i )) = v i and ?(v i , (v i , q f )) = q f are in D; and ? the transition ?(t, (t, s)) = s is in D

]. W. Czerwinski, C. David, K. Losemann, and W. Martens, As such, every transition has its unique label This concludes the reduction, which can be conducted in logarithmic space In order to complete the proof we need to show the following two facts Deciding definability by deterministic regular expressions, Proceedings of the 16th International Conference on Foundations of Software Science and Computation Structures (FOSSACS), pp.289-304, 2013.

T. Bray, J. Paoli, C. M. Sperberg-mcqueen, E. Maler, and F. Yergeau, Extensible Markup Language XML 1, Tech. rep., World Wide Web Consortium (W3C), w3C Recommendation, 2008.

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
URL : http://www.lsv.ens-cachan.fr/%7Esegoufin/Papers/Mypapers/streaming-pods.pdf

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

C. Konrad and F. Magniez, Validating XML documents in the streaming model with external memory, ACM Transactions on Database Systems (TODS), vol.38, issue.27, 2013.
DOI : 10.1145/2274576.2274581
URL : https://hal.archives-ouvertes.fr/hal-00580814

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
URL : https://doi.org/10.1016/s0022-0000(02)00030-2

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
URL : https://doi.org/10.1016/j.tcs.2004.10.035

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
URL : http://wwwbib.informatik.tu-muenchen.de/infberichte/2004/TUM-I0407.ps

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, pp.1-30, 2006.
DOI : 10.2168/LMCS-2(3:1)2006

P. T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory (ICDT, pp.297-311, 2003.
DOI : 10.1007/3-540-36285-1_20
URL : http://www.dcs.bbk.ac.uk/~ptw/icdt03.ps.gz

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

D. Fallside, P. Walmsley, and . Schema, Primer (second edition), Tech. rep., World Wide Web Consortium (W3C), w3C Recommendation at http://www.w3.org/TR, 2004.

A. Brüggemann-klein and D. Wood, Deterministic regular languages, Proceedings of the 9th Annual 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

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, ACM Transactions on the Web, vol.4, issue.4, pp.1-1432, 2010.
DOI : 10.1145/1841909.1841911
URL : http://alpha.uhasselt.be/~lucg6377/publications/www08.pdf

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-4, 2012.
DOI : 10.1145/2071368.2071372
URL : https://hal.archives-ouvertes.fr/hal-00226864

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

H. Chen and L. Chen, Inclusion Test Algorithms for One-Unambiguous Regular Expressions, Proceedings of the 5th 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

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

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

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
URL : http://alpha.uhasselt.be/~lucg6377/publications/mfcs09.pdf

D. Hovland, Regular Expressions with Numerical Constraints and Automata with Counters, Proceedings of the 6th International Colloquium on Theoretical Aspects of Computing, pp.231-245, 2009.
DOI : 10.1007/BFb0023820
URL : https://bora.uib.no/bitstream/1956/3628/3/Hovland_LNCS%205684.pdf

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

B. Groz, XML security views: Queries, updates and schemas, 2012.
URL : https://hal.archives-ouvertes.fr/tel-00745581

J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education, 2007.
DOI : 10.1145/568438.568455

A. R. Meyer and L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, 13th Annual Symposium on Switching and Automata Theory (swat 1972), pp.125-129, 1972.
DOI : 10.1109/SWAT.1972.29

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
URL : https://doi.org/10.1016/s0022-0000(75)80050-x

P. Lu, J. Bremer, and H. Chen, Deciding determinism of regular languages, Theory of Computing Systems, pp.1-43, 2014.
DOI : 10.1007/s00224-014-9576-2