Peter Daniels
email: p.w.daniels@bham.ac.uk

Ni Pengfei

, 研究结果显示

, 大部分城市的制

业与服务业间的差距仍然很显著 。 关键词:都市化

, 中国

, 分税制

, 第 产业

Keywords: urbanisation, China, service industry 摘要 在中国的经济发展模式中 许多与城镇化相关的模式,其中一个很 要的部分是要广泛的发展服务

There are many dimensions to the evolving economic development model in China and the role for urbanization within it. One key component is a requirement to incorporate a wider range of service i dust ies, espe ially i the atio s fast-growing cities where there is demand for knowledge and related advanced services that will support, for example, the necessary shift to mo e ode a ufa tu i g. This paper summarizes progress towards servicification and the rationale for undertaking more research that will deepen understanding of the actual and potential contribution of producer services. Some recent empirical evidence on the growth trends for producer service in selected cities, including the four case study cities of Shanghai, Huangshan, Chongqing and Kunming, is presented. It is shown that in majority of cities the manufacturing-services gap remains a significant.

Table of contents

a) Servicification in China

More than 170 cities in China have a population in excess of one million; creating urban economies fit for the 21st century is a major challenge. Moreover, the expansion of such cities is expected to continue for at least three more decades as some 10 million people migrate from rural to urban areas every year. The number of mega-cities (or megalopolises) is expected to increase from three in 2003 to thirteen by 2020 (Economist Intelligence Unit, 2012; see also [START_REF] Woetzel | Dynamic Cities and Creative Clusters[END_REF][START_REF] Dobbs | Urban world: Mapping the economic power of cities[END_REF]; China Science Center of International Eurasian Academy of Science et al, 2012) and many of these will be located inland as efforts to shift city growth away from the eastern seaboard to cities such as Chengdu or Wuhan gathers momentum. They are already achieving annual GDP growth of more than 10 per cent, considerably higher than first tier cities such as Shanghai and Shenzhen (5-8 per e t . This is i li e ith the este de elop e t st ategy that seeks to take advantage of cheaper labour, lower land and infrastructure costs, good energy availability, and enhanced accessibility of the kind offered by the new high-speed rail network to encourage manufacturing and service firms to relocate from the coastal regions or to make FDI decisions favouring the western cites and provinces. It is likely that the provincial capitals that will attract much of the associated growth of service industries, replicating the experience of first-and second-tier cities in economies the world over [START_REF] Sassen | The global city[END_REF][START_REF] Sassen | Cities in a world economy[END_REF].

Rapid urbanisation coincides with a stage in Chi a s e o o i development that requires a refinement of its manufacturing export dependent growth model towards a model that incorporates a wider range of producer and consumer services. More rapid expansion of consumer and producer service jobs and output that will enable a more balanced, competitive economy made up of less labour-intensive primary and manufacturing sectors and a dynamic, innovative service sector (for an overview, see [START_REF] Ghani | Service with a smile[END_REF]. As part of this change, services are performing a complimentary role that is sometimes characterised as servicification; the intertwining of services with manufacturing as the latter make more use of, as well as produce and trade, in the former (National Board of Trade, 2012). 3An aspect of servicification that is relevant to the situation in China is that the manufacturing sector exports and imports more services than before. It also promotes goods exports in that some services assist with foreign markets by enabling reductions in transaction costs, the adaptation of products to new markets, devising and implementing marketing strategies, or improving productivity and competitiveness; all of which may result in larger export market shares [START_REF] Lodefalk | The role of services for a ufa turi g fir s e ports[END_REF]. 4Comparative advantage at the industry level has also been shown to be correlated with the intensity of the use of knowledge intensive business services [START_REF] Bottini | Does the interaction between service and manufacturing explain the recent trends in export specialization? A look at the evidence from the EU[END_REF]. Imports of business services not only have positive effects on manufacturing exports but also on value-added and employment in most technology-intensive industries [START_REF] Francois | Producer services, manufacturing linkages, and trade[END_REF]. However, such benefits are dependent upon the availability of a cadre of the highly-skilled services workers such as managers, professionals and technicians, especially in city labour markets where producer services, in particular, are prone to locate. As urbanisation in China continues apace access to human resources that will enable the development of producer services will be a key requirement. Also worth noting is the role of agglomeration economies that accrue to producer services, as well as services such as retailing, personal, education, healthcare from being located in cities. These, in turn, support further rounds of new firm formation (see for example [START_REF] Jacobs | The economy of cities[END_REF][START_REF] Rosenthal | The determinants of agglomeration[END_REF][START_REF] Kolko | Urbanization, agglomeration, and co agglomeration of service industries[END_REF]. Services stimulate positive spillovers to other sectors; in the case of producer services such as industrial design, marketing or information and communications technology facilitate the process of developing new products or encouraging investment that then underpins a dynamic industry sector and creates further demand for producer services.

There is a good deal of historical evidence that shows how national urban and economic transformation includes an increasing share of employment and output in services as income levels rise and the share of manufacturing output reaches a peak (or even declines). A process that gradually unfolded over 150 years in Europe has however been concatenated into less than 30 years in China, not least because the very rapid pace of urbanisation has been accompanied by a necessary expansion of services. This fits with the well-documented association between the urbanisation rate and the share of services in employment; countries across Asia conform to this relationship (see for example, Asian Development Bank, 2012).

b) Services and development in China

Chi a s se i e i dust ies ill e the atio s most significant force for promoting economic development and the main channel for solving Chi a s e ploy e t p o le s Hu Ji tao, P eside t of the People s 'epu li of Chi a, 2004).

Research on aspects of services industries and urban development in Asia work has increasingly included coverage of China where rapid economic growth has boosted average per capita incomes and burgeoning demand for consumer services (see for example Kwan-yui, 1998;[START_REF] Daniels | Producer services and the Asia-Pacific Region in a global context[END_REF][START_REF] Daniels | Globalisation, producer services and the city: is Asia a special case?[END_REF][START_REF] Daniels | Reflections on the 'old' economy, 'new' economy, and services[END_REF][START_REF] Daniels | Services and economic development in the Asia-Pacific[END_REF]Daniels, Hutton andHo, 2005, 2012;Peilin, 2011;[START_REF] Hutton | Intermediate services, economic restructuring, and urban transformation: insughts and prospects for China[END_REF]. Service industries have become one of the key activities participating in the dramatic expansion and transformation of Chi a s la ge a d u e ous ity-regions, especially those located adjacent to its coastal regions [START_REF] Luo | Chi a s se i e se to : a new battlefield for international corporations[END_REF][START_REF] Gong | Growth of the tertiary sector in Chi a s la ge ities[END_REF][START_REF] Yang | Services and metropolitan development in China: the case of Guangzhou[END_REF][START_REF] Lin | Service industries and transformation of city-regions in globalizing China: new testing ground for theoretical reconstruction[END_REF][START_REF] Zhang | Services research in China[END_REF] but also increasingly in the central and Western regions [START_REF] Yi | The intraurban location of producer services in Guangzhou, China[END_REF][START_REF] Li | China's new stage of development[END_REF]. 5 But the size of the service economy in China still lags some way behind even other countries in Asia (Table 1). The share of services in total value-added in 1990 was less than half the equivalent figure for the US, with only a comparatively small increase to just over 50 per cent by 2010. Other countries in developing Asia, including India, have also been consistently ahead of China. Using another measure, in 2008/9 the urbanisation rate (share of urban population) was 43 per cent and the share of services in employment was 33 per cent (42 per cent for share of GDP). This compares with 98 per cent and 90 per cent respectively for Hong Kong or 82 5 The rapidity of the transition to a service economy in cities is conveyed in the following observations in 2004 by a restaurateur in Beijing: When I first came to Beijing in 1978 to study medicine, I could find neither restaurants nor taxis. You could not find one empty taxi on the street. There were only two-star class hotels, the Beijing and Minzu. And there was only one foreign restaurant, Maxim's, in Beijing. By 2004 the city had more than 622 hotels, 572 of which were star-rated, with a total of 103,000 rooms. Delicious and exquisite cuisines from around the world could easily be found in Beijing. At the end of 2003, there were 11.09 million mobile phone subscribers, meaning that 76.1 mobile phone sets were in use for every 100 local residents. About 61 of each 100 families in Beijing had personal computers. The most popular departments in universities and colleges were those focused on professional service industries such as information technologies and telecommunications, logistics, law, auditing, human resources management and advertising (quoted in [START_REF] Li | Service industries expanding in China[END_REF]. per cent/73 per cent for the Republic of Korea (World Bank, 2012).

While gains from the development of services can be demonstrated through the findings of research in the advanced economies, there are many obstacles still to be overcome in China. The situatio has ee like ed to ei g t apped i t aditio al se i es Asia De elop e t Ba k, 2012, xviii); labour productivity lags far behind that of advanced economies, reflecting the ongoing dominance of traditional service industries that a much larger share of total services output compared with advanced economies where market producer services, alone, account for some 20 per cent of the total. Modernization of traditional services will generate improvements in productivity (including in the traditional sectors) and be more amenable to cross-border trade (see for example Goswami et al, 2012). The Asian Development Bank (2012) also identifies bottlenecks to the modernization of services such as a regulatory structure that is not fit for purpose, infrastructure limitations, and shortages of suitably qualified/skilled human capital. It is the efo e ot su p isi g ou empirical understanding of how these diverse [service] sectors actually function and the type of economic policy initiatives that might promote sectoral growth, job creation, and innovatio remains underdeveloped (Kirkegaard, 2012, p.2). There is still much to understand about what determines the wide inter-regional variations in the types of services available and access to them [START_REF] Wang | The service sector in the Chinese economy: a geographic appraisal[END_REF].

The comment by Wang is especially applicable to producer services. Thus, esea h o intermediate or producer services, which are younger services in China, is still in a relatively early stage of development, despite the fact that these activities are becoming crucial in the economic developme t p o ess Yeh a d Ya g, 2012, p.4). These services are a major player in economic urbanisation and regional development in Europe and elsewhere (Taylor et al, 2011, Rubalcaba and[START_REF] Rubalcaba | Urban concentration of European business services and the role of regional policies[END_REF] and it is now e og ised that they ha e at least th ee st ategic le el i pa ts o Asia ities, i ludi g those i China. These are: recomposition of city industrial structures towards services in line with the rise of post-Fordist production systems, the intra-urban reconfiguration of land use towards services, including the emergence of first-and second-tier cities as centres of knowledge development and innovation, and the formation of a new metropolitan class of professional and managerial workers (Yeh and Yang, 2012, p.9). To these might be added another strategic level impact, a requirement for labour that can sustain the development of producer services i.e. the availability of workers with appropriate higher level educational qualifications and/or professional skills. A shortage of these kinds of workers will constrain the ability of the cities to nurture domestic producer service firms as well as efforts to attract foreign-invested services and manufacturing firms.

c) Why research on producer services is important

The Secretary General of the OECD very recently observed that:

The i for atio re olutio has ha ged the a (Gurría, 2013, p.1) This is the a kd op fo the p odu e se i es halle ge that o f onts rapidly emerging economies such as China and this has been summarized as follows:

our
State-of-the-art services are needed for manufacturing firms to connect to global value chains and to develop competitiveness in more skill-intensive activities along the alue hai a d o e ope usi ess se i es a kets ould generate a win-win scenario where countries with comparative advantage in business services would generate well-paying jobs in this sector, while countries with comparative advantage in manufacturing would benefit from access to state-of-the-art business services that would help the o e up the alue hai i a ufa tu i g. (Gonzalez et al, 2012, 176) Therefore, for service and manufacturing firms to stay competitive in their industry sector they need to constantly review and improve processes, product design and utility, ways of contacting customers, service delivery, or ways of using capital. Deployment of numerous different business models, such as just-in-time delivery, economies of scale, lean production, flexible specialization, product customization, sourcing high quality components, or conforming to local market product specifications, is necessary. Success will depend upon the procurement of the expertise available from a wide range of knowledge intensive business services such as computer, R&D, legal, accountancy, logistics, and management consultancy services. If companies want to move up the value chain, as is the case for many firms in China, the requirement for such inputs will become even greater. On the other side of the coin, the bundling of services with goods has become increasingly important so that, for example, an engineering company making components and systems for delivery will provide freight, packaging, storage of spare parts as part of its contract with client companies. If it is too small to provide all these services efficiently it may work with strategic partners to ensure a comprehensive solution. Likewise, manufacturers offer post-sales services such as maintenance and repairs, sales of spares, diagnostic tools, surveillance, and management and rental/leasing of equipment, either separately or incorporated into their products. The options are numerous and shaped by the type product and whether the after-sales are business-to-business or businessto-consumer.

Chinese scholars are devoting more research attention to producer services but there are analytical hurdles to overcome (Cheng, 2006a(Cheng, , 2006b; 2013, see also Appendix). [START_REF] Wang | The service sector in the Chinese economy: a geographic appraisal[END_REF] draws a distinction between research that has focused on specific services and studies concerned with the service sector as a whole. Examples of the former include financial services (Wang et al, 2007), retail services [START_REF] Wang | Store wars: Changing retail ownership in Beijing[END_REF], and the internet (Zhang, 2008) and they tend to outnumber the latter. Analysis is fraught with difficulties (see for example, [START_REF] Gong | Growth of the tertiary sector in Chi a s la ge ities[END_REF][START_REF] Mattoo | China's accession to the WTO: The services dimension[END_REF][START_REF] Yang | Services and metropolitan development in China: the case of Guangzhou[END_REF][START_REF] Lin | Toward a post-socialist city? Economic tertiarization and urban reformation in the Guangzhou metropolis, China[END_REF][START_REF] Lin | Service industries and transformation of city-regions in globalizing China: new testing ground for theoretical reconstruction[END_REF][START_REF] Wang | The service sector in the Chinese economy: a geographic appraisal[END_REF]), not least because of the universal problem of the availability of robust disaggregated cross-sectional or time series data for groups or classes of activity within services (Qiang and Xue, 1998). Efforts are being made to rectify these shortcomings, although it is perhaps not surprising that one of the activities that has largely been overlooked is producer services (see for example [START_REF] Yeh | Producer services and industrial linkages in the Hong Kong-Pearl River Delta Region[END_REF]Cheng, 2006a;[START_REF] Liu | Role of producer services in regional economic growth: a study of the Yangtze River Delta[END_REF][START_REF] Li | The Development of producer services and the upgrading of the manufacturing sectors in China[END_REF]. Some of the data problems can be overcome using input-output analysis (Cheng 2006b). It is shown that, firstly, producer services developed rapidly between 1981 and 2000 (the period o e ed i Che g s study i a solute alue of output as well as in relative proportion. Annual growth rates for their use as intermediate inputs exceeded the rates for services and for national output but this still left the share of producer services in national output at less than half the levels for the UK and the US. Secondly, inputoutput analysis also shows that labour-intensive sectors such as commerce rather than high technology and knowledge or human capital intensive services are prominent. These are the activities, even though they are now expanding, that ake the p odu e se i es gap i Chi a a sig ifi a t p o le . Che g s 2006 also examines the destinations of producer service outputs; in 1981 almost two-thirds went into manufacturing and a third into services but by 2000 the balance had shifted with services using 38 per cent of producer service outputs. Again, while this trend is encouraging, and but even allowing for further change since 2000, it likely still leaves China some distance behind the US and the UK where the majority of producer services output is utilized by other services.

d) Diverse role of producer services in urban economic development

Demand for producer services is expected to grow rapidly as they provide both the essential infrastructure for production and export trade and a conduit for ideas and innovation leading to improvements in the competitiveness of local/regional economies, sectors of economic activity, or individual firms [START_REF] Hansen | The strategic role of producer services in regional development[END_REF][START_REF] Bryson | Service worlds: People, organizations, technologies[END_REF]Warf, 2004, Yang and[START_REF] Yang | State, market and growth of service industries in metropolitan Guangzhou[END_REF].

Because producer services provide intermediate inputs throughout the value chain they interface with a large number of economic sectors across the economy; many small and medium-sized firms start-ups are producer services which, by supplying state-of-the-art knowledge and expertise, contribute to the success of small firms in other sectors (Daniels and Bryson, 2002;Rubalcaba and Kox, 2007). Because they are so intensively knowledge-based, many producer services are also at the cutting edge of creating innovative new products and to be effective they need to initially develop to support a local client base and then follow clients outside their national markets (export and FDI) [START_REF] Bryson | Business service firms, service space and the management of change[END_REF].

The precise pace and direction will be shaped by several considerations and some of these will be explored before turning to some recent empirical evidence on the growth of producer, especially in the major cities.

Chi a s a ility to o pete a oad i goods, services, and agriculture will be partly shaped by the liberalization of telecommunications, financial and business services in accordance with WTO commitments (Yeh, 2004). 6 Liberalization in parallel with a rapidly expanding and restructured manufacturing sector creates potential demand for producer services provided that, in contrast to firms in the advanced economies, those that are internalised by manufacturing SOEs, for example, are externalized [START_REF] Li | The Development of producer services and the upgrading of the manufacturing sectors in China[END_REF]. 7 It is suggested that this has held back the formation of independent business and professional service enterprises, to some extent explaining why such producer services are relatively underdeveloped and incapable of meeting demand from domestic, as well overseas, firms for high quality knowledge and expertise. Foreign invested service and goods-producing enterprises also prefer imported producer services or those available through other overseas suppliers with a presence in China, especially in the large cities along the coastal margins. One of the principal challenges is therefore how to implement a shift in the demand for producer services to external specialist firms (both domestic and inward invested) that will function in a more efficient, quality driven and professional way that will have the effect of providing much better support for the development, upgrading and enhanced competitiveness of manufacturing firms [START_REF] Li | The Development of producer services and the upgrading of the manufacturing sectors in China[END_REF].

The challenges to be overcome vary across different types of producer service. The capacity of the Chinese economy to export goods and services will be increased if, for example, domestic logistics services are able to access foreign capital and technology that substantially reduces the cost of exporting goods from the inland provinces as well as increasing their attractiveness for FDI [START_REF] Qui | / Personal networks, institutional involvement, and foreign direct investment flows into China's interior[END_REF]. However, many SOEs, especially in manufacturing, still operate their own logistics businesses and are reluctant to outsource to third party logistics providers.

Secondly, logistics are subject to significant levels of localized regulation, often enacted by several different local and provincial government bodies, that discourages the provision of logistics services that cover the whole country. In addition, the logistics market is highly fragmented because of the spatial imbalance in economic growth and local protectionism, while the legal system regulating logistics is also geographically variable. This has not prevented an expansion of logistics services such as the express delivery by some 20 per cent per annum since 1990 (much higher that annual GDP growth), although more than 80 per cent of the market is now occupied by multinational logistics companies after it was fully opened to foreign investors in There are also several structural challenges facing the development of financial services in China, including the fact that capital markets remain underdeveloped, the absence of an institutional market, the immature banking system, and a regulatory structure that does not foster innovation in a predictable and transparent way [START_REF] Paulson | Prepared remarks presented at a meeting in Shanghai[END_REF]). The banking system, for example, is changing but it is far from modern, efficient, and market-driven system with proper controls, management, and professional staff. Some bank credit officers still prefer to make safe loa s to SOEs a ked y i pli it go e e t gua a tees, athe tha to isky dynamic small, medium-sized, and private businesses. Effective corporate control of a massive and geographically dispersed branch network is also a demanding challenge, and local pressures still exert excessive influence on branch lending decisions. Better risk management; more consumer finance products; greater competition, including of electronic payment systems; and opportunities for new banks to expand branch networks far more quickly are amongst the improvements needed [START_REF] Paulson | Prepared remarks presented at a meeting in Shanghai[END_REF]. The insurance sector would also benefit from greater opportunities to expand branches in China since such limitations impact commercial (intermediate) as well as (consumer) final demand for these services.

A further consideration is that producer services are key to developing standards and practices and training of the professional occupations that are critical for the continued growth of activities su h as Chi a s pu li a ou ti g p ofessio that will enable the development and international harmonization of the country's accounting standards and tax system).

Management consulting services also need boosting since: …. eak a age e t is the ajor o strai t o the competitiveness of Chinese companies. Despite two decades of joint ventures and enormous investments in training, Chinese managers continue to fail in the critical tasks of systems integration and optimization. The problem is fundamental, embedded in the economic system itself. The dominance of stateowned enterprises in major manufacturing and service sectors, together with extensive state intervention throughout the economy, has sustained the premium on good political skills o er oder a age e t apa ilities (Lieberthal and Lieberthal, 2004, 8).

The way forward for commercial and professional services will require a mix of foreign firms and local firms, with commercial presence essential for the former. Joint ventures with foreign majority ownership in foreign invested construction and engineering projects have been allowed since 2001 but in legal services, for example, foreign firms are not permitted to directly practice Chinese law and can only advise on legal affairs related to their home country or provide information on the impact of the Chinese legal environment. As a constituent part of the pathway towards the construction of a new industrialized economy in China, proactive support for the development of producer services is now a given (Wu, 2005). Yet many key issues remain, including improvements in timeliness and conditions associated with cross-border transfer and storage of data; the movement of services business people; sounder and clearer rules on the role of State-owned and linked enterprises creating competitive markets; improving the conditions for commercial presence for foreign companies; and the development of a set of principals providing best practice regulation (Global Services Network, 2011).

e) Growth of producer services in China: Provinces and selected cities, 2004-2009

As a precursor to more detailed research that examines some aspects of the production and consumption of producer in a sample of businesses in the cities used as case studies for the UrbaChina project, it is necessary to explore the existing level of producer service activity in Chinese cities (see also Yeh and Yang, 2013a, b).

In 2009 more than 40 per cent of the total GVA of 37 leading cities was accounted for by service activities with cities in the west generally performing less well poorly compared with the leading cities in the coastal provinces (Fig. 1) (see also Appendix, Fig. 1 and Fig. 2). This compares with a share nearer 70 per cent typical for equivalent cities in Europe. Beijing is the only city with services GVA (75.5 per cent) larger than the European average; Guangzhou and Shanghai are still some way behind at around 60 per cent. Producer services8 GVA was 15.7 per cent of total Chinese GVA in 2009 and, with few exceptions, the share in the top cities exceeded the national average, especially Beijing (39.9 per cent), Guangzhou (26.7 per cent), Hohhot (28.4 per cent), Shanghai (32.7 per cent), Shenzhen (26.4 per cent) and Urumqi (23.8 per cent). This is illustrated in Fig. 2a which illustrates the stronger positive relationship between city size and producer services GVA (r 2 = 0.399) compared with all services GVA (r 2 = 0.179). As city size increases the share of producer services GVA is larger than in smaller cities. This is illustrated in a slightly different way in Fig. 2b which shows that the absolute values of both services and producer services GVA are closely correlated with city size. The trend line for services is steeper than for producer services, although the correlation is very similar and this reflects the ability of the larger cities to attract and retain a wider mix of service functions (such as corporate headquarters, regional offices of financial institutions) than lower order cities.

Based on the same sample of 37 leading cities, financial intermediation and transport, storage and postal services account for the largest share of producer services GVA with Beijing (13.2 per cent), Hangzhou (10.2 per cent) and Shenzhen (13.5%) prominent for financial intermediation and Huhehot (17.6 per cent), Shijiazhuang (9.1 per cent) and Xining (9.8 per cent) prominent for transport, storage and postal services. In addition to financial intermediation, information transmission, computer services and software are major contributors to total GVA in Shanghai (12 per cent) and Beijing (8.8 per cent). With some exceptions such as Dongguan (9.7 per cent), Guangzhou (7.5 per cent) and Beijing (6.7 per cent), leasing and business services account for a small share of total GVA in all the cities (even less than information transmission, computer services and software). It would seem that in the majority of cities the knowledge-intensive market services that are crucial to some of local and national economic adjustments discussed earlier, are still relatively underdeveloped. There are exceptions such as the cities at the apex of the hierarchy, notably Shanghai, Beijing and Guangzhou, but even there the absolute values of leasing and business services GVA are not much higher than those for scientific research, technical services and geologic prospecting (Fig. 3).

The relationship between city size, total GVA and share of producer services GVA is in line with expectations based on the results from similar research on European and North American cities (Yeh and Yang, 2013c). But the overall level and diversity of producer service activity remains lower than in the cities of the advanced economies and it is therefore interesting to look more closely at the trends in producer service activity in a number of Chinese cities. The average annual change for producer service employment in 120 cities between 2004 and 2009 relative to the numbers employed in these services in 2009 is interesting (Fig. 4). In the case of cities with more than 100,000 employed in producer services in 2009 the average annual change since 2004 has been consistently positive. In broad terms, for these cities as the scale of producer service employment has increased so has the average annual change. The picture is less consistent for cities with fewer than 100,000 producer service jobs; approximately one-third recorded negative average annual rates, while others recorded rates at or above those typical of cities with larger producer service clusters (see Fig. 4). There are likely to be several reasons for the variable performance of the smaller city clusters, these include: city location (western, central, eastern regions), proximity to larger, competing city, the structure of economic activity, functional role, level of foreign investment, or presence of foreign-owned firms.

Thus, almost all of the provincial capitals show higher annual rates of producer services employment growth than the major cities that have maintained the largest share of producer services employment throughout the period 2004-2009. Many of the former are engaged in a catching up process, often from a low employment base. This is apparent when the average annual change in producer services employment (2004)(2005)(2006)(2007)(2008)(2009) is plotted against the average annual change in city population (Fig. 5). For the 64 cities shown, some of the highest producer service annual growth rates have occurred for cities with modest population growth such as Wenzhou, Hefei, Xiameng and Qingdao. While the recent expansion of producer services in China has been concentrated in the largest cities, in much the same way as in Europe, it is also the case that as the demand for these services increases supply will trickle down to cities lower down the hierarchy. Although the time period is just five years, there are indications that the hegemony of cities such as Shanghai and Guangzhou for the production of producer services is being displaced by some dispersal, albeit slowly, to the provincial capitals (see Yeh and and Yang, 2013c). In most of the provinces producer services are also disproportionately concentrated in the capital cities, replicating the national dominance of Beijing and Shanghai at provincial level.

However, the overall growth (or contraction) or producer services in cities may mask differences between different types of producer service. It is therefore useful to disaggregate the totals for each city into the five sub-groups (excluding real estate) available from official statistics. The annual average employment change (2004)(2005)(2006)(2007)(2008)(2009) for each of these has been plotted against the equivalent values for producer services as a whole, covering 184 cities (Fig. 6a-e). In more than two-thirds (131) of the cities employment growth in all producer services has been positive between 2004 and 2009 with some cities recording changes in excess of 20 per cent per annum (this may of course have taken place in circumstance where the absolute number of jobs is small). Employment in transport, storage, and postal services has grown in most of the cities at a similar rate to all producer services (r 2 =0.542) to produce a tight distribution that reflects the need for these services to be available in every city; many of them cannot be made available to customers remotely using IT for example (Fig. 6a). However, only 70 cities achieved positive growth over the period. For information and computer services there is a much weaker relationship (r 2 =0.169) with the overall rates for producer services (Fig. 6b). While the changes in the majority of cities are greater than those typical for transport, storage, and postal services, there are still more than 20 cities where overall and sub-sector employment change has been negative and there is also a similar number of cities where overall growth has been positive but information and related services have failed to keep pace.

Not only have financial intermediation services been the major source of absolute growth in producer services employment, they have also performed better than average across all 184 cities (Fig. 6c). Even where overall producer services employment has declined between 2004-2009, employment in financial intermediation services has expanded so that 153 cities have seen these activities expand. This is by far the best performance by any of the sub-groups of producer services. Perhaps the most disappointing performance is shown by the most knowledge-intensive activities: leasing, and especially, business services (Fig. 6d). Not only does the scatter diagram reveal wide variations between the cities, showing that those locations with the highest overall growth of producer services are also associated with a high growth of leasing and business services, but 57 cities recorded negative growth during the period (compared to 53 cities for producer services overall). Finally, the smallest sub group of scientific, technical services and geological prospecting includes activities that are often found in the largest corporate complexes such as Beijing, Shanghai and Shenzhen. It is therefore not surprising that there is a poor correlation (r 2 =0.152) overall and sub-group employment change and, as for leasing and business services, about one-third of the cities recorded negative employment changes between 2004 and 2009 (Fig. 6e).

In summary, some 54 per cent of the average annual growth of producer services in the Chinese provinces is a function primarily of the size of the urban population (Table 2). The regression analysis, which excludes the four province-level municipalities (Beijing, Tianjin, Shanghai and Chongqing) shows that average annual change in city population (2004)(2005)(2006)(2007)(2008)(2009) and nominal city GVA explain more of the growth a iatio tha a ity s sha e of total p odu e services employment or the change in that share over the five-year period. Some 55 per cent of the variation in the average annual growth of producer services (2004)(2005)(2006)(2007)(2008)(2009) in 58 cities can be explained by city employment in producer se i es 200 a d ea h ity s sha e of total producer services employment (2009) (Table 3). Interestingly, city population (2009), as well as average annual change of city population (2004)(2005)(2006)(2007)(2008)(2009), are less significant explanatory variables. This underlines the significance of cumulative causation for the location and development of producer; cities, irrespective of population size, that have accumulated a significant cluster of producer services (by volume or diversity) tend to attract further rounds of growth and investment that reinforces their initial advantage.

f) Producer services in the case study cities: brief overview

Most of the published case studies of producer services in Chinese cities have focused on their intra-urban location, especially in Shanghai and Guangzhou (Zu et al, 2006;Zhong and Yang, 2008;[START_REF] Han | The spatial distribution of producer services in Shanghai[END_REF][START_REF] Yan | Location of producer services and urban competitiveness: the case of Guangzhou. Sy posiu o P odu e Se i es a d Chi a s Economic and Urban Development[END_REF][START_REF] Yi | The intraurban location of producer services in Guangzhou, China[END_REF][START_REF] Zhong | Geographical research on the flow system of producer services trade: taking Guangzhou as an export city[END_REF]Qin andHan, 2013, Zhou, 2013;[START_REF] Gu | Transformation of urban spatial structure under a service economy: the case of Beijing[END_REF]. There is scope for more research that examines the production and consumption of producer services in cities using information gathered from a sample of firms with establishments in the case study cities for the UrbaChina project.

Given the differences in the population and location of the four case study cities there are considerable variations in the size and structure of the producer services activities in each (Table 4). Services are by far the largest contributor to total GVA in Shanghai which is the dominant se i e ity follo ed y Hua gsha although here it is consumer services linked to tourism that are important. This is evident from the very low proportion of total GVA attributed to producer services (8.9 per cent), less than half the equivalent value for Chongqing and about a quarter of the value for Shanghai (32.7 per cent).

In line with the differences in city population, there is wide variation in the numbers employed in producer services in 2009 (Fig. 7). 2012) have provided some insights on the role of service activities in economic planning and policy. The urban economy and strategies for shaping economic restructuring of the kind that will diversify urban employment or make available to local enterprises the types of knowledge and expertise that will help to make enterprises (primary, secondary and tertiary) more competitive in domestic, but especially international markets, are not at the forefront of research in these cities. The discussions highlighted that urbanization strategy is driven to a considerable extent by the challenges of accommodating the rapid expansion of the urban population. This has overshadowed issues arising from the rapid industrialisation that has been dominated by the growth of manufacturing but, until recently, without a corresponding recognition of the growing importance of services, including producer services. This has remained the case even as cities like Shanghai and Kunming, amongst many others, are heavily engaged in the development of new growth centres beyond the existing city limits. Apart from the challenges that this presents for sustainable urban growth (water, energy, waste management, food production), there are also questions about its relationship with existing and potential producer services activities/employment growth. There is an emphasis on provision of infrastructure and the formation of functional areas such as new towns or new business zones that is not necessarily supportive of the marketization of activities such as producer service. Since in many cities these activities are still relatively immature it is important not to dilute any of the agglomeration economies that are crucial for nurturing their role in urban economic development or, indeed, the market access crucial to providers and clients alike. In many cities, including those like Kunming, the development of the service sector has been relatively slow although, as noted earlier, the growth of leasing and business services is notable. Even so, the ongoing shift towards a form of market economy has made some cities, particularly in the inland provinces, vulnerable to the greater flexibility of location choice for some manufacturing activities (that may previously have made location choices dictated by government directives). If they choose to move away this will hold back the demand for, and discourage the development of, producer service activities.

Tables and figures

  of contents .................................................................................................................................... a) Servicification in China ..................................................................................................................... b) Services and development in China .................................................................................................. c) Why research on producer services is important .............................................................................. d) Diverse role of producer services in urban economic development ................................................... e) Growth of producer services in China: Provinces and selected cities, 2004-2009 ............................. f) Producer services in the case study cities: brief overview ............................................................... References ........................................................................................................................................... Tables and figures .................................................................................................................................

  2005. FedEx, UPS, TNT and DHL constitute the major players in the express service segment; for example, FedEx set up its Asia-Pacific Hub in Guangzhou in 2006 and provides a network covering over 250 cities and TNT s se i e i ludes 200 ities, aki g Chi a its second largest market after Europe. Yet, in certain respects the development of logistics se i es has o falle ehi d Chi a s e o o i growth.

Figure 1 :

 1 Figure 1: Services and producer services share (%) of total city GVA, selected cities, 2009

Figure 3 :Figure 4 :Figure 5 :

 345 Figure 3: City population (2000) and producer services GVA, 2009: by type of service

Figure 6a :

 6a Figure 6a: Average annual change (%) in employment in (1) all producer services and in (2) transport, storage, and post services, 2004-2009 (selected cities)

Figure 6c :

 6c Figure 6c: Average annual change (%) in employment in (1) all producer services and in (2) financial intermediationservices, 2004-2009 (selected cities)

Figure 6e :Figure 7 :R²

 6e7 Figure 6e: Average annual change (%) in employment in (1) all producer services and in (2) scientific research, technical service and geological prospecting services, 2004-2009 (selected cities)

Figure 8 :

 8 Figure 8: Employment in producer services, average annual change (%) (2004-2009: UrbaChina case study cities

Table

  It is clearly very different to the other three cities since leasing and business services have also contracted at an almost comparable average annual rate which is the opposite of the position in Chongqing and Kunming; both have recorded the highest average annual growth rates in these services. They have also grown, but more slowly, in Shanghai where information transmission and related activities, financial intermediation and scientific research have grown faster during the six year period covered here.

	With the exception of Huangshan transport, storage and postal services is the largest overall employer, especially in Shanghai. While leasing and business services are the second largest employer in Kunming ahead of financial intermediation, the latter is prominent in Chongqing, Shanghai and Huangshan. Chongqing and Huangshan are notable for the very low level of employment in leasing and business services compared with Shanghai which, as expected, has almost as many employed in this sector as in financial intermediation. Scientific and related services are notable sources of employment only in Chongqing and Shanghai. Finally, between 2004 and 2009 most of the changes in employment in the different types of producer services in the case study cities have been positive (Fig. 8). Huangshan is the only city where overall producer service employment has declined. There are limits to the extent to which analysis of secondary data on the development of producer services in the wider context of very rapid urbanization in China can provide any meaningful answers to questions such as: how aware of the benefits of using producer services are potential client firms; why have producer services grown and diversified more quickly in some cities; what are the factors contributing to the establishment of new producer service firms in cities as well as to the behaviour and growth of existing firms; what types of firm are the clients of producer services, where are they located, what is the scale of the transactions, what has determined the choice of supplier, and what are the determinants of externalization decisions. In-depth information from a small sample of businesses (suppliers and users of producer services) is the principal way of filling some of the gaps left by an analysis of secondary data. It is also important to understand the local context for the development of producer services and a series of meetings with city officials, corporate representatives and academic colleagues in Kunming and Shanghai (March

Table 1 :

 1 Share (%) of services in value-added: China and selected othereconomies, 1990 and 2010

												Public
	Country	Trade	Hotels and	Transport	Real estate	Communications, finance, and	administration,	Total services
				restaurants	and storage	and dwellings	business services	community,
												personal and
												other services
		1990 2010 1990 2010 1990 2010 1990 2010 1990	2010	1990	2010	1990 2010
	Developing
	Asia
	China	6.8	8.5	1.6	2.1	3.8	4.9	2.1	7.3	9.4	9.4	7.9	11.2	31.5 43 .4
	Hong Kong	21.8	24	3	3.3	7.7	8.1	5.1	5.2	19.4	24.4	30.3	27.9	87.2	92.9
	South Korea	11.8	8.3	2.4	2.4	4.7	4.5	6.5	8.1	11.2	16.4	14.8	19.2	51.5	58.5
	India	11.8	15.1	1	1.4	6.4	6.3	5	6.1	8.7	11	13.3	14.5	46.1	54.7
	OECD
	Japan	12.8	12.3			4.9	4.5	9.4	13	13.6	17.2	19.1	25.7	59.8	72.6
	United States	12.9	11.6	3.4	3.8	3	2.8	12.1	12.2	18.9	25.1	23	24.8	73.4	80.2
	Source: After Noland et al (2012), Extracted from Table 2, 36.

Table 2 :

 2 Multiple regression, with average annual change in producer service employment as the dependent variable, provinces(excluding Tianjin, Shanghai, Beijing and Chongqing)

	Regression Statistics
	Multiple		0.737093
	R. square		0.543305
	Adjusted R. square		0.399086
	Standard error		2.486692
	Observations		26
	ANOVA
	df	SS	MS	F		Significance F
	Regression	6	139.7706	23.2951	3.767216	0.012197
	Residual	19	117.4891	6.183637
	Total	25	257.2597

Table 3 :

 3 Multiple regression, with average annual change in producer services employment as the dependent variable, leading cities

	Regression Statistics
	Multiple R.	0.739995678
	R. square	0.547593604
	Adjusted R. square	0.504092989
	Standard error	3.041532654
	Observations

Table 4 :

 4 Population and GVA (2009): UrbaChina case study cities

						Producer	Producer
	City	Population of urban area (2010)	Total GVA (100 million yuan) (2009)	Services GVA Yuan) (2009) (100 million	Services share (%) of total GVA	services GVA Yuan) (2009) (100 million	services share (%) of total GVA
	Chongqing	5,402,721	6,530.01	2,474.44	37.89	1,042.60	15.97
	Huangshan	1,500,000	266.96	122.99	46.07	23.73	8.89
	Kunming	3,184,580	n.a.	n.a.	n.a.	n.a.	n.a.
	Shanghai	22,315,426	15,046.45	8,930.85	59.36	4,920.55	32.70

UrbaChina, UMR 8173 Chine Corée Japon, 190-198 avenue de France 75244 Paris cedex 13, France urbachina-edition@services.cnrs.fr

Also referred to as servitization, see[START_REF] Neely | The servitization of manufacturing: further evidence[END_REF]. For a recent comprehensive analysis with a strong Asia focus, including empirical examples from China, seeHirakawa et al (2013).

It has been estimated that the servitization rate in China has increased from 1 per cent in 2011 to 20 per cent in 2010(Neely et al, 2011, cited in Bao and Toivenen, 2012, see alsoLiu, 2009, Vandermerwe and[START_REF] Vandermerwe | Servitization of business: adding value by adding services[END_REF].

I dia s liberalization of business services has made it a leading exporter of these services(Kumar and Joseph, 2005).

[START_REF] Li | The Development of producer services and the upgrading of the manufacturing sectors in China[END_REF] cite the interesting case of a study in 2006 by the China Federation of Logistics and Purchasing of the market for logistics services by manufacturing enterprises in China, It emerged that 49 per cent of manufacturers had their own car teams, 46 per cent owned their own warehouses, 48 per cent had their own mechanized offloading facilities, 9 per cent owned elevated or cubic warehouses, 13 per cent had dedicated rail lines, and only 19 per cent of the manufacturers had raw materials logistics managed by third parties.

Excluding real estate. Producer services are classified as: Transport, storage and post: Information transmission, computer services and software; Financial intermediation; Leasing and business services; Scientific research, technical services, and geologic prospecting.


I R Ène Durand

G Éraud

S Énizergues

Marc Sylvestre
email: sylvestr@labri.fr

I Durand
email: idurand@labri.fr

G S Énizergues

TERMINATION OF LINEAR BOUNDED TERM REWRITING SYSTEMS

Keywords: 1998 ACM Subject Classification: regular research paper term rewriting, termination, rewriting strategy

For the whole class of linear term rewriting systems and for each integer k, we define k-bounded rewriting as a restriction of the usual notion of rewriting. We show that the problem of the existence of an infinite k-bounded derivation, called the k-bounded termination problem, is decidable. The k-bounded class (BO(k)) is, by definition, the set of linear systems for which every derivation can be replaced by a k-bounded derivation. In general, the k-bounded termination problem for BO(k) systems is not equivalent to the termination problem. This leads us to define more restricted classes for which those problems are equivalent: the classes BOLP(k) of k-bounded systems that have the length preservation property. By definition, a system is BOLP(k) if every derivation of length n can be replaced by a k-bounded derivation of length n. We define the class BOLP of bounded systems that have the length preservation property as the union of all the BOLP(k) classes. The class BOLP contains (strictly) several already known classes of systems: the inverse left-basic semi-Thue systems, the linear growing term rewriting systems, the inverse Linear-Finite-Path-Ordering systems, the strongly bottom-up systems.

Introduction

General context. A Term-Rewriting System (TRS in short) is said terminating when it does not admit any infinite derivation. Such a property is part of the definition of a complete TRS, which is a useful algebraic notion. This property is also pertinent for TRSs which are models of functional programs or any kind of computational process. The termination-problem is the problem to know whether a given TRS R is terminating or not. It is well-known that this problem is undecidable for general finite TRS ( [START_REF] Huet | On the uniform halting problem for term rewriting systems[END_REF]) and even for quite restricted subclasses of TRS (see [START_REF] Dauchet | Simulation of Turing machines by a regular rewrite rule[END_REF], [START_REF] Matiyasevich | Decision problems for semi-Thue systems with a few rules[END_REF] for example). Nevertheless, because of its importance, many techniques have been developed in order to prove termination of TRSs (see in particular [START_REF] Dershowitz | Rewrite Systems[END_REF],[9, section 1.3], [14, chap. 6]) or even to decide automatically termination, but for specific classes of TRS.

Contents. The present paper follows the last trend of research quoted above: 1-we show that termination is decidable for a particular strategy that we call bounded rewriting, 2-we deduce from this decision procedure that the usual termination problem is decidable for some classes of TRS.

We define a new rewriting strategy for linear systems called bounded rewriting. Let k ∈ N. Intuitively, a derivation is said to be k-bounded (bo(k)) if when a rewriting rule is applied, the parts of the substitution located at a depth greater than k are not used further in the derivation, i.e. do not match a left-handside of a rule applied further. A rewriting system R will be said to be k-bounded (bo(k)) if for any derivation s → * R t, there exists a k-bounded derivation s bo(k) → * R t. The class of k-bounded systems is denoted by BO(k), and the class of bounded systems BO is k∈N BO(k). A rewriting system will be said to bo(k)-terminates if there is no infinite bo(k)derivation. The main result of this paper is the decidability of the bo(k)-termination problem. This rewriting strategy is closely related to the bottom-up strategy introduced in [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF]: every bottom-up system is bounded, and for every bounded system, there is an equivalent system which is bottomup. Both strategies are defined using marking tools, but the definition of the bounded strategy is simpler and more intuitive. For every linear system (R, F) and every integer k, there is a system (R ′ , F) such that ∀n ∈ N,

→ n R =→ n R ′ and bo(k) •→ n R = bo(0) •→ n R ′ .
Thus, it is sufficient to prove that the bo(0)-termination problem is decidable to obtain the decidability of the bo(k)-termination problem, for k ∈ N. Following the idea developed for the bottom-up strategy, we use a ground rewriting system S ∪ A to simulate bo(0)-derivations. This construction is made in such a way that the existence of an infinite bo(0)-derivation in R is equivalent to the existence of an infinite derivation in S ∪ A. It follows from the decidability of the termination problem for ground systems that the bo(0)-termination problem is decidable. The system A has rules which allow to replace any subterm of a term t located at an internal node by a leaf labeled by the constant symbol #, and the system S consists of a set of rules of the form lσ → rσ where l → r ∈ R and σ is a substitution that maps variables to an element of

F 0 ∪ {#}. A bo(0)-step C[lσ] → C[rσ] in R is simulated in two steps : first, using A, we reduce C[lσ] to C[lσ ′ ]
where lσ ′ ∈ LHS(S), and then we apply the rule lσ ′ → rσ ′ ∈ S. We define a subclass of BO(k), the length preservation bottom-up class BOLP(k), for which the termination problem and the k-bounded termination problem are equivalent. A BO(k) system is BOLP(k) iff for every derivation s → * R t there is a bo(k) derivation of same length. The class of length preservation bounded system BOLP is k∈N BOLP(k). This class contains several already known systems: the inverse left-basic semi-Thue systems [START_REF] Sakarovitch | Syntaxe des langages de Chomsky, essai sur le determinisme[END_REF], the linear growing term rewriting systems [START_REF] Jacquemard | Decidable approximations of term rewriting systems[END_REF], the inverse Linear-Finite-Path-Overlapping systems [START_REF] Takai | Right-linear finite path overlapping term rewriting systems effectively preserve recognizability[END_REF], and the strongly bottom-up systems [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF].

Preliminaries

Words and Terms

The set N is the set of positive integers. A finite word over an alphabet A is a map u : [0, ℓ -1] → A, for some ℓ ∈ N. The integer ℓ is the length of the word u and is denoted by |u|. The set of words over A is denoted by A * and endowed with the usual concatenation operation u, v ∈ A * → u • v ∈ A * . The empty word is denoted by ε. A word u is a prefix of a word v iff there exists some w ∈ A * such that v = u • w. We denote by u v the fact that u is a prefix of v. Assuming a total order on A, we denote by Lex the lexicographic order on words.

We assume the reader familiar with terms. We call signature a set F of symbols with fixed arity ar : F → N. The subset of symbols of arity m is denoted by F m . As usual, a set P ⊆ N * is called a tree-domain (or, domain, for short) iff for every u ∈ N * , i ∈ N:

(u • i ∈ P ⇒ u ∈ P ) & (u • (i + 1) ∈ P ⇒ u • i ∈ P ).
We call P ′ ⊆ P a subdomain of P iff, P ′ is a domain and, for every u ∈ P, i ∈ N:

(u • i ∈ P ′ & u • (i + 1) ∈ P ) ⇒ u • (i + 1) ∈ P ′ .
A (first-order) term on a signature F is a partial map t : N * → F whose domain is a non-empty tree-domain and which respects the arities. We denote by T (F, V) the set of first-order terms built upon the signature F ∪ V, where F is a finite signature and V is a denumerable set of variables of arity 0.

The domain of t is also called its set of positions and denoted by Pos(t). The set of variables of t is denoted by Var(t). The root symbol of t, t( ) is also denoted by root(t). The set of variable positions (resp. non variable positions) of a term t is denoted by Pos V (t) (resp. Pos V (t)). The set of leaves of t is the set of positions u ∈ Pos(t) such that u • N ∩ Pos(t) = ∅. It is denoted by Lv(t). We write Pos + (t) for Pos(t)\{ }. Given v ∈ Pos + (t), its father fth(v) is the position u such that v = u • w and |w| = 1. Given a term t and u ∈ Pos(t) the subterm of t at u is denoted by t/u and defined by Pos(t/u) = {w | u • w ∈ Pos(t)} and ∀w ∈ Pos(t/u), t/u(w) = t(u • w). A term which does not contain twice the same variable is called linear. Given a linear term t ∈ T (F, V), x ∈ Var(t), we shall denote by pos(t, x) the position of x in t. The depth of a term t is inductively defined by:

• dpt(t) := 0 if t ∈ V, • dpt(t) := 1 if t ∈ F 0 , • dpt(t) := 1 + max({dpt(t/i )), i ∈ {0 , ..., n}}) if root(t) ∈ F n .
A term containing no variable is called ground. The set of ground terms is T (F). Among all the variables, there is a special one . A term containing exactly one occurrence of is called a context. A context is usually denoted as

C[]. If v is the position of in C[], C[t]
denotes the term C[] where t has been substituted at position v. We also denote by C[] v such a context and by C[t] v the result of the substitution. We denote by |t| := Card(Pos(t)) the size of a term t. A substitution σ is a mapping from V to T (F, V). The substitution σ extends uniquely to a morphism σ : T (F, V) → T (F, V), where σ(f (t 1 , ..., t n )) = f (σ(t 1 ), ..., σ(t n )), for each f ∈ F, t i ∈ T (F, V). Let t be a linear term and Pos V (t) = {u 1 , ..., u n }, where the u i are given in lexicographic order. The term t is said to be standardized if for all i, 1 ≤ i ≤ n, t/u i = x i .

Term rewriting systems

A rewrite rule built upon the signature F is a pair l → r of terms in T (F, V) which satisfies Var(r) ⊆ Var(l). We call l (resp. r) the left-handside (resp. right-handside) of the rule (lhs and rhs for short). A rule is linear if both its left and right-handsides are linear. A rule is left-linear if its left-handside is linear. Given a set of rules R, we denote by LHS(R) the set {l |l → r ∈ R}. A term rewriting system (system for short) is a pair (R, F) where F is a signature and R a set of rewrite rules built upon the signature F such that LHS(R) ∩ V = ∅. When F is clear from the context or contains exactly the symbols of R, we may omit F and write simply R. Given a rewriting system (R, F), and two terms t 1 , t 2 , we say that there exists a R-rewriting step between t 1 and t 2 in R and write t 1 → R t 2 if there exists a context C[], a rule l → r ∈ R, and a substitution σ such that t 1 = C[lσ] and t 2 = C[rσ]. The term lσ is called a redex of t 1 , and rσ is called a contractum of t 1 . Given some n ≥ 0, a derivation in R of length n from s to t is a sequence of the form

s = s 0 → R s 1 → R ... → R s n . The relation → n
R is defined as follows: s → n t if there exists a derivation of length n from s to t. The relation → * R (→ + R ) is defined by: s → * t (s → + t) if there is some n ≥ 0 (n > 0) such that s → n R t. More generally, the notation defined in [START_REF] Klop | Term rewriting systems[END_REF] will be used in proofs.

A system is linear (resp. left-linear) if each of its rules is linear (resp. left-linear). A system R is growing [START_REF] Jacquemard | Decidable approximations of term rewriting systems[END_REF] if for every rule l → r ∈ R, all variables in Var(l) ∩ Var(r) occur at depth 0 or 1 in l. Two rewriting systems (R, F) and (R ′ , F) are said to be equivalent if for all n ≥ 0, → n R =→ n R ′ . A system R is said to terminate if there is no infinite derivation in R.

Bounded rewriting

In order to define bounded rewriting, we need some marking tools. In the following we assume that F is a signature. We shall illustrate many of our definitions with the following system

Example 3.1. F = {a, b, f, g, h, i}, R 1 = {f(x) → g(x), g(h(x)) → i(x), i(x) → a, a → b}.

Marking

We mark the symbols of a term using natural integers.

Marked symbols.

Definition 3.2. We define the (infinite) signature of marked symbols:

F N := {f i | f ∈ F, i ∈ N}.
For j ∈ N, we denote by F ≤j the signature:

F ≤j := {f i | f ∈ F, i ≤ j}.
The mapping m : F N → N maps every marked symbol to its mark: m(f i ) = i.

Marked terms.

Definition 3.3. The terms in T (F N , V) are called marked terms.

The mapping m is extended to marked terms by: if t ∈ V, m(t) := 0, otherwise, m(t) := m(root(t)). For every f ∈ F, we identify f 0 and f ; it follows that

F ⊂ F N , T (F) ⊂ T (F N ) and T (F, V) ⊂ T (F N , V).
We use mmax(t) to denote the maximal mark of a marked term t:

mmax(t) := max{m(t/u) | u ∈ Pos(t)}. Example 3.4. m(a 1 ) = 1, m(i 0 (a 2 )) = 0, m(h 3 (a 0 )) = 3, m(h 1 (x)) = 1, m(x) = 0, mmax(i 0 (a 1 )) = 1, mmax(x) = 0.
Definition 3.5. Given t ∈ T (F N , V) and i ∈ N, we define the marked term t i whose marks are all equal to i:

if t is a variable x t i := x if t is a constant c t i := c i otherwise t = f (t 1 , . . . , t n ), where n ≥ 1 t i := f i (t 1 i , . . . , t n i )
This marking extends to sets of terms S (S i := {t i | t ∈ S}) and substitutions σ (σ i : x → (xσ) i ).

Notation: in the sequel, given a term t ∈ T (F, V), t will always refer to a term of T (F N , V) such that t 0 = t. Definition 3.6. For every marked term t, we denote by t the unique marked term such that:

Pos( t) := Pos(t), ∀u ∈ Pos V (t), m( t/u) := max(m(t/u), |u| + 1).
We extend this definition to marked substitutions ( σ : x → xσ) and sets of terms

( S := { s | s ∈ S}). Example 3.7. Let t 1 = f 0 (f 1 (x)), and t 2 = f 2 (f 2 (h 2 (a 2 ))). We have: t 1 = f 1 (f 2 (x)), t 2 = f 2 (f 2 (h 3 (a 4 ))).

Marked rewriting

Let R be a left-linear system, s ∈ T (F N ). Let us suppose that s decomposes as

s = C[lσ] v , with (l, r) ∈ R, (3.1)
for some marked context C[] v and substitution σ. We then write s •→ t when

s = C[lσ], t = C[r σ]. (3.2)
More precisely, an ordered pair of marked terms (s, t) is linked by the relation •→ iff, there exists C[] v , (l, r), l, σ fulfilling equations (3.1-3.2). (This is illustrated by Figure 1, where the marks are noted between brackets

[. . .]). C C l r s t v [m(s/w)] [0] [k] [max(k, |w| + 1)]
x σ w xσ The map s → s 0 (from marked terms to unmarked terms) extends into a map from marked derivations to unmarked derivations: every

s 0 = C 0 [l 0 σ 0 ] v 0 •→ C 0 [r 0 σ 0 ] v 0 = s 1 •→ . . . •→ C n-1 [r n-1 σ n-1 ] v n-1 = s n (3.3)
is mapped to the derivation

s 0 = C 0 [l 0 σ 0 ] v 0 → C 0 [r 0 σ 0 ] v 0 = s 1 → . . . → C n-1 [r n-1 σ n-1 ] v n-1 = s n . (3.4)
The context C i [] v i , the rule (l i , r i ), the marked version li of l i and the substitution σ i completely determine s i+1 . Thus, for every fixed pair (s 0 , s 0 ), this map is a bijection from the set of derivations (3.3), to the set of derivations (3.4).

From now on, each time we deal with a derivation s → * t between two terms s, t ∈ T (F, V), we may implicitly decompose it as (3.4) where n is the length of the derivation, s = s 0 and t = s n .

Bounded derivations

Definition 3.8. The marked derivation (3.3) is k-bounded (bo(k)) if for every 0 ≤ i < n, mmax(l i ) ≤ k. The derivation (3.4) is bo(k) if the corresponding k-marked derivation (3.3) is bo(k).
In particular, the marked derivation (3.3) is bo(0) iff for every 0 ≤ i < n, l i = l i .

Example 3.9. Let us consider the following derivations in R 1 :

(

1) f(h(a)) → g(h(a)) → i(a) → a (2) f(h(a)) → g(h(a)) → g(h(b)) → i(b) → a The first derivation is bo(1) since the associated marked derivation is bo(1): f(h(a)) •→ g(h 1 (a 2 )) •→ i(a 2 ) •→ a. The second one is bo(2): f(h(a)) •→ g(h 1 (a 2 )) •→ g(h 1 (b)) •→ i(b 1 ) •→ a.
Let k ∈ N. It is clear that the composition of two bo(k) marked derivations is bo(k) too, but the composition of two unmarked bo(k) derivations might not be bo(k), as shown in the following example:

Example 3.10. The two derivations in R 1 : f(h(a)) → g(h(a)) and g(h(a)) → i(a) → a are bo(0) while the derivation: f(h(a)) → g(h(a)) → i(a) → a is not bo(0) (but is bu(1)).
In the following we thus (mainly) manipulate marked bo(k)-derivations. Let us introduce some convenient notations.

bo(k) •→ * R is defined by: s bo(k) •→ * R t iff there exists m ∈ N such that s bo(k) •→ m R t. The binary relation bo(k) → n R over T (F) is defined by: s bo(k) → n R t iff there exists a bo(k)-derivation from s to t of length n. The binary relation bo(k) → * R is defined by: s bo(k) → * R t iff there exists m ∈ N such that s bo(k) → m R t.
Next lemma shows that the study of bo(k)-derivations can be reduced to the study of bo(0)derivations.

Lemma 3.12. Let R be a linear rewriting system and let k > 0. There exists an equivalent linear system R ′ such that: for all n ∈ N, bo(k

) → n R = bo(0) → n R ′ . Sketch of proof. Let R ′ be the rewriting system consisting of the rules: {lσ → rσ | l → r ∈ R, σ : V → T (F, V), lσ is standardized, dpt(σ) ≤ k }.
One can easily check that R ′ is finite, equivalent to R and that, for all n ∈ N, bo(k

) → n R = bo(0) → n R ′ .
Example 3.13. Let us consider the bo(1)-derivation in example 3.9 f(h(a)) → g(h(a)) → i(a) → a and the system R ′ built for R 1 and k = 1. We have:

R ′ ={f(x 1 ) → g(x 1 ), f(f(x 1 )) → g(f(x 1 )), f(g(x 1 )) → g(g(x 1 )), f(h(x 1 )) → g(h(x 1 )), f(i(x 1 )) → g(i(x 1 )), f(a) → g(a), f(b) → g(b), g(h(x 1 )) → i(x 1 ), g(h(f(x 1 ))) → i(f(x 1 )), g(h(g(x 1 ))) → i(g(x 1 )), g(h(h(x 1 ))) → i(h(x 1 )), g(h(i(x 1 ))) → i(i(x 1 )), g(h(a)) → i(a), g(h(b)) → i(b), i(x 1 ) → a, i(f(x 1 )) → a, i(g(x 1 )) → a, i(h(x 1 )) → a, i(i(x 1 )) → a, i(a) → a, i(b) → a, a → b}
and the following bo(0)-derivation in R ′ :

f(h(a)) •→ f(h(x 1 ))→g(h(x 1 )) g(h(a 1 )) •→ h(x 1 )→i(x 1 ) i(a 1 ) •→ i(x 1 )→a a.

Bounded systems

We introduce here a hierarchy of classes of rewriting systems, based on their ability to meet the bounded restriction over derivations. Definition 3.14. Let p be some property of derivations. A system (R, F) is called P if ∀s, t ∈ T (F) such that s → * R t there exists a p-derivation from s to t. We denote by BO(k) the class of BO(k) systems. One can check that, for every k > 0, BO(k -1) BO(k). Finally, the class of bounded systems BO is defined by: BO = k∈N BO(k). The membership problem for BO(k) is shown to be undecidable in the appendix, using a result of [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF]. Definition 3.15. We say that the system R bo(k)-terminates iff there is no infinite bo(k)-derivation in R. The bo(k)-termination problem for a linear system R is the following problem: INSTANCE: A linear system R, and an integer k. QUESTION: Does R bo(k)-terminate ?

The main result of this paper is the decidability of the bo(k)-termination problem.

Simulation of bounded derivations by a ground rewriting system

In this section, we prove that a bo(0)-derivation can be simulated using a ground term rewriting system. Definition 4.1. Let # be a constant such that # / ∈ F 0 . Let A be the (infinite) rewriting system on T (F ∪ {#} N ) consisting of the rules:

{f i (a 1 , . . . , a n ) → # i | i ∈ N, f ∈ F n , n > 0, a 1 , . . . , a n ∈ (F 0 ∪ {#}) N }.
For j ∈ N, we denote by A ≤j the restriction of A on T ((F ∪ {#}) ≤j ) consisting of the rules:

{f i (a 1 , . . . , a n ) → # i | i ≤ j, f ∈ F n , n > 0, a 1 , . . . , a n ∈ (F 0 ∪ {#}) ≤j }. Lemma 4.2. Let s, t ∈ T ((F ∪ {#}) N ). If s → * A t, then s → * A t. Definition 4.3. A marked term t ∈ T ((F ∪ {#}) N , V
) is said to be smoothly-increasing (s-increasing in short) iff for every branch b, the sequence of marks on b has the form: 0, 0, . . . , 0, 1, 2, . . . , ℓ

i.e. more formally: for every w ∈ Lv(t), there exists some u w such that,

• ∀v u, m( t/v) = 0, • ∀v u, ∀i ∈ N, if v • i w then m( t/v • i) = m( t/v) + 1.
A substitution σ is said to be s-increasing if for every x ∈ V, the term xσ is s-increasing.

Note that by definition of a s-increasing term t, and since the variables are all marked by 0, for all positions u ∈ Pos V (t), for all v u, m(t/v) = 0.

Example 4.4. The terms f 0 (h 1 (x)) and f 2 (h 1 (a 2 )) are not s-increasing. The terms f 0 (f 0 (h 1 (a 2 ))) and f 1 (a 2 ) are s-increasing. Proof. Since ∈ V, it is an immediate consequence of the definition of s-increasing.

Lemma 4.6. Let s be a s-increasing term and s bo(0) •→ * R t. The marked term t is s-increasing. Proof. Let us prove that the result holds by induction on n the length of the derivation

s bo(0) •→ * R t. If n = 0, the result holds. Let n > 0. There is a term s n-1 such that s bo(0) •→ n-1 R s n-1 bo(0) •→ R s n .
By induction hypothesis, s n-1 is s-increasing. By definition of a bo(0) marked rewriting step, there exists C[] v , l → r ∈ R and σ such that: s n-1 = C[lσ] v , and t = C[r σ] v . As s n-1 is s-increasing, since m(s n-1 /v) = 0, the context C[] v is s-increasing. By definition of , for every x ∈ Var(r), x σ is s-increasing. Since the term r is s-increasing, several applications of lemma 4.5 at each position u ∈ Pos V (r) show that r σ is s-increasing. We can conclude using the same lemma that C[r σ] v is s-increasing. Definition 4.7. Let t ∈ T ((F ∪ {#}) N , V) be a marked term and P be a subdomain of Pos(t) such that Pos V (t) ⊆ P . We define Red(t, P ) as the unique term such that Pos(t ′ ) = P and such that t → * A Red(t, P ).

The term Red(t, P ) is obtained from t by substituting the subtree t/u by the symbol # m(t/u) , for every position u ∈ P \Lv(t) such that ∀i ∈ N, u • i / ∈ P .

Lemma 4.8. Let t ∈ T ((F ∪ {#}) N , V) and P be a subdomain of Pos(t) such that Pos V (t) ⊆ P .

We have Red( t, P ) = Red(t, P ).

Proof. Since acts only on marks, we have Red( t, P ) 0 = ( Red(t, P )) Note that by definition of a s-increasing term, Topd(t) is a subdomain of t and since for every u ∈ Pos V (t), m(t/u) = 0, we have Pos V (t) ⊆ Topd(t). Definition 4.10 (Top of a term). Let t be a s-increasing term. We denote by Top(t) the term Red(t, Topd(t)).

Example 4.11. Let t 1 = f 0 (h 1 (a 2 )), t 2 = f 0 (h 0 (a 1 )). We have:

Topd(t 1 ) = { , 0}, Topd(t 2 ) = Pos(t 2 ), Top(t 1 ) = f(# 1 ), Top(t 2 ) = t 2 .
Intuitively, the top of a term t will be the only part of t which could be used in a bo(0)-derivation starting on t. We extend this definition to sets of s-increasing terms (Top(S) := {Top(t) | t ∈ S}) and to s-increasing marked substitutions (Top(σ) : x → Top(xσ)). Lemma 4.12. Let C[] v , t 1 be s-increasing and let t = C[t 1 ]. We have:

Top(t) = Top(C[] v )[Top(t 1 )] v .
Proof. By lemma 4.5, t is s-increasing. Since is a variable and since C[] v is s-increasing, for every u v, m(t/u) = 0. So, v ∈ Topd(t), and by definition of Top, the result holds. Lemma 4.13. Let t and σ be s-increasing. We have: Top(tσ) = Top(t)Top(σ).

Proof. This lemma is obtained by applying lemma 4.12 several times at each position v ∈ Pos V (t). 4.0.2. The ground system S. Definition 4.14. We consider the following ground rewriting system S over T ((F ∪ {#}) ≤1 ) consisting of all the rules of the form: lσ → S r σ, where l → r is a rule of R, and

σ : V → (F 0 ∪ {#}) ≤1 .
Note that since σ : V → (F 0 ∪ {#}) ≤1 , by definition of , σ : V → (F 0 ∪ {#}) ≤1 . The system S ∪ A ≤1 will be used to simulate the bo(0)-derivations in R.

4.0.3. Lifting lemma. Lemma 4.15. Let s ′ ∈ T ((F ∪ {#}) N ) , s, t ∈ T ((F ∪ {#}) ≤1 ). Assume that s ′ → * A s → S t. There exists a term t ′ ∈ T ((F ∪ {#}) N ) such that s ′ bo(0) •→ R t ′ → * A t. * bo(0) A * s s ′ t S A t ′ R Figure 2: Lemma 4.15
Proof. We have s → S t. This means that s = C[lσ] v , t = C[r σ] v , for some rule l → r ∈ R, marked context C[] v , and marked substitution σ : V → (F 0 ∪ {#}) ≤1 . Since s ′ → * A s, and since A goes from bottom to top, there exists a context C

′ [] v , a substitution σ ′ such that s ′ is of the form s ′ = C ′ [lσ ′ ] v . with C ′ [] v such that C ′ [] → * A C[],
and σ ′ such that for every x ∈ Var(l),

xσ ′ → * A xσ. By definition of bo(0) •→, s ′ = C ′ [lσ ′ ] v bo(0) •→ R t ′ := C ′ [r σ] v . By Lemma 4.2, for every x ∈ Var(r), x σ ′ → * A x σ. Hence, t ′ = C ′ [r σ ′ ] → * A C[r σ ′ ] → * A C[r σ] = t.
We have built a derivation:

s ′ bo(0) •→ t ′ → * A t.
The result holds. Example 4.16. Let us consider the system S built from the system R 1 .

S = {f(#) → g(# 1 ), f(# 1 ) → g(# 1 ), f(a) → g(a 1 ), f(a 1 ) → g(a 1 ), f(b) → g(b 1 ), f(b 1 ) → g(b 1 ), g(h(#)) → i(# 1 ), g(h(# 1 )) → i(# 1 ), g(h(a)) → i(a 1 ), g(h(a 1 )) → i(a 1 ), g(h(b)) → i(b 1 ), g(h(b 1 )) → i(b 1 ), i(#) → a, i(# 1 ) → a, i(a) → a, i(a 1 ) → a, i(b) → a, i(b 1 ) → a, a → b}.
We have the following derivation:

g(h(a)) → A,a→# g(h(#)) → S,f(h(#))→i(# 1 )) i(# 1 )).
In the proof of lemma 4.15, we build the derivation:

g(h(a)) bo(0) •→ R 1 ,g(h(x))→i(x) i(a 1 )) → A,a 1 →# 1 i(# 1 ).

Projecting lemma.

Lemma 4.17 (projecting lemma). Let s ∈ T (F N ) be s-increasing, and s bo(0) •→ R t. There is a derivation: Top(s) → * A ≤1 → S Top(t). So, τ = Top( σ), and

Top(t) = Top(C[] v )[rTop( σ)] v = Top(C[] v )[r τ ] v .
We have built a derivation: Top(s) → * A ≤1 → S Top(t). The result holds. Example 4.18. Let us consider the system R 1 , S built for this system, and the following bo(0)

rewriting step: s = f(f(g 1 ((a 2 )))) •→ R 1 ,f(x)→h(x) t = h(f 1 (g 2 (a 3 ))).
We have Top(s) = f(f(# 1 )), Top(t) = h(# 1 ), and the following derivation:

f(f(# 1 )) → A ≤1 f(#) → S,f(#)→h(# 1 ) h(# 1 ).

Decidability of the termination

In this section, we prove that the bo(k)-termination problem is decidable. Proof. Assume that S ∪ A ≤1 does not terminate. Then there exists an infinite rewriting sequence of terms in T ((F ∪ {#}) ≤1 ). The system A ≤1 is obviously terminating. Thus, such an infinite derivation contains an infinite number of steps in S and is of the form:

s 0 → * A ≤1 s 1 → S s 2 → * A ≤1 s 3 → S s 4 → * A ≤1 . . . → S s 2n → * A ≤1 .
. . . We now show that repeated applications of lemma 4.15 yields an infinite marked bo(0)-derivation in R: first, consider s 0 → * A ≤1 s 1 → S s 2 . By lemma 4.15 there exists t 1 such that s 0 bo(0

) •→ R t 1 → * A s 2 . Since t 1 → * A s 2 , we can apply lemma 4.15 to t 1 → * A s 3 → S s 4 . We obtain a term t 2 such that s 0 bo(0) •→ R t 1 bo(0) •→ R t 2 → * A s 4 .
Following this process, we obtain an infinite sequence such that s 0 bo(0)

•→ R t 1 bo(0) •→ R t 2 bo(0) •→ R . . . bo(0) •→ R t n . . .. We conclude that R does not terminate.
Proposition 5.2. If R does not bo(0)-terminate, then S ∪ A ≤1 does not terminate.

Proof. If R does not bo(0)-terminate, there is an infinite derivation:

s 0 = s 0 bo(0) •→ R s 1 bo(0) •→ R . . . s n bo(0) •→ R . . . .
The term s 0 is s-increasing since it has no mark. Moreover, the derivation step s 0 bo(0) •→ R s 1 is bo(0). By lemma 4.17, s 0 = Top(s 0 ) → * A ≤1 → S Top(s 1 ). Another application of lemma 4.17 on

s 1 bo(0) •→ R s 2 leads to a derivation: Top(s 0 ) → + S∪A ≤1 Top(s 1 ) → + S∪A ≤1 Top(s 2 )
. Following this process, we obtain an infinite derivation:

Top(s 0 ) → + S∪A ≤1 Top(s 1 ) → + S∪A ≤1 . . . Top(s n ) → + S∪A ≤1 .
. . and S ∪ A ≤1 does not terminate.

Theorem 5.3. The bo(0)-termination problem is decidable. Proof. By propositions 5.1 and 5.2, a linear system R bo(0)-terminates iff the system S ∪ A ≤1 terminates. It is well known that the termination problem for ground systems is decidable (see e.g.[1, page 99-100]) and we can decide whether the system S ∪ A ≤1 terminates. Thus, the bo(0)termination problem is decidable.

Corollary 5.4. The bo(k)-termination problem is decidable.

Proof. It is just a consequence of theorem 5.3 and lemma 3.12.

Note that in general, for a BO(0) system, the bo(0)-termination property and the termination property are not equivalent. Definition 5.5. Let R be a BO(k) system. We say that R has the bo(k) length preservation property if for every n ∈ N:

→ n R = bo(k) → n R .
We denote by BOLP(k) the class of BO(k) systems that have the bo(k) length preservation property. Finally, the class of bounded systems with the length preservation property is denoted by BOLP. One can check that for every k > 0, BOLP(k -1) BO(k).

Example 5.6. Let R 2 = {f(x) → g(x), g(a) → f(a)}. This system is BO(0) but does not have the bo(0) length preservation property. There is a derivation of length 2: f(a) → g(a) → f(a), but there is no bo(0)-derivation of length 2 from f(a) to f(a) (there is one of length 0). Moreover, this system does not terminate but bo(0)-terminates.

Corollary 5.7. The termination problem for systems in BOLP(k) is decidable.

Proof. Let us prove that, for a system R ∈ BOLP(k), the bo(k)-termination and termination are equivalent properties. Clearly, if R does not bo(k) terminate, then the system R does not terminate. Conversly, let us suppose that there is an infinite derivation:

s 0 → R s 1 → R s 2 → R . . . → R s n . . . . Since R has the bo(k) length preservation property, there is for each m ∈ N a marked bo(k)- derivation D m such that D m = s 0 bo(k) •→ m R s m .
The system R has a finite number of rules, so there is only a finite number of possible one step rewriting starting on s 0 . Hence, there exists a term

s ′ 1 such that the set {m ′ | D m ′ = s 0 bo(k) •→ R s ′ 1 bo(k) •→ m ′ -1 R s m ′ } is infinite.
Repeating this process, we obtain an infinite derivation:

s 0 bo(k) •→ R s ′ 1 bo(k) •→ R . . . bo(k) •→ R s ′ n bo(k)
•→ . . . . Hence, the system R does not bo(k)-terminate. We have established that: R bo(k)-terminates ⇔ R terminates. By corollary 5.3, the bo(k)-termination problem is decidable. Hence, the termination problem for systems in BOLP(k) is decidable.

We prove in the appendix that several classes of rewriting systems are (stricly) included in the class of BOLP rewriting systems :

• the inverse left-basic semi-Thue systems (viewed as unary term rewriting systems) [START_REF] Sakarovitch | Syntaxe des langages de Chomsky, essai sur le determinisme[END_REF],

• the linear growing term rewriting systems [START_REF] Jacquemard | Decidable approximations of term rewriting systems[END_REF],

• the inverse Linear-Finite-Path-Overlapping systems [START_REF] Takai | Right-linear finite path overlapping term rewriting systems effectively preserve recognizability[END_REF],

• the strongly bottom-up linear systems [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF]. As a consequence, these systems have a decidable termination problem. Note that, using the same method as the one used to prove the decidability of the termination problem for BOLP(k) systems, one can decide for every R ∈ BOLP(k) and every t ∈ T (F) whether there exists some infinite derivation in R starting from t. It is also shown in the appendix, using a result of [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF], that BO(k) systems inverse preserve rationality.

Related works and perspectives

Related works. We borrowed from [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF] the idea of simulating derivations according to a special strategy by some ground system. Note however, that the class BO(k) itself is new. Its advantages over the class BU(k) is that its definition is simpler, it allows a simpler proof of the projecting lemma and it makes lemma 1 true, while this lemma, mutatis mutandis, does not hold for the class BU(k).

The principle of replacing the original rewriting relation over a signature F by some other binary relation over a marked-alphabet F N was already used in [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF] in order to get an algorithm for termination. However, the two marking mechanisms turn out to be different: -in the case of word rewriting systems, the marked derivation used here is not generated by a semi-Thue system while the marked derivation of [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF] is generated by an (infinite) semi-Thue system; -the direct image of a rational set R by a system which is match-bounded over R is rational while the direct image of a rational set by a BO(0) system needs not be rational; from this point of view our BO(0)-semi-Thue systems resemble the inverses of match-bounded systems (though, they are not comparable for inclusion); -the marking process used here extends naturally to terms while the notion of [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF] seems more difficult to extend to terms (although interesting ways of doing such an extension have been studied in [START_REF] Geser | On tree automata that certify termination of left-linear term rewriting systems[END_REF] and successfully implemented).

Perspectives. Let us mention some natural perspectives of development for this work:

• it is tempting to extend the notion of bounded rewriting (resp. system) to left linear systems. This class would extend the class of growing systems studied in [START_REF] Nagaya | Decidability for left-linear growing term rewriting systems[END_REF]; • we think that the direct image of a context-free language through bounded rewriting is context-free; • the whole class of bounded systems (at least semi-Thue) should have a decidable termination problem; • one should try to devise a class of semi-Thue systems that includes both the class of BO(k) systems and the class of inverses of match-bounded systems, and still possesses the interesting algorithmic properties of these classes. Some work in these directions has been undertaken by the authors. and, m(

s n /u) = max(m( s n-1 /u ′ ), |w 1 | + 1). (A.7) We distinguish two subcases: -case 4.1: m( s n /v) = m( s n-1 /v ′ ).
Then m( s n-1 /v ′ ) > 0, and by induction hyptothesis,

m( s n-1 /u ′ ) -m( s n-1 /v ′ ) ≥ |u ′ | -|v ′ |. By equation (A.7), m( s n /u) ≥ m( s n-1 /u ′ ). Since |u ′ | -|v ′ | = |u| -|v|, m( s n /u) -m( s n /v) = m( s n /u) -m( s n-1 /v ′ ) ≥ m( s n-1 /u) -m( s n-1 /v ′ ) ≥ |u| -|v|. The result holds. -case 4.2: m( s n /v) = |w| + 1. By equation (A.7), m( s n /u) ≥ |w 1 | + 1. Moreover, |w 1 | = |w| + |u| -|v|. Hence, m( s n /u) -m( s n /v) ≥ |w 1 | + 1 -(|w| + 1) = |u| -|v|.

The result holds.

Corollary A.10. If d is wbu, then for all n, 0 ≤ i ≤ n, for every u, v ∈ Pos(s i ),

u v ⇒ m(s i /u) ≤ m(s i /v).
Proof. It is a immediate consequence of the lemma A.9.

Definition A.11. Let t be a marked term. We denote by N u (t) the number of positions v ≺ u such that m(t/v) = m(t/u):

N u (t) := |{v | v ≺ u, m(t/v) = m(t/u)}|.

Note that by lemma

A.8, if d is wbu, for all i, 0 ≤ i ≤ n, N u (s i ) = |u| -|v u |, where v u := inf({v | v u, m(s i /v) = m(s i /u)}). Lemma A.12. If d is wbu, then for all i, 1 ≤ i ≤ n, for all u ∈ Pos(s i ), m( s i /u) ≤ m(s i /u) • e + N u (s i ).
Proof. The proof is made by induction on n the length of the derivation d. If n = 0, s 0 = s 0 = s 0 , and the result holds. Let n > 0. We have to prove that for every u ∈ Pos(s n ),

m( s n /u) ≤ m(s n /u) • e + N u (s n ).
We distinguish three cases.

-case 1:

u ≺ v n-1 or u ⊥ v n-1 . Then, u ∈ Pos V (C[] v n-1 ), and N u (s n ) = N u (s n-1 )
. By induction hypothesis on n -1, the result holds.

-case 2: ∃w ∈ Pos V (r n-1 ) such that u = v n-1 • w. Then, m( s n /u) = m(s n /u) = m(r n-1 /w) = 0, and the result holds.

-case 3: ∃x ∈ Var(r n-1 ), ∃w ∈ Pos(xσ n-1 ) such that u

= v n-1 • pos(r n-1 , x) • w : Let u ′ = v n-1 • pos(l n-1 , x) • w. By definition, m( s n /u) = max(|w| + 1, m( s n-1 /u ′ )), (A.8) By definition of σ n-1 , xσ n-1 = xσ n-1 M (C[l n-1 ] v n-1 , x)
. By lemma A.8, and since l n-1 / ∈ V,

M (C[l n-1 ] v n-1 , x) = M (l n-1 , x) = m(l n-1 /fth(pos(l n-1 , x))) + 1.
Hence, for all w 1 ∈ Pos(xσ n-1 ),

m(xσ n-1 /w 1 ) = m(s n /v n-1 • pos(r n-1 , x) • w 1 ) (A.9) = max(m(s n-1 /v n-1 • pos(l n-1 , x) • w 1 ), m(l n-1 /fth(pos(l n-1 , x))) + 1). Let v := inf{w ′ | w ′ u ′ , m(s n /u) = m(s n /w ′ )}, and let v ′ := inf{w ′ | w ′ u ′ , m(s n-1 /u ′ ) = m(s n-1 /w ′ )}.
We have:

N u (s n ) = |u| -|v| and N u ′ (s n-1 ) = |u ′ | -|v ′ |.
We distinguish three subcases:

-case 3.1: v ′ v n-1 Since d is wbu, m(s n-1 /v n-1 ) = 0. By lemma A.8, m(s n-1 /v ′ ) = 0,

Figure 1 :

 1 Figure 1: A marked rewriting step

Definition 3 . 11 .

 311 Let n, k ∈ N. The binary relation bo(k) • → n R over T (F N ) is defined by: s bo(k) • → n R t iff there exists a bo(k)-marked derivation from s to t of length n. The binary relation

Lemma 4 . 5 .

 45 Let C[] and t be s-increasing. The term C[t] is s-increasing.

Figure 3 :

 3 Figure 3: Projecting lemma

Proposition 5 . 1 .Figure 4 :

 514 Figure 4: Proposition 5.1

  and by definition of v ′ , m(s n-1 /v ′ ) = m(s n-1 /u ′ ). By lemma A.8, for all w 1 u ′ , m(s n-1 /w 1 ) = 0. By equation (A.9), for all w 2 , u w2 v n-1 • pos(r n-1 , x), m(s n /w 2 ) = 1. Moreover, m(s n /v n-1 • fth(pos(r n-1 , x))) = m(r n-1 /fth(pos(r n-1 , x))) = 0, and we have v = v n-1 • pos(r n-1 , x). So, N u (s n ) = |u| -|v n-1 • pos(r n-1 , x)| = |w|.In addition, since m(s n-1 /u ′ ) = 0, by lemma A.7, m( s n-1 /u ′ ) = 0, and by equation (A.8), m( s n /u) = |w| + 1. We thus have:m(s n /u) = 1, m( s n /u) = |w| + 1, N u (s n ) = |w|, and since e ≥ 1, m( s n /u) = m(s n /u) + N u (s n ) ≤ m(s n /u) • e + N u (s n ).The result holds.

Figure 5 :

 5 Figure 5: Lemma A.12, case 3.1.-case 3.2:∃w 1 ∈ Pos V (l n-1 ), |w 1 | ≥ 1 such that v ′ = v n-1 • w 1 . Since d is wbu, m(l n-1 ) = m(s n-1 /v n-1 ) = 0. By definition of v ′ and by lemma A.8, for all w 2 , u ′ w 2 v ′ , m(s n-1 /w 2 ) = m(s n-1 /u ′ ). In particular, m(s n-1 /v n-1 • fth(pos(l n-1 , x))) = m(s n-1 /u ′ ). So, by equation (A.9), for all w 2 , u w 2 v n-1 • pos(r n-1 , x), m(s n /w 2 ) = m(s n-1 /u ′ ) + 1, and since m(s n /v n-1 • fth(pos(r n-1 , x))) = m(r n-1 /fth(pos(r n-1 , x))) = 0, we have v = v n-1 • pos(r n-1 , x). So, N u (s n ) = |u| -|v n-1 • pos(r n-1 , x)| = |w|.In addition, by lemma A.7, since m(s n-1 /v ′ ) > 0, we have m( s n-1 /v ′ ) > 0. By lemma A.9,m( s n-1 /u ′ )m( s n-1 /v ′ ) ≥ |u ′ | -|v ′ |.

  s n-1 /u ′ ) + 1]

Figure 6 : 1 w 1

 611 Figure 6: Lemma A.12, case 3.2.-case 3.3:∃w 1 ∈ Pos(xσ n-1 ) such that v ′ = v n-1 • pos(l n-1 , x) • w 1 .By definition of v ′ , and by lemma A.8, for allw 2 ≺ v ′ , 0 ≤ m(l n-1 /w 2 ) < m(s n-1 /u ′ ). Let z = v n-1 • pos(r n-1 , x) • w 1 . By equation (A.9), for all w 2 , u w 2 •z, m(s n /w 2 ) = m(s n-1 /u ′ ). (A.10) Hence, v v n-1 •pos(r n-1 , x)•w 1 , and there exists w ′ 1 w 1 such that v = v n-1 •pos(r n-1 , x)•w ′ 1 . Since N u ′ (s n-1 ) = |u ′ | -|v ′ | = |w| -|w 1 | and since N u (s n ) = |u| -|v| = |w| -|w ′ 1 |, we have N u (s n ) ≥ N u ′ (s n-1 ). By lemma A.7, since m(s n /z) > 0, we have m( s n /z) > 0, and by lemma A.9, m(s n /u)m( s n /z) ≥ |u| -|z|. By definition, m( s n /z) = max(|w 1 | + 1, m( s n-1 /v ′ )) ≥ |w 1 | + 1and we have:m( s n /u) ≥ m( s n /z) + |u| -|z| ≥ |w 1 | + 1 + |u| -|z|. Since |u| -|z| = |u ′ | -|v ′ | = |w| -|w 1 |, we obtain m( s n /u) ≥ |w 1 | + 1,and by equation (A.9), m( s n /u) = m( s n-1 /u ′ ). We thus have: m(s n /u) = m(s n-1 /u ′ ), m( s n /u) = m( s n-1 /u ′ ), N u (s n ) ≥ N u ′ (s n-1 ).

Appendix A. Appendix

A.1. Bottom-up derivations

The class of BO linear systems is closely related to the class of bottom-up systems BU introduced in [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF] in the following sense: every BU system is BO, and for every BO system, there is an equivalent system which is BU. The BU systems are also defined using marking tools. The marked derivation used to defined BU system will be denoted by ⊲→. Let us recall some of the definitions given in [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF].

The right-action of the monoid (N, max, 0) over the set F N consists in applying the operation max on every mark: for every t ∈ F N , n ∈ N, Pos( t n) := Pos( t), ∀u ∈ Pos( t), m(( t n)/u) := max(m( t/u), n), ( t n) 0 = t0 For every linear marked term t ∈ T (F N , V) and variable x ∈ Var( t), we define: M ( t, x) := sup{m(t/w) | w < pos(t, x)} + 1.

(A.1)

Let s ∈ T (F N ) and t ∈ T , and let us suppose that s ∈ T (F N ) decomposes as

for some marked context C[] v and substitution σ. We define a new marked substitution σ (such that σ 0 = σ 0 ) by: for every x ∈ Var(r),

We then write s ⊲→ t when

(A.4) The map s → s 0 (from marked terms to unmarked terms) extends into a map from marked derivations to unmarked derivations: every derivation d:

is mapped to the derivation d: [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF]). The marked derivation (A.5) is weakly bottom-up if, for every i, 0 ≤ i < n, m(l i ) = 0,.

Definition A.2 ([4]

). The derivation (A.6) is weakly bottom-up if the corresponding marked derivation (A.5) starting on the same term s = s is weakly bottom-up.

We shall abbreviate "weakly bottom-up" to wbu.

Note that a bu(k) derivation is bu -(k + 1).

Sketch of proof. One can check, by induction on n the length of the derivation (A.6), that the associated marked derivation (A.5) satisfies:

If the derivation (A.6) is bu -(k), then the derivation (A.5) satisfies:

Hence, for all j, 0 ≤ j ≤ n, mmax(s j ) ≤ k and the derivation (A.6) is bu(k).

Let us introduce a convenient notation.

Definition A.5. Let k ≥ 1. The binary relation bu(k) ⊲→ * R over T (F N ) is defined by: s bu(k) ⊲→ * R t if and only if there exists a bu(k) marked derivation from s to t. The binary relation bu(k) → * R over T (F) is defined by: s bu(k) → * R t if and only if there exists a bu(k)-derivation from s to t. Lemma A. 6 ([4]). Let R be a linear system and n ∈ N. If s → n R t then there exists a wbu derivation between s and t of length n.

A.2. Bottom-up systems

We denote by BU(k) the class of bu(k) systems, by BU -(k) the class of bu -(k) systems. We define the class of bottom-up systems, denoted BU, by:

By definitions of bu and bu -, for all k > 0, BU(k -1) ⊆ BU -(k). By lemma A.4, for all k ∈ N, BU -(k) ⊆ BU(k). Hence, we have:

A system is said to be strongly bu(k) iff every wbu derivation is bu(k). The class of strongly BU(k) systems is denoted by SBU(k). We define strongly bottom-up systems, denoted SBU by:

A.3. Bottom-up systems and Bounded systems

Before proving the equivalence between BO and BU, we start by giving some technical lemmas. Let us consider d and d: the derivation (A.6), and its associated marked derivation (A.5) using ⊲→. We denote by d the associated derivation using •→:

Proof. We made this proof by induction on n the length of the derivation d. If n = 0, then s n = s n = s n , and the result holds. Let us suppose that n > 0. By induction hypothesis on n -1, for all i, 0 ≤ i ≤ n -1, for all u ∈ Pos(s n-1 ),

Let us prove that for all u ∈ Pos(s n ),

Let u ∈ Pos(s n ). We distinguish three cases.

• case 1:

), and by induction hypothesis,

The result holds.

Then, m(

Then, by definition of σ, m(s n /u) = m(xσ/w) > 0, and by definition of σ, m( s n /u) = m(x σ/w) > 0. The result holds.

Lemma A.8 ([4]

). If d is wbu, the following assertion holds:

Lemma A.9. If d is wbu, the following assertion holds: for all i,

Proof. We make this proof by induction on n. If n = 0, the result holds. Let us suppose that n > 0, and that the result holds for every i, 0 ≤ i ≤ n -1. Let u ∈ Pos(s n ) and let v u. We have to prove that:

Since d is wbu, m(l n-1 ) = 0, and by lemma

The result holds.

There exists w 1 , w w

By induction hypothesis,

Hence,

The result holds.

A.4. Equivalence between bounded systems and bottom-up systems

We are now ready to prove the equivalence between BO and BU.

Lemma A.13. A derivation is bu -(1) iff it is bo(0).

Proof. The derivation (A.6) is bu -(1) iff the marked derivation using ⊲→ satisfies: for every i, l i = l i , and this derivation is bo(0) iff the marked derivation using •→ satisfies: for every i, l i = l i . We conclude using lemma A.7.

Corollary A.14. Every BO(k) system is equivalent to a BU -(1) system.

Proof. It is an immediate consequence of lemmas 3.12, and A.13. Note that the equivalent BU -(1) system can be effectively built.

) and e, we have

Proposition A.16. The classes BO and BU are equivalent in the following sense:

(1) BU ⊆ BO.

(2) For every system R ∈ BO, there is an equivalent system R ′ in BU.

Proof. Since BU = k∈N BU -(k), by lemma A.15, BU ⊆ BO. By corollary A.14, for every system R ∈ BO, there is an equivalent system R ′ ∈ BU -(1). The result holds.

A.5. Some other properties of bounded systems Let us give some properties which directly follow from the equivalence between BU and BO and the results presented in [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF].

Definition A.17. A system (R, F) is said to inverse-preserves rationality if for every recognizable set T ⊆ T (F), the set (→ * R )[T ] := {s ∈ T (F) | ∃t ∈ T, s → * R t} is recognizable too. Theorem A.18 ([4]). Every BU system inverse preserves rationality.

Corollary A.19. Every BO system inverse preserves rationality.

Proof. Using corollary A.14, we can effectively build an equivalent BU -(1) system. We conclude using theorem A.18.

, there is a wbu-derivation of length n. By definition of SBU(k), this derivation is bu(k). Since a bu(k) derivation is bu -(k + 1), by lemma A.15, this derivation is bo((k + 1) • e). This derivation is of length n, and the system R is BOLP((k + 1) • e).

Proposition A.24. The termination problem for systems in SBU is decidable.

Proof. This is an immediate consequence of lemma A.23 and of corollary 5.7.

It is shown in [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF] that classes SBU(k) have a decidable membership problem. Note that SBU ⊂ BOLP, as shown in the following example.

This system is bu(1), and for each k ∈ N we can build a wbu derivation which is not bo(k): f(f(f(f(. . . (a)) . . .) ⊲→ f(f 1 (f 1 . . . (a 1 )) . . .) ⊲→ f(f 2 . . . (a 2 )) . . .) ⊲→ . . . but for every derivation, there is a bo(0)-derivation which has the same length: f(. . . (f(f(f(f(a)) . . .) •→ f(. . . (f(f(f(a 1 )) . . .) •→ f(. . . ((f(f 1 (a 2 )) . . .).

A.6. Some bounded systems

The class of SBU systems, which is included in BOLP, contains several classes of systems [START_REF] Durand | Bottom-up rewriting is inverse recognizability preserving[END_REF]. Among them, there are:

• the inverse left-basic semi-Thue systems (viewed as unary term rewriting systems)

• the linear growing term rewriting systems • the inverse Linear-Finite-Path-Overlapping systems. By corollary 5.7, for all these systems, the termination problem is decidable.

If accepted for publication by RTA, this work will be licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.