César Ducruet

Hidekazu Itoh

Olivier Joly

Material flows and local economic structure: port-region linkages

Keywords: freight flows, port traffic, regional development, typology, value chain

The main goal of this paper is to identify mutual influences between the specialization of traffics passing through seaports and the socio-economic characteristics of their surrounding regions. While the contemporary era is marked by the fading spatial fix of value chains as notably seen in the dereliction of port's local linkages, a systematic and comparative empirical analysis remains lacking.

One main reason is the absence of internationally harmonized data on the precise spatial distribution of port-related hinterland flows as well as inadequacies between the volume and the value of freight. This research proposes to overcome such difficulties based on a common set of 21 traffic and socioeconomic indicators covering 189 port regions in Europe, Japan, and the United States. Main results underline invariants as well as local specificities in the functional and spatial affinity between certain traffics and certain types of regions. While large urban and financial centres tend to polarize most valued, diversified, and weighty traffics, rural regions generally concentrate agricultural goods and minerals, and industrial regions concentrate combustibles and metals. Beyond the simple reflection of local demand, such results confirm the path-dependency of the association between material flows and regional economic development. A typology of port regions is proposed in order to map the distribution of port regions and to zoom on specific local conditions.

Material flows and local economic structure: port-region linkages in Europe, Japan, and the United States

Introduction

Contemporary transport systems are marked by a dematerialization of the economy and rising average transport distances thereby making it increasingly difficult for decision-makers and scholars to map and explain the distribution of firms and flows in relation to their spatial environments [START_REF] Leslie | Spatializing commodity chains[END_REF][START_REF] Hesse | The transport geography of logistics and freight distribution[END_REF]. Continuous progress in the physical and organisational connectivity of transport systems as well as reduced trade barriers and logistics costs fostered the spatial volatility of flows, resulting in both concentration and diffusion of markets and flows across regions and nations [START_REF] Fujita | The Spatial Economy: Cities, Regions and International Trade[END_REF][START_REF] Hesse | Cities, material flows and the geography of spatial interaction: urban places in the system of chains[END_REF]. As noted by [START_REF] Janelle | Globalization and research issues in transportation[END_REF], the absence of disaggregated data on detailed flows has often been a major obstacle to the analysis of their spatial determinants.

Conversely, most research on transportation networks focuses dominantly on freight movements, capacity and connectivity problems in abstract spaces (e.g. graph theory, complex networks, routing and modelling), and carriers' strategies, with minor attention paid to the (changing) socio-economic characteristics of localities [START_REF] Ducruet | Structure and dynamics of transportation networks: models, methods, and applications[END_REF]. Such state of affairs also relates with the persistent divide between qualitative and quantitative approaches within transport geography as well as the difficulty identify underlying causal structures [START_REF] Goetz | Bridging the qualitative-quantitative divide in transport geography?[END_REF].

Recent efforts have, however, expanded the understanding of the spatial fix of flows as well as the role of local economies in shaping such flows. It was found, for instance, significant correlation between the volume of air flows and the demographic and economic attributes of airport cities in various contexts [START_REF] Neal | The causal relationship between employment and business networks in U.S. cities[END_REF][START_REF] Dobruszkes | An analysis of the determinants of air traffic volume for European metropolitan areas[END_REF][START_REF] Wang | Exploring the network structure and nodal centrality of China's air transport network: A complex network approach[END_REF] as well as strong interdependences between the pattern of communication flows and the wellbeing of localities [START_REF] Eagle | Network diversity and economic development[END_REF]. Similar empirical research on maritime flows remains far less developed due to the drastic lack of data on land-based, hinterland freight flows that would enable the delineation of regions containing most port users [START_REF] Darnton | We can have hinterland data[END_REF][START_REF] Mccalla | Dealing with globalisation at the regional and local levels: The case of contemporary containerization[END_REF][START_REF] Guerrero | Les aires d'influence des ports de la France entre réseau et gravitation[END_REF]. Assembling and analyzing port traffic and socio-economic data on port regions on the level of three large economic areas (namely Europe, Japan, and the United States) is proposed in this paper as a means to complement such statistical lacks and methodological difficulties. Technological, managerial changes in shipping and ports as well as the reorganization of hinterlands may not have fully eroded the spatial fix of freight flows, notably in relation with the adjacent territory or port region. Revealing such linkages might prove useful for the explanation of traffic distribution across space. The extent to which the structure of freight flows reflects -at least partly -the nature of adjacent economies also raises important methodological issues of data and geographic relevance, which will be explored further in the following sections.

The remainder of this paper is as follows. Section 2 offers a discussion on the nature of port traffic, with regard to specific commodities, locations, and the problem of transit flows when trying to assign such traffic to particular places. Section 3 introduces the data and methodology used to compare the mutual specialization of port traffic and local economies in Europe, Japan, and North America. Section 4 describes the main trends obtained from a Principal Components Analysis (PCA) and hierarchical classification of port regions. Finally, Section 5 discusses the implications of the results for port policy and regional planning as well as prospects for further research in the field.

Background and issues in port-region linkages

The port region remains a rather fuzzy concept broadly defined as the "immediate hinterland" of the port where most of its clients and port-related activities are located [START_REF] Vleugels | The economic impact of ports on the regions they serve and the role of industrial development[END_REF][START_REF] Ducruet | Port regions and globalization[END_REF]. Although ports are traditionally seen as strategic gateways conferring distinct characters to their territories compared with those of central places [START_REF] Bird | Gateways: slow recognition but irresistible rise[END_REF], more recent evidences depict a dereliction of ports' local linkages [START_REF] Hoare | British ports and their export hinterlands: A rapidly changing geography[END_REF][START_REF] Todd | The interplay of trade, regional and technical factors in the evolution of a port system: The case of Taiwan[END_REF][START_REF] Campbell | Increasing trade, declining port cities: Port containerization and the regional diffusion of economic benefits[END_REF][START_REF] Vallega | Cityports, coastal zones and sustainable development[END_REF][START_REF] Musso | Ports and employment in port cities[END_REF]. Many large ports, however, have maintained their activities through rapid and profound transformations [START_REF] Lee | Spatial glocalization in Asia-Pacific hub port cities: A comparison of Hong Kong and Singapore[END_REF]Wang and Cheng, 2010;[START_REF] Hall | Why are maritime ports (still) urban, and why should policy makers care?[END_REF]. While ports have been largely left aside by regional development literature [START_REF] Hall | The Institution of Infrastructure and the Development of Port-regions[END_REF], the local economy has been ignored in studies of port selection factors [START_REF] Ng | Port competition: The case of North Europe[END_REF] and of the added value of port traffics [START_REF] Charlier | Sur le concept de tonnages pondérés en économie portuaire. L'exemple du Northern Range[END_REF][START_REF] Haezendonck | Essays on Strategy Analysis for Seaports[END_REF]. Discussions on port-related local economic growth provide either general views and models [START_REF] Stern | Developmental effects of geopolitically located ports[END_REF][START_REF] Fujita | The role of ports in the making of major cities: Self-agglomeration and hub-effect[END_REF][START_REF] Haddad | Port efficiency and regional development, Unpublished paper, Associação Nacional dos Centros de Pós-Graduação em Economia[END_REF] or in-depth case studies lacking comparability such as those about port impacts (Hall, 2004a). Most of the time, research is unidirectional by looking at how port and maritime activities influence and impact local economic development while it ignores how the latter influences and impacts the first.

Although it has always been difficult to measure the benefits of port activities to local economies [START_REF] Bird | Seaports and Seaport Terminals[END_REF] especially in a comparative perspective, some recent studies have provided a number of empirical results supporting the idea of lowering but maintained portregion linkages. Both quantitative [START_REF] De Langen | The economic performance of seaport regions[END_REF] and qualitative [START_REF] Mccalla | Intermodal freight terminals: locality and industrial linkages[END_REF] approaches have revealed a lack of linkages between port activities and their adjacent economies in the United States and Canada. Port regions also appeared poorer than other regions in Europe [START_REF] Lever | Regional economic growth and port activities in European cities[END_REF] and the United States [START_REF] Grobar | The economic status of areas surrounding major U.S. container ports: Evidence and policy issues[END_REF][START_REF] Hall | Container ports, local benefits and transportation worker earnings[END_REF] in terms of regional GDP per capita and average wage levels. Another set of studies pointed, however, at noticeable interdependencies between local economies and traffic dynamics. The size and diversity of urban economies adjacent to ports influences to some degree the size and diversity of port traffics in the United States [START_REF] Carter | A comparative analysis of United States ports and their traffic characteristics[END_REF] and in Europe [START_REF] Ducruet | Commodity variety and seaport performance[END_REF], while smaller ports are often more specialized and bound to local industries [START_REF] Kuby | Technological change and the concentration of the U.S. general cargo port system: 1970-88[END_REF].

One very important aspect of port-region linkages is the influence of the local setting or context. For instance, the correlation between total port throughput and the demographic weight of port cities has dramatically lowered on a global level since the 1990s but it has maintained or even increased in specific regions such as Oceania and North America [START_REF] Ducruet | Frontline soldiers of globalisation: port-city evolution and regional competition[END_REF], due to the diversity of urban-port trajectories, port systems configurations, and hinterland spatial patterns [START_REF] Lee | A tale of Asia's world ports: the spatial evolution in global hub port cities[END_REF][START_REF] Rodrigue | Comparative North American and European gateway logistics: the regionalism of freight distribution[END_REF]. As seen in Figure 1, different geographical areas exhibit contrasted hinterland spatial patterns, notably due to the uneven balance between coastal and inland locations in terms of economic concentrations and transport network connectivity. Europe is more characterized by an inland concentration of core economic regions as opposed to Asia and North America, although the latter has also developed continental connections through intermodal transport. One direct implication of such configurations is the varied importance of transit flows at seaports and hence, a different meaning of port-region linkages depending on the local context. In China, gross regional product, amount of Foreign Direct Investment, and industrial productivity had a positive influence on port traffic growth during the 1995-2007 period [START_REF] Cheung | Port city factors and port production: analysis of Chinese ports[END_REF]. Across OECD countries and during the same period, regional specialization in the industrial and tertiary sector had a negative and positive influence respectively on the volume and growth of container port throughputs [START_REF] Ducruet | Port regions and globalization[END_REF]. The weak linear correlation between port traffic volume and the number of firms in port-related sectors has been confirmed globally [START_REF] Jacobs | The location and global network structure of maritime advanced producer services[END_REF] but without contradicting the fact that certain specialized gateways keep concentrating both tertiary activities and traffics, such as Rotterdam and Houston [START_REF] Jacobs | Integrating world cities into production networks: the case of port cities[END_REF].

While most existing studies neglect the diversity of port traffics, another central argument of this research is that different cargo types will have different affinities with the outlying region where port traffic takes place [START_REF] Haefner | Forecast of key commodity flows at a regional port[END_REF][START_REF] Marti | Chilean ports: commodity specialization and potential for containerization[END_REF], as seen in the example of port-industry complexes processing imported raw materials for local transformation, such as petrochemicals [START_REF] Rodrigue | The Geography of Transport Systems[END_REF][START_REF] Dunford | Regional development: port-industrial complexes[END_REF], and in the case of automobile imports (Hall, 2004b). Indeed, there are wide differences among commodities passing through seaports in terms of travelled distance and spatial friction as demonstrated by [START_REF] Debrie | Re)spatialiser la question portuaire : pour une lecture géographique des arrière-pays européens[END_REF] on the French case. One major difficulty is that one same port may handle a combined set of commodities serving multiple industries inside and outside the port region. However, such functional and regional differences that are known in practice were not sufficiently tested empirically based on comparable data and rigorous statistical methods.

[Insert Figure 1 about here]

Data and methodology

The contours of port regions

One first step was to select economically and spatially relevant local units that would be comparable across Europe, Japan and the United States. A trade-off between their number and size resulted in a selection of 115 NUTS-2 regions (Europe, 16 countries), 39 prefectures (Japan), and 35 States (United States) recording port traffic in the year 2008 and for which comparable socio-economic data was available. We are aware of the limits of such arbitrary definitions, which do not always match the true extent of port hinterlands and/or port regions.

The work of [START_REF] Patton | General cargo hinterlands of New York, Philadelphia, Baltimore, and New Orleans[END_REF] on general cargo hinterlands in the United States clearly recalled the difficulty delineating such regions and the fact that large ports handle large volumes destined to / originating from distant areas, thus with no relationship with local industries, and depending on the directionality (i.e. imports vs. exports) as well as intermodal arrangements (i.e. rail). For instance, it was estimated that 70% of Marseilles' port traffic in 1900 was destined to local industries [START_REF] Garnier | L'aire métropolitaine marseillaise et les territoires de l'industrie[END_REF], while more recently, 75% of New York's port traffic was generated and consumed within a 300 mile radius from the port [START_REF] Rodrigue | The Port Authority of New York and New Jersey: Global changes, regional gains and local challenges in port development[END_REF]. The urban areas of Bordeaux (France) and Busan (South Korea) accounted for only 15% and 10% of respective port traffics in recent years (source: port authorities).

Customs data notably allows calculating the share of the adjacent region in total port traffic (Table 1): in 2005, French coastal regions (départements) surrounding ports were responsible for 63% and 18% of French total traffic volume and value respectively [START_REF] Ducruet | Activité portuaire et villes[END_REF]. Such imbalance between volume and value directly translates the polarization of most valuable flows by the Paris capital region and other large inland cities. Larger ports tend to handle higher transit traffics than smaller ports due to the wider spatial extent of their hinterlands, especially for Le Havre, Paris' main gateway. Traffic is thus inflated by transit flows either landward (i.e. road, rail, river, pipeline, air-sea) or seaward (i.e. coastal and short-sea shipping, transhipment, and feedering). The fact that about 40% of French exports pass through Antwerp and other Benelux ports is a good example of such detours [START_REF] Gouvernal | Short sea and deep sea shipping markets in France[END_REF]. For Le Havre, about one-third of its container traffics relate with the Greater Paris region (source: port authority). The share of transit flows varies from one port to another depending on their specialisation in hinterland and/or hub functions. Hinterland ports may also be maritime hubs, such as Rotterdam (30% transhipment), while others stand as "pure transhipment hubs" due to the absence of a local cargo base, such as Gioia Tauro in Calabria.

Yet, transit flows are not entirely disconnected from the local economy since they create the need for additional activities and infrastructures (e.g. warehousing, packaging), but not every large port has been able to create such value-added. Even a large coastal metropolis may prefer distant port terminals than its own due to problems of congestion and negative environmental impacts locally.

[Insert Table 1 about here] The choice of administrative regions was motivated by the availability of socio-economic data and by the fact that those regions remain large enough to contain a majority of port-related activities composing the so-called port cluster [START_REF] De Langen | Analysing the performance of seaport clusters[END_REF]. While in some cases the regional unit is too small (e.g. the Lander of Hamburg) or too large (e.g. California including Los Angeles, Oakland, and other ports) in comparison with hinterlands, it still has relevance in terms of the location of activities directly related with the port. Large ports located within such urban areas will thus be amputated in terms of hinterland coverage. This is particularly true for containers due to the inland shift of many logistics and distribution activities during the current "port regionalization phase" [START_REF] Notteboom | Port regionalization: Toward a new phase in port development[END_REF]. Among European port cities for instance, it is often the case that a large proportion of transport activities locate in suburban areas [START_REF] Ducruet | Measuring intermodalism at European port cities: an employment-based approach[END_REF]. Nevertheless, administrative regions remain highly relevant to test the influence of large cities on traffic flows, because port-region linkages are not only about physical transfers but also refer to immaterial interdependencies, such as within the tertiary sector, which locate in or close to the Central Business District (CBD) near the port.

The choice of port traffics

The nature and level of economic specialization of such regions was measured on the level of six employment sectors based on various data sources (see Table 2) 2 . In addition to these core variables were added regional GDP, unemployment, population size and population density as proxies for market size and economic wealth. Each regional indicator was calculated as a location quotient based on the national average (e.g. percentage of primary sector employment in total employment of region i divided by percentage of primary sector employment in total employment of the country), except for demographic size and population density (i.e. score of region i divided by mean score of all regions). Mixing regional indicators and port traffic indicators, of course, has the "risk of attributing to port-related differences what are in fact differences in regional economic structure" [START_REF] Hall | The Institution of Infrastructure and the Development of Port-regions[END_REF].

Traffic data of individual ports located within the same administrative region was summed by main category in order to have the same number than for employment variables. Original sources were in fact dissimilar by their number of detailed traffic categories and their classification methods 3 . From the 18 categories provided by Eurostat, containers were counted as manufactured goods although their detailed content is unknown and may include other commodities such as neo-bulks, while some other traffic categories are not fully explained: other dry bulk, other liquid bulk, and other general cargo. In comparison, the 81 and 146 commodities for Japan and the United States respectively were more easily classified into six common categories. While each traffic category corresponds to specific products, the precise link with the aforementioned economic sectors may not be obvious, due to the impossibility distinguishing imports from exports for each commodity. For instance, manufactured goods that are generally containerized have links with multiple sectors depending on the context, such as manufacturing (e.g. export), retail (consumption), and transport/logistics (e.g. warehousing, distribution) ( [START_REF] Van Der Lugt | Ports as locations for logistics activities[END_REF]. The same type of raw materials can be handled within very distinct local economies depending on if it is exported (e.g. cereals exported from an agricultural region) or imported (e.g. cereals imported from a manufacturing region). In addition, some ports have widened their commodity mix through successive (and often path-dependent) diversification phases. Many modern container ports are or have been heavy industrial complexes, as seen in South Europe for instance with the close overlap between main container hubs and former petrochemical and steelwork sites such as Sines, Huelva, Cagliari, Gioia Tauro, and Taranto. Each of the six commodity categories was transformed into a location quotient as follows: percentage of combustibles traffic in total traffic of region i divided by percentage of combustibles traffic in total traffic of the country/continent.

A few other traffic variables were calculated to complement the analysis of specialization, such as traffic size, international traffic (i.e. extra-EU27 for Europe), inbound traffic, level of commodity diversity, and level of spatial friction. International and inbound traffic provide information on the extent of port activities and their directionality, while traffic size expresses the overall performance of the port region in accumulating physical flows. International and inbound traffics were changed to indices based on the same method than for commodity categories (i.e. percentage of international traffic in total port traffic of region i divided by percentage of international traffic in total port traffic of the country/continent). Traffic size is simply a ratio between the total port traffic of each region and the average traffic of all regions. The level of commodity variety was proposed by [START_REF] Ducruet | Commodity variety and seaport performance[END_REF] in order to reflect the capacity of a given port (or region) to handle multiple flows. It is calculated for each port region as the inverse of the sum of absolute differences in commodity shares at country/continent level. Higher values point at more diversified ports and lower values underline strongly specialized port regions. The level of spatial friction was derived from the work of [START_REF] Debrie | Re)spatialiser la question portuaire : pour une lecture géographique des arrière-pays européens[END_REF] on French port hinterlands. Their analysis applied a spatial interaction model on customs data on the amount of transported freight by commodity types to/from seaports within the country in order to estimate the role of distance on the volume of port-related flows. They particularly demonstrated that in general, manufactured goods travel longer distances than liquid and dry bulks. Each of the six traffic categories was weighted according to their results by commodity-specific parameters4 . This indicator particularly highlights which commodities are more likely to remain produced, consumed, and/or processed within the port region (captive hinterland) as opposed to more mobile commodities reaching farther markets (contestable hinterlands). The traffic of each port region was then weighted by calculating the share of distance-constrained traffic in total port traffic (spatial friction index).

[Insert Table 2 about here] 4. Traffic specialisation and regional specialisation

Main trends

The comparison of correlation coefficients among all variables at each area allows a first understanding of the main trends affecting port-region linkages (Figure 2). Pearson and Spearman correlations are compared given the different statistical distribution of variables.

The main trend for Japan is a coincidence between traffic volume, manufactured goods, and a profile of large, densely populated, richer, and tertiary regions. It underlines the closeness between urban hierarchy and port hierarchy for the most valued goods. Other traffics have limited correlation with regional indicators, except for the slightly significant ones between the agricultural sector and minerals traffic. Most other significant correlations occur either among traffic variables or socio-economic variables, such as metals and traffic volume, combustibles and international traffic. Spearman correlations provide a similar picture, with the exception of metals traffic with population density, and international traffic with the industrial sector and regional GDP. For the United States and Europe, correlations remain rather moderate compared with Japan, thereby suggesting a lower statistical significance of port-region linkages in those areas. The highest positive correlation for the United States occurs between traffic volume and demographic size, followed by manufactured goods traffic and the financial sector, metals traffic and the retail sector, agricultural goods traffics and the agricultural sector, international traffic and the construction and financial sectors. Moreover, Spearman correlations show some strong relationships between public services and combustibles, chemicals and diversity, and agricultural and metal products. Despite some differences, such trends are comparable with Japan due to the proximity between large traffics of higher valued goods, the tertiary (finance and real estate) sector, and population. Japan and the United States have indeed in common to concentrate container traffics at major urban centres that also concentrate higher-order economic functions. In the European case, Pearson correlations are rather insignificant and cannot account for tangible port-region linkages as in the previous cases. This is partly solved by looking at Spearman correlations based on ranks rather than initial values. Similar trends thus emerge, such as the closeness between manufactured goods traffic, the financial sector and population density, while demographic size is positively and significantly correlated with traffic volume, traffic diversity, and international traffic, but also chemicals and metals. It thus confirms that among the three areas considered, the nature of port-region linkages remains similar as most voluminous and valued goods concentrate at tertiary and populated regions. Although the statistical significance differs greatly, the nature of port-region linkages is comparable thus supporting the idea of invariants in the geography and locational factors of port traffics.

[Insert Figure 2 about here] The application of a Principal Components Analysis (PCA) on each of the three datasets provides some answers to the initial hypotheses (Table 3). Results for Japan exhibit higher statistical significance, followed by the United States and Europe, thereby reflecting upon their respective spatial configurations. Due to the presence of many different countries and to the continental character of hinterlands in Europe, its cumulated variance reaches only 51% at the fourth principal component, compared with 59% for the United States and 71% for Japan.

The lower score of the United States compared with Japan is also explained by the fact that some ports serve more distant hinterlands than their adjacent regions, notably through extensive intermodal services such as by railways. It may thus be interpreted that port-region linkages have weaker significance in Europe compared with other regions. Nevertheless and despite such differences, port-region linkages share similar trends across the three areas as discussed in the following sections and based on Figure 3. A hierarchical clustering was applied to the four main principal components in order to establish a typology of port regions in each area, where the best represented port regions in each cluster is highlighted.

[Insert Table 3 about here] [Insert Figure 3 about here]

Europe

European port regions are characterized by an affinity between minerals, metals, agricultural goods and the agricultural, construction, and industry sectors (PC1). This constitutes a rather logical association since such sectors mostly need raw materials and intermediate inputs for performing their activities. This group of variables is opposed to a profile of urban centre where tertiary activities, especially the financial sector, retail, as well as population, density, and regional GDP are closer to manufactured goods traffic. The clustering (Figure 4) confirms that such regions are large coastal capital cities (Oslo, Stockholm, Copenhagen, Hamburg, London, and Lisbon), mostly located in North Europe (first cluster). Except for Helsinki, Gdansk, Piraeus, and Bilbao, regions belonging to the second cluster tend to locate close to Europe's core economic areas, i.e. the European megalopolis from London to Milano. There is thus a relatively strong influence of continental location on the nature and level of port-region linkages in Europe. The fact that combustibles, traffic size, international and import traffics also participate to this trend indicate that those larger and richer regions are mostly consumer markets best connected to global flows. This trend is very important as it marks a very logical functional contrast between traditional regions and advanced regions. The cluster of traditional regions is, indeed, generally located at the periphery of Europe (e.g. Greece, Atlantic, Scandinavia) despite a few exceptions such as East Flanders, North Brabant, and Luneburg.

The second trend (PC2) is mostly an opposition between large, international traffic of combustibles and regions specialized in minerals and metals, with a tendency to be also richer and more densely populated on average. This can be interpreted as an opposition between a profile of Maritime Industrial Development Area (MIDA) specialized in the industrial sector while handling petro-chemical traffics [START_REF] Vigarié | Maritime Industrial Development Areas: Structural evolution and implications for regional development[END_REF] and a profile of urban region specialized in solid bulks and general cargoes. Other trends show an opposition between a profile of steelworks region (PC3) based on metals traffic and the industrial sector and a profile of deprived region where unemployment is higher than average. On the map, clusters show a rather strong spatial pattern. Deprived regions (third cluster) are mostly in Southern Europe (southern Italy, Andalucia) with the exception of Mecklenburg-Vorpommern (Germany); they have in common to have been the focus of growth pole strategies in the 1970s based on heavy industries as well as container hub strategies in the 1990s (e.g. Algeciras, Cagliari, Gioia Tauro, Taranto), but such projects have not succeeded in creating more employment and regional balance, in a context of oil crisis and due to the limited local economic impacts of container transhipment. This cluster is built in opposition to GDP and the industrial sector, which suggests lower economic wealth and weaker industrial base.

Another group of regions (fifth cluster) is better defined by specialized traffics serving local industries specialized in metals and manufactured goods, such as Antwerp, Zeebrugge, Bremen, and Valencia, with more international openness and stronger socio-economic backgrounds. Lastly, the most geographically spread category (sixth cluster) is composed of port regions specialized in combustibles with a high importance of the immediate hinterland (friction). They have in common to be remotely located from Europe's core economic regions and/or to face industrial reconversion, such as Dunkirk in the Nord-Pas-de-Calais region as well as most United Kingdom regions. Their specialization is defined in the cluster in opposition to the first cluster (GDP, finance, manufactured goods) thereby reinforcing the idea of relatively deprived regions where heavy industries and lower valued goods dominate.

[Insert Figure 4 about here]

Japan

The main trend (PC1) opposes large cities to traditional industrial regions. Large traffics and traffics of manufactured goods are well represented against combustibles and friction. As seen in Figure 5 (first and second clusters), it corresponds to a handful of large urban regions (i.e.

the Japanese megalopolis from Tokyo to Fukuoka) producing and consuming many valueadded good. Tokyo stands as the only multifunctional centre but it has in common with the second class important features such as being a large tertiary centre and a large port simultaneously. This recalls the pattern of hinterlands in Asia (Figure 1) where there is a good adequacy between economic concentrations and traffic concentrations for the aforementioned reasons. Such large urban regions handle about half of domestic freight cargo through interregional flows. Although they are less represented on the first component (PC1), international traffic and traffic diversity are positively correlated with such trends, as well as retail, thus supporting further the profile of dynamic and global urban regions. On the other hand, traditional regions are characterized by a coincidence between the agricultural, industry, and construction sectors and traffics such as combustibles, agricultural goods, and minerals.

This opposition recalls the one found in Europe and provides similar spatial patterns on the map, with advanced urban regions being core economic regions and traditional regions being more peripheral (fourth cluster).

The second component opposes a profile of industrial region handling combustibles and international traffic with a profile of agricultural and deprived region (unemployment) mostly handling minerals. Thus, the first trend suggests the existence of strong local industry linkages mostly through importing raw materials for processing plants, again recalling the trend on Europe based on the concept of MIDA. Such regions have more favourable socio-economic environments than in the opposed trend as seen with the positive sign for regional GDP; they serve as strong industrial areas for domestic supply chains, such as Mie, Toyama, Ishikawa, Aichi, Fukushima, Shizuoka, Fukui, and Ibaraki. The opposed trend comprises two peripheral regions (Hokkaido and Okinawa) and are not characterized by specific economic functions except for public services. Other trends point at another opposition between deprived regions handling large volumes of combustibles and more advanced regions handling mostly raw materials (minerals, metals) while being specialized in the industrial sector. Those advanced regions benefit from their inclusion in the megalopolis, they are specialized port regions complementing the functions of nearby tertiary centres through a spatial division of activities (i.e. backward linkages) along the main urban corridor of the country.

[Insert Figure 5 about here]

United States

The case of the United States provides a very clear opposing trend (PC1) between urban tertiary centres handling most valued goods and traditional regions handling mostly raw materials, as seen in the two former cases. One common trend with Europe is that, unlike for Japan, combustibles traffic is grouped with manufactured goods. In fact on the map (Figure 6), it shows the prominence of East coast port regions together with Texas and California, which concentrate higher-order activities, population, and largest traffics. Massachusetts, Rhode Island, and Connecticut belong to a separate cluster (second) where combustibles are better represented than in the first class hosting major metropolises. They are functionally and spatially opposed to port regions located for their majority in the interior and characterized by agricultural traffics (fourth cluster) and to Midwest regions specialized in the industrial sector and minerals traffics. Such traditional port regions have also in common certain social weaknesses due to difficult reconversion (e.g. rustbelt) and declining population. This echoes a relatively well-known regional geography of the United States where port traffics simply reflect the dominance of certain local industries. Other port regions are those specialized in specific industries and traffics and are often geographically confined to certain areas, such as agricultural and chemicals in the Northwest and at the mouth of the Mississippi (e.g. Washington, Louisiana), manufactured goods and metals in Georgia and South Carolina.

Those two latter regions have a very diversified industrial background.

[Insert Figure 6 about here]

Conclusion

This paper has provided a novel analysis of the interplay between the local socio-economic conditions of areas surrounding ports and the nature and structure of port traffics, based on a dataset of 21 indicators covering 189 so-called port regions in Europe, Japan, and the United States. Main results can be summarized as follows. First, the statistical relationships between socio-economic variables and port traffic variables are meaningful because they underline rather logical sector-specific links whereby certain traffics have noticeable affinities with specific regional characteristics. Thus, despite the probable mismatch between administrative regions and the true extent of port hinterlands, ports traffics are very sensible to the nature of the local economy in which they are handled. Second, the three studied geographical areas, despite wide differences in historical legacies, spatial and trade patterns, share noticeable similarities in the nature of port-region linkages. Economically and demographically larger, richer regions where the tertiary sector dominates often concentrate larger, more diversified traffic volumes as well as higher valued goods such as containers and consumer products, as opposed with agricultural and industrial regions, which are more specialized in bulk traffics in relation with their dominant activity. There are, of course, local specificities across the three regions as such trends are more linear in Japan due to the better overlap between port hierarchy and urban hierarchy and the simple fact that Japan is an island country thus limiting transit flows. The industrial sector also does not have the same influence on port traffic specialization depending on the context but overall, there is a striking invariance in the results beyond local specificities. The typology of port regions obtained through hierarchical clustering also confirmed a very logical distribution of different types of port-regions linkages, often showing a contrast between the core (e.g. megalopolises) and the periphery within the country or continent. The outcomes of the research allow to confirm that port activities are not disconnected from their local economies, so that further research is needed in order to push further the analysis of port-region linkages, perhaps by zooming in a more disaggregated way on traffics and employment sectors, thus allowing to better discuss the implications of strong port-region linkages on current and future local economic development opportunities and strategies.

Possible improvements may be obtained by more in-depth reflection about the correspondence between administrative units where socio-economic data is available and hinterland patterns, traffic catchment / generation areas around ports. Attributing different administrative levels to ports according to the volume and nature of their traffics could be one interesting direction to consider, with smaller and more distance-constrained ports being bound to lower administrative levels (e.g. NUTS-3 region in Europe, county in the United States, sub-prefectures and districts in Japan) or city levels (e.g. Functional Urban Areas or Large Urban Zones in Europe, cities and wards in Japan), while larger ports could be attributed an intermediate level (NUTS-2, state, prefecture) and largest ports extending across two or more regions, such as Le Havre and Rouen (France) being counted as ports of the whole Seine axis including the two NUTS-2 units of Greater Paris region and Upper Normandy or even the NUTS-1 level comprising Ile-de-France and Bassin Parisien. Perhaps, such exercise would prove even more successful by considering the spatial layout of the transport network. In any case the correlation between port traffics and regional specialization shall be closer to reality, i.e. without amputating too much port hinterlands while remaining within reasonable geographical limits. Another possible research direction is the extension of the analysis to other geographical areas where data is potentially available, in the developed (e.g. Australia, New Zealand, Mexico Canada, South Korea, Hong Kong, Singapore) and developing (e.g. India, Russia, Brazil, Turkey, China) worlds. This effort would possibly confirm the existence of invariants in port-region linkages and balance the results obtained here on developed countries only. Other indicators could be integrated in the analysis, such as passenger flows (ferry, cruise), flows by other transport modes such as air flows to study their combination with port traffics (see [START_REF] Ducruet | Cities in worldwide air and sea flows: a multiple networks analysis[END_REF], connectivity indicators in maritime and land-based networks (see [START_REF] Chapelon | L'accessibilité, marqueur des inégalités de rayonnement des villes portuaires en Europe[END_REF][START_REF] Thill | Intermodal containerized shipping in foreign trade and regional accessibility advantages[END_REF], but also other regional indicators such as about innovation, environment, and wages depending on their large-scale availability. Lastly, it is fundamental to consider dynamics in both traffics and socioeconomic conditions of port regions, in order to verify possible convergence between respective diversification and specialization processes and, perhaps, better identify to what extent changes in port traffic structure not only illustrates but also influences local socioeconomic development.

2

  The principal data sources are Eurostat for Europe, the Annual Report on Prefectural Accounts (Cabinet Office of the Government), the Labor Force Survey, Employment Structure Basic Survey, and National Population Census (Statistics Bureau, Ministry of Internal Affairs and Communications) for Japan, the Bureau of Statistics and the OECD Territorial Database for the United States. 3 Data sources used to measure port traffics are Eurostat for Europe, the Ministry of Land, Infrastructure, Transport and Tourism (MLIT) for Japan, and the Army Corps of Engineers for the United States.

Figure 2 :Figure 4 :Figure 5 :Figure 6 :

 2456 Figure 2: Correlations among all variables in 2008 by geographic area

Port Total port traffic * Share of the local administrative unit in total port traffic *

						Container traffic **
		Volume (tons)	Value (Euros)	Volume (%) Value (%)	Volume (tons)	Share in total port traffic (%)
	Rouen	8,942,804 10,525,770	69.0	13.5	1,136,000	5.2
	Le Havre	8,305,550 29,213,899	22.8	13.4	17,685,000	25.0
	Marseille	7,019,774	7,986,530	64.5	22.3	7,292,000	7.8
	Dunkerque	3,937,047	2,294,024	79.8	41.5	1,559,000	3.2
	Nantes-St. Nazaire	2,631,685	959,309	73.5	54.1	1,169,000	3.4
	Languedoc-Roussillon (a) 2,041,343	534,717	76.5	73.2	61,000	1.6
	Bordeaux	1,292,146	392,860	95.3	78.2	444,000	5.2
	Bretagne (a)	1,242,471	388,765	99.5	97.9	234,000	9.6
	La Rochelle	1,074,273	155,471	99.6	96.8	0	0.0
	Dieppe	326,985	104,036	78.7	37.3	38,000	3.8
	Boulogne	42,879	27,760	57.4	26.9	0	0.0

Table 1 : Weight and share of coastal regions in French ports' traffics in 2005

 1 Sources : calculated based on * Guerrero (2010) and ** Eurostat (a) reference is the Région instead of Département N.B. data accounts for extra-EU maritime flows excluding oil products

	Type of indicator	Code	Specialization	Code	General characteristics
		T_COMBUS *Combustibles (coal, oil, gas)	T_SIZE	*Traffic size
		T_CHEMI	*Chemical products & fertilizers	T_IMPOR	*Import/inbound traffic
		T_METAL	*Metal products (iron & steel, scrap)	T_INTER	*International traffic
	Port	T_AGRIC	*Agricultural, forestry products & live	T_DIVER	*Commodity
	traffic		animals		diversity
		T_MINER	*Minerals & construction materials (ores, sand, gravel)	T_FRICT	***Spatial friction
		T_MANUF	*Manufactured goods (containers, vehicles,
			food products)
		R_AGRIC	**Employment in agriculture and fisheries	R_POPUL	*Demographic size
		R_CONST	**Employment in construction	R_DENSI	*Population density
	Socio-	R_INDUS	**Employment in mining & manufacturing	R_UNEMP **Unemployment
	economic	R_RETAI	**Employment in retail, hotel, & transport	R_RGDP	**GDP per capita
		R_FINAN	**Employment in finance & real estate
		R_PUBLI	**Employment in public services

Table 2 : List of traffic and regional indicators

 2 index based on national/continental average ** index based on national average *** other method

*

World Conference on Transport Research (WCTR) SIG-2, Antwerp, Belgium, May 21-22

The weighting value for each commodity type corresponds to the share of variance (%) explained by distance and has been measured as follows: 30.1% for manufactured goods,

53.7% for chemicals, 57.1% for minerals, 67.9% for metals, 75% for agricultural goods, and 92% for combustibles. 2012 World Conference on Transport Research (WCTR) SIG-2, Antwerp, Belgium, May 21-22

Acknowledgments

This research has benefitted financial support from the European Commission in the framework of the European Spatial Planning Observatory Network (ESPON) project on Territorial Impact of Globalization on Europe and its Regions (TIGER). Authors are grateful to Marine Le Cam for her support on data collection and preparation.

 1: Hinterland patterns of some large regions Source: [START_REF] Lee | A tale of Asia's world ports: the spatial evolution in global hub port cities[END_REF]


Arnaud Gotlieb
email: arnaud.gotlieb@inria.fr

Michel Leconte
email: leconte@ibm.fr

Bruno Marre
email: marre@cea.fr

Constraint solving on modular integers

Constraint solving over finite-sized integers involves the definition of propagators able to capture modular (a.k.a. wrap-around) integer computations. In this paper, we propose efficient propagators for a fragment of modular integer constraints including adders, multipliers and comparators. Our approach is based on the original notion of Clockwise Interval for which we define a complete arithmetic. We also present three distinct implementations of modular integer constraint solving in the context of software verification 4 .

Introduction

Using constraint solving to automatically generate program inputs is an emerging trend in software verification. In the last decade, several tools based on Finite Domains (FD) constraint solving were proposed that perform test inputs generation for C programs (e.g., InKa [START_REF] Gotlieb | A clp framework for computing structural test data[END_REF], PathCrawler [START_REF] Marre | On-the-fly generation of k-path tests for c functions[END_REF]), test case generation for reactive programs (e.g., GATEL [START_REF] Marre | Test selection strategies for lustre descriptions in gatel[END_REF]), or property-oriented software verification (e.g., CPBPV [START_REF] Collavizza | Cpbpv: A constraintprogramming framework for bounded program verification[END_REF], Euclide [START_REF] Gotlieb | Euclide: A constraint-based testing platform for critical c programs[END_REF]). In these tools, automated verification of intenunsigned long len = 2147483648; % Equal to 2 31 void f(unsigned long buf) { 1.

if (buf + len < buf) { 2.

. . . sive integer computations involves solving constraints over finite-sized integers.

As an example, consider the problem of reaching5 statement 2 in the program of Fig. 1 that requires solving the decision buf+len < buf over unsigned 32bits integers. A naive translation of the decision of statement 1 as constraint buf + len < buf where buf belongs to 0..2 32 -1 and len = 2 31 , yields an incorrect result saying that statement 2 is unreacheable. In fact, it is trivial to see that this constraint is unsatisfiable when it is interpreted over Finite Domains (FD). However, statement 2 can be reached by selecting a test value such as buf = 2 31 , as 2 31 + 2 31 = 2 32 corresponds to value 0 in unsigned 32-bits integer arithmetic. Note also that simplifying buf + len < buf in len < 0 is forbidden in this arithmetic. The overall reason is that decision 2 should be rather interpreted as buf + len < buf mod (2 32 ). In fact, this problem is sometimes reported to as the "wrapping effect" and it turned out that programmers who take care of possible integer overflows routinely write programs that use this effect. In Fig. 1, statement 2 can only be reached by a wrapping behaviour. Unfortunately, all the previously mentionned tools that exploits constraint techniques for automated test data generation or property-oriented verification simply ignore this wrapping effect. In fact, as soon as finite domains are specified for each input and intermediate variable, these tools consider that programs with integer overflows are necessarily incorrect and should be rejected. This is obviously abusive and often conducts to report false negatives. This paper adresses this problem by providing efficient constraint solving over modular integer computations. We propose bound-consistency propagators for a linear fragment of these constraints that includes adders, multipliers and comparators. Our approach is based on the original notion of Clockwise Interval that captures the wrapping effect by considering intervals with modular integer bounds. An example of such Clockwise Interval is the interval [START_REF] Gotlieb | A clp framework for computing structural test data[END_REF][START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF] 8 that represents all the integers x such that x mod 8 = 7, x mod 8 = 0, x mod 8 = 1, x mod 8 = 2. For these Clockwise Intervals, we give a complete arithmetic that has not been published elsewhere.

In the context of the ANR CAVERN project6 we independently built three distinct implementations of modular integer constraint solving that are variations of clockwise interval arithmetics. These implementations of modular integer constraint solving are used in three software verification tools. Our first implementation called MAXC is used in the context of automatic test input generation for C programs. It implements bound-consistency filtering for a linear fragment of modular integer constraints. For example, for constraint buf ⊕2 31 < buf where ⊕ denotes modular addition over 32-bit integers, MAXC automatically prunes the domain of buf to the Clockwise Interval [2 31 , 2 32 -1] 2 32 , removing half of the variation domain of buf . Our second implementation called JSOLVER [START_REF] Leconte | Extending a cp solver with congruences as domains for software verification[END_REF] is intented to perform automatic analysis of rule-based programs. JSOLVER is based on classic intervals but it takes into account modular integer computations. A comparison with the Clockwise Interval arithmetics shows that JSOLVER is efficient but not optimal when computing local-consistencies over these constraints. Finally, the third implementation is called COLIBRI and it enables automatic test data generation for reactive programs [START_REF] Marre | Test selection strategies for lustre descriptions in gatel[END_REF]. COLIBRI implements modular integer constraints on domains represented as union of classic intervals.

The rest of the paper is organized as follows: Sec.2 introduces the notations and the formal definitions used in the rest of the paper. Sec.3 presents boundconsistency filtering on modular integer constraints. Sec.4 describes our three distinct implementations and discusses their relations with Clockwise Intervals. Finally, Sec.5 concludes and draws several perspectives to this work.

Preliminaries

Notations

Let Z denote the set of integers and Z b denote the finite set of integers modulo b. For any x ∈ Z and y ∈ Z * , x mod y denotes the integer r such that ∃q ∈ Z r = x-y * q and 0 ≤ r < y, while x quo y denotes q the quotient. In the following, we will fix b = 2 n where n is any non-negative integer. Since Z b consists of residue classes, several representations are possible. In this paper, we will consider two representations that can be used to emulate integral computations in imperative languages such C or Java: the unsigned representation {0, 1, . . . , b -1} and the signed representation {-b 2 , . . . , -1, 0, 1, . . . , b 2 -1}. For the sake of simplicity, we will use the unsigned representation (unless it is mentionned otherwise).

In the context of integer-based manipulations, a classic interval noted x..y where x, y ∈ Z and x ≤ y denotes the finite ordered set {x, x + 1, . . . , y -1, y}.

Definition 1 (Width). The width of an interval x..y is an integer, defined as follows: wid(x..y) y -x.

Clockwise Interval

Definition 2 (Clockwise Interval). Let x and y be two integers modulo b, a Clockwise Interval (CI) is noted [x, y] b and denotes the set {x, x+1 mod b, . . . , y-1 mod b, y}.

It differs from classic interval in that any of its element is a residue class of integer modulo b. Furthermore, the bound y is not required to be greater than x as the set {x, x + 1modb, . . . , y -1modb, y} is unordered. By convention, we consider that [0, b -1] b is the canonical representation of Z b itself. Note that other representations exist: [1, 0] b , [2, 1] b ,...,[b -1, 0] b . Clockwise Intervals that have a positive or null width are called proper CIs, while others are called improper CIs. The width of a CI is defined by extending the definition of width over classic intervals, by using the canonical representation: wid([x, y] b ) = wid(x..y). Note that width can then becomes negative in this case. The set of clockwise intervals over

Z b is finite. It is composed of {[] b , [0, 0] b , . . . , [b -1, b -1] b , [0, 1] b , [1, 0] b , . . . , [b - 2, b -1] b , [b -1, b -2] b , . . . , [0, b -1] b },

Building clockwise intervals

A classic interval can be converted into a CI by using the following formula:

x..y mod b [0, b -1] b if wid(x..y) ≥ b [x mod b, y mod b] b otherwise
We define the hull of a set of modular integers as being the smallest Clockwise Interval w.r.t. cardinality, that contains all the elements of the set. By convention, proper clockwise intervals are considered smaller than improper ones when they have same cardinality. Formally, Definition 4 (Hull). Let S = {x 1 , . . . , x p } be a subset of Z b , the hull of S is a CI noted S, defined as:

S Inf card ({[x i , x j ] b |{x 1 , . . . , x p } ⊆ [x i , x j ] b )
Building an algorithm from this definition yields an untractable procedure as it would require considering p! possible combinations of the bounds. Fortunately, we have the following proposition: Proposition 2. Let S = {x 0 , . . . , x p-1 } be an ordered subset of Z b , and let x -1 denotes x p-1 , then

S = [x i , x i-1 ] b where i ∈ 0..p -1 such that card([x i , x i-1 ] b ) is minimized
Therefore, when S is ordered, S can be computed in linear time w.r.t. size of S.

Proof. The case where [x

i , x i-1 ] b is proper, i.e., x i = x 0 and x i-1 = x p , is trivial. Let suppose that [x i , x i-1 ] b is an improper CI. Firstly, it is clear that S ⊆ [x i , x i-1 ] b as S is ordered (∀i ∈ 1..p -2, x 0 ≤ x i-1 ≤ x i ≤ x p-1 ). Secondly, as card([x i , x i-1 ] b ) is minimized, it remains to show that there does not exist a CI [k, l] b where j = i -1 that contains S and that is tighter than [x i , x i-1 ] b ). If l > x i-1 then x i-1 ∈ [k, l] b and if k < x i then x i ∈ [k, l] b , meanning that l ≤ x i-1 and k ≥ x i . By this, we get card([k, l] b ) ≥ card([x i , x i-1 ] b ) which contradicts the hypothesis.

Clockwise Interval Arithmetic

Having defined Cl, we now turn on the definition of Clockwise Interval Arithmetic that allows us to perform computations over intervals.

Definition 5 (Addition). Let [i, j] b and [k, l] b be two CI, then the addition operation, noted ⊕, is defined as:

[i, j] b ⊕[k, l] b      [0, b -1] b if card([i, j] b ) = b or card([k, l] b ) = b or card([i, j] b ) + card([k, l] b ≥ b [(i + k) mod b, (j + l) mod b] b otherwise Correction property: ∀x ∈ [i, j] b , ∀y ∈ [k, l] b , (x + y) mod b ∈ [i, j] b ⊕ [k, l] b . For example, [2, 3] 8 ⊕ [3, 2] 8 = [0, 7] 8 while [2, 2] 8 ⊕ [3, 3] 8 = [5, 5] 8 .
Definition 6 (Substraction). Let [i, j] b and [k, l] b be two CI, then the substraction operation, noted , is defined as:

[i, j] b [k, l] b      [0, b -1] b if card([i, j] b ) = b or card([k, l] b ) = b or card([i, j] b ) + card([k, l] b ≥ b [(i -l) mod b, (j -k) mod b] b otherwise Correction property: ∀x ∈ [i, j] b , ∀y ∈ [k, l] b , (x -y) mod b ∈ [i, j] b [k, l] b . For example, we have [0, 1] 8 [0, 1] 8 = [7, 1] 8 . Note that [0, b-1] b is
absorbing for ⊕ and . For those two operations, similarily to the situation in classic Interval Arithmetic, the computations can be performed on the bounds of Clockwise Intervals. This is no longer the case for multiplication and division, as the tightest CI that encloses all the solutions cannot be computed by using only bounds of its operands in those cases. Let us first define precisely the considered operations: Computing the resulting CI by enumerating all the elements of its operands seems unreasonnable in the context of large-sized machine integers. The following subsection describes a method that permits to compute the resulting optimal CI in the case of multiplication by a constant k, without requiring a ful enumeration of the domain of possible values.

An efficient method for computing optimal CI in the presence of multiplication operators

The method is based on the following notes:

the structure of Z 2 n is well known: the divisors of 0 are powers of 2 ; thanks to proposition 2, ({x 1 , ..., x p }) can be computed efficiently when the set {x 1 , ..., x p } is ordered.

Let k be a constant modulo b = 2 n , let [i, j] b be a CI, we describe a method that allows to compute the minimum and the maximum values of k *

[i, j] b = ({k * i mod b, k * (i + 1) mod b, ..., k * j mod b}).
We start by eliminating some trivial cases:

If k = 0, then k * [i, j] b = ({0}) = [0, 0] b . If k = 1, then k * [i, j] b = [i, j] b . If i ≤ j and k * j < b, then k * [i, j] b = [k * i, k * j] b .
Let now suppose that k is a constant greater or equal to 2 and k * j ≥ b or i > j. We have the following proposition:

Proposition 3. Let k = 2 w , q 1 = k * i quo b and q 2 = k * j quo b, then: M ax(k * [i, j] b ) = b -d where d = M in q1<q≤q2 (q * b mod k) and M in(k * [i, j] b ) = d where d = M in q1<q≤q2 (-q * b mod k).
Proof. (sketch of, partial) Let p be the element of [i, j] b for which k * p mod b is maximized in Z b , and let q be the smallest value such that k * p < q * b, then we consider d = q * b -k * p. We claim that d = q * b mod k as 0 < p < k. It remains to find the value of q that minimizes q * b mod k. As p ∈ [i, j] b , we know that q 1 < q ≤ q 2 by definition of q. Therefore we can explore the possible values of q from q 1 + 1 to q 2 , up to k -1 values.

For example, consider k * [i, j] b where k = 5 and [i, j] b = [2, 7] 8 . Applying Prop.3, we get q1 = 5 * 2 div 8 = 1 and q2 = 5 * 7 div 8 = 4. For q = 2, 3, 4, computing r q = q * b mod k and r -q = -q * b mod k leads to: r 2 = 16 mod 5 = 1 and r -2 = -16 mod 5 = 4, r 3 = 24 mod 5 = 4 and r -3 = -24 mod 5 = 1, r 4 = 32 mod 5 = 2 and r -4 = -32 mod 5 = 3. The minimum over the r i is obtained when q = 2 and then M ax(5 * [2, 7] 8 ) = 8 -r 2 = 1. For the r -i , it is obtained when q = 3 leading to M in(5 * [START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF][START_REF] Gotlieb | A clp framework for computing structural test data[END_REF] Finding similar propositions for generalized multiplication and division may be possible, but one can also use Prop.3 to compute over-approximations of the resulting CIs. It suffices to use the bounds of each operand interval as a constant, to apply Prop.3 on each of the four double products, and keep the smallest intersection of results. But note that, optimality is usually lost with this approach.

Constraint propagation over Clockwise Intervals

In this section, we define projection functions that allow to perform constraint propagation over CI. As usual in Finite Domains constraint solving, each variable X is associated a finite domain dom(X) of possible values. We consider here that domain are (over-)approximated by CI: CI(X)

(dom(X)).

Set-based operations over CI

Inclusion, union and intersection of Clockwise Intervals are defined by using their set-theoretic definition counterpart. For example, inclusion over CI is defined as follows:

[i, j] b ⊆ [k, l] b ⇐⇒ {i, i + 1, . . . , j} ⊆ {k, k + 1, . . . , l}
Note however that union and more surprisingly intersection are not closed over CI. For example, [START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF][START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF]

x ∈ [i, j] b is true iff x ≥ i ∧ x ≤ j when [i, j] b is proper and x ≥ i ∨ x ≤ j when [i, j] b is improper.
This property comes directly from definition of CI.

The meet operator

As the computations of meet is at the core of constraint propagation engine, finding an efficent algorithm is of great importance. The definition given above requires to explore each element of both domains at least once. This can be costly when large domains are involved during constraint propagation. The following proposition offers ways to compute the meet operation more efficently:

Proposition 4. Let X = [i, j] b and Y = [k, l] b be two CI, then X Y is defined as: if wid(X) * wid(Y ) = 0 (suppose for example that X = [i, i] b ) X Y =      [i, i] if X = [i, i] b ∧ i ∈ Y [k, k] if Y = [k, k] b ∧ k ∈ X [] b otherwise if wid(X) * wid(Y ) > 0 then X Y = [] b if wid(X) > 0 ∧ wid(Y ) > 0 ∧ max{i, k} > min{j, l} [max{i, k}, min{j, l}] b otherwise if wid(X) * wid(Y ) < 0 then X Y =                        [] b if j < k ∧ l < i [k, j] b if j ≥ k ∧ l < i [i, l] b if j < k ∧ l ≥ i Y if j ≥ k ∧ l ≥ i ∧ card(Y ) ≤ card(X) X if j ≥ k, l ≥ i ∧ card(X) < card(Y )
In these cases, proving that CI(X) CI(Y ) = ({i, i + 1, . . . , j} ∩ {k, k + 1, . . . , l}) is not difficult.

Note that the situation differs from classic Interval Arithmetic where the intersection of two intervals is always an interval enclosed within its two operands.

Here, [i, j] b [k, l] b is sometimes not included in both [i, j] b or [k, l] b . This could be problematic w.r.t. the monotony of projection functions. Fortunately, the meet operation requires to minimize the cardinality of the resulting clockwise interval. Hence, each time a projection function is called on variable X, the cardinality of CI(X) decrases. This ensures the computations progress towards a fixpoint.

: the join operator The join operation is defined accordingly:

[i, j] b [k, l] b ({i, i + 1, . . . , j} ∪ {k, k + 1, . . . , l}) Proposition 5. Let CI(X) = [i, j] b and CI(Y ) = [k, l] b , then CI(X) CI(Y ) can be defined as follows: if wid(CI(X)) ≥ 0 ∧ wid(CI(Y )) ≥ 0 then CI(X) CI(Y ) = [i, l] b if card([i, l] b ) ≤ card([k, j] b ) [k, j] b otherwise
Note that these two operations ( , ) give the CI set a structure of a finite lattice.

Relations over CI

Let X, Y be two variables over Z b , the relation X = Y leads to prune CI(X) and CI(Y ) with the following rule: CI(X), CI(Y ) ← CI(X) CI(Y ). In CI Arithmetic, the relation X ≤ Y leads to prune CI(X) = [i, j] b and CI(Y ) = [k, l] b with the rule CI(X) ← CI(X) [0, max(CI(Y ))]. Other relations can easily be derived from these ones.

Bound-consistency for modular integer constraints

From the formula given above, one can derive practical algorithms to perform bound-consistency on modular integer constraints. The simplest approach is to implement propagators on Clockwise Intervals within an AC-3 propagation algorithm. Once a CI becomes empty, then the constraint system is shown as being unsatisfiable. If none CI become void, then the resulting CIs encompass all the solutions of modular integer constraints.

For the linear fragment of modular integer constraints (i.e., addition, substraction, multiplication by a constant) this approach maintains optimal CIs at the cost of bounds computations. However, as soon as variable multiplication is encountered, optimality requires time-quadratic exploration of CIs. This is prohibitive in the context of 32-bits or 64-bits integer arithmetic. This problem is similar to the situation in bit-vector arithmetic [START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF] where variable multiplication requires time-quadratic computations on the number of bits. For these non-linear constraints, as said previously, one can gave up optimality by computing Clockwise Intervals that over-approximate optimal clockwise intervals. In the implementations described below, several propositions are made in this direction.

Implementations

In the context of the ANR CAVERN project, three distinct implementations of modular integer constraint solving were done. During this work, it appears that Clockwise Interval may be a unifying notion capturing the essence of modular integer interval computations.

MAXC

At INRIA Rennes, the Clockwise Interval Arithmetic shown above was directly implemented in MAXC, a solver dedicated to modular constraint solving. In a near future, this solver should be integrated within EUCLIDE [START_REF] Gotlieb | Euclide: A constraint-based testing platform for critical c programs[END_REF], an automatic test data generator for critical C programs. The constraint system that is derived from EUCLIDE includes modular constraints based on arithmetic operators (+,-,*,div,mod) and high-level operators such as reification and global constraints dedicated to program verification. We do not detail these operators here as our paper is focussed on modular constraint solving. Propagators in MAXC are implemented in C for efficiency reasons while the general propagation queue is implemented in Prolog. Each variable is associated to a CI and contracting propagators aim at pruning CIs of their inconsistent values. The size of variables that can be represented in MAXC ranges from 1 bit to 64 bits as these are the sizes typically found in primitive types in C. The data structure for encoding CIs maintains cardinality and width: In this data structure, USH stands for unsigned short integer which corresponds to 16-bits integers while UL stands for unsigned long, i.e. 32-bits integers. Other keywords can easily be understood as variations of these two. Note that encoding 64-bits integer Clockwise Interval arithmetics is still possible but greater formats cannot be encoded. The solver applies bound-consistency propagators on this data structure for ⊕, , ⊗, .... It maintains optimal CIs for the linear fragment of these constraints. The input format of constraints is an intermediate one, where complex constraints have already been decomposed in simpler ones. Typical requests are of the form: test1 :-% In 3-bits integer arith., solveur:init_env(E), % X = 5, Y in 2..7, Z in 5..0, Z = X*Y lfd:news([X,Y,Z],int [START_REF] Leconte | Extending a cp solver with congruences as domains for software verification[END_REF],['X','Y','Z'],E), % should produce lfd:equal(const('5'),X), % Y in 3..6, Z in 6..7 lfd:equal(in('2','7'),Y), lfd:equal(in('5','0'),Z), lfd:equal('*',X,Y,Z), solveur:solve(E), lfd:affiche([X,Y,Z]).

Many operators still have to be implemented in order to capture modular integer constraints coming from C programs, including bit-to-bit operators (e.g., &, |, ~) , logical operators (e.g., &&, ||), nonlinear operators coming from destrucive assignment (i.e., i *= i++ that correspond to constraint i 2 = (i 1 + 1) 2 ), and so on.

JSOLVER

JSolver is a IBM-ILOG Constraint-Based Programming library in (pure) Java. It is derived from the C++ library IBM-ILOG Solver and has been tailored for the static and dynamic analyses of rule-based programs [START_REF] Berstel | Using constraints to verify properties of programs[END_REF][START_REF] Leconte | Extending a cp solver with congruences as domains for software verification[END_REF]. Currently, these analyses are performed using an idealized integer arithmetic where modular computations are ignored. Consequently overflows on integers are reported as errors and the corresponding rule-based programs are rejected which is the expected behaviour, as these programs are exploited by end-users and not by developers.

We recently investigated the use of CP to perform static analysis of rules in order to optimize their compilation in a discrimination network [START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF]. Unlike the above usage, this requires using the program execution semantics where integer overflows are silently done (such as in Java). We report here on our first implementation of bound consistency for integer modular constraints by using classic intervals as defined in mathbooks: a classic interval a..b with integer bounds a and b is the set of integers {x|a ≤ x ≤ b}. Let us consider two positive 32-bits integers and suppose we want to determine the range of the sum of these (signed) integers ranging from 1 to 2 31 -1. By using an idealized semantics for integer computations, we get that the sum is ranging from 2 to 2(2 31 -1). Of course, this range could be exactly represented by using unbounded values such as bigInteger in Java or approximated by 2.. + inf inity. But, taking into account modular integer arithmetic, we found that the sum is actually ranging on -2 31 ..-2 union 2..2 31 -1. The classic interval which covers all these values is the set of all representable signed values on 32 bits M IN IN T..M AX IN T . Note that such classic intervals usually over-approximate the results that could be computed using Clockwise Intervals as, for example, the CI [2, -2] 2 32 on signed 32-bits integers corresponds precisely to -2 31 .. -2 union 2..2 31 -1 that is overapproximated by the classic interval -2 31 ..2 31 -1. To give a flavor of inferences which could be made on classic interval for modular integer arithmetic, let us continue our example by constraining the sum to be greater than -2. Let x, y and z be three signed 32-bits integers such that z, the sum of x and y, is greater than -2. x and y are ranging on 1..M AX IN T and z is ranging on -1..M AX IN T . As the transformation x = z -y (resp. y = z -x) is correct in modular integer arithmetic, we actually found that x (resp. y) is ranging on 1..M AX IN T -1. As z = x + y, we deduce that z is ranging on 2..M AX IN T , then discovering that z is positive.

To formally define what our computations are, let us assume that we are dealing with modular integer with a machine representation ranging from a smaller integer denoted by m and a larger integer here denoted by M . let x..y be a classic interval. u, v represent x and y in a (m, M ) computer integer arithmetics if m ≤ u ≤ M , m ≤ v ≤ M and x = u + k u (M -m + 1), y = k v (M -m + 1) for two integers k u and k v . We may then introduce a cast m,M function from classic intervals to (m, M ) intervals with the following definition:

cast m,M (x..y) = u..v if k u = k v m..M if k u ! = k v
This cast function provides concise definition for modular arithmetic. For example the (best) forward operator for the sum z of x and y is z in cast m,M (x min + y min ..x max +y max ). As z = x+y is equivalent to x = y-z in modular arithmetic, the (best) backward operator is defined by x in cast m,M (z min -y max ..z maxy min ) and y in cast m,M (z min -x max ..z max -x min ).

The multiplication by a scalar is not so straightforward. On 32-bits signed integer, the powers of 2 are divisors of 0 and the congruence domains [START_REF] Leconte | Extending a cp solver with congruences as domains for software verification[END_REF] are not preserved. For example, 2 * M IN IN T = 0 and 3 * M IN IN T which is equal to M IN IN T is not even divisible by 3. However, solving ax = b on 32-bits signed integers is not so difficult. First we note that if a power of 2 divides a, it should also divide b for the equation to have a solution. By simplifying by this power of 2, say 2 p , we obtain a x = b mod 2 (32-p) . We find then the inverse u of a mod 2 (32-p) . We infer that x = (ua )x = u(a x) = ub mod 2 (32-p) . Finally, we obtained a range for x in 32-signed integers and a congruence domain to be propagated. We can apply this method to the solving of ax in m..M on 32-bits integers in a similar way. First, if 2 p divides a, we keep only the multiples of 2 p from m..M ax. Then we simplify m and M to solve ax in m ..M mod 2 (32-p) by finding an inverse u of a , leading to x in u * m ..u * M mod 2 (32-p) . Here again, we infer a range for x mod 2 32 and a linear congruence to be propagated. To end this short report on our preliminary implementation, we should say that the general multiplication of two variables is propagated by using the cast function. This leads very often to the top approximation of the full integers, being not complete but at least correct. For future implementations, we are thinking of making use of the k u integer indicators in the cast function definition, as proposed in the tool COLIBRI described below. We also think to switch our implementation from classic intervals to clockwise intervals as the performance should be similar whilst the precision is improved.

COLIBRI

COLIBRI is a constraint library developped at CEA LIST for its test generation tools: GATeL for the functional testing of LUSTRE/SCADE models [START_REF] Marre | Test selection strategies for lustre descriptions in gatel[END_REF], PathCrawler for the structural testing of C code [START_REF] Williams | Pathcrawler: Automatic generation of path tests by combining static and dynamic analysis[END_REF] and Osmose for the structural testing of binary code [START_REF] Bardin | Structural testing of executables[END_REF]. This library provides domains and constraints for integer, real and floating point interval arithmetics. Furthermore, a congruence domain is combined with the integer domain as described in [START_REF] Leconte | Extending a cp solver with congruences as domains for software verification[END_REF].

The integer domain is implemented by union of intervals with finite bounds. These bounds can be any integer since we use big integers provided by the Gnu Multi-Precision library. This representation of integer domains allows to precisely represent improper clockwize intervals. For example, using clockwise intervals we have [START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF][START_REF] Collavizza | Cpbpv: A constraintprogramming framework for bounded program verification[END_REF] 8 ⊕ [4, 7] 8 = [START_REF] Gotlieb | Euclide: A constraint-based testing platform for critical c programs[END_REF][START_REF] Berstel | Using constraints to verify properties of programs[END_REF] 8 . This interval corresponds to the following union of classic intervals 0..3 ∪ 6..7 which is denoted by [0..3, 6..7] in COLIBRI.

In order to handle the signed and unsigned integer arithmetics used by computer languages, COLIBRI provides signed and unsigned modular arithmetics operations when the modulo is a positive power of two (i.e., when b = 2 n with n > 0). For each operation op in +, -, ×, div, rem, power we provide the operations op s,n and op u,n which correspond to the modular signed and unsigned versions of op. The implementation of these operations uses the following definition of modular operations.

∀(A, B, C) ∈ Z 2 n 3 , A op su,n B = C ≡ (∃K, AopB = C + K × 2 n )
The range of K can be easily characterized for each op su,n according to 2 n . For example, for the + u,n operation -1 ≤ K ≤ 1, while for the × u,n operation 0 ≤ K ≤ 2 n -1.

Thus, according to the previous equivalence, the constraint propagators of any modular operation can be implemented with those of non modular operations. This is exactly the way modular operations are implemented in COL-IBRI. For example, the constraint A + u,n B = C where variables A, B and C belong to [0, 2 n -1] is handled by the following conjunction of constraints: A+B = X ∧K ×2 n = Y ∧X +Y = C where the initial domain of K is [0, 2 n -1], Notice that the congruence domain knows that variable Y is a factor of 2 n and as soon as C (resp. Y ) handles a congruence one can infer a congruence for Y (resp. C).

For each modular operation, the variable K is a precise indication of underfow/overflow: when K < 0 this means that there is an underflow, when K > 0 this means that there is an overflow while when K = 0 there is no underfow/overflow. Such an indicator could be very helpfull for verification tools when checking computation w.r.t. underfow/overflow. This is why COLIBRI modular constraints handle a supplementary argument U O which abstracts the sign of K: U O belongs to [-1, 1] and has the same sign as K. Any assignment of this variable U O can be used to force underflow (U O = -1), overflow (U O = 1) of normal computation (U O = 0). Moreover, one can force non normal behaviour by stating that U O <> 0.

To conclude this short presentation of modular operations in COLIBRI, let us remark that the accuracy of this implementation relies on the use of union of intervals with big integer bounds. This could be considered very expensive for constraints systems involving heavy computations. However, as shown by a recent experiment [START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF] using SMT-LIB benchmarks our implementation of modular arithmetics is competitive with powerfull SMT solvers.

Conclusions and perspectives

In this paper, we introduced Clockwise Intervals as a way to capture modular interger interval computations. We described three distinct implementations of modular integer constraint solving that have applications in program testing and analysis. We have also seen that finding optimal bounds in bound-consistency filtering of modular integer computations is not trivial and often requires approximations. For general multiplication and division, efficient ways to compute optimal bounds still need to be found. On the foundations of the approach, Clockwise Interval appears as a good tool to describe bound-consistency on modular integer computations but its relations with other Interval Arithmetics still need to be studied. On the applications of modular integer constraint solving, experimental evaluation is required in the diverse contexts presented earlier in the paper, namely, automatic test inputs generation for C programs, test case generation for reactive programs and rule-based program analysis. Another perspective of this work concerns the way other dedicated constraint solver could be married with Clockwise Intervals. For example, the recent work of Bardin et al. in [START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF] showed that dedicated bitvectors operators could be efficiently coupled with classic intervals. It remains to find ways to integrate such arithmetics within Clockwise Intervals.

Fig. 1 .

 1 Fig. 1. Program taking care of integer overflow

  where [] b denotes the empty clockwise interval. Definition 3 (Cardinality). Let [x, y] b be a CI, then its cardinality is an integer modulo b defined as: card([x, y] b ) (y -x + 1) mod b. By convention, card([0, b -1] b ) = b and 0 < card([x, y] b ) ≤ b. For example, card([7, 0] 8 ) = 2 while wid([7, 0] 8 ) = -7. The following property immediatly holds: Proposition 1. A CI [x, y] b contains exactly card([x, y] b ) elements, if represented over [1, b] b . Proof. If y ≥ x, then the set [x, y] b = {x, x + 1, . . . , y -1, y} is ordered and contains y -x + 1 elements. The special case where y -x + 1 = b corresponds to the CI [0, b -1] b and then card([0, b -1] b ) = b. If y < x, then [x, y] b = {x, x + 1, . . . , b -1} ∪ {0, 1, . . . , y} and so, it contains (b -x) + (y + 1) elements. In this case, b -x + y + 1 ≡ y -x + 1 mod b that gives the expected result.

Definition 7 (

 7 Multiplication by a constant k). Let k be a constant modulo b and [i, j] b a CI, then the multiplication by k is defined as follows: k * [i, j] b ({k * i mod b, k * (i + 1) mod b, ..., k * j mod b}) Definition 8 (Multiplication). Let [i, j] b and [k, l] b be two CI, then the multiplication operation, noted ⊗, is defined as: [i, j] b ⊗[k, l] b ({i * k mod b, i * (k+1) mod b, ..., (i+1) * k mod b, ..., j * l mod b}) Definition 9 (Division). Let [i, j] b and [k, l] b be two CI, then the division operation, noted , is defined as: [i, j] b [k, l] b ({i/k mod b, i/(k+1) mod b, ..., (i+1)/k mod b, ..., j/l mod b}) As an example, consider the multiplication by a constant operation 4 ⊗ [2, 4] 8 . With the formula, we get ({4 * 2 mod 8, 4 * 3 mod 8, 4 * 4 mod 8}) = ({0, 4}) = [0, 4] 8 . Unfortunately, the bounds of the resulting CI [0, 4] 8 cannot be computed by using only the bounds of CI operands as 4 * 2 ≡ 4 * 4 ≡ 0 mod 8.

  8 ) = r -3 = 1. Hence, 5 * [2, 7] 8 = [1, 7] 8 has been computed by exploring only the divisors of b in k * i..k * j, instead of looking at all the double products k * l within the same range.

8 ∩[ 1 , 6 ] 8 =

 8168 {1, 2, 5, 6}. Hence, we define the meet operation as taking the smallest CI that contains all the elements of the intersection:[i, j] b [k, l] b ({i, i + 1, . . . , j} ∩ {k, k + 1, . . . , l})For example, we got:[START_REF] Forgy | Rete: A fast algorithm for the many pattern/many object pattern match problem[END_REF][START_REF] Bardin | An alternative to sat-based approaches for bit-vectors[END_REF] 8[START_REF] Bardin | Structural testing of executables[END_REF][START_REF] Gotlieb | Euclide: A constraint-based testing platform for critical c programs[END_REF] 8 = [1, 6] 8 and [5, 1] 8 [0, 6] 8 = [5, 1] 8 . The main question is whether these operations can be computed efficiently. The following property helps answering this question: Let x be an integer modulo b, then

This work is supported by ANR-07-SESUR-003 CAVERN Project

Reachability is a fundamental problem in software program verification.

cavern.inria.fr

Acknowledgments

We would like to thank the members of the ANR CAVERN project who participated to our initial discussions on this topic, namely Bruno Berstel, Bernard Botella, Claude Michel, Michel Rueher, and Nicky Williams.