. We, A. ?. Let, ?. Dfa, L. Such, V. Struct et al.,

A. , B. , I. The-case-of, and G. Dfa, C can be chosen as the product of A and B. The automaton B can be constructed in time time O(2 |V| ) which is constant since V is a parameter of the certainty problem rather than being part of its input Then ? is a certain answer of Q(A) on G iff Inst(G * ?)?Struct) iff the empty ?-assignment is a certain answer of Q(C) on G . Based on this fact, the PTime reduction Cert, ) is obvious. Also, ? is a certain non-answer of Q(A) on G iff Inst(G * ?) ? L(A) = ? iff Inst(G ) ? L(A) = ? iff the empty ?-assignment is a certain non-answer of Q(A). This yields the PTime reduction showing Cert ¬ans ?,V (G, A) ? p Cert ¬ans ? V ,? (G, A)

, Corollary 1 (Non-linear patterns) For all B ? {ans, ¬ans}, G ? {Pat, cPat} and A ? {Dfa, Nfa}, the problem Cert B ?,V (G, A) is PSpace-complete

. Proof, N. Let, G. {patg, and A. , Since Incl ? (G, A) and Incl ? V (G, A) are PSpace-complete by Theorem 2, the problem Cert ans ?,V (G, A) is also PSpace-complete. On the other hand, ) by Lemma 5 and Proposition 5. Then by Theorem 2, coMatch ? (G, A) and coMatch ? V (G, A) are PSpace-complete (since PSpace is closed by complementation ), and thus Cert ¬ans ?,V (G, A) is PSpace-complete. This completes the proof. Our next objective is to study the complexity of the four certainty problems but restricted to compressed linear string patterns

, For all A ? {Dfa, Nfa}, the certainty problems Cert ¬ans ?,V (cLinPat, A) (1) and Cert ans ?,V (cLinPat, Dfa) (2) can be solved in PTime. The problem Cert ans ?,V (G, Nfa) is PSpace-complete for all G ? {LinPat, Corollary, vol.2, issue.3

. Proof, The statements are proved respectively

N. , A) ? p coMatch ? V (cLinPat, A) ? PTime, so Cert ¬ans ?,V (cLinPat, A) ? PTime, ) follows Theorem 3 and the reductions Cert ans ?,V (cLinPat, Dfa) ? p Cert ans ? V ,? (cLinPat, Dfa) ? p Incl ? V (cLinPat, Nfa) ? PTime. (3) For all G ? {LinPat, cLinPat}, Incl ? (G, Nfa) = p Cert ans ?,? (G, Nfa) ?

?. Cert-ans, V. Nfa-)-?-p-cert-ans, ?. V. , ?. Nfa-)-?-p-incl, and ?. Nfa, Since for all G ? {LinPat, Nfa) are PSpacecomplete by Theorem 3, we have that Cert ans ?,V (G, Nfa) is PSpace-complete

R. 1. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter et al., Foundations of Modern Query Languages for Graph Databases, ACM Computing Surveys, vol.50, issue.5, 1610.
DOI : 10.1007/978-1-4419-6045-0_6

D. Angluin, Finding patterns common to a set of strings, Journal of Computer and System Sciences, vol.21, issue.1, pp.46-62, 1980.
DOI : 10.1016/0022-0000(80)90041-0

L. Babai and E. Szemeredi, On The Complexity Of Matrix Group Problems I, 25th Annual Symposium onFoundations of Computer Science, 1984., pp.229-240, 1984.
DOI : 10.1109/SFCS.1984.715919

M. Benedikt, A. Jeffrey, and R. Ley-wild, Stream firewalling of xml constraints, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, pp.487-498, 2008.
DOI : 10.1145/1376616.1376667

P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti et al., Random Access to Grammar-Compressed Strings and Trees, SIAM Journal on Computing, vol.44, issue.3, pp.513-539, 2015.
DOI : 10.1137/130936889

H. Björklund, W. Gelade, and W. Martens, Incremental XPath evaluation. ACM Trans. Database Syst, vol.35, issue.4, p.29, 2010.

M. Blondin, A. Krebs, and P. Mckenzie, The complexity of intersecting finite automata having few final states. computational complexity, pp.775-814, 2016.

I. Boneva, J. Niehren, and M. Sakho, Approximating Certain Query Answering on Hyperstreams, 2018.

C. David, L. Libkin, and F. Murlak, Certain answers for XML queries, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data, PODS '10, pp.191-202, 2010.
DOI : 10.1145/1807085.1807112

D. Debarbieux, O. Gauwin, J. Niehren, T. Sebastian, and M. Zergaoui, Early nested word automata for XPath query answering on XML streams, Theoretical Computer Science, vol.578, pp.100-125, 2015.
DOI : 10.1016/j.tcs.2015.01.017
URL : https://hal.archives-ouvertes.fr/hal-00676178

A. Gascón, G. Godoy, and M. Schmidt-schauß, Context Matching for Compressed Terms, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, pp.93-102, 2008.
DOI : 10.1109/LICS.2008.17

O. Gauwin and J. Niehren, Streamable Fragments of Forward XPath, International Conference on Implementation and Application of Automata, pp.3-15, 2011.
DOI : 10.1145/1458082.1458305
URL : https://hal.archives-ouvertes.fr/inria-00442250

O. Gauwin, J. Niehren, and S. Tison, Earliest??Query??Answering for Deterministic Nested Word Automata, 17th International Symposium on Fundamentals of Computer Theory, pp.121-132, 2009.
DOI : 10.1016/j.ipl.2008.08.002
URL : https://hal.archives-ouvertes.fr/inria-00390236

O. Gauwin, J. Niehren, and S. Tison, Queries on XML streams with bounded delay and concurrency. Information and Computation, pp.409-442, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00491495

T. J. Green, A. Gupta, G. Miklau, M. Onizuka, and D. Suciu, Processing XML streams with deterministic automata and stream indexes, ACM Transactions on Database Systems, vol.29, issue.4, pp.752-788, 2004.
DOI : 10.1145/1042046.1042051

M. Kay, A streaming XSLT processor In Balisage: The Markup Conference 2010, Balisage Series on Markup Technologies, vol.5, 2010.

D. Kozen, Lower bounds for natural proof systems, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pp.254-266, 1977.
DOI : 10.1109/SFCS.1977.16

V. Kumar, P. Madhusudan, and M. Viswanathan, Visibly pushdown automata for streaming XML, Proceedings of the 16th international conference on World Wide Web , WWW '07, pp.1053-1062, 2007.
DOI : 10.1145/1242572.1242714

O. Kupferman and M. Y. Vardi, Model Checking of Safety Properties, Formal Methods in System Design, vol.19, issue.3, pp.291-314, 2001.
DOI : 10.1007/3-540-48683-6_17

P. Labath and J. Niehren, A functional language for hyperstreaming XSLT, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00806343

S. Maneth, A. O. Pereira, and H. Seidl, Transforming XML Streams with References, String Processing and Information Retrieval -22nd International Symposium, SPIRE 2015 Proceedings, volume 9309 of Lecture Notes in Computer Science, pp.33-45, 2015.
DOI : 10.1007/978-3-319-23826-5_4

B. Mozafari, K. Zeng, and C. Zaniolo, High-performance complex event processing over XML streams, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, pp.253-264, 2012.
DOI : 10.1145/2213836.2213866

D. Olteanu, SPEX: Streamed and Progressive Evaluation of XPath, IEEE Transactions on Knowledge and Data Engineering, vol.19, issue.7, pp.934-949, 2007.
DOI : 10.1109/TKDE.2007.1063

W. Plandowski, The complexity of the morphism equivalence problem for contextfree languages, 1995.

M. Schmidt, S. Scherzinger, and C. Koch, Combined Static and Dynamic Analysis for Effective Buffer Minimization in Streaming XQuery Evaluation, 2007 IEEE 23rd International Conference on Data Engineering, pp.236-245, 2007.
DOI : 10.1109/ICDE.2007.367869
URL : http://www.cs.cornell.edu/%7Ekoch/www.infosys.uni-sb.de/publications/INFOSYS-TR-2006-13.pdf

H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Progress in Computer Science and Applied Series. Birkhäuser, 1994.
DOI : 10.1007/978-1-4612-0289-9