Diego Figueira
email: diego.figueira@labri.fr

Leonid Libkin
email: libkin@inf.ed.ac.uk

Path Logics for Querying Graphs: Combining Expressiveness and Efficiency

We study logics expressing properties of paths in graphs that are tailored to querying graph databases: a data model for new applications such as social networks, the Semantic Web, biological data, crime detection, and others. The basic construct of such logics, a regular path query, checks for paths whose labels belong to a regular language. These logics fail to capture two commonly needed features: counting properties, and the ability to compare paths. It is known that regular path-comparison relations (e.g., prefix or equality) can be added without significant complexity overhead; however, adding common relations often demanded by applications (e.g., subword, subsequence, suffix) results in either undecidability or astronomical complexity.

We propose, as a way around this problem, to use automata with counting functionalities, namely Parikh automata. They express many counting properties directly, and they approximate many relations of interest. We prove that with Parikh automata defining both languages and relations used in queries, we retain the low complexity of the standard path logics for graphs. In particular, this gives us efficient approximations to queries with prohibitively high complexity. We extend the best known decidability results by showing that even more expressive classes of relations are possible in query languages (sometimes with restriction on the shape of formulae). We also show that Parikh automata admit two convenient representations by analogs of regular expressions, making them usable in real-life querying.

I. INTRODUCTION

Our main object of interest is logics for querying edgelabeled graphs. Of course such logics exist in abundance, and they come in many flavors, depending on the intended applications. Many such applications arise in verification, and logics are designed to specify temporal properties observed along paths in graphs. We are interested in logics that arise in the study of semistructured data, i.e., data that does not conform to the standard relational model [START_REF] Abiteboul | Data on the Web: From Relations to Semistructured Data and XML[END_REF]. These classes of logics have many commonalities [START_REF] Libkin | Logics for unranked trees: an overview[END_REF], [START_REF] Marx | Conditional XPath[END_REF], but they are still sufficiently distinct due to the nature of applications and specific computational requirements posed by them.

The main need for the development and study of the logics we are looking at comes from graph databases [START_REF] Robinson | Graph Databases[END_REF]. They have emerged as a new trend in data management technology fairly recently, and have attracted much attention due to numerous applications in many active areas where the underlying data is naturally modeled as a graph; these include social networks, Semantic Web and RDF, biological networks, crime detection, etc. Multiple prototypes and commercial systems exist, includ-ing NEO4J, INFINITEGRAPH, ALLEGROGRAPH, ORIENTDB; see also [START_REF] Angles | Survey of graph database models[END_REF], [START_REF] Barceló | Querying graph databases[END_REF], [START_REF] Wood | Query languages for graph databases[END_REF] for recent surveys of the area.

Among the proposals for logical languages for querying graph data, the ones that use regular path queries, or RPQs have become most commonly accepted (although other interesting proposals exist as well, for instance those based on adapting spatial calculi for semistructured data [START_REF] Cardelli | A spatial logic for querying graphs[END_REF], [START_REF] Dawar | Expressiveness and complexity of graph logic[END_REF]). RPQs, proposed initially in [START_REF] Cruz | A graphical query language supporting recursion[END_REF], check the existence of a path whose label belongs to a regular language. Formally, such a query is of the form x

L -→ y
where L is a regular language. When applied to a graph G, it returns pairs of nodes x and y such that there is an Llabeled path between them. Such queries play the role of atomic formulae in other formalisms. Most commonly, they are closed under conjunction and existential quantification, resulting in conjunctive regular path queries (CRPQs) [START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF], [START_REF] Florescu | Query containment for conjunctive queries with regular expressions[END_REF] by analogy with the usual conjunctive queries, i.e., the ∃, ∧-fragment of first-order predicate logic. One commonly writes them as rules: for instance, q(x) :-x a + --→ y, x b + -→ y looks for nodes x from which both an a-labeled path and a b-labeled path to the same node y exist. CRPQs are well understood, and have many nice properties: for instance, they can be efficiently evaluated, matching the combined complexity of relational conjunctive queries [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF]. However, for many applications their power is insufficient [START_REF] Barceló | Querying graph databases[END_REF], [START_REF] Fan | Graph pattern matching revised for social network analysis[END_REF], [START_REF] Wood | Query languages for graph databases[END_REF]. The main shortcomings of CRPQs stem from the fact that

• they cannot compare paths; and • they are limited to regular properties of paths. For instance, already over a decade ago, the RDF community proposed a query language in which paths can be compared for specific semantic associations [START_REF] Anyanwu | ρ-Queries: enabling querying for semantic associations on the semantic web[END_REF]. Applications in biology and crime detection often require checking the similarity of paths, e.g., based on their edit distance, or relations such as subword or subsequence. We refer to [START_REF] Angles | Survey of graph database models[END_REF], [START_REF] Barceló | Querying graph databases[END_REF], [START_REF] Fan | Graph pattern matching revised for social network analysis[END_REF], [START_REF] Wood | Query languages for graph databases[END_REF] for multiple concrete examples of properties of paths that need to be checkable by logical query languages.

Thus, finding ways to increase the power of graph query languages has been a major theme in graph data research over the past several years. When it comes to comparing paths, the key idea is to name paths and quantify over them [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], [START_REF] Hellings | Walk logic as a framework for path query languages on graph databases[END_REF]. Once we have the ability to refer to paths, we can use them in formulas by testing relationships between them. To give a concrete example, consider a formula q(x, y) :-

x π1:a + ----→ z, z π2:b + ---→ y, |π 1 | = |π 2 |. (1)
It says that there is an a-labeled path π 1 from x to some node z, from which there is a b-labeled path π 2 to y such that the lengths of π 1 and π 2 are the same. In other words, x and y are connected by a path labeled a n b n for some n ≥ 1. The above formula comes from a class of extended CRPQs [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], which continue to enjoy many nice computational properties. Their data complexity is in NLOGSPACE (the best possible, as they express NLOGSPACE-complete reachability), and their combined complexity is PSPACE-complete, matching that of first-order logic (and thus of traditional relational databases).

Relations on paths used in extended CRPQs are regular (or synchronized) relations. The best way to visualize such a relation (say, binary) is to think of an automaton over a pair of words with two synchronously moving heads, first looking at the initial letters of the words, then at their second letters, and so on; when one word ends, only the remaining head continues. Examples of such relations are equal length, equality, prefix, or having edit distance bounded by a fixed constant [START_REF] Sakarovitch | Elements of Automata Theory[END_REF].

However, many real-life relations of interest are not regular. Relations such as subword, subsequence, suffix which are very often required to express semantic associations between paths in RDF, or in biological and crime detection applications are not regular but rational [START_REF] Choffrut | Relations over words and logic: a chronology[END_REF], [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]: they are given by automata whose heads move asynchronously.

So it seems natural to add them to RPQ-based logical formalisms. This carries a huge price though: the query evaluation problem becomes undecidable with adding subword or suffix, and of astronomical complexity when subsequence is added [START_REF] Barceló | Graph logics with rational relations[END_REF]. To lower the complexity, severe restrictions are required: only one relation among paths can be used in the query, and the query itself must be restricted syntactically [START_REF] Barceló | Graph logics with rational relations[END_REF], [START_REF] Barceló | Graph logics with rational relations: the role of word combinatorics[END_REF]; this effectively rules out such query languages.

Problem: adding relations needed in real-life querying tasks to existing logical formalisms leads to prohibitively high complexity. But at the same time one cannot give up and dismiss such queries since they do often arise in practice.

Our approach: we look for suitable approximate solutions. To make it work, we need a sufficiently expressive and at the same time efficient logical framework in which finding approximate answers to queries involving complex nonregular properties is feasible.

To understand what such a framework might be, we appeal to an example. Consider a graph database used in a crime detection application, and assume that a query requires the comparison of two paths. One of them, π, is known to indicate criminal activity, the other, π , is suspect, and we want to see if π occurs as a subsequence of π. This is computationally too expensive [START_REF] Barceló | Graph logics with rational relations[END_REF], but instead we can attempt to check whether # a (π ) ≤ # a (π) for every label a, where # a (π) is the number of occurrences of a in π. This does not give the exact answer to the query of course, but it selects paths that need to be further analyzed -and, as we shall see, this can be answered with low complexity. If we are interested in a subword relation, we can select a portion of path π so that the numbers of occurrences of all symbols in that portion will be the same as in π .

This approach could be used with many properties that need to be tested by graph database queries, and not only counting occurrences of letters. For instance, suppose that a word w i indicates a position of interest on a path π i , and we want to check if letters that follow each occurrence of w 1 in π 1 , and each occurrence of w 2 in π 2 , form the same word. This similarly can be approximated by counting the numbers of occurrences of each label a after w i in π i , and comparing these numbers.

Thus, the general idea is to replace precise properties of words by their counting approximations. This approach has been used successfully in verification [START_REF] Dang | Binary reachability analysis of discrete pushdown timed automata[END_REF], [START_REF] Esparza | Complexity of pattern-based verification for multithreaded programs[END_REF], [START_REF] Hague | Synchronisation-and reversal-bounded analysis of multithreaded programs with counters[END_REF], [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF], [START_REF] König | Verification of graph transformation systems with context-free specifications[END_REF], and it seems natural to extend it to querying paths in graph databases.

Note that we go beyond simple Parikh images (i.e., counting letter occurrences). To capture properties of words formed by specific positions, we may need to express languages like

L ba=ca = w
the number of as that follow a b = the number of as that follow a c What makes it possible for us to provide efficient query evaluation mechanism is the existence of an automata model for these properties: Parikh automata [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF]. The intuition behind them is as follows. Assume that we have a fixed number k of counters. Each automaton transition, in addition to the usual NFA transition, carries a k-vector of integers; in a run, when such transition applies, these numbers are added to the counters. At the end, one checks a linear arithmetic constraint to determine acceptance. To accept the language L ba=ca , we have counters r 1 and r 2 ; then r 1 is incremented in the state reached after reading ba, and r 2 in the state reached after reading ca. Acceptance is given by r 1 = r 2 .

We demonstrate that these automata are very suitable for asking complex graph queries, due to three reasons:

• They can express counting approximations for many relevant properties that are otherwise too expensive to use directly in queries; • they lead to good complexity of query evaluation; and • there are natural ways of expressing languages given by such automata, making them usable in real-life queries.

Contributions

We prove some results about Parikh automata that are necessary for understanding how to use them in graph querying, and demonstrate a few query languages based on Parikh automata that are both expressive and have good query evaluation complexity; these languages go significantly beyond previously known decidable languages in terms of their expressiveness. In more detail, we do the following.

• We pinpoint the exact complexity of some decidable problems related to Parikh automata, as these are needed to establish the complexity of query evaluation. • We show that paths definable by Parikh automata can be added to CRPQs without an increase in complexity. • We develop a theory of Parikh-definable relations, rather than languages, coming up with natural analogs of regular and rational relations over words. We do this by using a notion of synchronizations recently proposed in [START_REF] Figueira | Synchronizing relations on words[END_REF] as it lets one define classes of relations without relying on modes of acceptance, as is usually done in formal language theory. We also provide two natural analogs of regularity, allowing us to incorporate more relations into queries, and show that some problematic relations like subword and subsequence can naturally be approximated by regular Parikh relations. thus, to be able to use Parikh automata in real-life query languages, we need an analog of regular expressions for them. We present in fact two such analogs, one based on the idea of marking positions in a regular expression, and the other on choosing regular expressions that apply to prefixes of a word. Organization Basic notations are given in Section II. In Section III we give necessary information about Parikh automata. Section IV studies evaluation of CRPQs with Parikh automata. In Section V we investigate relations based on Parikh automata, and in Section VI we study query evaluation with such relations. In Section VII we provide two types of regular expressions for Parikh automata. Due to space limitations, complete proofs are in the appendix.

II. PRELIMINARIES

Basic notations Let N + = {1, 2, . . . } and N = N + ∪ {0}. We write k to denote the set {1, . . . , k}. We use letters A, B to denote finite alphabets. The set of finite words over A is denoted by A * . For a word w = a 1 • • • a n ∈ A * , the letter a i in the ith position is denoted by w[i], the subword a i • • • a j by w[i, j], and the length n of the word by |w|. Given w ∈ A * and a letter a ∈ A, we define # a (w) as the number of occurrences of a in w.

For two words u = a 1 • • • a n ∈ A * and v = b 1 • • • b n ∈ B * , we write u ⊗ v for the word (a 1 , b 1 ) • • • (a n , b n ) ∈ (A × B) * .
This definition can be extended to words of different length: in that case, the shorter word (say, u) is padded with |v| -|u| letters ⊥ that do not occur in A, B to a word u (of the same length as v) and then we take u ⊗ v to be u ⊗ v. This definition straightforwardly extends to tuples of words, i.e., to

w 1 ⊗ w 2 ⊗ • • • ⊗ w k .
Parikh images, semilinear sets, and Presburger arithmetic For a finite, ordered, alphabet A = {a 1 , . . . , a k }, the Parikh image of a word w ∈ A * , written Π(w), is the vector of N k whose ith component contains # ai (w), the number of occurrences of a i in w. The Parikh image of a language L is Π(L) = {Π(w) | w ∈ L}.

A linear set is a subset of N k that can be described as

{v 0 + α 1 v1 + • • • + α n vn | α 1 , . . . , α n ∈ N} (2)
for some n ∈ N and v0 , . [START_REF] Ginsburg | Semigroups, Presburger formulas, and languages[END_REF] and to Parikh images of context free (or regular) languages [START_REF] Parikh | On context-free languages[END_REF]. Moreover, using the doubling function to represent each n ∈ N as a term of Presburger arithmetic of size O(log n), we have the following.

Lemma II.1. For any given semilinear set, an equivalent existential Presburger formula can be produced in linear time.

Graph databases, RPQs and CRPQs

The standard abstraction of graph databases [START_REF] Angles | Survey of graph database models[END_REF], [START_REF] Barceló | Querying graph databases[END_REF], [START_REF] Robinson | Graph Databases[END_REF] is finite A-labeled graphs G = V, E , where V is a finite set of nodes, or vertices, and

E ⊆ V × A × V is a set of labeled edges. A path p from v 0 to v m in G is a sequence of edges (v 0 , a 1 , v 1 ), (v 1 , a 2 , v 2 ), • • • , (v m-1 , a m , v m ) from E, for some m ≥ 0.
The label of p, denoted by λ(p), is the word

a 1 • • • a m ∈ A * .
The main building blocks for graph queries are regular path queries, or RPQs [START_REF] Cruz | A graphical query language supporting recursion[END_REF]; they are expressions of the form x L → y, where L is a regular language over A. Given an Alabeled graph G = V, E , the answer to an RPQ above is the set of pairs of nodes (v, v ) such that there is a path p from v to v with λ(p) ∈ L. Conjunctive RPQs, or CRPQs [START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF], [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF] are the closure of RPQs under conjunction and existential quantification. We present them in a rule-based notation; formally, a CRPQ is an expression of the form

ϕ(z) :-x 1 L1 --→ y 1 , • • • , x m Lm --→ y m , (3)
where x i , y i s are variables, and z is a tuple of variables among those (as usual, variables that appear in the body of the rule but not in the head are assumed to be existentially quantified; that is, we can view CRPQ (3) as ϕ(z) = ∃z m i=1 (x i Li -→ y i ), where z refers to the tuple of variables used in the body but not in the head).

The semantics naturally extends the semantics of RPQs: ϕ(ā) is true in G iff there is a tuple b of nodes so that ā, b witness every RPQ in the body: if u i , v i from ā, b interpret x i and y i , then there is a path p i between u i and v i whose label

λ(p i ) is in L i .
Relations on words Regular relations on words are simply defined by the acceptance of the word w 1 ⊗ • • • ⊗ w k by an NFA. That is, to determine if a tuple (w 1 , . . . , w k ) ∈ (A * ) k is in the relation, one runs an NFA over the word w 1 ⊗ • • • ⊗ w k over the alphabet (A ∪ {⊥}) k . Such an automaton first looks at the first symbols of all words, then at their second symbols, etc.; when a word ends, it is padded with the extra symbol ⊥. We denote the class of such relations REG.

Examples of regular relations are prefix, equality, equal length, and bounded edit distance. There are, however, many other important relations that are non-regular. These are suffix:

w suff u iff u = v • w for some v; subword: w subw u iff u = v • w • v for some v, v
, and subsequence: w subseq u if some letters can be deleted from u in a way that results in w. These three relations are not regular but rational: they can be defined by asynchronous automata with k heads (for k-ary relations), or alternatively by regular expressions over (A ∪ {ε}) k , see [START_REF] Sakarovitch | Elements of Automata Theory[END_REF].

III. PARIKH AUTOMATA

For presentational purposes, we give a slight syntactic variation of the usual definition of Parikh automata from [START_REF] Karianto | Parikh automata with pushdown stack[END_REF], [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF]. This easier to grasp definition follows the intuition explained in [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF] and is in the spirit of models such as [START_REF] Alur | Regular functions and cost register automata[END_REF]. It is readily seen to be equivalent to the original definition, which we present as well, and which in fact is often better suited for proofs.

Definition III.1. A Parikh Automaton, or PA, of dimension k, is a tuple PA = (Q, A, δ, q 0 , F, C), where Q is a finite set of states, A is a finite alphabet, q 0 ∈ Q is the initial state, F ⊆ Q is the set of final states, C is a semilinear set in N k (called a constraint set), and the transition relation δ is a finite subset of Q × A × N k × Q. A run ρ of PA on a word w = a 1 • • • a m ∈ A * is a map from {0, . . . , m} to Q × N k such that • ρ(0) = (q 0 , 0); • if ρ(i) = (q, r
) and ρ(i + 1) = (q , r ) then there exists a transition (q, a i+1 , v, q ) ∈ δ such that r = r + v. A run is accepting if ρ(m) ∈ F × C. A word is accepted if it has an accepting run. The set of accepted words is denoted by L(PA).

In other words, the run starts in q 0 and has all zeros in k counters r. If it is in state q and reads a, and there is a transition (q, a, v, q ), it can enter q and add v to the counters, componentwise. For acceptance, the automaton must be in an accepting state, and have the tuple of counters in the set C.

Note that one can easily model the condition q ∈ F by an extra counter, only accepting by the configuration of counters. We also call the set of all tuples from N k that appear in transitions of PA its auxiliary set.

Languages accepted by PAs are closed under union, intersection, homomorphisms, inverse homomorphisms and concatenation (though not complementation and iteration). A deterministic version of PAs is known to be strictly weaker than arbitrary PAs [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF]. PAs are also known to be equivalent to reversal-bounded multicounter machines [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF] in the sense that they describe the same class of languages [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF], [START_REF] Cadilhac | Affine Parikh automata[END_REF].

Original definition We now present the definition of kdimensional Parikh automata from [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF], [START_REF] Karianto | Parikh automata with pushdown stack[END_REF]. Such automata are pairs PA = (A , C) where

A = (Q, A × D, δ, q 0 , F ) is an NFA over A × D, and D is a finite subset of N k , which we call auxiliary set. A word w = a 1 . . . a n is accepted by (A , C) if there is a word v = v1 . . . vn over D such that w ⊗ v is accepted by A and i≤n vi ∈ C.
Note that we simply incorporated the tuples of numbers over the finite set D ⊂ N k into transitions, and the summation into the definition of a run. The translations between the two versions preserve all complexity bounds. When we use this definition, we shall write ⊕v for i≤n vi when v = v1 • • • vn (with ⊕v = 0 when v is the empty word).

An alternative characterization. We now provide two closely related views of Parikh automata that will help us better visualize their power and later define analogs of regular expressions for them. Let A = (Q, A, δ, q 0 , F ) with δ ⊆ Q × A × Q be a usual NFA. We can view a run ρ of A on a word w as a |w| + 1-tuple of states, i.e., a map from {0, 1, . . . , |w|} to Q.

Proposition III.1. For a language L ⊆ A * the following are equivalent:

1) L is accepted by a Parikh automaton;

2) there is an NFA A over A with the set of states Q and a semilinear set C ⊆ N |Q| such that

L = {w | ∃ accepting run ρ of A on w with Π(ρ) ∈ C};
3) there is an alphabet B, an NFA A over A × B and a semilinear set

C ⊆ N |A|•|B| such that L = {w | ∃v ∈ B * : w ⊗ v ∈ L(A ) and Π(w ⊗ v) ∈ C}.

A. Complexity of Parikh automata

It is known that language nonemptiness (is L(PA) = ∅?) and membership (is w ∈ L(PA)?) are decidable for Parikh automata [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF], [START_REF] Karianto | Parikh automata with pushdown stack[END_REF]. Here we pinpoint their exact complexity, as it will be needed later.

Proposition III.2. Both the nonemptiness and membership problem for Parikh automata are NP-complete. They can be solved in polynomial time if the dimension is fixed and all numbers are represented in unary.

Proof sketch. We explain the proof for nonemptiness. Consider PA = (A, C) of dimension k so that L(A) ⊆ (A × D) * with D = { d1 , . . . , dn }. We first build an existential Presburger formula ϕ C (y 1 , . . . , y k ) describing C in linear time, by Lemma II.1. We then produce an existential Presburger formula ϕ Π A (x 1 , . . . , x k ) for Π({v | u ⊗ v ∈ L(A)}) ⊆ N n in linear time. This is possible by a combination of [START_REF] Verma | On the complexity of equational Horn clauses[END_REF] and a small fix to their (slightly underconstructed) formula given in [START_REF] Hague | Synchronisation-and reversal-bounded analysis of multithreaded programs with counters[END_REF]. From ϕ Π A one can obtain, in polynomial time, a formula ϕ A describing {⊕v | u ⊗ v ∈ L(A)} ⊆ N k . Finally, we check for satisfiability of ϕ A ∧ ϕ C in NP [START_REF] Scarpellini | Complexity of subcases of Presburger arithmetic[END_REF]. For NP-hardness, one can reduce from the Subset Sum Problem: given integers n 1 , . . . , n k , whether there is a non-empty subset of them whose sum is 0.

For the unary representation of (A, C), one can construct in polynomial time an automaton B over an alphabet of size k such that Π(L(B)) = C, and an automaton

A from A so that Π(L(A )) is {⊕v | w ⊗ v ∈ L(A)}.
To test emptiness, we just test if Π(L(A )) ∩ Π(L(B)) = ∅, using the fact that the problem of whether the Parikh images of two given regular languages are disjoint is in PTIME, when the alphabet is fixed [START_REF] Kopczyński | Parikh images of grammars: Complexity and applications[END_REF], [START_REF] Lin | Model Checking Infinite-State Systems: Generic and Specific Approaches[END_REF].

Another problem whose precise complexity we need is the problem of nonemptiness of intersection of languages. For regular languages, it is a classical PSPACE-complete problem [START_REF] Kozen | Lower bounds for natural proof systems[END_REF].

The language intersection problem for PAs is defined as follows: its input is a set PA 1 , . . . , PA m of Parikh automata, and the question is whether

m i=1 L(PA i ) = ∅.
Solving this will be essential for understanding combined complexity of several classes of graph queries. We now show that going from NFAs to PAs, we keep the upper bound on the complexity of the problem.

Proposition III.3. The language intersection problem for Parikh automata is PSPACE-complete.

Proof sketch. Let PA i = (A i , C i ) for i ∈ m, so that each A i has an alphabet A × D i with D i ⊆ N ni ,
under the definition of [START_REF] Klaedtke | Monadic second-order logics with cardinalities[END_REF]. We define a NFA A over S N ⊆ N N for N = i n i , and • it guesses an alphabet letter

S = max{||v|| ∞ |v ∈ i D i }, so that ⊕L(A) = {⊕v | v ∈ L(A)}
(a i , xi ) ∈ A × D i for each A i so that a 1 = • • • = a m ,
• it stores the states q 1 , . . . , q m to which transitions lead for each automaton, as well as the vectors x1 , . . . , xm , and • it reads x1 , . . . , xm one at a time using m transitions.

The idea is that, by reading one xi at a time, we are summing (instead of multiplying) the auxiliary sets of A 1 , . . . , A m .

By [START_REF] Lin | Model Checking Infinite-State Systems: Generic and Specific Approaches[END_REF]Theorem 7.3.1], the Parikh image Π(L(A)) ⊆ N n can be described by a finite union of linear sets of the form

{v 0 + n i=1 α i vi | α 1 , • • • , α n ∈ N} (4)
so that n ≤ n, and

max i ||v i || ∞ is bounded by (n|Q|) O(n) ,
where Q is the statespace of A. From this representation one can easily obtain a semilinear set for ⊕L(A) ⊆ N N whose every linear set is of the form (4) so that n ≤ n and

max i ||v i || ∞ is bounded by (n|Q|) O(n) ; hence these numbers are at most exponential in i |A i |.
Therefore, due to Lemma II.1 and the use of binary representation of numbers, ⊕L(A) can be given as a disjunction i ϕ i of existential Presburger formulas, each of which has size linear in n + N and logarithmic in |Q|.

The existential Presburger formula ϕ C for m i=1 C i can be built in linear time due to Lemma II.1. Hence, we have that

ϕ = i ϕ i ∧ ϕ C represents ⊕L(A) ∩ C, and that each ϕ i ∧ ϕ C is of size polynomial in {(A i , C i )} i∈m . By [41, Theorem 6 (A)], if an existential Presburger formula such as θ = ϕ i ∧ ϕ C is satisfiable,
there is a satisfying assignment so that each variable is assigned a number that is at most exponential in |θ|. Thus, ϕ is satisfiable iff there exists a word v ∈ D * so that ⊕v ∈ ⊕L(A) ∩ C and ||⊕v|| ∞ is at most exponential in {(A i , C i )} i∈m . By building A on-the-fly we can guess and verify the existence of such v using only polynomial space. By Savitch's theorem, we can then test, in PSPACE, whether ϕ is satisfiable, which is equivalent to A being nonempty, which in turn is equivalent to i L(A i , C i ) = ∅. Thus, the statement follows.

Our final result is on the intersection of the language of a fixed PA with a regular language. This is needed for determining data complexity of several query languages.

Proposition III.4. For a fixed Parikh automaton PA, the problem of checking, for an input NFA A, whether L(PA) ∩ L(A) = ∅ can be solved in NLOGSPACE.

Proof sketch. Let (A 1 , C 1 ) be a fixed PA and A an input NFA. Let A be an NFA such that

L(A ) = {v | ∃u ∈ L(A) : u ⊗ v ∈ L(A 1 )}. Notice that A is linear in A. It suffices to check whether ⊕L(A ) ∩ C 1 = ∅. By the previous proof, ⊕L(A ) ∩ C 1 is
given by an existential Presburger formula ϕ = i ϕ i ∧ ϕ C1 so that each ϕ i ∧ ϕ C1 is logarithmic in the number of states of A (and thus of A).

By [START_REF] Scarpellini | Complexity of subcases of Presburger arithmetic[END_REF], a satisfiable disjunct ϕ i ∧ ϕ C1 has a satisfying assignment with numbers exponential in ϕ i (since ϕ C1 is fixed). Thus, if ⊕v ∈ ⊕L(A ) ∩ C 1 , there is one where all numbers in ⊕v are at most polynomial in A. This can be checked in NLOGSPACE guessing one position of v at a time and keeping a counter of logarithmic number of bits, ensuring that the sum of the guessed word is of size at most polynomial in A.

IV. QUERY EVALUATION WITH PARIKH AUTOMATA Recall that CRPQs (3) are defined as formulae of the form ϕ(z) :-

x 1 L1 --→ y 1 , • • • , x m Lm --→ y m ,
where each x i Li -→ y i is an RPQ, and variables used in the body but not in the head are existentially quantified. We assume that regular languages L i s are represented by NFAs.

If the L i s are given by Parikh automata, we refer instead to RPQ(PA) and CRPQ(PA) queries. For instance, L a n b n = {a n b n | n > 0} is a PA-definable language, and hence x L a n b n ----→ y is an RPQ(PA) query selecting pairs of nodes that have a path between with the label from L a n b n . Using previous formalisms, one needed relations on paths to do this, see [START_REF] Abiteboul | Data on the Web: From Relations to Semistructured Data and XML[END_REF]. CRPQs combine several RPQs: for instance,

ϕ(x) :-x L a n b n ----→ y, x L a n b n ----→ z, y a + --→ z
finds nodes x from which we can reach, by a path of the form a n b n , two nodes that are connected by an a-labeled path.

Given a class Q of queries over graphs, recall that data complexity and combined complexity of Q refer to the following problems:

• for combined complexity, the input is a query ϕ(x) from Q, a graph G, and a tuple ū of nodes such that |ū| = |x|; the question is whether ϕ(ū) is true in G; • for data complexity, the query ϕ(x) is fixed, i.e., only G and ū are the parameters. For ordinary RPQs and CRPQs, data complexity is in NLOGSPACE. In fact it is already NLOGSPACE-complete for the very simple RPQ x A * --→ y as this is simply the NLOGSPACE-complete reachability problem. For RPQs based on NFAs, combined complexity is in PTIME, and for CRPQs it is NP-complete. Again the latter is the best possible, since combined complexity of relational conjunctive queries is NPcomplete.

In general, when it comes to good complexity of query evaluation, the following is usually assumed. First, data complexity must always be tractable. Solving intractable problems on large volumes of data is simply out of the question. Combined complexity can be single exponential, reflecting the fact that in practical query evaluation algorithms, the size of the query is usually in the exponent. In fact relational database languages are based on first-order logic, for which data complexity is very low (AC 0 ) and combined complexity is PSPACE-complete; when one goes to the ∃, ∧-fragment (conjunctive queries), it drops to NP.

We now show that adding Parikh conditions to RPQs costs us very little: the bounds for data complexity, and for combined complexity of CRPQs do not change at all. Combined complexity for RPQs changes, but it still is bounded by the good complexity of evaluating CRPQs. More precisely, we have the following. (II) Combined complexity of both RPQ(PA) and CRPQ(PA) is NP-complete.

Proof idea. For RPQs, as usual, we take the product of the automaton with the graph viewed as an NFA, where the endnodes of the RPQ serve as the initial and the final state. The bounds then follow from Proposition III.2 for combined and from Proposition III.4 for data complexity. Hardness follows from the hardness of PA nonemptiness: we simply take a fixed graph in which every path from A * is realized. For CRPQs, an extra guessing step for witnesses of existential quantifiers is involved, which does not affect the complexity (since its size depends only on the query). 2

V. SYNCHRONIZED PARIKH RELATIONS

Query (1) from the introduction used a binary relation on paths. In fact, much of the motivation for this work stems from the need to use relations, in particular, relations that lead to computationally infeasible queries. Our goal now is twofold:

• first, we study relations rather than languages defined by PAs, and • second, we see how to use these relations in queries. We now concentrate on the first item; the second one is studied in the next section.

How can we define relations given by PAs? For NFAs, one typically operates not with one, but with three relational analogs of regular languages. In terms of increasing power, these are recognizable, regular, and rational relations [START_REF] Choffrut | Relations over words and logic: a chronology[END_REF], [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]. They correspond to three different ways of defining regularity of languages: by recognizability by a finite monoid, by acceptance by an NFA, and by regular (or rational) expressions. However, already in the binary case, these result in different classes of relations.

So what can we do with if the notion of NFA is replaced by Parikh automata? We do not yet have commonly accepted regular expressions for Parikh automata that can be lifted to relations, and the algebraic theory of PAs is in its infancy [START_REF] Cadilhac | The algebraic theory of Parikh automata[END_REF]. Instead, we use a recently proposed approach to defining relations over words that does not depend on the underlying properties of automata but rather on how these relations are synchronized [START_REF] Figueira | Synchronizing relations on words[END_REF].

To explain this idea, consider two words, w 1 = abacb and w 2 = bcaac in A * . A possible synchronization is:

1 a 2 b 1 b 1 a 1 c 2 c 2 a 1 b 2 a 2 c
It is a shuffle of these two words, where each position is marked with 1 or with 2, indicating which word they come from. Formally, this is a word in (2 × A) * (recall that k stands for {1, . . . , k}). If we read the gray-shaded positions marked with 1, we see the word w 1 ; if we read positions marked with 2, we see w 2 . Now we can run an automaton (e.g., an NFA) over such a synchronization to determine if the pair (w 1 , w 2 ) is in the relation, and it is the shape of the word of 1s and 2s that determines what types of relations we get. If such words come from the language 1 * 2 * , we get recognizable relations. If they come from (12) * (1 * |2 * ) (i.e., alternate between 1s and 2s until one of the words is finished), we get regular relations. And if there is no restriction on the word over {1, 2}, we get rational relations [START_REF] Figueira | Synchronizing relations on words[END_REF].

Thus, to define relations based on Parikh automata, we shall use the same notion of synchronization, but will run Parikh automata over them; words over positions 1 and 2, rather than ad hoc notions, will determine types of relations we get. Now we present this idea formally.

A. Synchronizations and regularity for Parikh relations

A synchronization of a tuple (w 1 , . . . , w k ) of words in A * is a word over k × A so that the projection on A of positions labeled i is exactly w i , for i = 1, . . . , k. Every word w in (k × A) * is a synchronization of a uniquely determined ktuple (w 1 , . . . , w k ), where w i is the sequence of A-letters corresponding to the symbol i in the first position of k × A. We denote such tuple (w 1 , w 2 , . . . , w k ) by

[[w]] k and extend it to languages S ⊆ (k × A) * by [[S]] k = {[[w]] k | w ∈ S}.
For L ⊆ k * , we say that a word u ⊗ v ∈ (k × A) * is Lcontrolled if u ∈ L; a language is L-controlled if all its words are. We now look at relations given by Parikh automata over L-controlled synchronizations for a regular language L ⊆ k * :

REL PA (L) = [[S]] k
S is defined by a Parikh automaton over k × A and is L-controlled .

For a set L of regular languages we define REL PA (L) =

{REL PA (L) | L ∈ L}. Let All = {k * | k ∈ N + }.
Then REL PA (All) contains all the relations that can be defined in our framework; these are analogs of rational relations, which are similarly defined when the automata are NFAs rather than PAs [START_REF] Figueira | Synchronizing relations on words[END_REF]. These include all regular relations on words as well as subsequence, subword, suffix, concatenation (e.g., {(u, v, w) | w = uv}) and even relations that can add counting constraints, e.g., {(u, v, w) | w = uv and |u| = 2|v|}, using the power of PAs.

For NFA-based relations, the notion of regularity (in the binary case) is given by the synchronizing language (12) * (1 * |2 * ), and regular length-preserving k-ary relations are given by (12 • • • k) * [START_REF] Figueira | Synchronizing relations on words[END_REF]. To extend this for relations based on Parikh automata, we go beyond the standard description of regular relations: those, for instance, include prefix but not suffix. We present a way of synchronizing relations that lets us use the suffix relation, among others, in graph queries, in a way that avoids undecidability issues of [START_REF] Barceló | Graph logics with rational relations[END_REF].

Let π = (p 1 , . . . , p k ) be a permutation of k, and let w π,i stand for the word whose letters are p i , . . . , p k appearing in the increasing order (for instance, w π,1 = 12

• • • k). Define - → L π = w * π,1 • w * π,2 • • • w * π,k-1 • w * π,k and ← - L π = w * π,k • w * π,k-1 • • • w * π,2 • w * π,1 Let - → L k = π - → L π and ← - L k = π ← - L π
where π ranges over permutations of k. For example,

- → L 2 = (12) * (1 * |2 * ) and ← - L 2 = (1 * |2 * )(12) * , for k = 3 we have - → L 3 = (123) * (12) * (1 * |2 * ) | (13) * (1 * |3 * ) | (23) * (2 * |3 * ) ← - L 3 = (1 * |2 * )(12) * | (1 * |3 * )(13) * | (2 * |3 * )(23) * (123) * .
We define

--→ REG k PA = REL PA ( - → L k ) and ← -- REG k PA = REL PA ( ← - L k )
and finally

--→ REG PA = k>0 --→ REG k PA and ← -- REG PA = k>0 ← -- REG k PA .
Relations in these classes express many properties of interest and, in a way to be described shortly, approximate every rational relation. We first list some examples of relations in these classes.

• Every relation in REG is also in

--→ REG PA . • Every length-preserving regular relation (i.e., a regular relation R such that (w 1 , . . . , w k ) ∈ R implies |w 1 | = • • • = |w k |)
given by an NFA (or even a PA) is in both

--→ REG k PA and ← -- REG k PA .
In fact, this is true even if we impose the criterion that -d ≤ |w i | -|w j | ≤ d for all i, j ≤ k, for some fixed d ∈ N. For instance, the equal-length and fixed-edit-distance relations are in both --→ REG

) | Π(w 1 ⊗ • • • ⊗ w k ) ∈ C} is in both --→ REG k PA and ← -- REG k PA . • The prefix relation is in --→ REG 2 PA but not in ← -- REG 2 PA . • The suffix relation suff is in ← -- REG 2 PA but not in --→ REG 2 PA .
• The subword relation subw and the subsequence relation subseq belong to neither

--→ REG 2 PA nor ← -- REG 2 PA .
To show that they approximate arbitrary rational relations, we define shuffle k (w) ⊆ A * as the set of shufflings of w ∈ A * preserving the number of subwords of length ≤ k, that is, the set of all words w ∈ A * such that # v (w) = # v (w ) for each v ∈ A * with |v| ≤ k. Here # v (w) counts the number of occurrences of v as a subword of w. For example, shuffle 1 (w) is the set of all words w with Π(w) = Π(w ), and in general w ∈ shuffle k (w) implies Π(w) = Π(w ).

For a relation R ⊆ (A * ) m , we define

shuffle k (R) = (w 1 , . . . , w m ) (w 1 , . . . , w m ) ∈ R and w i ∈ shuffle k (w i ), i ∈ m
That is, we approximate a relation by only insisting on preserving the numbers of occurrences of words of fixed length, for instance replacing subsequence by checking whether Π(w) ≤ Π(w ) in the simplest case of k = 1.

It turns out that every such approximation falls into both classes of analogs of regular relations. Proposition V.1. If R is an arbitrary m-ary rational relation, and

k ≥ 1, then shuffle k (R) is in both --→ REG m PA and

← --REG m

PA . There is a simple relationship between classes --→ REG PA and ← --REG PA . For a tuple w = (w

1 , • • • , w k ), let wr = (w r 1 , • • • , w r k )
, where w r is the reverse of w, and let R r = { wr | w ∈ R}. Then it is immediate from the definitions that R ∈ ← --

REG PA iff R r ∈ --→ REG PA . Since (R r ) r = R, this implies that R ∈ --→ REG PA iff R r ∈ ← -- REG PA .
We need one closure property of these analogs of regular relations (that in particular gives us other examples of relations in these classes).

Proposition V.2. For every k > 0, classes --→ REG k PA and ← -- REG k
PA are closed under intersection. In fact, for any two PA-definable

- → L k -or ← - L k -controlled languages S 1 , S 2 ⊆ (k × A) * we have [[S 1 ∩ S 2 ]] k = [[S 1 ]] k ∩ [[S 2 ]] k .
We show in fact a slightly more general closure result that works for every class REL PA (L) where L is Parikh-injective, i.e., the function Π : L → N k is injective. Languages -→ L k and ← -L k are easily seen to be such.

VI. PARIKH RELATIONS IN QUERIES

We now look at queries in which relations on paths can be used, i.e., queries similar to [START_REF] Abiteboul | Data on the Web: From Relations to Semistructured Data and XML[END_REF]. If one uses NFAs to define such relations, then those synchronized by languages from -→ L k (i.e., relations from the class REG) can be added to CRPQs with a small complexity cost [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF]. Our motivation comes from the inability to extend good complexity results to relations that are often needed in applications, e.g., subword and subsequence [START_REF] Barceló | Graph logics with rational relations[END_REF], [START_REF] Barceló | Graph logics with rational relations: the role of word combinatorics[END_REF]. But such relations admit good approximations given by Parikh automata.

Indeed, as already discussed in the introduction, an approximation of the subsequence relation is

R subseq = {(u, v) | ∀a ∈ A : # a (u) ≤ # a (v)}.
This relation is easily seen to be shuffle 1 ( subseq ), and thus it is in --→ REG 2 PA (and in ← --REG 2 PA as well), i.e., an analog of regular relations given by Parikh automata. For the subword relation, one can get an even more precise approximation than doing shuffling. Consider

R subword = {(u, v) | ∃i, j∀a ∈ A : # a (u) = # a (v[i, j])}.
This again is a relation from REL PA ( -→ L 2 ): one synchronously runs a PA over u ⊗ v, guesses the positions i and j in v and increments counters only between those positions.

Thus, important rational relations that cannot be directly used in queries due to the complexity considerations, can be approximated by regular relations based on Parikh automata. We will show that those can be evaluated with good data and combined complexity.

A. CRPQs with relations

Let R be a class of relations on words. We assume that R has relations of every arity k ≥ 1 (in particular, languages as relations of arity 1); this could be a class of regular, or rational relations, or a class of the form REL PA (L), e.g., --→ REG PA or ← --REG PA . The class CRPQ rel (R) of queries extends CRPQs with relations from R. Formally, such a query is of the form

ϕ(z) :-x 1 π1:L1 ---→ y 1 , • • • , x l π l :L l ---→ y l , R 1 ( χ1 ), • • • , R m ( χm ), where • π 1 , • • • , π l
are the path variables of ϕ; they are pairwise distinct; • each L i is a language (unary relation) from R;

• z is a tuple of variables among x i , y i s;

• each χj is a tuple of variables among the π i s of the same arity as R j .

An example is the query (1) from the introduction that uses a single 'equal-length' regular relation.

The semantics is a natural extension of the semantics of CRPQs. Given a graph G and a tuple ā of its nodes of the same arity as z, the formula ϕ(ā) is true if there exists a tuple b of nodes interpreting the variables used in the body but not in the head so that:

• for each i ≤ l, there exists a path p i between the interpretations u i , v i of x i , y i such that its label λ(p i ) is in L i ; • for each χj = (π j1 , . . . , π js ), the tuple of labels of the paths (λ(p j1 ), . . . , λ(p js )) is in R j .

The set of all tuples ā such that ϕ(ā) holds in G is denoted by ϕ(G).

The class of CRPQs extended with regular relations, called ECRPQs in [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], is CRPQ rel (REG) in this notation. The extension with all rational relations was considered in both [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF] and [START_REF] Barceló | Graph logics with rational relations[END_REF], and, due to its undecidability, less expressive languages CRPQ rel (REG+ suff ), CRPQ rel (REG+ subw ), and CRPQ rel (REG+ subseq ) have been studied, i.e., those with arbitrary regular relations and just one particular rational relation. Those turned out to have horrendous complexity as well, so [START_REF] Barceló | Graph logics with rational relations: the role of word combinatorics[END_REF] restricted them even further, replacing regular relations with regular languages and keeping just one rational relation (we indicate this by omitting REG in the list of relations, e.g., CRPQ rel ( subseq ), but of course paths can still be checked for membership in a regular language).

The table below provides a summary of known complexity results from [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], [START_REF] Barceló | Graph logics with rational relations[END_REF], [START_REF] Barceló | Graph logics with rational relations: the role of word combinatorics[END_REF]. When a particular complexity class is mentioned, the problem is complete for it. Non-PR stands for non-primitive-recursive. Thus, from the complexity point of view, only two languages, CRPQ rel (REG) and CRPQ rel ( suff ), can be viewed as potentially usable. However, they both put severe restrictions on the use of relations in queries: the former completely rules out rational but non-regular relations, and the latter only allows one particular relation, at the expense of excluding all other relations, even regular ones.

We shall now see how to generalize and extend these positive results.

B. Regularity and query evaluation

To achieve our goal and significantly extend the only positive complexity results, we deal with languages CRPQ rel ( --→ REG PA ) and CRPQ rel ( ← --REG PA ). That is, we

• extend regular languages to languages defined by PAs; and • use relations from --→ REG PA and ← --REG PA in queries. These languages are significant extensions of previously known decidable languages of path-based queries on graphs (we shall give some examples of their power shortly). As our main result we show that despite adding much to the expressiveness, these extensions do not cost us computationally.

Theorem VI.1. For queries in CRPQ rel ( --→ REG PA ) and CRPQ rel ( ← --REG PA ), data complexity is in NLOGSPACE, and combined complexity is in PSPACE.

Of course we also have NLOGSPACE-and PSPACEcompleteness, as hardness was already known for small fragments of these languages [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], [START_REF] Barceló | Graph logics with rational relations: the role of word combinatorics[END_REF], so this result is indeed the best possible.

We now give examples of the power of these languages, before providing a sketch of the proof of the theorem.

Queries in CRPQ rel ( --→ REG PA ). This language is a natural extension of CRPQ rel (REG) to Parikh automata: instead of relations given by synchronized NFAs, we now can use relations given by synchronized Parikh automata. In particular, in this language we can use counting approximations R subseq of subseq and R subword of subw , even though the relations themselves cannot be added to CRPQ rel (REG) due to complexity considerations. In terms of the results of such approximations, we have the following observation, due to the monotonicity of CRPQs.

Lemma VI.2. Given two queries

ϕ(z) :-x 1 π1:L1 ---→ y 1 , • • • , x l π l :L l ---→ y l , R 1 ( χ1 ), • • • , R m ( χm ), ϕ (z) :-x 1 π1:L1 ---→ y 1 , • • • , x l π l :L l ---→ y l , R 1 ( χ1 ), • • • , R m ( χm ),
such that R j ⊆ R j for all j = 1, . . . , m, we have ϕ(G) ⊆ ϕ (G) for every graph G.

Hence, replacing relations with their counting approximations results in overapproximation of query results, which was exactly our intention. We now give a couple of examples motivated by a common application of graph databases, namely social networks and in particular crime detection [START_REF] Fan | Graph pattern matching revised for social network analysis[END_REF]. Consider a simple version of a query that attempts to detect criminal activity:

ϕ(x, y) :-x π:L --→ z, x π :L ---→ y, π subseq π
Here L describes known criminal activity in a network of people, and L gives paths to be analyzed. We want to find ys that are connected to x in a way resembling known illicit activity involving x. Due to the nature of those activities in the network, not all of them may be known yet, hence we are looking for subsequences of known activities as an indication that the connection of x and y is suspect and needs to be investigated further. This query ϕ is too complex to evaluate, due to the presence of subseq , but its replacement ϕ (x, y) :-

x π:L --→ z, x π :L ---→ y, R subseq (π, π ) from the class CRPQ rel ( --→ REG 2
PA ) will be much more efficient, and will overapproximate the answer to ϕ, i.e., no objects of interest will be lost.

As another example, consider comparing paths for similarity; these queries are common in both social networks [START_REF] Fan | Graph pattern matching revised for social network analysis[END_REF] and Semantic Web applications [START_REF] Anyanwu | ρ-Queries: enabling querying for semantic associations on the semantic web[END_REF]. Some measures, e.g., fixed edit distance, are regular, but some are not. Consider the following one: two words u and v are k-similar if u ∈ shuffle k (v), i.e., each word w of length ≤ k occurs the same number of times in u and in v. The picture below has an example of two 2-similar paths starting at the same node z and realizing the same local patterns up to length 2 over the alphabet {a, b}:

ϕ(z) :-x 1 π1 -→ y 1 , . . . , x l π l -→ y l , R 1 ( χ1 ), . . . , R m ( χm ),
where without loss of generality we assume that languages witnessing all the π i s are A * (since any regular condition λ(π i ) ∈ L i can be checked in the second part of the query by L i (π i )).

We first show the combined complexity case. Let G = V, E be a labeled graph over the alphabet A. Let v be a tuple of vertices of the arity |z|. We want to check if v ∈ ϕ(G). We first guess a valuation ν :

{x i , y i } i≤l → V so that ν(z[i]) = v[i] for every i ≤ l.
Let k j be the arity of the relation R j , and let t = k 1 + • • • + k m . Next, we produce the following relations over (A * ) t :

• the relation R × containing all tuples ( w1 , . . . , wm ) so that wi ∈ R i for all i ∈ m, • for every π that appears both in position i of R j and i of R j a relation R i,j,i ,j of tuples (w 1,1 , . . . , w 1,k1 , . . . , w m,1 , . . . , w m,km )

so that w j,i = w j ,i , • every RPQ x π -→ y used in ϕ so that π appears in position i of R j a relation S G,ν i,j of tuples like (5) so that w j,i is accepted in the automaton represented by G having ν(x), ν(y) as initial and final states respectively.

Note that the intersection of all these relations is nonempty iff v ∈ ϕ(G).

It is easy to see that all the aforementioned relations are

- → L t - controlled since each R j is - → L k j -controlled.
Further, it is easy to see that for every one of these relations one can build a PA synchronizing it in polynomial time, given PAs synchronizing the R j 's of ϕ. By Proposition V.2, the intersection of all these relations is empty iff the intersection of all the PA synchronizing them is. We can test the emptiness of the latter intersection in PSPACE due to Proposition III.3. Even though we performed an initial polynomial guessing, by Savitch's Theorem the procedure remains PSPACE.

Let us now analyze the case where the query ϕ is fixed. Note that the relations S G,ν i,j s can be synchronized using NFAs instead of PAs. (In other words, we do not need to make use of the semilinear constraint set.) Let then A 2 be the NFA synchronizing S G,ν i,j . Since the number of relations S G,ν i,j s is bounded by a function on ϕ, we have that A 2 can be built so that it is polynomial in the NFA synchronizing the S G,ν i,j s, which in turn are polynomial in G and v. Furthermore, its transitions can be produced on-the-fly using logarithmic space. Let (A 1 , C 1 ) be the PA synchronizing the remaining relations R × ∩ R i,j,i ,j . Since these depend only on the query, this is a fixed PA. Using Proposition III.4, it follows that we can check whether L(A 2 ) ∩ L(A 1 , C 1 ) is empty in NLOGSPACE, and thus check whether (v, ρ) ∈ ϕ(G).

C. Syntactic restrictions

We now look at query answering in the language that imposes no restrictions on the type of relations that can be used, i.e., it uses arbitrary relations from REL PA (All). Recall that these are relations in which no restrictions whatsoever are imposed on allowed synchronizations. These include suffix, subword, subsequence, and many properties definable by Parikh automata, e.g., pairs (u, v) so that v = wu (u is a suffix of v), and # a (u) = # a (w) for every a ∈ A.

Of course we know that in general query evaluation in CRPQ rel (REL PA (All)) is undecidable; for that, we do not even need Parikh automata [START_REF] Barceló | Graph logics with rational relations[END_REF]. To recover decidability, or, better yet, achieve good complexity, it is important to impose syntactic restrictions on the language. We now do it in the way that generalizes all previously known decidable restrictions for graph queries with relations on paths.

Consider again a query

ϕ(z) :-x 1 π1:L1 ---→ y 1 , • • • , x m πm:Lm ----→ y m , R 1 ( χ1 ), • • • , R l ( χl ),
Let R( χ) be an atom used in this query, where χ = (π i1 , . . . , π in ). Define G R( χ) as an undirected graph whose vertices are π i1 , . . . , π in , and edges are {π i1 , π i2 }, {π i2 , π i3 }, • • • {π in-1 , π in }. If n = 1, there are no edges. We let G ϕ be the undirected multi-graph consisting in the union of all the G Rj ( χj ) s.

We say that ϕ:

• is strongly-acyclic if G ϕ is acyclic (note that if there is more than one edge between two vertices, G ϕ is not acyclic; the "strongly-" prefix is to distinguish it from other notions of acyclicity [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF]); The proof follows the construction of the proof of Theorem VI.1, using Proposition III.2 for the last two items, and a lemma below on the complexity of join evaluations. If we have relations R 1 ⊆ (A * ) k1 and R 2 ⊆ (A * ) k2 , and numbers i

1 ≤ k 1 and i 2 ≤ k 2 , the join R 1 i1,i2 R 2 ⊆ (A * ) k1+k2 consists of the tuples (ū 1 , ū2 ) such that ū1 ∈ R 1 , ū2 ∈ R 2 , and ū1 [i 1 ] = ū2 [i 2 ].
Lemma VI.4. Given two Parikh automata PA 1 and PA 2 with constraint sets C 1 and C 2 that synchronize R 1 ⊆ (A * ) k1 and R 2 ⊆ (A * ) k2 , respectively, one can build in polynomial time a Parikh automaton PA synchronizing R 1 i1,i2 R 2 such that its constraint set is C 1 × C 2 and the size of the auxiliary set of PA is linear in those of PA 1 and PA 2 .

These result go beyond what is known even for regular relations; for instance, part (I) of Theorem VI.3 extends a result about acyclic queries for recognizable relations and one given binary rational relation from [START_REF] Barceló | Graph logics with rational relations[END_REF].

VII. REGULAR EXPRESSIONS FOR PARIKH AUTOMATA

So far we defined queries in languages CRPQ rel (R) by presenting languages and relations with automata, but it is highly unlikely that a user of a graph query language will be doing the same. In practice such a user is likely to use a declarative formalism, probably some type of regular expressions. For NFAs, we know very well what regular expressions are; in fact they found their way into UNIX commands (grep etc.) and programming languages such as PERL, PYTHON, AWK.

If we want to make Parikh automata and relations based on them usable, we need to provide an easy way to specify languages definable by them. We do this now, by presenting two candidate descriptions of languages given by Parikh automata. One of them is based on the idea of marking positions in a regular expression, and it captures the power of PAs. The other works well for some cases when marked expressions become too complicated; it is based on choosing expressions matching initial segments of words.

A. Expressions with marking

To explain the idea of these expressions, consider first the language L a n b n . It can also be defined as the language given by a * b * with the additional constraint that # a (w) = # b (w). We can thus use an expression (a * b * , a = b) to define it: the first component is a usual regular expression, and the second is a constraint on the numbers of occurrences. For instance,

(a * b * c * , a + 2b > c) defines words w ∈ L(a * b * c * ) with # a (w) + 2 • # b (w) > # c (w).
Such expressions are sufficient to define languages given by NFAs together with a semilinear constraint on Parikh images, but as we saw, Parikh automata go further than that. Consider, for instance, the language L 0 = {ba n ca n | n ≥ 0}. Simply counting as does not help us any more. What we can do instead is use a technique similar to the one that defines unambiguous regular languages [START_REF] Brüggemann-Klein | One-unambiguous regular languages[END_REF]: namely, we mark positions in the regular expression. We use the expression ba * 1 ca * 2 , with a 1 and a 2 referring to different occurrences of the same symbol a, but now we can refer to their individual counts. To define L 0 , we shall now use (ba * 1 ca * 2 , a 1 = a 2 ): it still defines words from ba * ca * but now with a semilinear constraint that the number of a 1 s (i.e., as after the b) is the same as the number of a 2 s (i.e., as after the c).

A marked expression therefore is an expression in which each symbol is marked with a natural number (we can view unmarked symbols b, c above as marked with 0); that is, an expression over the alphabet A × D, where D is a finite subset of N. While in the examples above these expressions are very simple and intuitive, sometimes they can grow to be a bit hard to parse, even for simple languages. Coming back to the language L ba=ca (the number of as that occurring after a b and after a c is the same), the expression to describe it is together with the constraint a 1 = a 2 . (The sublanguage in the middle, under the inner Kleene star, denotes the set of words in which neither ba not ca occurs.) We now propose alternative expressions that, while slightly weaker in terms of their power, work better for languages like L ba=ca .

B. Expressions with choice

For languages like L ba=ca , it is better to use expressions with choice. We define such a language with the expression {(A * ba, 0 1 ), (A * ca, 1 0 )}, together with constraint x 1 = x 2 . This works as follows. The use of pairs of numbers next to expressions indicates the use of two counters, say x 1 and x 2 . Suppose we are given a word w = a 1 • • • a n . When a prefix of it matches the first expression, A * ba, we add 0 and 1 to the counters, and when it matches the second expression, A * ca, we add 1 and 0 to the counters. So having x 1 = x 2 after reading the whole word is equivalent to having equal numbers of as following a b and a c. Now we define these expressions formally. A Parikh expression with choice is an expression of the form (E, C), where E = {(e 1 , v1 ), . . . , (e m , vm )}, each e i is a regular expression over A, each vi is in N k , and C is a semilinear set in N k .

To define the language (over A) given by E, let e 0 define the complement of all the e j s (i.e., its language is the complement of i L(e i )) and let v 0 = 0. Then a word w = a 1 • • • a n is in L(E, C) iff for every position i ≤ n, there is j i ∈ [0, m] such that:

• a 1 • • • a i ∈ L(e ji ), and PAs resulting from translating Parikh expressions with choice have an additional property: whenever (q, a, v, q ) and (q, a, ū, q ) are transitions, then q = q . But despite being slightly weaker, this class of expressions covers many examples of interest, and appears to be intuitive enough to be used in query languages. Expressions with marking also are quite intuitive for many languages, and they do capture PAs.

VIII. CONCLUSIONS

We showed that with the use of Parikh automata we avoided the curse of rational relations in graph database queries, at the expense of approximations, of course. Such approximate solutions can be found effectively, matching bounds for best graph queries and traditional query languages for relational databases, in terms of combined complexity. The formalism of PAs, in addition, directly expresses many properties of interest in graph querying, and PAs come with at least two alternative ways of specifying languages that can be used in querying, similar to the way usual regular expressions are used.

Several questions remain. Among technical questions, there is one regarding the use of path variables in queries, as was done in [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF] for CRPQ rel (REG). One needs to find effective PA representations of sets of paths returned by a query, and understand their complexity. We also would like to show that expressions with choice are provably weaker than expressions with marking (the notion of determinism that is known to be weaker for PAs is actually more restrictive than the automata such expressions translate into).

Regarding directions for future work, we would like to look at obtaining underapproximations, as opposed to overapproximations, of query answers (say, for queries involving subword, subsequence, and similar relations). Is there a model sharing good computational properties with PAs that can be used for that purpose? Another has to do with extending the formalism beyond navigational properties, i.e., to querying the topology of the graph (say, connections in a social network) and data stored in it (e.g., data about people in the social network). Extensions of RPQs that handle data have been proposed [START_REF] Libkin | Regular path queries on graphs with data[END_REF]; they treat paths as data words and use automata formalisms for those [START_REF] Bojańczyk | Twovariable logic on data words[END_REF]. One possible approach is then to enhance such automata with features of PAs.

  has nonempty intersection with m i=1 C i iff the instance has the positive answer. This automaton A has the alphabet D of size n = |D 1 | + • • • + |D m | that consists of all vectors (0, . . . , 0 j<i nj , xi , 0, . . . , 0 j>i nj ) for i ∈ m and xi ∈ D i . The automaton A simulates the execution of A 1 , . . . , A m in parallel by iterating the following:

Theorem IV. 1 .

 1 The following complexity bounds hold for RPQs and CRPQs based on Parikh automata:(I) Data complexity of both RPQ(PA) and CRPQ(PA) is in NLOGSPACE.

  Note that k-similarity is not a regular relation, nor can it be described by Parikh images if k ≥ 2, but this is a relation in --→ REG PA . Hence, we can look, for instance, for nodes z from which k-similar paths to two distinct nodes exist by a CRPQ rel ( --→ REG PA ) query ϕ(z) :-z π -→ x, z π -→ y, π ∼ k π , π = π , where ∼ k is the k-similarity relation. It achieves the same complexity as CRPQ rel (REG) queries, even though it uses relations that go beyond what has so far been possible to use with reasonable complexity.

  For a word w from (A × D) * , its A-projection π A (w) simply drops the second component of each letter. Now a marked Parikh expression over A is a pair (e, C), where e is a regular expression over A × D for a finite D ⊂ N, and C is a semilinear set in N |A|•|D| . It defines the language L(e, C) = {π A (w) | w ∈ L(e) and Π(w) ∈ C}. From Proposition III.1, part 3, we obtain: Corollary VII.1. The classes of languages defined by Parikh automata and by marked Parikh expressions are the same.

(ba 1

 1 |ε) (A -{b, c}) * (b(A -{a})|c(A -{a})|ε) * (ca 2 |ε) *

•

  i≤n vji ∈ C.Proposition VII.2. Languages given by Parikh expressions with choice are definable by Parikh automata.

  Queries in CRPQ rel ( ← --REG PA ). No decidable language that allows the use of suff and other relations has been known yet: decidability was only shown for CRPQ rel ( suff ), i.e., extension of CRPQs with suffix and nothing else. The language CRPQ rel ( ← --REG PA ) can use suffix with other regular relations, definable by NFAs and PAs, as long as they are synchronized by ← -L k . For instance, we can use suffix, equal-length, bounded edit-distance, and properties of Parikh images in a query, all at the same time, without incurring any complexity penalty.

	Proof sketch of Theorem VI.1. Suppose we have a formula of CRPQ rel ( --→ REG PA ) (the case for ← --REG PA being analogous) of the
	form

  • has join-size n if the size of each connected component of G ϕ is at most n;• has dimension n if every relation R i is given by a PA of dimension at most n.

	Theorem VI.3. (I) For strongly acyclic queries in
	CRPQ(REL PA (All)), data complexity is in NLOGSPACE
	and combined complexity is in PSPACE;
	(II) if the query is in addition of a fixed join-size n, the
	combined complexity is in NP;
	(III) if the query is furthermore of fixed dimension m, and all
	numbers in the definitions of PAs are given in unary, the
	combined complexity is in PTIME.

Acknowledgment We would like to thank Anthony Widjaja Lin and Eryk Kopczyński for helpful discussions. Diego Figueira is partially supported by ANR StochMC, Project Blanc ANR-13-BS02-0011-01.

NOTATION

For all our proofs we adopt the following presentation of Parikh automata given by Karianto [START_REF] Karianto | Parikh automata with pushdown stack[END_REF], which, as stated in Proposition III.1, is equivalent to the definition given before. A Parikh Finite Automaton (PA) of dimension k ≥ 1 over an alphabet A is a system (A, C) where A = (Q, A × D, δ, q 0 , F ) is a finite automaton over A × D, for some finite, nonempty set D ⊆ N k (called the auxiliary set), and C ⊆ N k is a semi-linear set (called the constraint set). The language recognized by (A, C) is defined as

PROOF OF LEMMA II.1

Proof: Note that for q ∈ N, we have that 2 q • x can be simply represented as

and thus for every m ∈ N we have that m • x can be represented with a term

of Presburger arithmetic of size O(log(m)), where m = i 2 qi . Further, this term can be built in linear time in the binary representation of m. From this observation, it follows that for any linear set represented in binary

one can build an equivalent Presburger formula ϕ(x 1 , . . . , x k ) in linear time: ∃α 1 , . . . , α n .

Hence, by a disjunction of such formulae, one can also compute, in linear time, Presburger arithmetic representations of semilinear sets.

PROOF OF PROPOSITION III.1

Proof: 1) ⇒ 2) Consider a PA of dimension k given as a pair (A, C) with A = (Q, A × D, δ, q 0 , F ), where D, C ⊆ N k . We show how to build an automaton A over A with statespace Q and a constraint set C verifying 2). We define the set of states as Q = Q × ({ 0} ∪ D), with an initial state (q 0 , 0) and set of final states F × ({ 0} ∪ D). The idea is that we internalize the second components of the letters read by A into the states of A , so that whenever A reads (a, x) reaching a state q, we have that A reads a reaching a state (q, x). Thus, the set of transitions of A consists of all ((q, x), a, (q , x )) so that (q, (a, x ), q ) ∈ δ. Let us fix an order Q = {p 1 < • • • < p m } for the m = |Q | states of A . We write pi ∈ D to denote the vector contained in the second component of the state p i . We define C ⊆ N m as

where (p 1 , . . . , pm ) t is the transpose of (p 1 , . . . , pm ). The fact that C is semilinear can be readily seen when working with Presburger arithmetic formulae. That is, if we have a formula ϕ(x 1 , . . . , x k ) describing C we have that the formula

Now we show w ∈ L(A, C) iff there is an accepting run ρ of A on w so that Π(ρ) ∈ C . From left to right, if w ∈ L(A, C) then there is a word v ∈ D * so that w ⊗ v ∈ L(A) with an accepting run ρ, so that ⊕v ∈ C. By construction of A , we have that ρ ⊗ v is an accepting run of A on w and that Π(ρ ⊗ v) • (p 1 , . . . , pm ) t = ⊕v ∈ C. Hence, Π(ρ ⊗ v) ∈ C for the accepting run ρ ⊗ v of A on w. For the right-to-left direction, suppose we have an accepting run ρ ⊗ v of A on w so that Consider a NFA A over A×D so that

We show that a word w is in the language of (A , C) iff there is some u ∈ B * so that w ⊗ u ∈ L(A) and Π(w ⊗ u) ∈ C.

From left to right, if w is in the language of the PA (A , C) then there is some v ∈ D * so that w ⊗ v ∈ L(A ) and ⊕v ∈ C. Let u ∈ B * so that (w ⊗ u) † = v; we then have that w ⊗ u ∈ L(A). Further, since ⊕v = Π(w ⊗ u), we have Π(w ⊗ u) ∈ C. From right to left, assume there is some u ∈ B * so that

PROOF OF PROPOSTION III.2

Proof: We focus first on the emptiness problem. Let (A, C) be a PA of dimension k so that L(A) ⊆ A×D with D = { d1 , . . . , dn }. We first build an existential Presburger formula ϕ C (y 1 , . . . , y k ) describing C in polynomial time (Lemma Theorem II.1). We then produce an existential Presburger formula ϕ Now let (A, C) be a PA so that C and the working alphabet are represented in unary. Note that from C one can produce in polynomial time an automaton B over an alphabet of size k, say B = {b 1 , . . . , b k }, so that the Parikh image of L(B) is C. Similarly, one can produce in polynomial time an automaton A from A so that the Parikh image of L(A ) is {⊕v | w ⊗ v ∈ L(A)}. 1 Note that both polynomial translations make use of the fact that numbers are represented in unary. In [START_REF] Kopczyński | Parikh images of grammars: Complexity and applications[END_REF] (also in [START_REF] Lin | Model Checking Infinite-State Systems: Generic and Specific Approaches[END_REF]) it is shown that the problem of whether the Parikh image of two given regular languages is disjoint is in PTIME, assuming the alphabet is fixed. Thus, we can check whether

(and thus whether (A, C) is empty) in polynomial time.

Let us now consider the emptiness problem. Given a word w ∈ A * and a PA (A, C) we produce A so that L(A ) = L(A) ∩ {w ⊗ v | v ∈ D * } in polynomial time, and we then check (A , C) for emptiness as before.

Finally, for NP-hardness, one can easily reduce from the Subset Sum Problem: the problem of, given k integers n 1 , . . . , n k , whether there is a non-empty subset of them whose sum is 0. For any such instance 1 Indeed, it suffices to introduce a simple modification on the transition relation of A, so that for each letter (a, (β 1 , . . . , β k )) read by A, we have that A reads β 1 times b 1 , followed by β 2 times b 2 , etc.

we can produce a PA (A, C) of dimension 2 so that a • • • a k ∈ L(A, C) iff the instance has a positive answer. For this, we take C = {(n, n) | n ∈ N} and we build A in the following way. We use k + 1 states q 0 , . . . , q k so that the initial and final states are q 0 and q k respectively. We use an auxiliary set D = {(n i , 0) | n i > 0} ∪ {(0, -n i ) | n i < 0} ∪ {(0, 0)} and a singleton alphabet A = {a} (we assume, without any loss of generality, that no n i is zero). For every i ∈ k we have a transition (q i-1 , (a, (0, 0)), q i ); a transition (q i-1 , (a, (n i , 0)), q i ) if n i > 0; and a transition (q i-1 , (a, (0, -n i )), q i ) if n i < 0. Note that the automaton basically chooses either to use n i (by reading the auxiliary element (n i , 0) or (0, -n i ) depending on its signature) or not to use it (by reading (0, 0)). If the PA is non-empty, then its language is {a •

and there must be a non-empty subset of {n 1 , . . . , n k } so that the positive numbers sum up to n and the negative numbers sum up to -n, for some n ∈ N. Hence, a • • • a k ∈ L(A, C) iff the instance has a positive answer, and thus the emptiness and membership problems are NP-hard.

PROOF OF PROPOSITION III.3

Proof: PSPACE-hardness follows from the fact that the Intersection Problem for NFA is already PSPACEcomplete [START_REF] Kozen | Lower bounds for natural proof systems[END_REF]Lemma 3.2.3]; here we show that it belongs to PSPACE. Let (A 1 , C 1 ), . . . , (A m , C m ) be PA given as instance of the problem, with

We define a NFA A so that ⊕L(A)∩C = ∅ iff the instance has a positive answer. Let R be 1≤i≤m

where ∅ denotes the 0-tuple (i.e., the tuple of dimension 0). Let N = i∈m n i and n = i∈m |D i |. We define the alphabet of A as

where l i = 1≤j<i n j , r i = i<j≤m n j and 0 k stands for the all 0's k-tuple. 2 Note that |D| = n. We define the statespace of A as

The idea is that A simulates the execution of A 1 , . . . , A m in parallel by iterating the following mechanism:

• it stores the states q 1 , . . . , q m to which transitions lead for each automaton, as well as the vectors x1 , . . . , xm , and • it reads x1 , . . . , xm one at a time using m transitions. The sole purpose of this way of simulating A 1 , . . . , A m is to keep the alphabet of A linear. The idea is that, by reading one xi at a time, we are summing (instead of multiplying) the auxiliary sets of A 1 , . . . , A m .

Formally, we define the initial state as (q 1 0 , . . . , q m 0 , ∅), the final states as {(q 1 , . . . , q m , ∅) | q i ∈ F i , i ∈ m}, and the transitions as • ((q, ∅), (x 1 , 0 r1 ), (q , (x 2 , . . . , xm ))) for every q = (q 1 , . . . , q m ), q = (q 1 , . . . , q m ) and a ∈ A so that

which means that s = (m+1) for some ∈ N + , and there is a word

and since only the indices equivalent to i modulo m+1 contain vectors different from 0, it follows that

This means that 2 For the cases i = 1 and i = m we obtain D 1 × {0 r 1 } and {0 ln } × Dn respectively.

, where ȳi j (with i ≤ m) is the vector containing xi j in the coordinates { i <i k i + 1, . . . , i ≤i k i } and 0 everywhere else, and ȳm+1 j = 0. Let us fix an arbitrary linear order on D = { d1 < • • • < dn }. By [START_REF] Lin | Model Checking Infinite-State Systems: Generic and Specific Approaches[END_REF]Theorem 7.3.1], the Parikh image Π(L(A)) ⊆ N n of A can be described by a finite union of linear sets of the form

so that n ≤ n, and

. From this representation one can obtain a semilinear set corresponding to ⊕L(A) ⊆ N N whose every linear set is of the form (6) so that n ≤ n and

To do this, we replace every vi = (β 1 , . . . ,

Therefore, due to Lemma II.1, we obtain:

Observation A.1. ⊕L(A) can be represented as a disjunction i ϕ i of existential Presburger formulas, each of which has size linear in n + N and logarithmic in |Q|.

Hence, 3 if an existential Presburger formula such as θ = ϕ i ∧ ϕ C is satisfiable, there is a satifying assignment so that each variable is assigned a number that is exponential in |θ|. Thus, ϕ is satisfiable iff there exists a word v ∈ D * so that ⊕v ∈ ⊕L(A) ∩ C and ||⊕v|| ∞ is at most exponential in {(A i , C i )} i∈m . By building A on-the-fly we can guess and verify the existence of such v using only polynomial space. By Savitch's theorem (PSPACE = NPSPACE), we can then test, in PSPACE, whether ϕ is satisfiable, which is equivalent to A being nonempty, which in turn is equivalent to i L(A i , C i ) = ∅. Thus, the statement follows.

PROOF OF PROPOSITION III.4

We show the following: For any fixed PA (A 1 , C 1 ), given a NFA A 2 , the problem of whether

Proof: Let A be the projection of the second component of A 1 intersected with A 2 , that is,

It suffices to check whether ⊕L(A)∩C 1 = ∅. By the previous Observation A.1 in the proof of Proposition III.3, we have that ⊕L(A) ∩ C 1 can be represented by an existential Presburger formula ϕ = i ϕ i ∧ ϕ C1 so that each ϕ i ∧ ϕ C1 is logarithmic in the number of states of A, and thus also logarithmic in A 2 .

By [41, Theorem 6 (A)], each θ = ϕ i ∧ ϕ C1 is satisfiable iff there is a satisfying assignment so that each variable is assigned a number that is exponential in θ, and hence polynomial in A 2 . Thus, ϕ is satisfiable iff there exists a word v ∈ D * so that ⊕v ∈ ⊕L(A) ∩ C 1 and ||⊕v|| ∞ is at most polynomial in A 2 . This can be checked in NLOGSPACE guessing one position of v at a time and keeping a counter of logarithmic number of bits, ensuring that the sum of the guessed word is of size at most polynomial in A 2 .

PROOF OF PROPOSITION V.1

Proof: Let A be a NFA synchronizing R ⊆ (A * ) n . Let w 1 , . . . , w K be all the words of A + of length at most k. Note that the set

is semilinear. Indeed, it suffices to extend A to work over the alphabet n × A ≤k in order to keep track of the last k letters seen for each of the components i ∈ n, and then take its Parikh image. Consider then the -→ L n -controlled PA (A , C), where A operates over the alphabet (n × A) × {0, 1} nK (with {0, 1} nK as the auxiliary set), so that whenever it reads (j, a, (u 1 1 , . . . , u K 1 , . . . , u 1 n , . . . , u K n )) we have that u i j = 1 iff j = j and the word read so far in the j-th component has w i as a suffix, for every i ∈ K. 3 It is worth mentioning that Scarpellini shows this for the version of Presburger arithmetic we use (that is, with the doubling function).

Thus, for every w ∈ L(A , C) there is v so that w ⊗ v ∈ L(A ) and ⊕v ∈ C. By definition of A , assuming

This means that there is (v 1 , . . . , v n ) ∈ R so that # wj (v i ) = # wj (u i ) for all i ∈ n, j ∈ K. This shows that shuffle k (R) ∈ --→ REG n PA . It is easy to see that a ← -L n -controlled automaton synchronizing the same relation as A can also be built. Thus,

Proof: This is a trivial generalization of the case for regular relations and k = 2 contained in [23] that we repeat here for the sake of clarity. Let S 1 , S 2 ⊆ (k × A) * be two L-controlled PA languages. It is immediate that the language

Then, there must be w 1 ∈ S 1 and w 2 ∈ S 2 so that

Note that the projection onto the first component of w 1 must be equal to the projection onto the first component of w 2 since L is Parikh-injective. Then, we must have that

The following is a simple observation from the definition of

Thus, by Lemma A.2, we obtain Proposition V.2 as a corollary.

PROOF OF THEOREM VI.1

In the proofs that follow, we will assume that, for S a class of relations, formulae of CRPQ rel (S) are of the form

where

• without loss of generality we assume that languages witnessing all the π i s are A * (since any regular condition λ(π i ) ∈ L i can be checked in the second part of the query by

• every R j is in S and χj is a k j -tuple of of variables from {π i } i of the same dimension k j as R j ,

• the elements of z range over the node variables of ϕ.

Proof: The lower bounds for this problem come from the evaluation problem for ECRP Q [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], which is a subclass of instances of this problem. Henceforward we assume we work with --→ REG PA , since the proof for ← --REG PA is completely analogous. Let us first show the combined complexity case, where both the query and graph are part of the input. Let ϕ be as in ( †), and let G = V, E be a labelled graph over the aphabet A. Let v be a vector of vertices that is given. We want to check if v ∈ ϕ(G). We first guess a valuation ν :

for every i ∈ l. Given two vertices x, y of G, let us write G[x, y] to denote the language recognized by the NFA whose transition relation is the labeled graph G, and initial and final states are, respectively, x and y. Next, we produce the following relations

• for every π that appears both in position i of R j and i of R j a relation R i,j,i ,j def = {(w 1,1 , . . . , w 1,k1 , . . . , w m,1 , . . . , w m,km ) | w j,i = w j ,i } which assures that the i-th component of R j is joined with the i -th component of R j ;

• for every RPQ x π -→ y so that π appears in position i of R j a relation S G,ν i,j def = {(w 1,1 , . . . , w 1,k1 , . . . , w m,1 , . . . , w m,km ) | w j,i ∈ G[ν(x), ν(y)]} which ensure that the path π is compatible with G, ν, that is, that π is indeed a path of G from the node associated to x to the node associated to y in the guessing ν. We first show that the intersection of all these relations is nonempty iff v is a solution of ϕ(G). From right-toleft, if v ∈ ϕ(G), through the guessed valuation ν, there are paths w 1 , . . . , w l of G corresponding to the paths π 1 , . . . , π l so that for every R j ( χj ) with χ j = (π i1 , . . . , π i k j ) we have a tuple wj = (w i1 , . . . , w i k j ) ∈ R j . This means that ( w1 , . . . , wj ) ∈ R × and further that it verifies the equalities of R i,j,i ,j . Further, since the words w i according to x 1 π1 -→ y 1 , they also verify the restrictions imposed by S G,ν i,j . From left-to-right, if there is a tuple ( w1 , . . . , wm ) ∈ R × ∩ R i,j,i ,j ∩ S G,ν i,j this means that the valuation ν correctly guessed nodes that are compatible with the paths in w1 , . . . , wm contained in G. We are now left with the task to give a PSPACE procedure to test the above relations for emptiness.

It is easy to see that each of the aforementioned relations are

Further, it is easy to see that for every one of these relations one can build a PA synchronizing it in polynomial time, given PA synchronizing the R j 's of ϕ. For example, for R × it suffices to take the crosspduct of their cosntraint sets and to compose the NFA for each relation: first the automaton on {1, . . . , k 1 } × A synchronizing R 1 , then the automaton on {k 1 + 1, . . . , k 1 + k 2 } × A synchronizing R 2 (note that we shift the alphabets), etc. The resulting automaton is then -→ L t -controlled. For R i,j,i ,j and S G,ν i,j the construction is straightforward. Now that we have -→ L t -controlled PA PA 1 , . . . , PA s synchronizing each of the relations above, we have that, the intersection of all these PA synchronizes the intersection of all the relations above, that is

This is a consequence of Proposition V.2. This menas that

We can then test the emptiness of the latter intersection in PSPACE thanks to Proposition III.3. Note that, even though we performed an initial polynomial guessing, by Savitch's Theorem the procedure remains PSPACE.

Let us now analyse the case where the query ϕ is fixed. Note that the relations S G,ν i,j 's can be synchronized using NFA's instead of PA's. (In other words, we don't need to make use of the semilinear constraint set.) Let then A 2 be the NFA synchronizing S G,ν i,j . Since the number of relations S G,ν i,j 's is bounded by a function on ϕ, we have that A 2 can be built so that it is polynomial in the NFA synchronizing the S G,ν i,j 's, which in turn are polynomial in G, v. Further, its transitions can be produced on-the-fly using logarithmic space. Let (A 1 , C 1 ) be the (fixed) PA synchronizing the remaining (fixed) relations R × ∩ R i,j,i ,j . Using Proposition III.4, it follows that we can check whether L(A 2 ) ∩ L(A 1 , C 1 ) is empty in NLOGSPACE, and thus whether v ∈ ϕ(G).

PROOF OF THEOREM VI.3

Proof: (I) We first show that the combined complexity for strongly acyclic queries of CRPQ(REL PA (All)) is in NLOGSPACE. Let G = V, E be a labelled graph over the aphabet A, and let v be a vector of vertices of G. Assume ϕ is a strongly-acyclic query of the form ( †). We want to check if v ∈ ϕ(G). Without any loss of generality, let us assume that G ϕ is connected. (If it's not connected, one can divide the input vector and query into connected queries, and test each one for membership.) Let (A 1 , C 1 ), . . . , (A m , C m ) be PA synchronizing R 1 , . . . , R m , where C i ⊆ N ki for every i. We now proceed as in the proof of Theorem VI.1, where we reduce the problem to the intersection of several relations of arity k 1 + • • • + k m , assuming R i ⊆ (A * ) ki for i ∈ m. We consider the same relations defined in that proof: R × , R i,j,i ,j 's, S G,ν i,j 's. Remember that the intersection of these relations is non-empty iff v is a solution of ϕ(G). The key observation here is that we can build, in polynomial time, m PA synchronizing the relations S 1 , . . . , S m so that

This can be done because, on the one hand the relation

and on the other hand the relations S G,ν i,j 's impose at most one further constraint for each of the coordinates of R × (here we're using the fact that in the query ( †) all the π i 's are distinct).

We still have to produce the intersection with R i,j,i ,j . Remember that R i,j,i ,j basically joins component i of the tuple from relation R j with component i of the tuple from relation R j . Due to the strong-acyclicity of ϕ, this join graph looks like a tree, which allows us to use the repeated application of Lemma VI.4 obtaining a PSPACE procedure. More formally, strong-acyclicity entails the existence of a permutation p = 1 , . . . , m of 1, . . . , m and indices i 1 , j 1 , . . . , i m-1 , j m-1 so that

where perm p (R) of a relation R ⊆ A k1+ Thus through the (m -1 times) application of Lemma VI.4 we obtain a PA (A, C) synchronizing S , so that:

• A has an exponential number of states,

• A has a linear alphabet size, and

Finally, given the bounds above, by building A on-the-fly we obtain a PSPACE procedure as described in the proof of Proposition III.3.

If the query ϕ is fixed, we proceed in a similar way as in the proof of Theorem VI.1. We observe that we can build the transition relations of S 1 , . . . , S m in NLOGSPACE. It is easy to see that the automaton build by Lemma VI.4 can be built on-the-fly using logarithmic space. Thus, by a constant number of applications (as m is fixed) of the construction we obtain that a PA synchronizing S can be built on-the-fly and test for emptiness in NLOGSPACE.

(II) We proceed as before, where for each connected component we have that there is a constant number of automata involved and thus we can produce a PA for the intersection in polynomial time and check for non-emptiness in NP due to Proposition III.2.

(III) We proceed as before, using the second part of Proposition III.2 this time.

PROOF OF LEMMA VI.4

We show the following. Given two PA

so that the size of the auxiliary set of A is linear in those of A 1 , A 2 .

Proof:

The idea is that a state (q 1 , q 2 , ( , a)) represents that we are in state q 1 of A 1 , in state q 2 of A 2 and that we need to move forward A i from q i until it reads a letter of the form (i , a); more formally, from such a state we can either

• if = 1, advance through a transition (q 1 , ((j, a ), v), q 1 ) ∈ δ 1 by reading a letter ((j, a ), v 0 k2 ) to the state

, advance through a transition (q 2 , ((j, a ), v), q 2 ) ∈ δ 2 by reading a letter ((j, a ), 0 k1 v) to the state -(q 1 , q 2 , (j, a)) if j = k 1 + i 2 , or -(q 1 , q 2 , ε) if (j, a ) = (k 1 + i 2 , a). A state of the form (q 1 , q 2 , ε) means that component i 1 from A 1 and i 2 from A 2 are synchronized and we can either

• advance through a transiton (q 1 , ((j, a), v), q 1 ) ∈ δ 1 by reading a letter ((j, a), v 0 k2 ) to the state -(q 1 , q 2 , ε) if j = i 1 or -(q 1 , q 2 , (2, a)) if j = i 1 , or

• advance through a transiton (q 2 , ((j, a), v), q 2 ) ∈ δ 2 by reading a letter ((k 1 + j, a), 0 k1 v) to the state -(q 1 , q 2 , ε) if j = i 2 or -(q 1 , q 2 , (1, a)) if j = i 2 . Finally, the initial state is (q 1 0 , q 2 0 , ε) and the final states {(q 1 , q 2 , ε) | q 1 ∈ F 1 , q 2 ∈ F 2 }. Note that the size of A is polynomial in A 1 , A 2 , and that D is linear in D 1 , D 2 . Further, we have

PROOF OF PROPOSITION VII.2

Proof: Consider an expression with choice (E, C) where E = {(e 1 , v1 ), . . . , (e m , vm )}. Let A i be a DFA for L(e i ), for i ∈ m. We assume that A i = (Q i , A, q i 0 , F i , δ i ) where δ i is a function from Q i × A to Q i . Let A 0 = (Q 0 , A, q 0 0 , δ 0 , F 0 ) be a DFA whose language is A * -{L(e i ) | i ∈ m} (it corresponds to the expression e 0 used in the definition of acceptance by a Parikh expression with choice). This Parikh expression with choice is captured by a PA (Q, A, q0 , δ, F, C), where:

consists of tuples (s 0 , s 1 , . . . , s m ) so that s i ∈ F i for at least one i ∈ m (note that in any simultaneous run of the A i s over any word, at any point in the run at least one state will be final, by the definition of A 0 ; hence, this requirement simply eliminates unreachable states); • q0 = (q 0 0 , q 1 0 , . . . , q m 0 ); • F = Q, i.e., every state is final and acceptance is by the constraint set;

• a transition (s, a, v, s ), where s = (s 0 , s 1 , . . . , s m ) and s = (s 0 , s 1 , . . . , s m ) is in δ iff s i = δ i (s i , a) for all i ∈ m, and there is j ∈ m such that s j ∈ F j and v = vj or s 0 ∈ F 0 and v = 0. That is, the Parikh automaton simulates all the automata A 0 , A 1 , . . . , A m in parallel; if one of them, say A i , upon reading letter a enters a final state (which means the prefix is in L(e i )), the corresponding vector vi can be added to the counters (or all zeros, in the case of A 0 ). It is routine to verify that this automaton captures (E, C). Note also that it satisfies the condition mentioned in the paper: if (s, a, v , s ) and (s, a, v , s ) are both in δ, then s = s (although v need not equal v , so this is a weaker requirement that the determinism of PAs).