domain: spi phys

text:
V Fabbro

K S Jacobsen

S Rougerie

HAPEE, a statistical approach for ionospheric scintillation prediction in polar region

Keywords: ionospheric scintillation, L band, polar region, solar wind pressure, interplanetary magnetic field, scintillation indices I

The main objective of this study is to propose a forecasting model of ionospheric scintillation indices ROTI (Rate Of Tec Index) and σ φ for the polar region. In 2014, a first model was proposed using a simple empirical model driven by the Kp geomagnetic index, and where the main output was the instantaneous mean ROTI value [1]. In 2019, an updated model is proposed, where the main inputs are solar wind parameters, p (the solar wind pressure p) and B z (the z component of the Earth magnetic field). Moreover, a distribution of predicted ROTI or σ φ index is provided instead of a mean value. Thus, the model allows estimating the percentage of time of occurrence for a level of ROTI (or σ φ ) to be exceeded in the next 5 minutes or 1 hour, or the exceeded ROTI (or σ φ ) for a corresponding percentage of time. This empirical approach is based on 10 years of scintillation data collected by more than 15 GNSS stations in

Norway. Here, 1Hz ROTI and σ φ were used, and the network is operated by NMA. This paper will present the HAPEE model, and discuss initial validation work. This work is the result of a fruitful collaboration between the CNES, ONERA, NSC and NMA organizations.

INTRODUCTION

When crossing the ionosphere layer, L-band satellite navigation signals are impacted by a group delay effect and scintillation. The group delay effect leads to a positioning error of several meters to tens of meters. Most of it can be corrected in the case of Global Navigation Satellite Systems (GNSS) either using a dual frequency measurement, or using correction models (like Klobuchar model, NeQuick model, or TEC grids in the case of augmentation systems) for single frequency system. The scintillation generally occurs over the equatorial region and the polar zone, but it may also occur at mid-latitudes particularly when the solar activity increases or during strong geomagnetic storm. These events impact the signal and cause very fast variations of the amplitude and phase. Therefore, the signal fades and GNSS receivers may lose lock. The consequence on the navigation systems is the unavailability of the satellite link as well as the reduced reliability of the available information.

Several models exist for scintillation modeling: GISM (Global Ionospheric Scintillation Model) [START_REF] Béniguel | A Global Ionosphere Scintillation Propagation Model for Equatorial Regions[END_REF] referenced at the ITU [START_REF]Ionospheric propagation data and prediction methods required for the design of satellite services and systems[END_REF], provides mean scintillation indices values (S 4 for the amplitude scintillation, σ φ for the phase scintillation), and can provide also time series of amplitude and phase. However, this model is reliable only for the equatorial region, and the forecasting performances are limited as the model is driven only by the solar flux number F10.7, which is a daily parameter. The STIPEE model [START_REF] Galiègue | Validity of 2-D electromagnetic approaches to estimate log-amplitude and phase variances due to 3-D ionospheric irregularities[END_REF] proposes a 3D formulation of the problem reliable for polar and equatorial region and valid from weak up to strong scintillation. Nevertheless, this model is not proposing forecasting of scintillation indices. WBMOD [START_REF] Secan | An Investigation of Methods for Improving Models of Ionospheric Plasma-Density Irregularities and Radio-Frequency Scintillation[END_REF][6] (WideBandMODel), developed by NWRA (Northwest Research Associates) proposes statistics of scintillation for polar and equatorial region [START_REF] Rino | A power law phase screen model for ionospheric scintillation, Weak scatter[END_REF]. However, WBMOD is driven by monthly Sun Spot Number (SSN) and daily Kp parameters. Thus, it provides a statistical characterization of the scintillation for a given period, but cannot provide prediction at one hour, typically. Thus, though these models are very useful for link budget dimensioning or for receiver testing, they cannot be used in operational condition for forecasting purpose.

In [START_REF] Boscher | Modelling ionospheric effects for L band GNSS receivers at high latitudes[END_REF], a simple empirical model driven by the Kp geomagnetic index has been proposed based on the correlation between the ROTI (Rate Of TEC Index) and the electron energy fluxes measured from the NOAA POES satellites. The electron energy flux was sorted as a function of maps in McIlwain parameter L versus Magnetic Local Time (MLT), and several maps were proposed as a function of the Kp index. Finally, for a given position and time, the associated (or predicted) Kp is obtained, and a mean ROTI value is given [START_REF] Boscher | Modelling ionospheric effects for L band GNSS receivers at high latitudes[END_REF]. The algorithm has been implemented and tested by NMA [START_REF] Fabbro | a prediction model of ionospheric scintillation in polar region[END_REF]. The first conclusion was that the accuracy of the predicted magnetic index Kp is not sufficient for ROTI prediction purpose. We observe in active periods that the forecasted Kp is consistently underestimating the observed Kp, and overestimating in quiet periods. As a consequence, the bad Kp prediction leads to a degradation of the ROTI prediction. The second conclusion is that if the observed Kp is used, the ROTI predictions are coherent for quiet and moderate activity (i.e. Kp<5), and elevation > 40°. For low elevation and higher Kp value, the model performance is significantly degraded, providing underestimation of the scintillation intensity [START_REF] Jacobsen | Statistics of ionospheric disturbances and their correlation with GNSS positioning errors at high latitudes[END_REF]. Our conclusion is that models based on magnetic indices give a coarse idea of the scintillation condition, but they are not accurate enough for a monitoring system. In particular, strong events are not predictable with enough accuracy, and even the magnitude of scintillation during quiet periods is hardly estimable.

Because of those limitations, another approach to scintillation forecasting is proposed in this paper. First, instead of using Earth magnetic field inputs (Kp, Ae…) or solar activity inputs (SSN, F10.7…), space weather indices, i.e. parameters describing the solar wind, have been considered for inputs. Moreover, to improve the model relevance for link budget dimensioning or for receiver testing, a statistical approach has been chosen rather than a research of mean indices values. Section II is introducing the new model named HAPEE (High lAtitude scintillation Positioning Error Estimator). In section III the validation process is described, and the conclusions and future works are discussed in section IV.

II. HAPEE MODEL

In order to provide a new model, four main updates were proposed compare to the initial model [START_REF] Boscher | Modelling ionospheric effects for L band GNSS receivers at high latitudes[END_REF]:

First model update: The idea of this work is to search for a statistical relation between space weather indices (such as solar wind parameters, interplanetary magnetic field, particle density, electric field … ) and energy fluxes measured in polar region by low orbit satellites (such as POES satellite). From such analysis, the energy flux may be possible to forecast. As it is related to ROTI by previous models [START_REF] Boscher | Modelling ionospheric effects for L band GNSS receivers at high latitudes[END_REF], we could end up with a prediction model for ionospheric disturbance on GNSS signals in polar region. A sensitivity analysis of the energy flux to different parameters characterizing the solar wind has been performed. This analysis, not detailed in this paper, brings to light that no clear relation can be found considering each space weather parameter alone. Here interplanetary magnetic field angle θ, solar wind velocity V, solar pressure p, electric field component E y , magnetic field component B z have been considered. Please note that some of these parameters are correlated. As an example, the solar wind velocity is often a "consequence" of the variation of pressure p or of the density in the case of a Coronal Mass Ejection. Another example, high solar wind velocity is coming with highly variable B z (the z-component -in GSM coordinates-of the interplanetary magnetic field) in the High Speed solar wind Streams. Possible cross-correlations, considering several space weather indices as input and energy flux as output, have been studied. The more significant cross-correlations have been obtained considering the B z and p parameters. This analysis has been performed based on NOAA TED and MEPED electron measurements. Different maps of the energy flux, either in L-MLT or in longitude-latitude for a particular instant of a specific day (as in Figure 1) have been computed. Thus, for given B z and p values, these maps can be used to estimate the energy flux everywhere on the Earth. Starting from this preliminary analysis, the solar wind parameters B z and p have been considered as inputs of a ROTI index model. Third model update: the third update is to take into account time inertia of the ionosphere. It is well known that the ionosphere layer is adding a propagation time delay and this delay is different for the different values of latitude (or L values) and MLT. Where the Earth magnetic field lines are close to be open, the time delay can be very short, whereas it is higher in the aurora oval (between minutes up to several hours) and can reach several hours for lower latitudes. Moreover, the variability with MLT time must be added, introducing an important difference between night and day conditions. Thus, for t 0 a given time of measurement of the space weather indices B z and p, all scintillation index values during a following given period ∆t (from t 0 up to t 0 + ∆t) have been considered. The idea of the model is then to estimate a statistic of ROTI values obtained during the ∆t period.

Fourth model update: As said in §Erreur ! Source du renvoi introuvable., it is more appropriate for operational applications to characterize the scintillation through statistical distribution prediction. The goal of the requested model is to provide the probability to exceed a certain level of ionosphere disturbance during a given period ∆t.

Thus, for each intervals of B z , p, MLT and L, the distributions of the ROTI and σ φ indices have been analyzed from t 0 up to t 0 +∆t. Here, we have considered

mn t 5 = ∆ and hour t 1 = ∆
. To do so, the data provided by NMA are used, from 2007 up to 2017 over more than 15 stations in Norway (see Figure 2). We call this data set "set 1".

Figure 2: Set of GNSS receivers to build the model

The ROTI (based on 1 Hz sample rate data) and σ φ (based on 100 Hz sample rate data) indices are used for the regression. Before performing the complete database processing, a correction of ROTI index depending of the elevation has been applied. A study of this dependency has been proposed by Jacobsen et al. in [START_REF] Jacobsen | Statistics of ionospheric disturbances and their correlation with GNSS positioning errors at high latitudes[END_REF]. An exponential model was proposed. In Figure 3this model is compared with a simple sine correction (compensating the slant elongation of the path), the AATR index obliquity factor correction (estimated at 350 km), and the obliquity factor correction estimated at 350, 100 and 50 km. Considering that the best fit obtained by Jacobsen et al. is the reference, one can observe that the obliquity factor is converging to the data when the altitude of estimation is decreasing (supposed to be the mean altitude of the ionosphere layer). But the choice of an ionosphere altitude below 100 km is not physical, even at polar latitude. On the other hand, a simple correction by a sine function provides results very close to the Jacobsen et al. proposed function. Moreover, only measurements at elevation angles higher than 30 degrees are considered in the database. Finally, a simple correction by a sine function has been taken into account in the final data processing.

Figure 3: Variation of mean ROTI vs Elevation angle

In order to have reliable statistics, the intervals of B z and p are tuned. The final selection was 12 intervals between -20 and 20 nT for B z , and 6 intervals between 0 and 15 nPa for p. Different tests have been performed to study indices variability for a given space weather condition (i.e. combined B z and p intervals) associated to MLT and L intervals. Considering such a combination, in Figure 4 an example of ROTI distribution is proposed. A log-normal fit has been tested and is plotted as a red line. The global trend is well fitted by a log-normal probability density function and the latter has been chosen for the final model. The same exercise has been performed for σ φ distributions and is illustrated in Figure 5. Less data are available for this index, but a log-normal distribution should be adopted too.

( ) ( ) [ ] T ROTI erfc T > - - = - Pr 1 2 2 ln 1 σ µ , ( 1
)
where erfc -1 denotes the inverse of the complementary Gauss error function. An example of output is shown in Figure 8.

Second kind of output: Percentage of time exceeding a specified ROTI threshold

Input parameters:

• ROTI threshold (T)

• receiver position

• t 0 • ∆t (5 mn or 1 hour)
Similarly to the first approach, the µ and σ parameters as a function of the receiver's positions, t 0 and ∆t are derived from the HAPEE Data Base. Then, the model is producing the percentage (P) of the time for the ROTI threshold to be exceeded in the next period (for instance 5 minutes or 1 hour). The formulation used is:

( )       - - - = > = 2 ln 2 1 1 Pr σ µ T erfc T ROTI P , ( 2
)
where erfc denotes the complementary of the Gauss error function. An example of output is shown in Figure 9.

III. A FIRST VALIDATION OF THE HAPEE MODEL

For the validation of the HAPEE model, another set of data acquired by different receivers was used (Figure 10). This group of receiver differs from the ones used to build the model (represented in Figure 2). Moreover, data from 2018 were used for the validation (we remind the model has been developed with data from 2007 to 2017). We call this data set "set 2".

Figure 10: Set of GNSS receivers to test the model

In Figure 11, the ratio between the observed ROTI CDF vs the forecasted one is plotted. Here, three levels of ROTI were tested: low for ROTI < 2 TECU/min, Medium 2<ROTI<4 and high ROTI>4 TECU/min. From this figure, it can be observed globally that the HAPEE forecast provides ROTI values lower than the measured ones. The forecasts are valid at the highest percentages, but appear to struggle at the lower percentages (i.e. when the tail of the ROTI distribution is important).

Figure 11: Ratio between observed and forecast ROTI CDF for 3 different level of ROTI Threshold

However, after a deeper analysis, a part of the database appears to be doubtful. In Figure 12, we plot ROTI distributions of one specific receiver. On the left, the ROTI distribution is computed with all the satellite, and on the right with only one satellite. From these plots of ROTI data, it appears that a suspicious double peak is present in the distributions of measured ROTI. The lower peak seems coherent with the statistics extracted from 2007 to 2017, but the higher peak is strange. This effect is more important for some satellites than other. In the case of the satellite PRN 28, in Figure 13 the ROTI values are plotted vs the elevation angle for all the year 2018. One can see a hole in this distribution, which cannot be explained by a natural space weather effect. In Figure 14, a sky plot view of the mean ROTI over an entire year shows that one direction of arrival is much more impacted than the other, and here again, no space weather effects can explain these observations. After an analysis of the receiver close environment (Figure 15), a metallic pole can be noticed close to the GNSS antenna. The direction in azimuth of the strange mean ROTI values is similar to the direction of the metallic pole. Our assumption is that this pole might generate multipath to the GNSS antenna, and these multipath might bias the ROTI statistics. This conclusion will be validated further thanks to the SPRING simulator, a tool which is simulating the reception of a GNSS receiver in its surrounding environment [START_REF] Chapuis | SPRING, A powerful 3D GNSS simulator for constraint environment[END_REF]. The validation of the HAPEE model is therefore not complete. First, it is necessary to recheck the database and search if some multipath may bias the statistics. This is true for the "set 2" (validation data set), but it may be the case also for the "set 1" (data used to build the HAPEE model). For the "Set 1", 10 years of data have been used, and the multipath effect on the statistics may be smoother than in the "Set 2" where only one year of data is used. Also, this kind of interference is only present at a few receiver sites. That can explain why we did not observe such trouble on the statistic base on the "Set 1". and p parameters, for each receiver position point (characterized in latitude and longitude) two approaches are possible: first, the model is performing for a given percentage of the time, the corresponding level of exceeded ROTI or second, for a given level of exceeded ROTI, the corresponding percentage of the time.

This paper also presents the first validation of the HAPEE model. After a deep investigation of the specific data base used for the testing (different from the one to make the model), we suspect that multipath occurs for some GNSS stations and bias the statistics. Thus, the validation is not complete as the data set for model testing should be reviewed. From these experiences, it may be possible that multipath occurs also in the data set use for making the model. Thus, future work will focus on the data base cleaning of the multipath, and a new fit of the HAPEE model will be performed. The model can also be improved in term of modeling. For example, we should consider a time shift due to the access to the space weather parameters, and the delays of 5 minutes and 1 hour (considering these periods of interest for the final user). Moreover, a multivariate interpolation has to be applied to represent the final results and avoid discontinuities (or "patch" effect) due to intervals definition. Finally, an analysis of complementary inputs such as B x , B y , clock angle, time where consecutive negative B z value occur, could be carried out to improve the model sensitivity to solar wind conditions.

Figure 1 :

 1 Figure 1: Energy flux maps projected on the Earth for various solar wind pressures and components for 0h UT (calculation made on 1st January 2017). All the graphs are made using the same scale, given on the right, with the unit erg.cm -2 s -1Second model update: the second update has been to search for a correlation between the space weather indices (B z , p) and the ROTI index, without going through the energy flux as proposed in[START_REF] Boscher | Modelling ionospheric effects for L band GNSS receivers at high latitudes[END_REF]. This exercise has been performed defining intervals for the values of B z , p, and the coordinates MLT and L.

Figure 4 :Figure 5 :

 45 Figure 4: Example of ROTI distributions for B z , p, L and MLT intervals combination, 2015

Figure 6 and

 6 Figure 7 are examples of respectively mean and standard deviation of ROTI value sorted as a function of B z , p, MLT and L intervals.

Figure 6 :

 6 Figure 6: Example of mean value ROTI vs B z and p, for 5 min delay in the HAPEE model. For each B z and p interval, a map of mean value of ROTI in (L, Mc Ilwain) coordinates has been derived. Mean ROTI value is represented in colors.

Figure 7 :

 7 Figure 7: Example of standard deviation value ROTI vs B z and p, for 5 min delay in the HAPEE model. For each B z and p interval, a map of mean value of ROTI in (L, Mc Ilwain) coordinates has been derived. Standard deviation of ROTI value is represented in colors.

Figure 8 :. 5 Figure 9 :

 859 Figure 8: Map of ROTI value during next 5 minutes for percentile 0.5

Figure 12 :

 12 Figure 12: ROTI distribution, receiver BRGS. Left panel: all the satellites. Right panel: only satellite PRN = 28

Figure 13 :Figure 14 :

 1314 Figure 13: ROTI vs elevation, BRGS, PRN = 28

  IV. CONCLUSIONS A new model of ROTI index prediction, called HAPEE (for High lAtitude scintillation Positioning Error Estimator), is proposed based on a statistical fit of a ROTI 1 Hz database measured from 2007 up to 2017 in Norway. The different steps of the model regression are described in this paper. The model is established via (MLT, L-MacIlwain) coordinates system allowing generalizing the measurements performed in Norway to all high latitudes coordinates. The space weather activity is modeled by solar wind parameters B z (z component of the interplanetary magnetic field) and p (solar wind pressure) indices measured from a satellite at L1 Lagrange point and provided by NOAA. From measured B z

ACKNOWLEDGEMENTS

The authors would like to thank the Norwegian Mapping Authority (NMA) for the ROTI data processing and sharing, and more particularly Yngvild Andalsvik and Rune Hanssen. The authors would like also to thank Daniel Boscher, Sandrine Rochel and Joel Lemorton from ONERA for their work on this study.


Chris Keeler
email: keeler@cs.queensu.ca

Kai Salomaa
email: ksalomaa@cs.queensu.ca

Nondeterminism Growth and State Complexity

Tree width (respectively, string path width) measures the maximal number of partial (respectively, complete) computations of a nondeterministic finite automaton (NFA) on an input of given length. We study the growth rate of the tree width and string path width measures. As the main result we show that the degree of the polynomial bounding the tree width of an NFA differs by at most one from the degree of the polynomial bounding the string path width. Also we show that for m ≥ 4 there exists an m-state NFA with finite string path width such that any equivalent finite tree width NFA needs 2 m-2 + 1 states.

Introduction

Deterministic and nondeterministic finite automata (DFA and NFA) define the class of regular languages, and have been systematically studied for over 60 years. More recently there has been much interest in automata employing limited nondeterminism [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF][START_REF] Hromkovič | Communication complexity method for measuring nondeterminism in finite automata[END_REF][START_REF] Ravikumar | Relating the type of ambiguity of finite automata to the succinctness of their representation[END_REF]. Different measures of nondeterminism allow us to quantify the amount and type of nondeterminism present in an NFA's computations.

Ambiguity is probably the first nondeterminism measure to be studied systematically. The ambiguity [START_REF] Leung | Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata[END_REF][START_REF] Leung | Descriptional complexity of NFA of different ambiguity[END_REF][START_REF] Ravikumar | Relating the type of ambiguity of finite automata to the succinctness of their representation[END_REF][START_REF] Weber | On the degree of ambiguity of finite automata[END_REF] of an NFA A on an input string counts the number of accepting computations of A on that string and the tree width [START_REF] Hromkovič | Communication complexity method for measuring nondeterminism in finite automata[END_REF][START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF] of A counts the number of all computations of A on the input string. The string path width [START_REF] Keeler | Branching measures and nearly acyclic NFAs[END_REF][START_REF] Keeler | Cycle height of finite automata[END_REF] lies between tree width and ambiguity, as it does not count the partial computations counted by tree width, but it does count complete nonaccepting computations. We extend each of these measures of nondeterminism to functions on integers, and consider the growth rate of the corresponding function with respect to worst-case inputs of given length. The growth rate of ambiguity and tree width has been considered, respectively, e.g., in [START_REF] Leung | Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata[END_REF][START_REF] Ravikumar | Relating the type of ambiguity of finite automata to the succinctness of their representation[END_REF][START_REF] Weber | On the degree of ambiguity of finite automata[END_REF] and in [START_REF] Hromkovič | Communication complexity method for measuring nondeterminism in finite automata[END_REF].

State complexity is another topic in automata theory with much recent research [START_REF] Holzer | Descriptional and computational complexity of finite automata -a survey[END_REF][START_REF] Kutrib | Recent trends in descriptional complexity of formal languages[END_REF]. The study of state complexity aspects of limited nondeterminism was initiated by Goldstine et al. [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF] who showed that there exists an m-state NFA A such that any finite branching NFA equivalent to A needs 2 m-1 states. More generally, Goldstine et al. [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF] gave a spectrum result which establishes that there exist regular languages for which different finite amounts of nondeterminism yield incremental savings in the number of states. Hromkovič et al. [START_REF] Hromkovič | Communication complexity method for measuring nondeterminism in finite automata[END_REF] have shown that there exist m-state NFAs with linear ambiguity such that any equivalent finitely ambiguous NFA needs close to 2 m states. Palioudakis et al. [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF] showed that there exists an m-state unambiguous NFA such that an equivalent NFA with finite tree width needs 2 m-1 states. Here we establish a similar state complexity blow-up between NFAs of finite string path width and finite tree width, respectively.

The contents of this paper are as follows. Section 2 recalls definitions and fixes the notation. Section 3.1 shows that an NFA has polynomial string path width if and only if its tree width is polynomial and, furthermore, that the degrees of the polynomials differ by at most one. Also, it is shown that for NFAs without useless states the degree of the polynomial bounding the growth rate of ambiguity coincides with the polynomial bounding string path width. Section 3.2 shows that an NFA has exponential string path width if and only if it has exponential tree width. Section 4 gives polynomial-time algorithms to decide whether the growth rate of an NFA's tree width (respectively, string path width) is polynomial or exponential, and additionally, to compute the degree of the polynomial bounding the growth. These algorithms utilize existing algorithms from the literature [START_REF] Leung | Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata[END_REF][START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]. Section 5 shows that for m ≥ 4 there exists an m-state NFA A with finite string path width such that any finite tree width NFA equivalent to A needs at least 2 m-2 + 1 states.

Preliminaries

Here we recall definitions and notation needed in later sections. We assume that the reader is familiar with finite automata, and point them to resources such as [START_REF] Shallit | A Second Course in Formal Languages and Automata Theory[END_REF]. The set of strings over an alphabet Σ is denoted as Σ * , Σ + is the set of nonempty strings and the set of strings of length over Σ is Σ . We use |S| to mean the cardinality of a finite set S, ε to mean the empty string, and N to mean the set of positive integers. Consider a function f ( ) :

N → N. If for d ∈ N, f ( ) ∈ O( d ), (respectively, ∈ Θ( d ))
, then we say that f has polynomial growth degree d (respectively, strict polynomial growth degree d). If f ( ) ∈ 2 Θ( ) , then we say that f ( ) has exponential growth.

A nondeterministic finite automaton (NFA) is a 5-tuple A = (Q, Σ, δ, q 0 , F ) consisting of a finite set of states Q, a finite alphabet Σ, a transition function δ : Q × Σ → 2 Q , an initial state q 0 ∈ Q, and a set of final states F ⊆ Q. The transition function is extended in the usual way as a function δ :

Q × Σ * → 2 Q and the language recognized by A is L(A) = {w ∈ Σ * | δ(q 0 , w) ∩ F = ∅ }.
The NFA A is a deterministic finite automaton (DFA) if |δ(q, c)| ≤ 1 for all q ∈ Q and c ∈ Σ. If δ(q, c) is always a singleton set, A is a complete DFA.

Without loss of generality, we assume that all states of an NFA are reachable from the start state. In the event that there are non-reachable states, they can simply be removed. Unless otherwise specified, we do not assume that every state can reach a final state, i.e., states need not be co-reachable.

A path of A from p 1 ∈ Q to p +1 ∈ Q on a string a 1 • • • a ∈ Σ * is an ordered sequence of the form (p 1 , a 1 , p 2 , a 2 , . . . , p , a , p +1 ) such that p i+1 ∈ δ(p i , a i ), 1 ≤ i ≤ . The set of all paths from state q to state p on string w ∈ Σ * is denoted as paths(q, w, p).

A path of A from the initial state q 0 to a state p on string w is a (complete) computation on w and it is an accepting computation if p ∈ F . A path of A from the initial state q 0 to a state p on a prefix w 1 of w is a partial computation of A on w if either w 1 = w (complete computation) or w = w 1 bw 2 , b ∈ Σ, and δ(p, b) = ∅. That is, a partial computation on w must read the string as far as it can, until it encounters an undefined transition.

For L ⊆ Σ * , the Myhill-Nerode equivalence relation of L, ≡ L ⊆ Σ * × Σ * , is defined by setting for x, y ∈ Σ * :

x ≡ L y iff (∀z ∈ Σ * ) xz ∈ L ⇔ yz ∈ L
For a regular language L, the number of equivalence classes of ≡ L gives the number of states of the minimal complete DFA recognizing L [START_REF] Shallit | A Second Course in Formal Languages and Automata Theory[END_REF].

The ambiguity of an NFA A on a string w, denoted da(A, w), is the number of accepting computations of A on w. The ambiguity of A on all strings of length is da(A, ) = max{da(A, w) | w ∈ Σ }, and the ambiguity of A is da(A) = sup ∈N {da(A, )}. Note that da(A) may be infinite.

The string path width [START_REF] Keeler | Branching measures and nearly acyclic NFAs[END_REF][START_REF] Han | Ambiguity, nondeterminism and state complexity of finite automata[END_REF], roughly speaking, counts the number of complete computations and tree width [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF] counts the number of partial computations. Formally this is defined as follows. For an NFA A and string w, the string path width of A on w, spw(A, w), is the number of complete computations of A on w and the tree width of A on w, tw(A, w), is the number of partial computations of A on w. Again for ∈ N, we define spw(A, ) = max{spw(A, w) | w ∈ Σ } and tw(A, ) = max{tw(A, w) | w ∈ Σ }, as well as, spw(A) = sup ∈N {tw(A, )} and spw(A) = sup ∈N {spw(A, )}.

An NFA's tree width will grow unboundedly with respect to the length of the input string if and only if some cycle has a nondeterministic transition [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF]. Figure 1 gives a visual abstraction of this condition. Directly by the definitions, for any NFA A and ∈ N we have da(A, ) ≤ spw(A, ) ≤ tw(A, ). If all states of A are final, then the ambiguity and string path width of A are equal on any string. If A has no undefined transitions, then its string path width and tree width are equal.

The completion of an NFA A = (Q, Σ, δ, q 0 , F ) is obtained from A by adding a sink state that is the target of all previously undefined transitions. Formally, the completion of A is A = (Q , Σ, δ , q 0 , F ), where

Q = Q, if δ(q, b) = ∅ for all q ∈ Q and b ∈ Σ; Q ∪ {q sink }, otherwise,
and the transitions are defined by setting δ

(q sink , b) = {q sink }, for all b ∈ Σ, δ (q, b) = δ(q, b), if δ(q, b) = ∅; {q sink }, if δ(q, b) = ∅, q ∈ Q, b ∈ Σ.
Directly from the definition of string path width and tree width we get:

Lemma 1. For any NFA A and string w ∈ Σ * , spw( A, w) = tw(A, w).

3 Growth of string path width and tree width

Weber and Seidl [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF], based on earlier work, developed structural criteria to determine the growth rate of ambiguity of an NFA as a function of input length. We extend and modify these conditions to study the growth rate of string path width and tree width. In the following A = (Q, Σ, δ, q 0 , F ) is always an NFA.

Polynomial Growth

For an NFA A, da(A, ) ∈ Ω( d ), d ∈ N, if and only if A complies with a condition (IDA d ) [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF] which means that A can be viewed to have a "subgraph" of a certain type. We refer to such subgraphs as widgets. The widget (IDA d ) is almost the same as (ISPW d ) defined below and represented in Figure 2. The only difference is that (IDA d ) additionally requires that the state c d must be able to reach a final state.

To characterize polynomial string path width, we use a widget, (ISPW d ), modified from (IDA d ) [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]. -For all 1 ≤ i ≤ d: s i = c i , and paths(s i , v i , s i ), paths(s i , v i , c i ), and paths(c i , v i , c i ) are all non-empty. -For all 2 ≤ j ≤ d: paths(c j-1 , u j , s j ) is non-empty.

(ISPW d ): There exist states s 1 , c 1 , . . . , s d , c d ∈ Q, strings v 1 , . . . , v d ∈ Σ + ,
We call the cycle on s i a "seeding cycle" and the cycle on c i a "catching cycle". The states s i and c i must be connected by the same string v i occurring in the cycles. Note that the u j -strings can be empty, but the v i -strings cannot. When a string u j is empty for some 2 ≤ j ≤ d, states c j-1 and s j must be the same state. That is, there exists a state which is involved in a cycle on each of the strings v j-1 and v j (which may be the same string). Lemma 2. An NFA A has string path width Ω( d ) if and only if A admits a widget (ISPW d ), for some d ∈ N.

s1 c1 s2 . . . c d-1 s d c d . . . v1 v1 v1 u2 v2 v2 v d-1 v d-1 u d v d v d v d Fig. 2. Widget (ISPW d )
Proof. Let A be obtained from A by making all of its states final. From [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF] we know that A has degree of ambiguity Ω( d ) iff A admits the widget (IDA d ), and the latter holds iff A admits the widget (ISPW d ). For any string w, da(A , w) = spw(A, w).

An NFA's string path width will be finite if and only if it does not admit a widget (ISPW 1 ). Corollary 1. For an NFA A, spw(A) ∈ O(1) iff for all q, q ∈ Q and w ∈ Σ * such that q = q : (i) |paths(q, w, q)| ≤ 1 (ii) (|paths(q, w, q)| = 1 and |paths(q , w, q )| = 1) implies |paths(q, w, q )| = 0. Lemma 2 implies that an NFA A has tree width Θ( d ) exactly when A admits a widget (ISPW d ), but does not admit a widget (ISPW d+1 ).

For an NFA A, the ambiguity and string path width of A on a particular string, or on strings of given length, can be very different, even assuming that A has no useless states. For example, if spw(A, ) = 0, the string path width of A on all lengths 1, . . . , -1 must be positive. On the other hand, it is possible that da(A, ) = 0 and da(A, + 1) = 0.

However, as a consequence of Lemma 2 and [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF], we see that, for NFAs without useless states, the polynomial growth rates of ambiguity and string path width must coincide. Note that when A has no useless states, an (ISPW d ) widget is also an (IDA d ) widget. We give a visual abstraction of these alterations in Figure 3 (cf. Figure 2). Next we establish the correctness result for our new criterion. Proof. Suppose that A has tree width Ω( d ). By Lemma Conversely, assume that A admits a widget (ITW d ) and let A be the completion of A. Using the notation of Figure 3 Thus, by Lemma 2, A has string path width Ω( d ). By Lemma 1, tw(A, ) ∈ Ω( d ).

Again, Lemma 3 implies that tw(A, ) ∈ Θ( d ) exactly when A admits a widget (ITW d ) and does not admit a widget (ITW d+1 ).

Intuitively, tree width and string path width can seem very different measures because the former counts all computations while the latter counts only complete computations. As a consequence of Lemmas 2 and 3, we see that the degrees of polynomials bounding the growth rate of, respectively, the tree width and the string path width of an NFA differ by at most one. Theorem 1. Let A be an NFA and d ∈ N.

(i) If spw(A, ) ∈ Θ( d ), then tw(A, ) is in Θ( d ) or in Θ( d+1 ). (ii) If tw(A, ) ∈ Θ( d ), then spw(A, ) is in Θ( d ) or in Θ( d-1 ).
From the characterization of Lemmas 2 and 3 it follows also that, for all d ∈ N, there exists an NFA A such that spw(A, ) ∈ Θ( d ) and tw(A, ) ∈ Θ( d+1 ).

To conclude this section we observe that the criteria (ISPW d ) and (ITW d ) yield lower bounds for the number of states or the number of transitions of an NFA having polynomial string path (or tree) width. Proposition 1. Let A = (Q, Σ, δ, q 0 , F ) be an NFA and d ∈ N.

(i) If tw(A, ) ∈ Θ( d ), then 1 ≤ d < |Q|, and 2 • d ≤ |δ|. (ii) If tw(A, ) ∈ Θ( d ), and L(A) = w * , w ∈ Σ k , k ∈ N, then 1 ≤ (d • k) + 1 ≤ |Q| and d • (k + 1) ≤ |δ|. Furthermore, in case (i) (respectively, in case (ii)) there exists an NFA A such that d = |Q| -1 and 2 • d = |δ| (respectively, d • k + 1 = Q and d • (k + 1) = |δ|).

Exponential Growth

In the following A = (Q, Σ, δ, q 0 , F ) is again always an NFA. If NFA A complies with (EDA) (see Figure 5), then it has exponential ambiguity [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]. This condition requires that for some state q there exist two distinct paths from q to q with the same underlying string.

(EDA): There exists a co-reachable state q ∈ Q and a string w ∈ Σ * such that |paths(q, w, q)| ≥ 2.

The difference between ambiguity and string path width is that the latter measure does not require computations to be accepting. Based on this observation, we can formulate the widget (ECOMP) to characterize exponential string path width, and the correctness of (ECOMP) is verified in Lemma 4.

In the definition of the widget (EDA) or (ECOMP) the string w must have a length of at least two because there can be only one path from q to q on an individual alphabet symbol. Since the cycles must have a length of at least two, it follows immediately that an NFA admitting widget (ECOMP) has to admit (ISPW d ) for all d ∈ N (as should be the case).

(ECOMP): There exists a state q ∈ Q and a string w ∈ Σ * such that |paths(q, w, q)| ≥ 2. An NFA has exponential tree width if and only if it has exponential string path width. The "if"-direction of the following proposition is proved by applying Lemma 4 to the completion of the NFA. Proposition 2. Let A be an NFA. Then A has exponential tree width if and only if A has exponential string path width.

Algorithms for Deciding the Growth Rate

From Theorem 1, we know that there is a relationship between the polynomial degrees of an NFA's string path width and tree width. An algorithm which decides the polynomial degree of an NFA's string path width or tree width, roughly speaking, also decides the degree of the other measure.

Palioudakis et. al [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF] have shown that for an NFA A we can decide in polynomial time whether A has finite tree width, but did not give a more precise time bound for the algorithm. Theorem 2. Let A = (Q, Σ, δ, q 0 , F ) be an NFA. Then we can decide whether or not A has finite tree width in O(|Q| 4 • |Σ|) time.

Proof. For q ∈ Q and a ∈ Σ, we denote A q,a = (Q, Σ, δ q,a , q, F ) where the transitions are defined for

p ∈ Q, b ∈ Σ, δ q,a (p, b) = ∅, if p = q and b = a; δ(p, b), otherwise. (1)
In Algorithm 1, for states q and p of an NFA, the distance from q to p is the length of the shortest nonempty string that takes q to p. If p is not reachable from q, then the distance is ∞. The distance from q to itself is ∞ unless q is involved in a cycle. Complexity analysis of Algorithm 1: Creating each NFA takes O(|Q| + |δ|) time and space, and creating each distance matrix takes Θ(|Q| 3 ) time and Θ(|Q| 2 ) space using the Floyd-Warshall reachability algorithm [START_REF] Cormen | Introduction to Algorithms, 3rd Edition[END_REF]. There are |Q| • |Σ| NFAs A q,a and matrices which are created. In lines 8-16, we again check each combination of state and character, but the inner work on lines 10-14 is done Algorithm 1 Deciding if an NFA has finite tree width

Input: A = (Q, Σ, δ, q0, F ) Output: finite ∈ {true, false} 1: for all q ∈ Q do 2:
for all a ∈ Σ do 3:

Create Aq,a = (Q, Σ, δq,a, q, F ) as in (1).

4:

Create the distance matrix Mq,a[p, p ], where Mq,a[p, p ] is the minimum distance from state p ∈ Q to state p ∈ Q in the NFA Aq,a.

5:

end for 6: end for 7: finite = true 8: for all q ∈ Q do 9:

for all a ∈ Σ do 10:

if Mq,a[q, q] = ∞ then #q can reach itself starting with a 11:

if |δ(q, a)| ≥ 2 then #q is a nondeterministic branching point 12: finite = false 13:

end if 14:

end if 15:

end for 16: end for 17: return finite in constant time with the help of the reachability matrices. The algorithm then runs in O(|Q| 4 • |Σ|) time. Correctness analysis of Algorithm 1: Recall that an NFA has infinite tree width if and only if some cycle has a nondeterministic transition. The diagonal of each distance matrix gives the self-reachability for each combination of state and character. That is, for all q ∈ Q and a ∈ Σ, M q,a [q, q] = ∞ means that q can reach itself in A on a string that begins with a. The algorithm returns false ("unbounded tree width") if and only if there exists a state q ∈ Q and character a ∈ Σ such that M q,a [q, q] = ∞ and |δ(q, a)| ≥ 2.

Note that while Algorithm 1 could be modified to decide finiteness of string path width, its complexity would be worse than existing algorithms [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]. This is because the algorithm checks only for nondeterministic characters that initiate cycles, and does not check for strings across cycles.

To design efficient decision algorithms for deciding the growth rate of an NFA's tree width, we leverage existing algorithms [START_REF] Leung | Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata[END_REF][START_REF] Weber | On the degree of ambiguity of finite automata[END_REF] for deciding the growth rate of ambiguity. Lemma 5. [modified from [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]] Let A = (Q, Σ, δ, q 0 , F ) be an NFA. Then we can decide whether or not A's tree width is exponential in O(|Q| 4 • |Σ|) time.

Using Algorithm 1 and Lemma 5, we can decide whether the growth rate of tree width of A is finite or exponential, and the remaining possibility is polynomial.

Corollary 3. For an NFA A = (Q, Σ, δ, q 0 , F ), we can decide whether A's tree width is finite, polynomial, or exponential in O(|Q| 4 • |Σ|) time.

Using another algorithm by Weber and Seidl [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF], we can also determine the minimum degree of the polynomial bounding an NFA's tree width. Proposition 3. [modified from [START_REF] Weber | On the degree of ambiguity of finite automata[END_REF]] For an NFA A = (Q, Σ, δ, q 0 , F ) we can decide in O(|Q| 6 • |Σ|) time whether A's tree width is polynomial, and if so, the degree d > 0 such that tw(A, ) ∈ Θ( d ).

State Complexity

It is known that unambiguous NFAs may be significantly more succint than finite tree width NFAs [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF]. Since string path width lies in between the measures of ambiguity and tree width, we initiate here a descriptional complexity comparison of NFAs with finite string path width and finite tree width, respectively. We show that there exist finite string path width NFAs with m states such that an equivalent finite tree width NFA needs close to 2 m states.

Goldstine et al. [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF] establishes that for certain regular languages an NFA with finite branching has to be as large as a DFA. Instead of the branching measure [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF] the below lemma considers tree width. Lemma 6. [modified from [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF]] Let L ⊆ Σ * be a regular language and c ∈ Σ. If A is a finite tree width NFA for (cLc) * , then A needs as many states as the minimal incomplete DFA for (cLc) * . Set Q m = {0, 1, . . . , m + 2} and define A m = (Q m , Σ, δ, 0, {0}) where δ is defined by setting:

(i) δ(0, c) = {1}, δ(m + 2, c) = {0}, (ii) δ(1, a) = {1, 2}, δ(1, b) = {2}, (iii) δ(i, z) = {i + 1}, z ∈ {a, b}, 2 ≤ i ≤ m + 1.
All transitions not defined above are undefined. Figure 6 depicts the NFA A m and it is clear that L

(A m ) = (cL m c) * . Lemma 7. spw(A m ) = m + 2.
It is well known that the minimal DFA B m for L m has 2 m+1 states -the DFA B m just remembers the positions of symbols a among the last m+1 symbols read. Based on B m it is easy to construct an incomplete DFA C m for (cL m c) * by adding a new start state q new that is the sole accepting state of C m , a transition on c from q new to the start state of B m and a transition on c from each accepting state of B m to q new . The DFA C m has 2 m+1 + 1 states.

Next using Lemma 6 we show that any finite tree width NFA for (cL m c) * needs 2 m+1 + 1 states. The above means that the minimal complete DFA for (cL m c) * has (at least) 2 m+1 + 2 states, and hence the minimal incomplete DFA for (cL m c) * needs 2 m+1 + 1 states. The claim follows from Lemma 6.

As a consequence of Lemmas 7 and 8 we have: Theorem 3. For m ≥ 1 there exists an (m + 3)-state NFA with finite string path width such that any equivalent finite tree width NFA needs 2 m+1 + 1 states.

Note that Lemma 6 uses the language (cLc) * , while it seems that the same claim should hold also for (Lc) * and using the latter language would slightly improve the state complexity blow-up of Theorem 3. However, we have not been able to modify the original construction from [START_REF] Goldstine | On measuring nondeterminism in regular languages[END_REF] (that is needed for Lemma 6) to work with the simpler language. We can note that the NFA A m is also unambiguous. The size blow-up given by Theorem 3 is slightly worse than the known blow-up of converting an unambiguous NFA to a finite tree width NFA [START_REF] Palioudakis | State complexity of finite tree width NFAs[END_REF].

Conclusion

As the main result we have shown that the tree width of an NFA A grows polynomially if and only if the string path width of A is polynomial and the degrees of the polynomials differ by at most one. Furthermore, if A has no useless states then the degree of the polynomial growth rate of string path width coincides with the degree of the polynomial bounding the ambiguity of A. We have also initiated a descriptional complexity comparison of NFAs with finite string path width and finite tree width, respectively.

A topic for further research could include the descriptional complexity comparison of NFAs with different growth rates of tree width (respectively, string path width). For example, it is known that the size of NFAs with polynomial ambiguity is exponentially separated from the size of general NFAs [START_REF] Leung | Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata[END_REF][START_REF] Hromkovič | Communication complexity method for measuring nondeterminism in finite automata[END_REF].

Fig. 1 .

 1 Fig. 1. NFA with Infinite Tree Width

Corollary 2 .

 2 If A is an NFA without useless states, then spw(A, ) ∈ Θ( d ) if and only if da(A, ) ∈ Θ( d ), for d ∈ N. To characterize polynomial tree width, we define a new widget, (ITW d ), which is the same as (ISPW d ), except: (i) For the "last state" c d we remove the condition that |paths(c d , v d , c d )| > 0. That is, the final "catching loop" on state c d does not need to be present. (ii) For the final pair of states we modify the condition |paths(s d , v d , c d )| > 0 to be |δ(s d , a)| > 0 instead, where a is the first letter of v d . That is, the state s d with the final "seeding loop" only needs a nondeterministic transition on the first symbol of v d .

Fig. 3 .Lemma 3 .

 33 Fig. 3. Widget (ITW d ). The letter a must be the first symbol in v d .

Fig. 4 .

 4 Fig. 4. Completing the (ITW d ) widget to a (ISPW d ) widget

Fig. 5 .

 5 Fig. 5. Exponential Nondeterminism Growth Rate Widgets

  Let Σ = {a, b, c} and for m ∈ N define L m = (a + b) * a(a + b) m .

Fig. 6 .

 6 Fig.6. NFA Am recognizing the language (cLmc) *

  1, the completion of A, A, has string path width Ω( d ) and hence by Lemma 2, A admits the widget (ISPW d ). Since s i = c i for i = 1, . . . , d, none of the states s i 1 ≤ i ≤ d, or c j , 1 ≤ j ≤ d -1 can be the sink state of A because the only state reachable from the sink state is itself. Thus, in the widget (ISPW d ) of A, only the state c d may be the sink state and all transitions "before" entering c d must exist also in the original NFA A. This means that A admits (ITW d ).


Jarkko Kari
email: jkari@utu.fi

Low-Complexity Tilings of the Plane

Keywords: Pattern complexity, periodicity, Nivat's conjecture, low complexity configurations, low complexity subshifts, commutative algebra, algebraic subshifts, domino problem

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Commutative algebra provides powerful tools to analyze low complexity configurations, that is, colorings of the two-dimensional grid that have sufficiently low number of different local patterns. If the colors are represented as numbers, the low complexity assumption implies that the configuration is a linear combination of its translated copies. This condition can be expressed as an annihilation property under the multiplication of a power series representation of the configuration by a non-zero two-variate polynomial, leading to the study of the ideal of all annihilating polynomials. It turns out that the ideal of annihilators is essentially a principal ideal generated by a product of so-called line polynomials, i.e., univariate polynomials of two-variate monomials. This opens up the possibility to obtain results on global structures of the configuration, such as its periodicity. We first proposed this approach in [9,[START_REF] Kari | An algebraic geometric approach to Nivat's conjecture[END_REF] to study Nivat's conjecture. It led to a number of subsequent results [START_REF] Kari | Decidability and periodicity of low complexity tilings[END_REF][START_REF] Kari | Nivat's conjecture and pattern complexity in algebraic subshifts[END_REF][START_REF] Kari | An algebraic geometric approach to multidimensional words[END_REF][START_REF] Szabados | Nivat's conjecture holds for sums of two periodic configurations[END_REF]. In this presentation we review the main results without proofs -the given references can be consulted for more details. We start by briefly recalling the notations and basic concepts.

Configurations and Periodicity

A d-dimensional configuration over a finite alphabet A is an assignment of symbols of A on the infinite grid Z d . For any configuration c ∈ A Z d and any

Research supported by the Academy of Finland grant 296018 cell u ∈ Z d , we denote by c u the symbol that c has in cell u. For any vector t ∈ Z d , the translation τ t by t shifts a configuration c so that τ t (c) u = c u-t for all u ∈ Z d . We say that c is periodic if τ t (c) = c for some non-zero t ∈ Z d . In this case t is a vector of periodicity and c is also termed t-periodic. We mostly consider the two-dimensional setting d = 2. In this case, if there are two linearly independent vectors of periodicity then c is called two-periodic. A two-periodic c ∈ A Z 2 has automatically horizontal and vertical vectors of periodicity (k, 0) and (0, k) for some k > 0, and consequently a vector of periodicity in every rational direction. A two-dimensional periodic configuration that is not two-periodic is called one-periodic.

Pattern Complexity

Let D ⊆ Z d be a finite set of cells, a shape. A D-pattern is an assignment p ∈ A D of symbols in shape D. A (finite) pattern is a D-pattern for some finite D. Let us denote by A * the set of all finite patterns over alphabet A, where the dimension d is assumed to be known from the context. We say that a finite pattern p of shape D appears in configuration c if for some t ∈ Z d we have τ t (c)| D = p. We also say that c contains pattern p. For a fixed D, the set of D-patterns that appear in a configuration c is denoted by L D (c). We denote by L(c) the set of all finite patterns that appear in c, i.e., the union of L D (c) over all finite D ⊆ Z d .

The pattern complexity of a configuration c with respect to a shape D is the number of D-patterns that c contains. A sufficiently low pattern complexity forces global regularities in a configuration. A relevant threshold happens when the pattern complexity is at most |D|, the number of cells in shape D. Hence we say that c has low complexity with respect to shape D if

|L D (c)| ≤ |D|.
We call c a low complexity configuration if it has low complexity with respect to some finite shape D.

Nivat's Conjecture

The original motivation to this work is the famous conjecture presented by Maurice Nivat in his keynote address for the 25th anniversary of the European Association for Theoretical Computer Science at ICALP 1997. It concerns two-dimensional configurations that have low complexity with respect to a rectangular shape.

Conjecture 1 ( [12]

). Let c ∈ A Z 2 be a two-dimensional configuration. If c has low complexity with respect to some rectangle D = {1, . . . , n}×{1, . . . , m} then c is periodic.

The conjecture is still open but several partial and related results have been established. The best general bound was proved in [START_REF] Cyr | Nonexpansive Z 2 -subdynamics and Nivat's Conjecture[END_REF] where it was shown that for any rectangle D the condition |L D (c)| ≤ |D|/2 is enough to guarantee that c is periodic. This fact can also be proved using the algebraic approach [START_REF] Szabados | Nivat's conjecture holds for sums of two periodic configurations[END_REF].

The analogous conjecture in dimensions higher than two fails, as does a similar claim in two dimensions for many other shapes than rectangles [START_REF] Cassaigne | Subword complexity and periodicity in two or more dimensions[END_REF]. We return to Nivat's conjecture and our results on this problem in Section 2. A subset X of A Z 2 is called a subshift if it is closed in the topology and closed under translations. By a compactness argument, every configuration c that is not in X contains a finite pattern p that prevents it from being in X: no configuration that contains p is in X. We can then as well define subshifts using forbidden patterns: given a set P ⊆ A * of finite patterns we define

Basic Concepts of Symbolic Dynamics

X P = {c ∈ A Z d | L(c) ∩ P = ∅},
the set of configurations that do not contain any of the patterns in P . Set X P is a subshift, and every subshift is X P for some P . If X = X P for some finite P then X is a subshift of finite type (SFT).

In this work we are interested in subshifts that have low pattern complexity. For a subshift X ⊆ A Z d (or actually for any set X of configurations) we define its language L(X) ⊆ A * to be the set of all finite patterns that appear in some element of X, that is, the union of sets L(c) over all c ∈ X. For a fixed shape D, we analogously define L D (X) = L(X) ∩ A D , the union of all L D (c) over c ∈ X. We say that X has low complexity with respect to shape D if |L D (X)| ≤ |D|. For example, in Theorem 8 we fix shape D and a small set P ⊆ A D of at most |D| allowed patterns of shape D.

Then X = X A D \P = {c ∈ A Z d | L D (c) ⊆ P } is a low complexity SFT since L D (X) ⊆ P and |P | ≤ |D|.
The orbit of a configuration c is the set

O(c) = {τ t (c) | t ∈ Z 2 }
of all its translates, and the orbit closure O(c) of c is the topological closure of its orbit. The orbit closure is a subshift, and in fact it is the intersection of all subshifts that contain c. In terms of finite patters, c ∈ O(c) if and only if every finite pattern that appears in c appears also in c. Of course, the orbit closure of a low complexity configuration is a low complexity subshift.

A configuration c is called uniformly recurrent if for every c ∈ O(c) we have O(c ) = O(c). This is equivalent to O(c) being a minimal subshift in the sense that it has no proper non-empty subshifts inside it. A classical result by Birkhoff on dynamical systems implies that every non-empty subshift contains a minimal subshift, so there is a uniformly recurrent configuration in every non-empty subshift [START_REF] Birkhoff | Quelques théorèmes sur le mouvement des systèmes dynamiques[END_REF].

Algebraic Concepts

To use commutative algebra we assume that A ⊆ Z, i.e., the symbols in the configurations are integers. We also maintain the assumption that A is finite. We express a d-dimensional configuration c ∈ A Z d as a formal power series over d variables x 1 , . . . x d where the monomials address cells in a natural manner

x u1 1 • • • x u d d ←→ (u 1 , . . . , u d ) ∈ Z d
, and the coefficients of the monomials in the power series are the symbols at the corresponding cells. Using the convenient vector notation x = (x 1 , . . . x d ) we write

x u = x u1 1 • • • x u d d for the monomial that represents cell u = (u 1 , . . . u d ) ∈ Z d .
Note that all our power series and polynomials are Laurent as we allow negative as well as positive powers of variables. Now the configuration c ∈ A Z d can be coded as the formal power series

c(x) = u∈Z d c u x u .
Because A ⊆ Z is finite, the power series c(x) is integral (the coefficients are integers) and finitary (there are only finitely many different coefficients). Henceforth we treat configurations as integral, finitary power series.

Note that the power series are indeed formal: the role of the variables is only to provide the position information on the grid. We may sum up two power series, or multiply a power series with a polynomial, but we never plug in any values in the variables. Multiplying a power series c(x) by a monomial x t simply adds t to the exponents of all monomials, thus producing the power series of the translated configuration τ t (c). Hence the configuration c(x) is t-periodic if and only if x t c(x) = c(x), that is, if and only if (x t -1)c(x) = 0, the zero power series. Thus we can express the periodicity of a configuration in terms of its annihilation under the multiplication with a difference binomial x t -1. Very naturally then we introduce the annihilator ideal

Ann(c) = {f (x) ∈ C[x ±1 ] | f (x)c(x) = 0}
containing all the polynomials that annihilate c. Here we use the notation C[x ±1 ] for the set of Laurent polynomials with complex coefficients. Note that Ann(c) is indeed an ideal of the Laurent polynomial ring C[x ±1 ].

Our first observation relates the low complexity assumption to annihilators. Namely, it is easy to see using elementary linear algebra that any low complexity configuration has at least some non-trivial annihilators: Lemma 2 ( [9]). Let c be a low complexity configuration. Then Ann(c) contains a non-zero polynomial.

One of the main results of [9] states that if a configuration c is annihilated by a non-zero polynomial (e.g., due to low complexity) then it is automatically annihilated by a product of difference binomials.

Theorem 3 ( [9]

). Let c be a configuration annihilated by some non-zero polynomial. Then there exist pairwise linearly independent t 1 , . . . , t m ∈ Z d such that

(x t1 -1) • • • (x tm -1) ∈ Ann(c).
Note that if m = 1 then the configuration is t 1 -periodic. Otherwise, for m ≥ 2, annihilation by (x t1 -1) • • • (x tm -1) can be considered a form of generalized periodicity.

In the two-dimensional setting d = 2 we find it sometimes more convenient to work with the periodizer ideal

Per(c) = {f (x) ∈ C[x ±1 ] | f (x)c(x) is two-periodic }
that contains those two-variate Laurent polynomials whose product with configuration c is two-periodic. Clearly also Per(c) is an ideal of the Laurent polynomial ring C[x ±1 ], and we have Ann(c) ⊆ Per(c). In the two-dimensional case we have a very good understanding of the structure of the ideals Ann(c) and Per(c), see Theorems 9 and 10 in Section 3.

Contributions to Nivat's Conjecture

In [9] we reported an asymptotic result on Nivat's conjecture. The complete proof appeared in [START_REF] Kari | An algebraic geometric approach to Nivat's conjecture[END_REF]. Recall that the Nivat's conjecture claims -taking the contrapositive of the original statement -that every non-periodic configuration has high complexity with respect to every rectangle. Our result states that this indeed holds for all sufficiently large rectangles: Theorem 4 ( [9, 10]). Let c be a two-dimensional configuration that is not periodic. Then L D (c) > |D| holds for all but finitely many rectangles D.

Recall that Theorem 3 gives for a low complexity configuration an annihilator of the form (x t1 -1) • • • (x tm -1). If m = 1 then c is periodic, so it is interesting to consider the cases of m ≥ 2. Szabados proved in [START_REF] Szabados | Nivat's conjecture holds for sums of two periodic configurations[END_REF] that Nivat's conjecture holds in the case m = 2. Note that this case is equivalent to c being the sum of two periodic configurations [9]. Theorem 5 ( [14]). Let c be a two-dimensional configuration that has low complexity with respect to some rectangle. If c is the sum of two periodic configurations then c itself is periodic.

We have also considered other types of configurations. Particularly interesting are uniformly recurrent configurations since they occur in all non-empty subshifts. Recently we proved that they satisfy Nivat's conjecture, even when rectangles are generalized to other discrete convex shapes. We call shape D ⊆ Z 2 convex if D = S ∩ Z 2 for some convex set S ⊆ R 2 . In particular, every rectangle is convex.

Theorem 6 ( [6]

). Two-dimensional uniformly recurrent configuration that has low complexity with respect to a finite discrete convex shape D is periodic.

The presence of uniformly recurrent configurations in subshifts then directly yields the following corollary.

Theorem 7 ( [6]

). Let X be a non-empty two-dimensional subshift that has low complexity with respect to a finite discrete convex shape D. Then X contains a periodic configuration. In particular, the orbit closure of a configuration that has low complexity with respect to D contains a periodic configuration.

Note that the periodic element in the orbit closure of c means that c contains arbitrarily large periodic regions.

The existence of periodic elements provides us with an algorithm to determine if a given low complexity SFT is empty. This is a classical argument by Hao Wang [START_REF] Wang | Proving theorems by pattern recognition -II[END_REF]: There is a semi-algorithm for non-emptyness of arbitrary SFTs, and there is a semi-algorithm for the existence of a periodic configuration in a twodimensional SFT. The latter semi-algorithm is based on the fact that if a twodimensional SFT contains a periodic configuration then it also contains a twoperiodic configuration, and these can be effectively enumerated and tested. Now, since we know that a two-dimensional SFT that has low complexity with respect to a convex shape is either empty or contains a periodic configuration, the two semi-algorithms together yield an algorithm to test emptyness.

Theorem 8 ( [6]

). There is an algorithm that -given a set of at most |D| patterns P ⊆ A D over a two-dimensional convex shape D -determines whether there exists a configuration c ∈ A Z 2 such that L D (c) ⊆ P .

Line Polynomials and the Structure of the Annihilator Ideal

For a polynomial f (x) = f u x u , we call Supp(f ) = {u ∈ Z d | f u = 0} its support. A line polynomial is a polynomial with all its terms aligned on the same line: f is a line polynomial in direction u ∈ Z d if and only if supp(f ) contains at least two elements and supp(f ) ⊆ Zu. (Note that this definition differs slightly from the one in [9,[START_REF] Kari | An algebraic geometric approach to Nivat's conjecture[END_REF] where the line containing the non-zero terms was not required to go through the origin. The definitions are the same up to multiplication by a monomial, i.e. a translation.) Multiplying a configuration by a line polynomial is a one-dimensional process: different discrete lines v + Zu in the direction u of the line polynomial get multiplied independently of each other.

Difference binomials x t -1 are line polynomials so the special annihilator provided by Theorem 3 is a product of line polynomials. Annihilation by a difference binomial means periodicity -and this fact generalizes to any line polynomial: a configuration that is annihilated by a line polynomial in direction u is nu-periodic for some n ∈ Z. This is due to the fact that the line polynomial annihilator specifies a linear recurrence along the discrete lines in direction u.

The annihilator and the periodizer ideals of a configuration have particularly nice forms in the two-dimensional setting. Recall that f = {gf | g ∈ C[x ±1 ]} is the principal ideal generated by Laurent polynomial f . It turns out that a two-dimensional periodizer ideal is a principal ideal generated by a product of line polynomials.

Theorem 9 (adapted from [START_REF] Kari | An algebraic geometric approach to Nivat's conjecture[END_REF]). Let c be a two-dimensional configuration with a non-trivial annihilator. Then

Per(c) = f for a product f = f 1 • • • f m of some line polynomials f 1 , . . . , f m .
By merging line polynomials in the same directions we can choose f i in the theorem above so that they are in pairwise linearly independent directions. In this case m, the number of line polynomial factors, only depends on c. We denote m = Ord(c) and call it the order of c. If Ord(c) = 1 then c is periodic, and Theorem 5 states that the Nivat's conjecture is true among configurations of order two.

Theorem 9 directly implies a simple structure on the annihilator ideal: any annihilation of c factors through the two-periodic configuration

f 1 • • • f m c.
Theorem 10 ( [START_REF] Kari | An algebraic geometric approach to Nivat's conjecture[END_REF]). Let c be a two-dimensional configuration with a nontrivial annihilator. Then Ann(c) = f 1 • • • f m H where f 1 , . . . , f m are line polynomials and H is the annihilator ideal of the two-periodic configuration

f 1 • • • f m c.
As pointed out above, if c is annihilated by a line polynomial then c is periodic. The structure of Per(c) and Ann(c) allows us to generalize this to other annihilators. If a two-dimensional configuration c is annihilated (or even periodized) by a polynomial without any line polynomial factors then it follows from Theorem 9 that Per(c) is generated by polynomial 1, that is, c itself is already two-periodic. Similarly, if Per(c) contains a polynomial whose line polynomial factors are all in a common direction then Per(c) = f is generated by a line polynomial f in this direction, implying that c has a line polynomial annihilator and is therefore periodic. Such situations have come up in the literature under the theme of covering codes on the grid [START_REF] Axenovich | On multiple coverings of the infinite rectangular grid with balls of constant radius[END_REF].

Example 11. Consider the problem of placing identical broadcasting antennas on the grid Z 2 in such a way that each cell that does not contain an antenna receives broadcast from exactly a antennas and every cell containing an antenna receives exactly b broadcasts. Assume that D ⊆ Z 2 is the shape of coverage by an antenna at the origin. Let us represent this broadcast range as the Laurent polynomial f (x) = u∈D x u . Let c be a configuration over A = {0, 1} where we interpret c u = 1 as the presence of an antenna in cell u. Now, c is a solution to the antenna placement problem if and only if f (x)c(x) is the power series (b-a)c(x)+ a1(x) where 1(x) is the constant one power series 1(x) = u∈Z 2 x u . Indeed, (b -a)c(x) + a1(x) has values b and a in cells containing and not containing an antenna, respectively. In other words, c is a valid placement of antennas if and only if multiplying c(x) with polynomial f (x) -(b -a) results in the twoperiodic configuration a1(x). If f (x) -(b -a) has no line polynomial factors then we know that this condition forces c to be two-periodic. For example, if D = {(x, y) | |x| + |y| ≤ 1} so that each antenna only broadcasts to its own cell and the four neighboring cells, then b -a = 1 implies two-periodicity of any solution.

Low Complexity Configurations in Algebraic Subshifts

In [START_REF] Kari | Nivat's conjecture and pattern complexity in algebraic subshifts[END_REF] we considered low complexity configurations in algebraic subshifts where the alphabet A is a finite field F p . As Lemma 2 works as well in this setup, we have that every low complexity configuration c is annihilated by a non-zero polynomial f ∈ F p [x ±1 ]. We then have that c is an element of the algeraic subshift S f = {c ∈ A Z d | f c = 0} of all configurations over A = F p that are annihilated by f . So, to prove Nivat's conjecture it is enough to prove it for elements of algebraic subshifts. Clearly S f is of finite type, defined by forbidden patterns of shape D = -Supp(f ). We remark that the theory of this type of algebraically defined subshifts is well developed, see for example [START_REF] Schmidt | Dynamical systems of algebraic origin[END_REF].

Example 12. Let A = F 2 . The Ledrappier subshift (also known as the 3-dot system) is S f for f = 1 + x 1 + x 2 . Elements of S f are the space-time diagrams of the binary state XOR cellular automaton that adds to the state of each cell modulo 2 the state of its left neighbor.

While Lemma 2 works just fine over finite fields F p , Theorem 3 does not: it is not true that every element of every algebraic subshift would be annihilated by a product of difference polynomials. However, configurations over F p can be also considered as configurations over Z, without making calculations modulo p. If a configuration c over F p has low complexity then it also has low complexity as a configuration over Z, and thus in Z it has a special annihilator (x t1 -1) • • • (x tm -1) provided by Theorem 3. Now, considering all calculations modulo p we see that this special annihilator is also an annihilator over F p . We conclude that even over F p , every low complexity configuration has an annihilator that is a product of difference binomials.

Example 13. Let c be a low complexity configuration in the Ledrappier subshift of Example 12. It is then annihilated by f = 1 + x 1 + x 2 and by some g = (x t1 -1) • • • (x tm -1) that is a product of difference binomials. Because f does not have line polynomial factors while all irreducible factors of g are line polynomials, we have that f and g do not have any common factors. Replacing x 2 by f -1-x 1 in g, we can entirely eliminate variable x 2 from g, obtaining a new annihilator g = g -f f of c having no occurrence of variable x 2 . This annihilator g (x 1 ) is non-zero because f and g do not have common factors, which implies that c is horizontally periodic. We can repeat the same reasoning in the vertical direction, obtaining that c is two periodic. The reasoning in the example above can be generalized to other algebraic subshifts.

Theorem 14 ( [7]). Let c be a low complexity configuration of an algebraic subshift S f .

-If f has no line polynomial factors then c is two-periodic.

-If all line polynomial factors of f are in a common direction then c is periodic.

Note that in the theorem there is no assumption about the low complexity shape D, so the applicability of the theorem is not restricted to rectangles or convex shapes.

Conclusions and Perspectives

There remains many open questions for future study. Obviously, the full version of Nivat's conjecture is still unsolved. Our Theorem 6 suggests that perhaps periodicity is forced by the low complexity condition not only on rectangles but on other convex shapes as well, as conjectured by Julien Cassaigne in [START_REF] Cassaigne | Subword complexity and periodicity in two or more dimensions[END_REF]. In his examples of non-periodic low complexity configurations, the low complexity shape D is always non-convex. Moreover, all two-dimensional low complexity configurations that we know consist of periodic sublattices [START_REF] Cassaigne | Subword complexity and periodicity in two or more dimensions[END_REF][START_REF] Kari | Nivat's conjecture and pattern complexity in algebraic subshifts[END_REF]. For example, even lattice cells may form a configuration that is horizontally but not vertically periodic while the odd cells may have a vertical but no horizontal period. The interleaved non-periodic configuration may have low complexity with respect to a scatted shape D that only sees cells of equal parity. We wonder if there exist any low complexity configurations without a periodic sublattice structure. Theorem 5 proves Nivat's conjecture for configurations of order two. However, Ord(c) = 2 case is special in the sense that c is then a sum of periodic configurations, that is, finitary power series. In general, any configuration with a non-trivial annihilator is a sum of periodic power series [9], but already when Ord(c) = 3 these power series may be necessarily non-finitary [START_REF] Kari | An algebraic geometric approach to multidimensional words[END_REF]. It seems then that proving Nivat's conjecture for configurations of order three would reflect the general case better than the order two case. We also remark that proving Nivat's conjecture (for all convex shapes) would render the results of Section 2 obsolete.

There are also very interesting questions concerning general low complexity SFTs. By Theorem 7, a two-dimensional SFT that is low complexity with respect to a convex shape contains periodic configurations. Might this be true for nonconvex shapes as well ? If so, analogously to Theorem 8, this would yield and algorithm to decide emptyness of general low complexity SFTs. What about higher dimensions ? We do not know of any aperiodic low complexity SFT in any dimension d of the space. The following example recalls a family of particularly interesting low complexity SFTs. The periodic cluster tiling problem asks whether every tile that has a co-tiler also has a periodic co-tiler [START_REF] Lagarias | Tiling the line with translates of one tile[END_REF][START_REF] Szegedy | Algorithms to tile the infinite grid with finite clusters[END_REF]. This is a special case of the more general question on arbitrary low complexity SFTs discussed above. The periodic cluster tiling problem was recently answered affirmatively in the two-dimensional case [START_REF] Bhattacharya | Periodicity and decidability of tilings of Z 2[END_REF]. In [9] we gave a simple algebraic proof in any number of dimensions for the case -originally handled in [START_REF] Szegedy | Algorithms to tile the infinite grid with finite clusters[END_REF] -where |D| is a prime number.

Finally, the structure of the annihilator ideal is not known in dimension higher than two. We wonder how Theorem 10 might generalize to the three-dimensional setting.

  Let p ∈ A D be a finite pattern of shape D. The set [p] = {c ∈ A Z d | c| D = p} of configurations that have p in domain D is called the cylinder determined by p. The collection of cylinders [p] is a base of a compact topology on A Z d , the prodiscrete topology. The topology is equivalently defined by a metric on A Z d where two configurations are close to each other if they agree with each other on a large region around cell 0 -the larger the region the closer they are. Cylinders are clopen in the topology: they are both open and closed.

Example 15 .

 15 A d-dimensional cluster tile is a finite subset D ⊆ Z d , and a co-tiler is a subset C ⊆ Z d such that C ⊕ D = Z d . Visually, C gives positions where copies of tiles D can be placed so that every cell gets covered by one tile. Looking at the situation from an arbitrary covered cell u, we see that C is a co-tiler of D if and only if the set u -D contains precisely one element of C, for every u ∈ Z d . Representing a co-tiler C as the indicator configuration c u = 1 if u ∈ C and c u = 0 if u ∈ C, we have that the set of valid co-tilers for tile D is a low complexity SFT: The only allowed patterns of shape -D are those that contain single 1, and there are |D| such patterns.