Jason Vallet

Guy Melanc

Bruno Pinaud

JASPER: Just A new Space-filling and Pixel-oriented layout for large graph ovERview

When analysing data and handling a visualisation, users mainly spend their cognitive resources making sense of the graphical representation and mapping it back to the data and domain. This task becomes even more critical when dealing with larger data sets. Therefore, a valuable visualisation design strategy is to couple graphical representations and user tasks to better support the sense making process. This paper focuses on a particular task where users must make sense of state changes occurring on nodes of a graph. To this end, we propose JASPER, a new layout algorithm focusing on the visualisation of nodes inspired from pixel-oriented layouts, relying on node clustering to identify and represent existing connections through spatial adjacency.

JASPER can layout moderate size graphs in real-time and is able to tackle large graphs with up to 2 million nodes and 5 million edges in reasonable time (about half a minute). Furthermore, although JASPER has been designed around a specific application, the underlying methodology can be employed to draw quick overviews of any type of graphs. The paper lays down the underlying principles of JASPER, and reports it performances (execution times) on increasingly large graphs. JASPER is then used and showcased to visualise network propagation phenomenon in large graphs.

Introduction

In recent years, the graph drawing community has focused on increasingly larger graphs, evolving along the multiplication of the ever expanding social networks and their popularisation. Used to study social behaviours or consumer habits, social networks are nonetheless complex to draw and analyse due to their sheer size, thus giving them additional interest for the research community. Roughly speaking, a social network represents a set of users possibly connected to one another and, when depicted as a graph, users are represented by nodes while a connection between two users is symbolised by an edge. In general, the huge graphs resulting from the mining of such networks force us to face several hundreds of thousands [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], if not millions [START_REF] Leskovec | Signed networks in social media[END_REF], of nodes at once, thus pushing the existing representations, commonly used to display graphs of more moderate sizes, to their limits.

A lot of different techniques exist nowadays to draw graphs, and vary according to structural specificities (i.e. tree, directed/undirected or compound graphs). Most techniques aim at producing a human-readable and easily interpretable map of the network structure [START_REF] Tatiana Von Landesberger | Visual analysis of large graphs: State-of-the-art and future research challenges[END_REF]. Popular approaches to display graphs are node-link diagrams, matrices and hybrid visualisations mixing these two representations (e.g. [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF] and [START_REF] Rufiange | Treematrix: A hybrid visualization of compound graphs[END_REF]). However, all of those visualisation techniques have limitations when facing large graphs, especially node-link representations [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis[END_REF][START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF]. The difficulty of displaying millions of elements in a comprehensible fashion is obvious and, as a result, existing layout algorithms are not always efficient in representing such graphs. This is mainly due to the genericity of these methods whereas effective visual analysis can only be performed through appropriate visual representations [START_REF] Tatiana Von Landesberger | Visual analysis of large graphs: State-of-the-art and future research challenges[END_REF]. Depending, among others, of the analytical tasks we wish to perform, a good visualisation should thus allow to instantly identify the information that really matter.

In a recent work [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF], we proposed to use visual analytics to compare information propagation in social networks. However, when facing larger graphs (e.g. networks with thousands of users), we have been unable to find an existing layout which allows to understand at a glance how propagation operates on the network. Thus, we have decided to develop a new layout algorithm adequate for our needs: JASPER. It has been designed to compute compact layouts using pixel-oriented techniques so the resulting representations will give an overview of the graph. Propagation can be visually tracked as nodes change states using a simple color mapping.

Though JASPER is adapted to our particular problem, we believe it can be useful in a number of different situations as a complementary visualisation for evaluating at a glance some information on different graphs. Basically, our method adheres to the following observations:

1. Nodes are the most important elements and thus have to be clearly displayed, 2. Edges are important too but can impair the visualisation quality in dense graphs [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis[END_REF], 3. Whether we use a node-link diagram, a matrix or some hybrid visualisation, large graphs will still be too big for the viewer to process/visualise all the embedded information at once; all we can do is to give hints and directions.

The first point relates to the task JASPER is designed to support, with a clear focus on node states. The second point is addressed with authority, since JASPER makes edges non visible. This design choice however is not that radical given that edges carry no other information or attributes other than indicating that nodes are connected. The third observation underlines the fact that the occlusion problem raised by edges is a general one and applies to whatever visualisation we may consider when dealing with large graphs. To compensate this problem, a convenient visual metaphor can be used to suggest the presence of edges. To this end, we position nodes so that adjacent nodes (i.e. connected by an edge) remain as close as possible to each other, thus giving a hint of an existing connection between those elements to the viewer. We have to keep in mind that such approximation is necessary as representing every single detail in a legible way is not reasonable considering the number of elements we are handling. Following those observations and using our representation method is therefore not without drawbacks: there are limitations for users trying to visualise dynamic graphs with evolving topologies. This operation is beyond the scope of our current application as we are using snapshots of networks in a fixed configuration. It will nonetheless become relevant in the future as the structure of a social network is constantly evolving. As for now, we limit our visualisation on large static graphs and wish to solely visualise state modifications happening to different nodes.

In the following section, we will present some existing work related to our current solution and motivate in which aspects they were not appropriate for our application. This will be followed by the presentation of our method completed with some design and implementation details. We then produce some execution times and present resulting visualisations, extended afterwards as we introduce a use-case applying JASPER to the visualisation of a propagation phenomena. The final section allows us to start a discussion tackling existing problems, possible solutions and suggesting future work directions.

Related work

Information visualisation and graph drawing have been the subject of extensive research through the years [START_REF] Tatiana Von Landesberger | Visual analysis of large graphs: State-of-the-art and future research challenges[END_REF]. Among those works, three techniques are commonly used: node-link diagrams, matrices and hybrid visualisations. Node-link diagrams are quite familiar and natural representations for any graphs. Nodes and edges are both displayed and can thus give visual information (size, colour, shape, highlight, etc.). Though this type of visualisation can show the global structure of a graph, node-link diagram limitations are well-known as they give poor results when dealing with larger graphs and more particularly when edge density increases, quickly impairing their overall readability [START_REF] Ghoniem | On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis[END_REF][START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF]. Matrices, on the other hand, are simple to display and can be useful to appreciate the whole graph structure in one glance. Nodes and edges can still give visual information but the representation is nonetheless less natural and large matrices are difficult to work with [START_REF] Sansen | Edge visual encodings in matrix-based diagrams[END_REF]. Finally, hybrid visualisations (such as Node-trix [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF] or Mat-tree [START_REF] Rufiange | Treematrix: A hybrid visualization of compound graphs[END_REF]) can offer significant advantages from both previous solution but still require some learning efforts for users to get used to them.

Among all these possible representations, node-link diagrams, though proved to come with flaws, are often preferred to represent social networks [START_REF] Archambault | On the effective visualisation of dynamic attribute cascades[END_REF]. They are mostly displayed in small samples using force-directed layouts which can give rather good results on any kind of graph. However, such algorithms can not be computed on large graphs in a small amount of time [START_REF] Hachul | Large-graph layout algorithms at work: An experimental study[END_REF]. To find a solution to our large-graph visualisation problem, we thus have to look at works tackling visualisation of large-scale datasets (with several hundreds of thousands or millions of elements). Two examples of such work can be found in [START_REF] Auber | Multiscale visualization of small world networks[END_REF] and [START_REF] Shi | Himap: Adaptive visualization of large-scale online social networks[END_REF] where the authors propose multiscale visualisations of social networks. However, the resulting representations never show the graph in its entirety thus forbidding the kind of global overview we are seeking.

These two solutions nonetheless raise an interesting point in using the existing communities within the social networks to group nodes. More commonly called clusters when studied outside social networks, such node grouping can be used to simplify the layout computation in considering each cluster as a whole entity instead of trying to find an appropriate position for each node separately. This method has been used by Huang et al. [START_REF] Mao | A space efficient clustered visualization of large graphs[END_REF] and Didimo et al. [START_REF] Didimo | Fast layout computation of hierarchically clustered networks: Algorithmic advances and experimental analysis[END_REF] to visualise up to fifteen thousand nodes and forty thousand edges. Huang et al. and Didimo et al. both describe their representations as space-efficient and space-filling layouts. Such quality is obviously important when dealing with large graphs so any visual information carried by the displayed elements can be noticed without focusing on each one specifically. Additional algorithms using space-filling curves as a base for their resulting layout exist. A few years ago, Muelder et al. [START_REF] Muelder | Rapid graph layout using space filling curves[END_REF] have proposed such a method. Its computation is quick, it can be applied on large graphs (1M nodes and 2M edges) and the produced layouts seem clearer than those obtained with force-directed algorithms, nonetheless, edges impair node visibility in the densest parts of the graph. A somewhat similar solution has been later proposed by Auber et al. [START_REF] Auber | Gospermap: Using a gosper curve for laying out hierarchical data[END_REF] only using hierarchical data, thus making it inappropriate for general network visualisation. In this case however, edges are no longer needed as the hierarchy is indicated using coloured nested regions and borders, dividing the layout like a nested treemap. For more information and extended bibliographies on space-filling curves, we refer the reader to the two aforementioned papers ( [START_REF] Auber | Gospermap: Using a gosper curve for laying out hierarchical data[END_REF][START_REF] Muelder | Rapid graph layout using space filling curves[END_REF]).

The idea of using space-filling curves is elegant and allows to efficiently use space. This can however be pushed even further with a pixel-oriented visualisation as initially introduced by Keim [START_REF] Daniel | Designing pixel-oriented visualization techniques: theory and applications[END_REF]. This method is used to analyse records and visualise the possible correlation between two measures, one being displayed using the position of the elements along a space-filling curve while the second is depicted using a simple colour mapping. Pixel-oriented visualisations have been successfully used to visualise very large datasets containing up to a billion of elements [START_REF] Shneiderman | Extreme visualization: Squeezing a billion records into a million pixels[END_REF] and to perform social network analysis [START_REF] Gove | Netvisia: Heat map and matrix visualization of dynamic social network statistics and content[END_REF]. The capacity to display numerous elements is a necessity for our visualisation case, however, edges -carrying information on the connectedness of each node in the network-cannot be explicitly represented using a pixel-oriented method. Duarte et al. [START_REF] Felip | Nmap: A novel neighborhood preservation space-filling algorithm[END_REF] have recently encountered a similar problem and addressed it quite effectively. Their "Nmap" layout is introduced as being a neighbourhood preservation space-filling algorithm able to display connected nodes close to each other. As mentioned in the introduction, considering the number of elements to visualise, we have to represent the information simply and give hints on important facts as the user is not able to process that much information all at once. To this end, a layout algorithm offering to keep each node close to its neighbours, even if only approximately, seems a good solution. Though, it can not be applied on a smaller scale to obtain an exact representation, it presents sufficient qualities to be used to compute overviews on large graphs.

Presentation of our solution

Our solution is divided in two main phases (see Fig. 1). We first compute a layout based on a coarse representation of the initial graph. This step allows to improve the computation time as we limit the number of elements, thus simplifying the graph to produce. Then, we reorganise all the nodes along a spacefilling curve. The order on the curve for each node is based on its spatial position in the previous layout. The resulting layout is a space-filling representation with similitudes to pixel-oriented layout (only the nodes are displayed and existing edges are invisible by default). We end up with a compact visualisation where nodes belonging to the same connected group are set to be displayed spatially close to each other.

Phase I: layout using coarser graphs

Sometimes mentioned as a coarser graph or a skeleton graph, this method allows to describe an initial graph by a much simpler representation. Similar process can be found in different algorithms and techniques such as Auber et al. [START_REF] Auber | Multiscale visualization of small world networks[END_REF], Frishman et al. [START_REF] Frishman | Online dynamic graph drawing[END_REF], Itoh et al. [START_REF] Itoh | A hybrid space-filling and force-directed layout method for visualizing multiple-category graphs[END_REF] and Didimo et al. [START_REF] Didimo | Fast layout computation of hierarchically clustered networks: Algorithmic advances and experimental analysis[END_REF].

Grouping nodes

The starting point of our method is the application of a clustering algorithm on the initial graph. Typically, clustering algorithms are used to detect clusters in a graph, describing a subgroup of nodes particularly connected to each other. In graphs representing interactions between persons such as social networks, those groups are called communities. The subject is further developed by Fortunato [START_REF] Fortunato | Community detection in graphs[END_REF] where an overview of different existing clustering algorithms is presented and several of those techniques are compared. According to the author, the Louvain algorithm proposed by Blondel et al. [START_REF] Vincent | Fast unfolding of communities in large networks[END_REF] and Infomap of Rosvalt et al. [START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF] provide the best results. Finally, the execution time on large graphs provided by Blondel et al. in their paper, completed with additional support from Didimo et al. [START_REF] Didimo | Fast layout computation of hierarchically clustered networks: Algorithmic advances and experimental analysis[END_REF] showing the prominence of Louvain's clustering technique have convinced us to opt for this solution in our method.

Once we apply the clustering algorithm on a graph, each node will be put in the same subgroup as their closer neighbours. As we wish for each node to be as close as possible to its neighbours when displayed, we entirely rely on the clusters qualitythus on the clustering algorithm efficiency-to appropriately regroup each node with its proper relatives.

Building on clusters

Once each node is set in the adequate cluster with its closest neighbours, we have information on how to group users together. We start working on the initial graph to identify the different clusters and create a map of their relations. We thus obtain a first coarse graph. Repeating those operations several times produces coarser and coarser representations. Figure 2 shows an example of such treatment on a small graph. Starting with an initial graph (Fig. 2a), a computation of a coarser representation (Fig. 2b) gives us the connections between the clusters and results in a simpler graph. More generally, upon each computation of a coarser graph, we first group close nodes together then communities linked to one another. We use the groupings herein created to decide how close two users should be displayed.

Using a more formal approach, coarser representations can be described as follows. For a graph G n = (V n , E n ) identified by a set of nodes V n and a set of edges E n ⊆ V n ×V n , where n ≥ 0; we define G 0 as the initial graph we want to visualise and G 1 , G 2 , . . . as its gradually coarser representations. By applying a clustering algorithm on G k , where k ≥ 0, a set of clusters C k is created such as each node v ∈ V k belongs to one and only one cluster c ∈ C k (described as cluster(v) = c). Those groupings are then translated to a coarser representation of the graph, i.e., for each cluster c, a node w is created in a new graph G k+1 such as w ∈ V k+1 and, if an edge e ∈ E k exists between v and v ∈ V k , we update G k+1 following those two cases:

a) v and v are in distinct clusters (cluster(v) = cluster(v )),
then, an edge ε ∈ E k+1 is set between the two nodes w and w ∈ V k+1 -respectively representing cluster(v) and cluster(v ). When an edge linking w and w already exists, a weight can be set and updated to indicate the multiple connections between the two clusters. b) v and v are in the same cluster c (cluster(v) = cluster(v ) = c), then the edge e is not considered in graph G k+1 .

Layout computation

The layout is obtained through successive steps on the coarse representations. Starting with the coarsest graph G p , we gradually use the layout computed on the clusters in G k (p ≥ k > 0) to place the subgroups in G k-1 . The operation is repeated until G 0 is reached and treated.

To perform the first layout computation, we have to choose an efficient layout algorithm offering legible drawings in a small amount of time. In its survey on spring embedders and forcedirected layouts, Kobourov [START_REF] Stephen | Spring embedders and force directed graph drawing algorithms[END_REF] mentions some possible candidates for such application. Ultimately, we have selected the Fast Multipole Multilevel Method (FM 3 ) introduced by Hachul and Jünger [START_REF] Hachul | Drawing large graphs with a potential-field-based multilevel algorithm[END_REF]. The choice has been motivated based on the results showed by Hachul et al. [START_REF] Hachul | Large-graph layout algorithms at work: An experimental study[END_REF] and Archambault et al. [START_REF] Archambault | Topolayout: Multilevel graph layout by topological features[END_REF] as this layout method proposes a good balance between execution time and drawing quality with minimal edge-crossings and overlapping edges. Those two points are essentials as we wish to keep a readable layout of the clusters to easily distinguish one from another. An additional perk of the layout resides in its weighted variant offering advanced control if needed.

Computing the layout of the coarsest graph G p is straightforward as it simply requires to apply the algorithm layout on G p . The layout of any of the following coarser graphs G k , where k < p, needs a few additional steps. First, a local layout is computed in each cluster c ∈ C k . Then, freshly computed coordinates of each node v ∈ V k belonging to the cluster c are transformed through translation and scaling so that all nodes in c are displayed in an area around w ∈ V k+1 , representing c in the coarser graph G k+1 . Each node coordinate in a coarser graph G k+1 is thus used as an anchoring point to layout the nodes of G k . Those two steps are repeated until we reach G 0 and have computed the coordinates of each initial node.

Classic spring-embedded or force-directed layouts are timeconsuming to compute when facing thousands of elements [START_REF] Archambault | Topolayout: Multilevel graph layout by topological features[END_REF]. This nested method allows to compute several small layouts quickly. Furthermore, those operations and the geometrical transformations affecting node coordinates can be done independently from one another and thus be easily distributed. As a possible performance improvement evaluated on the testing graphs analysed in the following section, computing the inner layout of each cluster is not always the best choice as connections with nodes from outside the subgroup will not be accurately considered. In most cases where nodes within clusters are densely connected, a simple random layout gives acceptable results and allows to speed up the application by averting the nested layouts computations.

On a more general note concerning the whole Phase I, the rapidly decreasing number of nodes for each coarser representation makes the construction of G k+1 and each application of the clustering and layout algorithms on it quicker. This is not surprising considering the graphs obtained from the clusters are getting simpler, however, based on our observations on the testing graphs, repeated applications to obtain several levels of coarse graphs do not necessarily improve the resulting layouts. As a result, in our applications, only one coarser representation (G 1 ) has been computed and used for each graph. We offer nonetheless the general method as such, considering structured graphs with established hierarchical communities will benefit from it.

Phase II: pixel-oriented representation

Pixel-oriented visualisations have been presented by Keim [START_REF] Daniel | Designing pixel-oriented visualization techniques: theory and applications[END_REF] as a representation allowing to display important quantities of data in a minimal space. To do so, elements one wishes to display are ordered and placed along a space-filling curve. Our method uses a similar process with nodes being ordered according to their spatial position (computed by the end of Phase I). Each node is then laid on the space-filling curve at its given position. Finally, edges are hidden to obtain the maximum legibility.

Space division and node ordering

Node ordering can be computed fairly easily. We use a technique similar to the one employed for k-d tree construction [START_REF] Louis | Multidimensional binary search trees used for associative searching[END_REF]. A k-d tree is a data structure used for the storage of k-dimensional data, however, in our case, the only dimensions considered are those specified with the nodes layout position (x and y coordinates). We first divide the graph in two parts with a similar number of nodes in each halves using a pivot value on the first dimension. The two resulting halves are then divided again in two equal parts but using a pivot value on the second dimension. This process is repeated while alternating dimensions until each node is isolated and thus is given an order. We can compute from the start how many divisions will be necessary to isolate all the nodes, however, because we wish to conserve a regular shape for the layout, the number of division have to be equal for each halves. This means regions with fewer nodes have to incorporate "holes", or white-spaces, which are given an order too. Moreover, because the number of nodes is equally distributed in each halves during the division, the "holes" are evenly spread. Finally, the resulting shape of the layout will be either a square or a rectangle depending of the number divisions and nodes to display.

The variable form of the representation has been introduced to limit the number of "holes" in the resulting layout. Our ideal visualisation ratio is set to be 1:1, thus a square is appropriate. However, the successive divisions and the rearrangement along a space-filling curve -explained in the next subsection-do not give us the possibility to freely rearrange nodes. The appearance of "holes" is noticeable on representations with a limited number of nodes (see Fig. 4b) but becomes less visible when facing graphs with more nodes (see Fig. 5b). A variable layout shape allows us to avoid incorporating too many "holes" and to use most of

|) O(|E 0 |) O(|V 1 |log|V 1 | + |E 1 |) O(|V 0 |log 2 |V 0 |) O(|V 0 |log|V 0 |)
the space available by following a simple rule: let n ∈ N and |V | the number of nodes in the graph to display, the resulting shape will be a square if 2 × 4 n-1 ≤ |V | < 4 n and a rectangle otherwise (when

4 n < |V | ≤ 2 × 4 n ).
We test the number of nodes during the first space division (on the x coordinate) to either spread the data on a square or on half that surface, i.e., a rectangle.

Placement along a space-filling curve

Following the order computed during the space division operation, we can sort the nodes. We use the space-filling curve popularised by Morton [START_REF] Morton | A computer oriented geodetic data base and a new technique in file sequencing[END_REF]. Sometimes called Z-order curve, we will prefer the original layout using an N shape (see Fig. 3). For different developments of the curve, the number of nodes we are able to place along it evolves.

One can see how the successive space divisions give an appropriate order to each node to be displayed along this specific curve shape. Similar results can be obtained when using different curves designs or orientations -such as the Hilbert [START_REF] Hilbert | Ueber die stetige Abbildung einer Linie auf ein Flächenstück[END_REF] or the Z-order curves-as long as the node ordering during the division respects the path followed by the curve. This last point is crucial to conserve adjacency in the final layout, otherwise, nodes which should be close end up being separated if the space division and reconstruction do not follow the same pattern.

Complexity and results

After having introduced the algorithm and motivated each implementation choice, we now present the layout obtained when using our method. A specific use case will be introduced after this section but we wish to apply the algorithm to well known graphs beforehand for the reader to judge the resulting layouts and the computing times. First, let us speak a few words about the complexity of our method.

Complexity

We stay in the previous context by keeping the algorithm separated in two phases. Following the notation developed earlier, let |V 0 | and |E 0 | be respectively the number of nodes and edges of the initial graph G 0 , |V 1 | the number of clusters computed from G 0 (equal to the number of nodes from G 1 ) and |E 1 | the number of edges connecting those clusters (number of edges in G 1 ). We remind the reader we only compute one coarse representation (G 1 ) from the initial graph as we find using more than one level does not significantly improve the final layout. A more complete analysis showing the differences when using more than one coarser graph is left for future work.

The overall worst-case complexity is in 1. The given values concern non-parallel executions. However, due to the current operating systems abilities and processor architectures, we hardly recommend to use single-core implementation when parallelisation of instructions can be achieve easily with compiler tools like OpenMP.

O(|V 0 |log 2 |V 0 | + |E 0 |).

Execution times

Table 2 presents the results of our algorithm execution. The implementation and running time measurements have been done on a computer using an Intel i7-3840QM processor (2.8GHz, 4 hyper-threaded cores) with 32GB of RAM, a NVidia K2000M, running a Linux distribution (Ubuntu 14.04) and the visualisation software Tulip (http://tulip.labri.fr) [START_REF] Auber | Tulip III. In Encyclopedia of Social Network Analysis and Mining[END_REF] in its latest version (4.8). The time measurements have been performed with the Boost library (http://www.boost.org -version 1.55) and consider the real process time execution (processor time used exclusively for the program execution 1 ). The datasets used are freely available online on the Stanford Network Analysis Project website (http://snap.stanford.edu) and easily fit in random-access memory during computation as less than 8GB are used on the testing machine at all time. The graphic rendering and display times are not included in the measures, thus only concerning the layout computation. As an informal measure, the wiki-Talk layout has been displayed in less than 20s; please also note the important need in memory for the full rendering of the com-LiveJournal dataset ( 25GB).

The results presented in the table are average values obtained after 10 runs for each dataset. We use the existing implementations of Louvain and FM 3 available in Tulip, thus a small overhead due to the inner mechanisms of the framework is added to our workflow. Nonetheless, we end up being able to compute the layout on relatively large graphs (2M nodes and 5M edges) in roughly 35 seconds. The last dataset (com-LiveJournal) is presented to show the limits of our solution on a much denser graph. Table 2 shows some details concerning the time needed for intermediate computations as well. We observe the clustering algorithm is responsible on average for 30% of the total computation time on the first datasets while it is accountable for around 75% of the computation time needed for the last graph. Hence, the clustering algorithm impacts significantly on both the quality -when deciding the groupings-and the rapidity of the solution, especially when dealing with large and dense graphs. On the other hand, the layout algorithm (FM 3 ) executed on the coarse graph presents a relatively small workload (15% in the worst case) in comparison (measured as a part of the Coarsening time).

As planned, the results for some steps based on the previously announced complexities are different, the information given

Resulting visualisation

We illustrate the general results obtained with our technique using two datasets. The first one, presented in Figure 4, is a random network generated following the model of Wang et al. [START_REF] Wang | Random pseudofractal scale-free networks with small-world effect[END_REF]. The graph is rather small, only consisting of 30,000 nodes and 59,997 edges. Colours are mapped on the clusters to help differentiate one from another. The number of clusters, while being relatively low (between 70 and 80), is still significant enough so that no existing colour-scale can provide enough discernible variations [START_REF] Guastello | Human Factors Engineering and Ergonomics: A Systems Approach, Second Edition[END_REF]. Consequently, some cluster colours appear to be quite similar while truly being different. We first show the coarse graph and the final layout obtained when using our algorithm, respectively Figures 4a and4b. Figure 4c displays the same graph using a classic node-link view with a force-directed layout (FM 3 ).

One can use the colours to identify the correspondences in the clusters between the two layouts, when looking at the coarse graph and resulting layouts (resp. Fig. 4a and4b). Viewing those two representations side by side also allows to witness how our solution tends to preserve locality as connected clusters ends up next or not far one from another. Likewise, we can notice the nodes placement in Fig. 4b respects the clusters position from Fig 4a (for instance: the two orange clusters on the bottom-left or the "reddish" ones in the top-right area). Similar cross-examination is unfortunately much harder between the classic view (Fig. 4c) and the resulting layout (Fig 4b) due to the random initialisation performed by FM 3 , used in both drawings.

Altogether, the force-directed layout in Figure 4c provides a clear and understandable view of the graph. However, when facing densely connected or larger networks, force-directed representations are not clear enough and may take a long time to compute. To illustrate this point, we use the DBLP dataset (317,080 nodes and 1,049,866 edges) introduced in [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF]. Figure 5 shows the difference between the two rendered representations. The classic visualisation (Fig. 5a) using the FM 3 algorithm alone is unreadable and the communities, somewhat still discernible when solely using the force-directed algorithm with the previous example (Fig. 4c), now melt into a single shapeless mass. On the other hand, our resulting layout (Fig. 5b) offers a much clearer overview of the graph. Each cluster appears more distinctively, even with limited colour variations, and, as connected communities are most likely laid out one next to another, additional information and insights concerning the group relations can be gathered by the person visualising the graph. This point is especially true if the used visualisation framework proposes specific interactors for neighbour identification or exploration such as the neighbour highlighter [START_REF] Moscovich | Topology-aware navigation in large networks[END_REF]. As shown in Figure 5c, using such tool allows users to examine and study the graph as well as the connections between nodes. The absence of edges improves the visualisation overall legibility but those elements are not deleted and can still be visualised. Moreover, organising and positioning the nodes in clusters gives some structure to the graph, helping users in seeing which groups of nodes are connected.

Use case: overview of a propagation phenomenon

Our work emerged from a problem encountered while working on information propagation over social networks. The main task we were trying to achieve was to assist users in visualising how a propagation evolves, helping them to perform visual comparison between different propagation models. We were then looking for a simple way to obtain readable overviews of large graphs which could visually inform the user of the current state of propagation in the network. In the following, we quickly recall the principle of information propagation in a network and present some of the resulting visualisations we obtained using JASPER.

Propagation in a network

Information propagation is a basic phenomenon observed in social networks. The principle is similar to an infection, initially starting with a few contaminated persons and gradually transferred to their acquaintances and persons who may have been in contact with them. Such infection can start in one or several different locations in a network with some nodes transferring it to their neighbours. Newly contaminated nodes can themselves become infectious and thus able to spread the disease to their own neighbours, repeating the process.

One of our previous work [START_REF] Vallet | A visual analytics approach to compare propagation models in social networks[END_REF] was proposing to use visual analytics to compare existing propagation models describing such behaviour. We have shown how this task could be achieved on a small graph (300 nodes) drawn using a force-directed layout to give a simple and direct example. The propagation evolution was clearly noticeable, each node infection being notified by a changing colour, first, as it is touched -or contaminated-and then, as it becomes active, i.e., infectious. Nonetheless, without an algorithm able to compute a layout for a large graph in a small time, this visual method was not scalable. The algorithm presented in this paper aims at achieving such goal with a layout computable in a decent amount of time and presenting a full representation of the graph. The need for a spatial grouping of nodes in clusters becomes evident at this point as a propagation is due to local events, thus affecting first the nodes in clusters containing already infected elements. By gathering the connected nodes in the same area, we want to focus the visual changes induced by the propagation to a specific region of the graph displayed.

Our original work was using the graph rewriting software PORGY introduced in [START_REF] Pinaud | Porgy: A visual graph rewriting environment for complex systems[END_REF], however, facing large graphs similar to those studied in the previous section has proved to be too much for the program. Indeed, some of the performed operations, like the search of matching subgraphs, are very demanding and thus may take an overwhelming amount of time on large graphs. We thus have decided to discard for now the graph rewriting layer and only use the basic Tulip software [START_REF] Auber | Tulip III. In Encyclopedia of Social Network Analysis and Mining[END_REF], upon which PORGY is based, to perform and visualise the propagation. To this end, we have implemented the linear threshold model presented by Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] and used the Python interpreter embedded in Tulip to directly apply it to a network.

We have selected the DBLP dataset [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF] as a topological base for this use case. Every additional information concerning the graph, such as the influence on a user from another (noted b v,w ) or the threshold value for each node (θ v ), are randomly generated to compensate for our lack of knowledge. We nonetheless respect the model specificities noted by Kempe et al.: let N(v) and N A (v) be respectively all the neighbours of v and solely its active neighbours, i) the joint influence of the neighbours is never higher than 1 (∑ w∈N(v) b v,w ≤ 1) and ii) a node activates only when it is sufficiently influenced (i.e. when ∑ w∈N A (v) b v,w ≥ θ v ).

Visualising the resulting evolution

Figure 6 presents the visual overviews, obtained with JASPER, of a single propagation simulation. Just like before, we colour in a similar fashion the nodes belonging to the same clusters to allow their visual identification. The initial set of nodes, selected to be the propagation starting point, are coloured in black and can be identified as the dark rectangle in the central top part of Figure 6a in the red cluster. From this point and using the linear threshold model, we generate a propagation phenomenon. To visually depict this ongoing process, the colour of nodes relaying the propagation is changed to black. Fig. 6b shows the graph evolution after several propagation steps. Some nodes within the same cluster as the starting set have been contaminated and the infection is slowly spreading to other clusters. Fig. 6c and6d show additional overviews with an ever increasing number of infected nodes. As you may notice, the resulting layout is not quite identical to the one showed in Fig. 5b. It has been explained earlier that, as JASPER uses the FM 3 algorithm as a basic layout, the final representation is not deterministic. Additional changes may also be attributed to the local modularity optimisation performed by Louvain, the clustering algorithm used in our method.

In this use case, we have computed an additional layer of clustering compared to the results presented in the previous section. It allows us to group connected nodes more precisely. This underlying structure can be clearly seen in Fig. 6d. Two of the biggest clusters (top-left in light-blue and bottom-right in sandyellow) show a clean separation in the repartition of active and inactive nodes within them. This is not an artefact and can be explained, for instance, by either a high threshold value for one or several nodes between those two subclusters, or an insufficient influence of those central nodes on their inactive neighbours. If we look carefully, we can see that similar events actually happen in most of the clusters. When we continue the propagation process, some of those subclusters end up been infected while others keep their nodes completely inactive.

Discussion and future work

The use case previously presented exposes perfectly our main intention when initially designing this layout algorithm: to propose a legible overview for large graphs. We acknowledge the limitations of our method as we emphasize the overview characteristic of the resulting visualisation. Performing analysis or in-depth studies on a graph can not be achieved using our method alone. Obviously, if one tries to discover all there is to know about a graph using a single approach, it will not be sufficient to understand every singular detail; attaining this outcome will indeed require different methods and points of view. Only then, may it ultimately result in a more complete picture. This is true for our method as, due to our focus on node representation, we have mostly hidden the edges, thus disregarding some information. Even though we use node placement and colours to give hints of detected communities and existing connections, such metaphors are far from perfect and the visualisation produced is not entirely sound. Nevertheless, with the assistance of supplementary interactors and visual representations, additional insights on the structure of the graph and connections established through the edges can be easily accentuated; the neighbourhood highlighter available in Tulip or a matrix/node-link drawing focusing on specific sub-graphs are such tools. Furthermore, this lack of explicit information is not solely encountered when using our method as large graphs typically contain more information and details than one can possibly display simultaneously. Even other solutions similar to JASPER, using pixel-oriented layout to maximise the amount of information displayed in limited space, can only give an approximation [START_REF] Shneiderman | Extreme visualization: Squeezing a billion records into a million pixels[END_REF]. For instance, considering the wiki-Talk dataset (2, 394, 385 nodes), we realise that simply using one pixel to display each node is impossible as the sheer number of elements to display is bigger than the number of pixels available on nowadays common display interfaces (a "full HD" resolution is only able to display 1920 × 1080 = 2, 073, 600 pixels). Multi-level solutions like [START_REF] Auber | Multiscale visualization of small world networks[END_REF] and [START_REF] Shi | Himap: Adaptive visualization of large-scale online social networks[END_REF] can overcome such restrictions but only up to a certain point as their resulting layouts solely provide an approximated or partial representation of the graph.

The visualisation obtained with JASPER is very different from a typical node-link representation. Most notably, laying out the elements on a grid limits the number of direct spatial neighbours in the representation whereas a regular force-directed layout will not face such restriction. Any layout usually produces some distortion as it is not a perfect representation of the existing graph topology (different edges length, various radial distribution for The topic of dynamic data has been briefly mentioned earlier but not developed further. Obviously, the quick execution of our method allows to recompute a whole layout whenever an element is added or deleted, however, the non-deterministic characteristic of the drawings, imputed mostly to FM 3 , implies a complete transformation of the graph, thus disrupting the user mental map. Entirely recomputing the layout may in some cases be a mandatory step if added or deleted elements are key nodes or edges. Indeed, deleting the central node of a cluster may result in a division of the said cluster while inserting a new edge can result in two different clusters merging. Yet, we believe it is better to keep a certain continuity in the position of the elements, thus we plan to adapt JASPER to display dynamic graphs with minimal changes in the final layout and, consequently, on the mental map.

Conclusion

Initially created to be an efficient method to compute overviews of large graphs, we believe JASPER can be useful in all the situations where a quick visualisation to assess the state of a graph is required. When used with the appropriate colourmapping, the resulting graph can visually communicate relevant and accurate information as all the nodes are displayed at the same time, thus avoiding approximations or incomplete information one can encounter in other visualisations (for instance, when using multi-scale views).

The resulting layout is compact and present similarities with pixel-oriented layouts, allowing an efficient use of the available space. We believe this characteristic to be very important and, be-cause the size of the data sets we wish to visualise is continuously increasing with time, methods able to represent such large graphs will always be needed.

Figure 1 :

 1 Figure 1: Workflow showing how operations are pipelined in JASPER, starting from a graph with an unspecified layout and returning the same graph with a node arrangement similar to a pixel-oriented layout.

  (a) Initial graph G 0 ; each cluster C 0 is coloured differently for identification purpose.(b) Coarser representation G 1 ; each coarse representative is displayed using the same colour as its cluster.

Figure 2 :

 2 Figure 2: Example of a coarsening process on a simple graph divided in 10 clusters.

Figure 3 :

 3 Figure 3: Successive developments of the N-order space-filling curve introduced by Morton [27]; the layout is similar to a Z-order curve but with a 90 degrees rotation.

  The first phase, during which the coarse graph is built, is performed in O(|V 1 |log|V 1 | + |E 1 | + |E 0 |) while the second phase is done in O(|V 0 |log 2 |V 0 |). To simplify the expression, we maximise |V 1 | and |E 1 | to |V 0 | and |E 0 | respectively. The complete details for each step and computation phase are given in Table

  (a) Layout of the coarse graph using FM 3 -obtained after Phase I. (b) Graph displayed with a pixel-oriented layout; mapping based on the coarser graph representation -obtained after Phase II. (c) Node-link representation of the same graph using the FM 3 algorithm.

Figure 4 :

 4 Figure 4: Application of our solution on a random graph (30k nodes and 60k edges) generated with the model of Wang et al. [38]; the first two figures (a, b) show the intermediary and final layout of our algorithm while the third figure (c) shows the same graph displayed with a common force-directed layout.

  (a) Node-link representation of the network using the FM 3 algorithm; layout computed in 180 seconds using OGDF. (b) Coarse graph view transformed in a pixel-oriented view.

  (c) Use of a neighbour highlighter interactor on a node of the same graph.

Figure 5 :

 5 Figure 5: Application of our solution on the DBLP graph [26] (317k nodes and 1M edges); the first figure (a) shows the graph displayed with a force-directed layout while the second figure (b) uses a layout computed using JASPER. In the third figure (c), we use the representation (b) previously obtained, select a node and visualise its direct neighbours using a visual filter.

Figure 6 :

 6 Figure 6: Visualisation of a propagation phenomenon on the DBLP graph[START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF] (317k nodes and 1M edges) using JASPER overviews; the four layouts represent nonconsecutive steps of a single propagation simulation on the same graph, each node turning black (for visual impact) when becoming active, or infected, during the propagation.

Table 1 :

 1 Complexity of Phase I and II of JASPER applied on a graph G using one level of coarsening. |V 0 | and |E 0 | define respectively the number of nodes and edges of the initial graph G 0 while |V 1 | expresses the number of clusters computed from G 0 (equivalent to the number of nodes of G 1 ) and |E 1 | designates the edges connecting those clusters (similar to the number of edges of G 1 ).

		Phase I: coarser graphs	Phase II: pixel-oriented representation
	Step	Clustering Coarse graph construction Layout computation Node ordering Placement on the curve
	Complexity	O(|E 0

Table 2 :

 2 Presentation of the execution times for JASPER. Each time value is an arithmetic mean measured on 8 runs and expressed in seconds: Clustering gives the time for the clustering algorithm execution and Coarsening is for the rest of the Phase I operations; Phase II corresponds to the whole Phase II application (pixel-oriented layout computation); Total indicates the total execution time, sum of the previous values, and σ gives the standard deviation of the Total value.

		Graph size		Time (seconds)
	Dataset	Nodes	Edges	Clustering Coarsening Phase II	Total	σ
	email-Enron [26]	36,692	367,662	.23	.35	.27	.85	.02
	soc-Slashdot0922 [26]	82,168	948,464	.77	1.16	.59	2.52	.04
	com-DBLP [26]	317,080	1,049,866	3.11	1.32	2.37	6.80	.16
	com-Youtube [39]	1,134,890	2,987,624	8.35	5.87	9.08	23.30	.64
	wiki-Talk [25, 24]	2,394,385	5,021,410	9.84	4.18	20.24	34.26 1.64
	com-LiveJournal [39]	3,997,962 34,681,189	190.59	20.78	33.79	245.16 5.97
	earlier being only valid for single threaded executions. Thus,
	space-filling and node ordering computations are quicker than ini-
	tially expected thanks to their parallel implementations. To this
	end, we have used OpenMP (with G++ 4.82) to help improve our
	code efficiency and execute it on 8 simultaneous threads, the max-
	imum possible number on the computer used for measures. We
	plan to address the running time comparison when using different
	number of cores in future work.

Author Biography

Jason Vallet received his MSc in computer science from "Université du Québec à Chicoutimi" (2013) and is currently a PhD student in computer science at "Université de Bordeaux". His thesis subject is focused on information visualisation, graph rewriting, and their joint applications.

Guy Melanc ¸on received his PhD in combinatorial mathematics from "Université du Québec à Montréal" in 1991. Since 2007, he is a full professor in computer science at "Université de Bordeaux". His work has focused on information visualisation and network analysis.

Bruno Pinaud received his PhD in computer science from "Université de Nantes" in 2006. Since 2008, he is an associate professor in computer science at "Université de Bordeaux". His work has focused on information visualisation, graph rewrite modelling and experimental evaluation.


Olivier Finkel
email: olivier.finkel@ens-lyon.fr

An Example of Π 0 3 -complete Infinitary Rational Relation *

Keywords: infinitary rational relations, topological properties, Borel hierarchy, Π 0 3 -complete set

We give in this paper an example of infinitary rational relation, accepted by a 2-tape Büchi automaton, which is Π 0 3 -complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections.

Introduction

Acceptance of infinite words by finite automata was firstly considered in the sixties by Büchi in order to study decidability of the monadic second order theory of one successor over the integers [START_REF] Büchi | On a Decision Method in Restricted Second Order Arithmetic, Logic Methodology and Philosophy of Science[END_REF]. Then the so called ωregular languages have been intensively studied and many applications have been found, see [START_REF] Thomas | Automata on Infinite Objects[END_REF][START_REF] Staiger | ω-Languages[END_REF][START_REF] Perrin | Infinite Words, Automata, Semigroups, Logic and Games[END_REF] for many results and references. Since then many extensions of ω-regular languages have been investigated as the classes of ω-languages accepted by pushdown automata, Petri nets, Turing machines, see [START_REF] Thomas | Automata on Infinite Objects[END_REF][START_REF] Engelfriet | X-automata on ω-Words[END_REF][START_REF] Staiger | ω-Languages[END_REF] for a survey of this work.

On the other side rational relations on finite words were studied in the sixties and played a fundamental role in the study of families of context free languages [START_REF] Berstel | Transductions and Context Free Languages[END_REF]. Investigations on their extension to rational relations on infinite words were carried out or mentioned in the books [START_REF] Ya | Finite Automata, Behaviour and Synthesis[END_REF][START_REF] Lindner | Algebraische Codierungstheorie -Theorie der Sequentiellen Codierungen[END_REF]. Gire and Nivat studied infinitary rational relations in [START_REF] Gire | Relations Rationnelles Infinitaires[END_REF]GN84]. Infinitary rational relations are subsets of Σ ω 1 × Σ ω 2 × . . . × Σ ω n , where n is an integer ≥ 2 and Σ 1 , Σ 2 , . . . Σ n are finite alphabets, which are accepted by n-tape finite Büchi automata with n asynchronous reading heads. So the class of infinitary rational relations extends both the class of finitary rational relations and the class of ω-regular languages. They have been much studied, in particular in connection with the rational functions they may define, see for example [CG99, BCPS00, Sim92, Sta97, Pri00] for many results and references. Notice that a rational relation R ⊆ Σ ω 1 × Σ ω 2 × . . . × Σ ω n may be seen as an ω-language over the product alphabet Σ 1 × Σ 2 × . . . × Σ n . A way to study the complexity of languages of infinite words accepted by finite machines is to study their topological complexity and firstly to locate them with regard to the Borel and the projective hierarchies. This work is analysed for example in [START_REF] Staiger | Hierarchies of Recursive ω-Languages[END_REF][START_REF] Thomas | Automata on Infinite Objects[END_REF][START_REF] Engelfriet | X-automata on ω-Words[END_REF][START_REF] Lescow | Logical Specifications of Infinite Computations[END_REF][START_REF] Staiger | ω-Languages[END_REF]. It is well known that every ω-language accepted by a Turing machine with a Büchi or Muller acceptance condition is an analytic set and that ω-regular languages are boolean combinations of Π 0 2 -sets hence ∆ 0 3 -sets, [START_REF] Staiger | ω-Languages[END_REF][START_REF] Perrin | Infinite Words, Automata, Semigroups, Logic and Games[END_REF]. The question of the topological complexity of relations on infinite words also naturally arises and was asked by Simonnet in [START_REF] Simonnet | Automates et Théorie Descriptive[END_REF]. It was also posed in a more general form by Lescow and Thomas in [START_REF] Lescow | Logical Specifications of Infinite Computations[END_REF] (for infinite labelled partial orders) and in [START_REF] Thomas | Automata and Quantifier Hierarchies[END_REF] where Thomas suggested to study reducibility notions and associated completeness results. Every infinitary rational relation is an analytic set. We showed in [START_REF] Finkel | On the Topological Complexity of Infinitary Rational Relations[END_REF] that there exist some infinitary rational relations which are analytic but non Borel sets. Considering Borel infinitary rational relations we prove in this paper that there exist some infinitary rational relations, accepted by 2-tape Büchi automata, which are Π 0 3 -complete. Examples of Σ 0 3 -complete and Π 0 3 -complete infinitary rational relations have already been given in the conference paper [START_REF] Finkel | On Infinitary Rational Relations and Borel Sets[END_REF]. But the proof of the existence of Π 0 3 -complete infinitary rational relations was only sketched and we used a coding of ω 2 -words by pairs of infinite words. We use in this paper a different coding of ω 2 -words. This way we get some infinitary rational relations which have a very simple structure and can be easily described by their sections. The result given in this paper has two interests: 1) It gives a complete proof of a result of [START_REF] Finkel | On Infinitary Rational Relations and Borel Sets[END_REF]. 2) Some new ideas are here introduced with a new coding of ω 2 -words. Some of these new ideas led us further to the proof of very surprising results, answering the long standing open questions of the topological complexity of context free ω-languages and of infinitary rational relations. In particular infinitary rational relations have the same topological complexity as ω-languages accepted by Büchi Turing machines [START_REF] Finkel | Borel Ranks and Wadge Degrees of Omega Context Free Languages[END_REF][START_REF] Finkel | On the Accepting Power of 2-Tape Büchi Automata[END_REF]and for every recursive ordinal α there exist some Π 0 α -complete and some Σ 0 α -complete infinitary rational relations. The result presented in this paper is still interesting, although the result of the paper [START_REF] Finkel | On the Accepting Power of 2-Tape Büchi Automata[END_REF] is stronger; we use here a coding of ω 2 -words while in [START_REF] Finkel | Borel Ranks and Wadge Degrees of Omega Context Free Languages[END_REF][START_REF] Finkel | On the Accepting Power of 2-Tape Büchi Automata[END_REF] we used a simulation of Turing machines and the examples of infinitary rational relations we obtain are different. The result of this paper may also be compared with examples of Σ 0 3 -complete ω-languages accepted by deterministic pushdown automata with the acceptance condition: "some stack content appears infinitely often during an infinite run", given by Cachat, Duparc, and Thomas in [START_REF] Cachat | Solving Pushdown Games with a Σ 3 Winning Condition[END_REF] or with examples of Σ 0 n -complete and Π 0 n -complete ω-languages, n ≥ 1, accepted by non-deterministic pushdown automata with Büchi acceptance condition given in [START_REF] Finkel | Topological Properties of Omega Context Free Languages[END_REF]. The paper is organized as follows. In section 2 we introduce the notion of infinitary rational relations. In section 3 we recall definitions of Borel sets, and we prove our main result in section 4.

Infinitary rational relations

Let Σ be a finite alphabet whose elements are called letters. A non-empty finite word over Σ is a finite sequence of letters: x = a 1 a 2 . . . a n where for all integers i ∈ [1; n] a i ∈ Σ. We shall denote x(i) = a i the i th letter of x and x[i] = x(1) . . . x(i) for i ≤ n. The length of x is |x| = n. The empty word will be denoted by λ and has 0 letter. Its length is 0. The set of finite words over Σ is denoted Σ ⋆ . A (finitary) language L over Σ is a subset of Σ ⋆ . The usual concatenation product of u and v will be denoted by u.v or just uv.

For V ⊆ Σ ⋆ , we denote V ⋆ = {v 1 . . . v n | ∀i ∈ [1; n] v i ∈ V } ∪ {λ}.
The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a 1 a 2 . . . a n . . ., where for all integers i ≥ 1 a i ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) . . . σ(n) . . . and σ[n] = σ(1)σ(2) . . . σ(n) the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ ω . An ω-language over an alphabet Σ is a subset of Σ ω . For

V ⊆ Σ ⋆ , V ω = {σ = u 1 . . . u n . . . ∈ Σ ω | ∀i ≥ 1 u i ∈ V } is the ω-power of V .
The concatenation product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that:

(u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k -|u|) if k > |u|. If A is a subset of B we shall denote A -= B -A the complement of A (in B).
We assume the reader to be familiar with the theory of formal languages and of ω-regular languages. We recall that ω-regular languages form the class of ω-languages accepted by finite automata with a Büchi acceptance condition and this class is the omega Kleene closure of the class of regular finitary languages.

We are going now to introduce the notion of infinitary rational relation

R ⊆ Σ ω 1 × Σ ω 2 via acceptance by 2-tape Büchi automata. Definition 2.1 A 2-tape Büchi automaton is a 7-tuple T = (K, Σ 1 , Σ 2 , ∆, q 0 , F ), where K is a finite set of states, Σ 1 , Σ 2 , are finite alphabets, ∆ is a finite subset of K × Σ ⋆ 1 × Σ ⋆ 2 × K called the set of transitions, q 0 is the initial state, and F ⊆ K is the set of accepting states. A computation C of the 2-tape Büchi automaton T over the pair (u, v) ∈ Σ ω 1 × Σ ω
2 is an infinite sequence of transitions (q 0 , u 1 , v 1 , q 1 ), (q 1 , u 2 , v 2 , q 2 ), . . . (q i-1 , u i , v i , q i ), (q i , u i+1 , v i+1 , q i+1 ), . . .

such that: u = u 1 .u 2 .u 3 . . . and v = v 1 .v 2 .v 3 . . ..
The computation is said to be successful iff there exists an accepting state q f ∈ F and infinitely many integers i ≥ 0 such that q i = q f . The infinitary rational relation R(T ) ⊆ Σ ω 1 ×Σ ω 2 accepted by the 2-tape Büchi automaton T is the set of pairs (u, v) ∈ Σ ω 1 × Σ ω 2 such that there is some successful computation C of T over (u, v). The set of infinitary rational relations accepted by 2-tape Büchi automata will be denoted RAT 2 .

As noticed in the introduction an infinitary rational relation R ⊆ Σ ω 1 × Σ ω 2 may be considered as an ω-language over the product alphabet Σ 1 × Σ 2 . We shall use this fact to investigate the topological complexity of infinitary rational relations.

Borel sets

We assume the reader to be familiar with basic notions of topology which may be found in [Mos80, Kec95, LT94, Sta97, PP02].

For a finite alphabet X we shall consider X ω as a topological space with the Cantor topology. The open sets of X ω are the sets in the form W.X ω , where

W ⊆ X ⋆ . A set L ⊆ X ω is a closed set iff its complement X ω -L is an open set.
Define now the next classes of the Hierarchy of Borel sets of finite ranks:

Definition 3.1 The classes Σ 0 n and Π 0 n of the Borel Hierarchy on the topological space X ω are defined as follows:

Σ 0 1 is the class of open sets of X ω .
Π 0 1 is the class of closed sets of X ω . And for any integer n ≥ 1:

Σ 0 n+1 is the class of countable unions of Π 0 n -subsets of X ω . Π 0 n+1 is the class of countable intersections of Σ 0 n -subsets of X ω .
The Borel Hierarchy is also defined for transfinite levels, but we shall not need them in the present study. There are also some subsets of X ω which are not Borel. In particular the class of Borel subsets of X ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projection of Borel sets, see for example [Sta97, LT94, PP02, Kec95] for more details.

Recall also the notion of completeness with regard to reduction by continuous functions. For an integer n ≥ 1, a set F ⊆ X ω is said to be a Σ 0 n (respectively, Π 0 n , Σ 1 1 )-complete set iff for any set E ⊆ Y ω (with Y a finite alphabet):

E ∈ Σ 0 n (respectively, E ∈ Π 0 n , E ∈ Σ 1 1 ) iff there exists a continuous function f : Y ω → X ω such that E = f -1 (F ). A Σ 0 n (respectively, Π 0 n , Σ 1 1 )-complete set is a Σ 0 n (respectively, Π 0 n , Σ 1 1
)-set which is in some sense a set of the highest topological complexity among the Σ 0 n (respectively, Π 0 n , Σ 1 1 )-sets. Σ 0 n (respectively, Π 0 n )-complete sets, with n an integer ≥ 1, are thoroughly characterized in [START_REF] Staiger | Hierarchies of Recursive ω-Languages[END_REF].

Example 3.2 Let Σ = {0, 1} and A = (0 ⋆ .1) ω ⊆ Σ ω . A is the set of ωwords over the alphabet Σ with infinitely many occurrences of the letter 1. It is well known that A is a Π 0 2 -complete set and its complement A -is a Σ 0 2complete set: it is the set of ω-words over {0, 1} having only a finite number of occurrences of letter 1.

Π 0 3 -complete infinitary rational relations

We had got in [START_REF] Finkel | On Infinitary Rational Relations and Borel Sets[END_REF] some Π 0 3 -complete infinitary rational relations. We used a coding of ω 2 -words over a finite alphabet Σ by pairs of ω-words over Σ ∪ {A} where A is an additionnal letter not in Σ. We shall modify the previous proof (only sketched in [START_REF] Finkel | On Infinitary Rational Relations and Borel Sets[END_REF]) by coding an ω 2 -word over a finite alphabet Σ by a single ω-word over Σ ∪ {A}. This way we can get some Π 0 3 -complete infinitary rational relation having some extra property.

Theorem 4.1 Let Γ = {0, 1, A} be an alphabet having three letters, and α be the ω-word over the alphabet Γ which is defined by: α = A.0.A.0 2 .A.0 3 .A.0 4 .A.0 5 .A . . . A.0 n .A.0 n+1 .A . . .

Then there exists an infinitary rational relation

R ⊆ Γ ω × Γ ω such that: R α = {σ ∈ Γ ω | (σ, α) ∈ R} is a Π 0 3 -complete subset of Γ ω , and for all u ∈ Γ ω -{α} R u = {σ ∈ Γ ω | (σ, u) ∈ R} = Γ ω . Moreover R is a Π 0 3 -complete subset of Γ ω × Γ ω .
Proof. We shall use a well known example of Π 0 3 -complete set which is a subset of the topological space Σ ω 2 . The set Σ ω 2 is the set of ω 2 -words over the finite alphabet Σ. It may also be viewed as the set of (infinite) (ω × ω)-matrices whose coefficients are letters of Σ. If x ∈ Σ ω 2 we shall write x = (x(m, n)) m≥1,n≥1 . The infinite word x(m, 1)x(m, 2) . . . x(m, n) . . . will be called the m th column of the ω 2 -word x and the infinite word x(1, n)x(2, n) . . . x(m, n) . . . will be called the n th row of the ω 2 -word x. Thus an element of Σ ω 2 is completely determined by the (infinite) set of its columns or of its rows. The set Σ ω 2 is usually equipped with the product topology of the dicrete topology on Σ (for which every subset of Σ is an open set), see [Kec95] [PP02]. This topology may be defined by the following distance d. Let x and y be two ω 2 -words in Σ ω 2 such that x = y, then

d(x, y) = 1 2 n where n = min{p ≥ 1 | ∃(i, j) x(i, j) = y(i, j) and i + j = p}
Then the topological space Σ ω 2 is homeomorphic to the above defined topological space Σ ω . The Borel hierarchy and the projective hierarchy on Σ ω 2 are defined from open sets in the same manner as in the case of the topological space Σ ω . The notion of Σ 0 n (respectively Π 0 n )-complete sets are also defined in a similar way.

Let now

P = {x ∈ {0, 1} ω 2 | ∀m∃ <∞ n x(m, n) = 1}
where ∃ <∞ means "there exist only finitely many", P is the set of ω 2 -words having all their columns in the Σ 0 2 -complete subset A -of {0, 1} ω where A is the Π 0 2 -complete ω-regular language given in Example 3.2.

Recall the following classical result, [Kec95, p. 179]:

Lemma 4.2 The set P is a Π 0 3 -complete subset of {0, 1} ω 2 . Proof. Let B m = {x ∈ Σ ω 2 | x(m, 1)
x(m, 2) . . . x(m, n) . . . ∈ A -} be the set of ω 2 -words over Σ = {0, 1} having their m th column in the Σ 0 2complete set A -. In order to prove that, for every integer m ≥ 1, the set

B m is a Σ 0 2 -subset of Σ ω 2 , consider the function i m : Σ ω 2 → Σ ω defined by i m (x) = x(m, 1)x(m, 2) . . . x(m, n) . . . for every x ∈ Σ ω 2 . The function i m is continuous and i -1 m (A -) = B m holds. Therefore B m is a Σ 0 2 -subset of Σ ω 2 because the class Σ 0
2 is closed under inverse images by continuous functions.

Thus the set

P = m≥1 B m
of ω 2 -words over Σ having all their columns in A -is a countable intersection of Σ 0 2 -sets so it is a Π 0 3 -set.

It remains to show that

P is Π 0 3 -complete. Let then L be a Π 0 3 -subset of Σ ω . We know that L = ∩ i∈N ⋆ A i for some Σ 0 2 -subsets A i , i ≥ 1, of Σ ω . But A -is Σ 0 2 -complete therefore, for each integer i ≥ 1, there is some continuous function f i : Σ ω → Σ ω such that f -1 i (A -) = A i . Let now f be the function from Σ ω into Σ ω 2 which is defined by f (x)(m, n) = f m (x)(n). The function f is continuous because each function f i is continu- ous.
For x ∈ Σ ω f (x) ∈ P iff the ω 2 -word f (x) has all its columns in the ωlanguage A -, i.e. iff for all integers m ≥ 1

f m (x) = f m (x)(1)f m (x)(2) . . . f m (x)(n) . . . ∈ A - iff ∀m ≥ 1 x ∈ A m . Thus f (x) ∈ P iff x ∈ L = ∩ m≥1 A m so L = f -1 (P ).
is an open (i.e. a Σ 0 1 ) subset of (Σ ∪ {A}) ω .

On the other hand the function h is also injective thus it is a bijection from Σ ω 2 onto h(Σ ω 2 ). But a continuous bijection between two compact sets is an homeomorphism therefore h induces an homeomorphism between Σ ω 2 and h(Σ ω 2 ). By hypothesis L is a Π 0 3 -subset of Σ ω 2 thus h(L) is a Π 0 3 -subset of h(Σ ω 2 ) (where Borel sets of the topological space h(Σ ω 2 ) are defined from open sets as in the cases of the topological spaces Σ ω or Σ ω 2 ).

The topological space h(Σ ω 2 ) is a topological subspace of (Σ ∪ {A}) ω and its topology is induced by the topology on (Σ ∪ {A}) ω : open sets of h(Σ ω 2 ) are traces on h(Σ ω 2 ) of open sets of (Σ ∪ {A}) ω and the same result holds for closed sets. Then one can easily show by induction that for every integer

n ≥ 1, Π 0 n -subsets (resp. Σ 0 n -subsets) of h(Σ ω 2 ) are traces on h(Σ ω 2 ) of Π 0 n - subsets (resp. Σ 0 n -subsets) of (Σ ∪ {A}) ω , i.e. are intersections with h(Σ ω 2 ) of Π 0 n -subsets (resp. Σ 0 n -subsets) of (Σ ∪ {A}) ω . But h(L) is a Π 0 3 -subset of h(Σ ω 2 ) hence there exists a Π 0 3 -subset T of (Σ ∪ {A}) ω such that h(L) = T ∩ h(Σ ω 2 ). But h(Σ ω 2 ) is a closed i.e. Π 0 1 -subset (hence also a Π 0 3 -subset) of (Σ ∪ {A}) ω and the class of Π 0 3 -subsets of (Σ ∪ {A}) ω is closed under finite intersection thus h(L) is a Π 0 3 -subset of (Σ ∪ {A}) ω . Now h(L) ∪ (h(Σ ω 2 )) -is the union of a Π 0
3 -subset and of a Σ 0 1 -subset of (Σ ∪ {A}) ω therefore it is a Π 0 3 -subset of (Σ ∪ {A}) ω because the class of Π 0 3 -subsets of (Σ ∪ {A}) ω is closed under finite union.

In order to prove that h(L)

∪ (h(Σ ω 2 )) -is Π 0 3 -complete it suffices to remark that L = h -1 [h(L) ∪ (h(Σ ω 2 )) -] This implies that h(L) ∪ (h(Σ ω 2 )) -is Π 0 3 -complete because L is assumed to be Π 0 3 -complete. Lemma 4.4 Let P = {x ∈ {0, 1} ω 2 | ∀m∃ <∞ n x(m, n) = 1} and Σ = {0, 1}. Then P = h(P ) ∪ (h(Σ ω 2 )) - is a Π 0 3 -complete subset of (Σ ∪ {A}) ω .
Proof. It follows directly from the two preceding Lemmas.

Let now Σ = {0, 1} and let α be the ω-word over the alphabet Σ ∪ {A} which is defined by: α = A.0.A.0 2 .A.0 3 .A.0 4 .A.0 5 .A . . . A.0 n .A.0 n+1 .A . . .

We can now state the following Lemma.

Lemma 4.5 Let Σ = {0, 1} and α be the ω-word over Σ ∪ {A} defined as above. Then there exists an infinitary rational relation

R 1 ⊆ (Σ ∪ {A}) ω × (Σ ∪ {A}) ω such that: ∀x ∈ Σ ω 2 (x ∈ P ) iff ((h(x), α) ∈ R 1 )
Proof. We define now the relation R 1 . A pair y = (y 1 , y 2 ) of ω-words over the alphabet Σ ∪ {A} is in R 1 if and only if it is in the form

y 1 = U k .u 1 .v 1 .A.u 2 .v 2 .A.u 3 .v 3 .A . . . A.u n .v n .A. . . . y 2 = V k .w 1 .z 1 .A.w 2 .z 2 .A.w 3 .z 3 .A . . . A.w n .z n .A . . .
where k is an integer ≥ 1, U k , V k ∈ (Σ ⋆ .A) k , and, for all integers i ≥ 1, v i , w i , z i ∈ 0 ⋆ and u i ∈ Σ ⋆ and

|w i | = |v i | and [ |u i+1 | = |z i | + 1 or |u i+1 | = |z i | ]
and there exist infinitely many integers i such that

|u i+1 | = |z i |.
We prove first that the relation R 1 satisfies:

∀x ∈ Σ ω 2 (x ∈ P ) iff ((h(x), α) ∈ R 1 )
Assume that for some x ∈ Σ ω 2 (h(x), α) ∈ R 1 . Then (h(x), α) may be written in the above form (y 1 , y 2 ) with Consider now, for n ≥ N,

y 1 = U k .u 1 .v 1 .A.u 2 .v 2 .A.u 3 .v 3 .A . . . A.u n .v n .A. . . . y 2 = V k .w 1 .z 1 .A.w 2 .z 2 .A.w 3 .z 3 .A . . . A.w n .z n .A . . . y 1 = h(x) implies that for all integers n ≥ 1 U x k+n = u n .v n thus |u n .v n | = k + n -1. y 2 = α implies that for all integers n ≥ 1 w n .z n = 0 k+n-1 thus |w n .z n | = k + n -1. So |u n .v n | = |w n .
U x k+n = u n .v n = x(k + n -1, 1).x(k + n -2, 2) . . . x(2, k + n -2).x(1, k + n -1) We know that v n ∈ 0 ⋆ thus x(|v n |, k+n-|v n |) = x(|v n |-1, k+n+1-|v n |) = . . . = x(2, k+n-2) = x(1, k+n-1) = 0 and in particular x(K, k+n-K) = x(K-1, k+n+1-K) = . . . = x(2, k+n-2) = x(1, k+n-1) = 0 because |v n | ≥ K.
These equalities hold for all integers n ≥ N and this proves that the K first columns of the ω 2 -word x have only finitely many occurrences of the letter 1. But this is true for all integers K ≥ 1 so all columns of x have a finite number of occurrences of the letter 1 and x ∈ P .

Conversely it is easy to see that for each x ∈ P the pair (h(x), α) may be written in the above form (y 1 , y 2 ) ∈ R 1 .

It remains only to prove that the above defined relation R 1 is an infinitary rational relation. It is easy to see that the following 2-tape Büchi automaton T accepts the infinitary rational relation R 1 .

T = (K, Γ, Γ, δ, q 0 , F ), where K = {q 0 , q 1 , q 2 , q 3 , q 4 , q 5 } is a finite set of states, Γ = Σ∪{A} = {0, 1, A}, with Σ = {0, 1}, q 0 is the initial state, and F = {q 4 } is the set of final states. Moreover δ ⊆ K × Γ ⋆ × Γ ⋆ × K is the finite set of transitions, containing the following transitions:

(q 0 , a, λ, q 0 ), for all a ∈ Σ, (q 0 , λ, a, q 0 ), for all a ∈ Σ, (q 0 , A, A, q 0 ), (q 0 , A, A, q 1 ), (q 1 , a, λ, q 1 ), for all a ∈ Σ, (q 1 , λ, λ, q 2 ), (q 2 , a, 0, q 2 ), for all a ∈ Σ, (q 2 , A, λ, q 3 ), (q 3 , a, 0, q 3 ), for all a ∈ Σ, (q 3 , λ, λ, q 4 ) (q 3 , a, λ, q 5 ), for all a ∈ Σ, (q 4 , λ, A, q 2 ), (q 5 , λ, A, q 2 ).

Remark 4.6 Using classical constructions from automata theory, we could have avoided the set of transitions to contain some transitions in the form (q i , λ, λ, q j ), like (q 1 , λ, λ, q 2 ) or (q 3 , λ, λ, q 4 ).

Lemma 4.7 The set

R 2 = (Σ ∪ {A}) ω × (Σ ∪ {A}) ω -(h(Σ ω 2 ) × {α})
is an infinitary rational relation.

Proof. By definition of the mapping h, we know that a pair of ω-words over the alphabet (Σ ∪ {A}) is in h(Σ ω 2 ) × {α} iff it is in the form (σ 1 , σ 2 ), where σ 1 = A.u 1 .A. where for all integers i ≥ 1, u i ∈ Σ ⋆ and |u i | = i.

So it is easy to see that (Σ ∪ {A}) ω × (Σ ∪ {A}) ω -(h(Σ ω 2 ) × {α}) is the union of the sets C j where:

• C 1 = {(σ 1 , σ 2 ) / σ 1 , σ 2 ∈ (Σ ∪ {A}) ω and (σ 1 ∈ B or σ 2 ∈ B)} where B is the set of ω-words over (Σ∪{A}) having only a finite number of letters A.

• C 2 is formed by pairs (σ 1 , σ 2 ) where σ 1 or σ 2 has not any initial segment in A.Σ.A.Σ 2 .A. where n is an integer ≥ 1, for all i ≤ n w i , w ′ i ∈ Σ ⋆ , w n+1 ∈ Σ ⋆ , z 1 , z 2 ∈ (Σ ∪ {A}) ω and u, v ∈ Σ ⋆ and |v| = |u| + 1 Each set C j , 1 ≤ j ≤ 5, is easily seen to be an infinitary rational relation ⊆ (Σ ∪ {A}) ω × (Σ ∪ {A}) ω (the detailed proof is left to the reader). The class RAT 2 is closed under finite union thus

R 2 = (Σ ∪ {A}) ω × (Σ ∪ {A}) ω -(h(Σ ω 2 ) × {α}) =
R = R 1 ∪ R 2 ⊆ Γ ω × Γ ω
The class RAT 2 is closed under finite union therefore R is an infinitary rational relation.

  z n | but by hypothesis |w n | = |v n | therefore |u n | = |z n |.Moreover |u n+1 | = |z n | + 1 or |u n+1 | = |z n |. If |u n+1 | = |z n | + 1 then |u n+1 | = |u n | + 1 and |v n+1 | = |v n | because |u n+1 | + |v n+1 | = |u n | + |v n | + 1. If |u n+1 | = |z n | then |u n+1 | = |u n | and |v n+1 | = |v n | + 1 because |u n+1 | + |v n+1 | = |u n | + |v n | + 1.This proves that the sequence (|v n |) n≥1 is increasing because for all integers n ≥ 1 |v n+1 | = |v n | or |v n+1 | = |v n | + 1. Moreover by definition of R 1 we know that there exist infinitely many integers n ≥ 1 such that |u n+1 | = |z n | hence also |v n+1 | = |v n | + 1. Thus lim n→+∞ |v n | = +∞ Let now K be an integer ≥ 1 and let us prove that the K first columns of the ω 2 -word x have only finitely many occurrences of the letter 1. lim n→+∞ |v n | = +∞ thus there exists an integer N ≥ 1 such that ∀n ≥ N |v n | ≥ K.

  u 2 .A.u 3 .A.u 4 .A . . . .A.u n .A.u n+1 .A . . . σ 2 = α = A.0.A.0 2 .A.0 3 .A.0 4 .A . . . A.0 n .A.0 n+1 .A . . .

  rational relation. Return now to the proof of Theorem 4.1. Let

  • C 3 is formed by pairs (σ 1 , σ 2 ) where σ 2 / ∈ {0, A} ω .• C 4 is formed by pairs (σ 1 , σ 2 ) whereσ 1 = A.w 1 .A.w 2 .A.w 3 .A.w 4 .A . . . A.w n .A.u.A.z 1 σ 2 = A.w ′ 1 .A.w ′ 2 .A.w ′ 3 .A.w ′ 4 .A . . . A.w ′ n .A.v.A.z 2where n is an integer ≥ 1, for all i ≤ n w i , w′ i ∈ Σ ⋆ , z 1 , z 2 ∈ (Σ ∪ {A}) ω and u, v ∈ Σ ⋆ and |v| = |u| • C 5 is formed by pairs (σ 1 , σ 2 ) where σ 1 = A.w 1 .A.w 2 .A.w 3 .A.w 4 . . . A.w n .A.w n+1 .A.v.A.z 1 σ 2 = A.w ′ 1 .A.w ′ 2 .A.w ′ 3 .A.w ′ 4 . . . A.w ′ n .A.u.A.z 2

Acknowledgements. Thanks to Jean-Pierre Ressayre and Pierre Simonnet for useful discussions.

We have then proved that all Π 0 3 -subsets of Σ ω are inverse images by continuous functions of the Π 0 3 -set P therefore P is a Π 0 3 -complete set.

In order to use this example we shall firstly define a coding of ω 2 -words over Σ by ω-words over the alphabet (Σ ∪ {A}) where A is a new letter not in Σ.

Let us call, for x ∈ Σ ω 2 and p an integer ≥ 1:

the set of elements x(m, n) with m + n = p + 1 and

the sequence formed by the concatenation of elements x(m, n) of T x p+1 for increasing values of n.

We shall code an ω 2 -word x ∈ Σ ω 2 by the ω-word h(x) defined by

Let then h be the mapping from Σ ω 2 into (Σ ∪ {A}) ω such that, for every ω 2 -word x over the alphabet Σ, h(x) is the code of the ω 2 -word x as defined above. It is easy to see, from the definition of h and of the order of the enumeration of letters x(m, n) in h(x) (they are enumerated for increasing values of m + n), that h is a continuous function from Σ ω 2 into (Σ ∪ {A}) ω .

Remark that the above coding of ω 2 -words resembles the use of the Cantor pairing function as it was used to construct the complete sets P i and S i in [START_REF] Staiger | Rekursive Folgenmengen I[END_REF] (see also [START_REF] Staiger | Hierarchies of Recursive ω-Languages[END_REF] or [Sta97, section 3.4]).

Proof. The topological space Σ ω 2 is compact thus its image by the continuous function h is also a compact subset of the topological space (Σ ∪ {A}) ω . The set h(Σ ω 2 ) is compact hence it is a closed subset of (Σ ∪ {A}) ω and its complement (h(Σ ω 2 )) -= (Σ ∪ {A}) ω -h(Σ ω 2 ) Lemma 4.5 and the definition of R 2 imply that R α = {σ ∈ Γ ω | (σ, α) ∈ R} is equal to the set P = h(P ) ∪ (h(Σ ω 2 )) -which is a Π 0 3 -complete subset of (Σ ∪ {A}) ω by Lemma 4.4.

Moreover, for all

In order to prove that R is a Π 0 3 -set remark first that R may be written as the union:

We already know that P is a Π 0 3 -complete subset of (Σ ∪ {A}) ω . Then it is easy to show that P × {α} is also a Π 0 3 -subset of (Σ ∪ {A}) ω × (Σ ∪ {A}) ω . On the other side it is easy to see that Γ

Moreover let g : Σ ω 2 → (Σ ∪ {A}) ω × (Σ ∪ {A}) ω be the function defined by:

It is easy to see that g is continuous because h is continuous. By construction it turns out that for all ω 2 -words x ∈ Σ ω 2 (x ∈ P ) iff (g(x) ∈ R). This means that g -1 (R) = P . This implies that R is Π 0 3 -complete because P is Π 0 3 -complete.

Remark 4.8 The structure of the Π 0 3 -complete infinitary rational relation R we have just got is very different from the structure of a previous example given in [START_REF] Finkel | On Infinitary Rational Relations and Borel Sets[END_REF]. It can be described very simply by the sections R u , u ∈ Γ ω . All sections but one are equal to Γ ω , so they have the lowest topological complexity and exactly one section is a Π 0 3 -complete subset of Γ ω .