Barbara Coello

Loren Brandt

Jean-Pierre Cling

Lionel Fontagné

Jean-Pierre Laffargue

Brian Mccraig

Marta Menendez

Nina Pavcnik

Martin Ravallion

Qy-Toan Do

Marie-Cécile Thirion

Dominique Van De

Trade liberalization and poverty dynamics in Vietnam 2002-2006

Keywords: JEL Classification numbers: C23, I32, O19, O53 trade liberalization, poverty dynamics, Vietnam

This paper shows the evolution of poverty in Vietnam during the deepening of trade liberalization and examines the impact of trade-related variables at the household level. The study is based on a panel dataset of households followed in 2002 , 2004 and 2006. Trade-related . Trade-related variables at the household level are defined as the household specialization in terms of production and employment with respect to the type of jobs (wage earners or self-employed) and sectors (import-competing or exported manufactured goods, services, and in agriculture, rice, exported, subsistence and import-competing crops). For the poor, besides the expected positive impact of working in an export-related sector (in industry and in agriculture), diversification in self-employed non-farm activities appears to have been efficient at alleviating poverty. Moreover, the import-competing sectors (in industry and in agriculture) play also a positive role in poverty alleviation. The latter channel could be hindered in the near future, as Vietnam is now in the process of decreasing its import protection.

Introduction

The impact of trade liberalization on household welfare has been widely debated. Studies based on cross-country data have shown a positive impact of trade on growth and hence, on poverty (Dollar and Kraay, 2004). However, micro evidence at the household level shows that trade creates losers as well as winners [START_REF] Goldberg | Distributional Effects of Globalization in Developing Countries[END_REF]. In this paper we focus on poverty dynamics in an Asian country, Vietnam.

Vietnam has been often cited as an example of a successful economic liberalization and trade opening which managed to improve household welfare. Poverty dropped sharply, from 58% of the population at the start of economic reform to a mere 16% en 2006 [START_REF] Glewwe | Who gained from Vietnam's boom in the 1990's[END_REF]. Meanwhile, inequality either decreased or remained stable. Vietnamese experience in that respect contrasts with that of China where inequality increased during economic reform [START_REF] Ravallion | A Comparative Perspective on Poverty Reduction in Brazil, China and India[END_REF].

Poverty is studied in this paper in a micro-economic perspective, at the household level. A household is deemed poor if his consumption per capita is below a minimum level. Studies on poverty are often based on cross sections and focus mostly on one indicator, the share of poor in the population (the headcount). Here we look not only at the headcount but also at how far is a given household below the minimum level, namely the severity of poverty. Actually, we show that the severity of poverty increased for some household categories between 2002 and 2006, despite the general drop in the share of total population below the poverty line. Indeed, the distribution among the poor themselves matters. Households who remained poor after 2002 are far below the poverty line and could not easily improve their living conditions.

Theoretical analyses have shown the importance of looking at the dynamics of poverty. Recent empirical surveys on poverty have stressed the importance of following poverty mobility with longitudinal data (Dercon and Shapiro, 2009; see also Fall and Menendez, 2009, for developed countries). It matters indeed to know who escape poverty and who is staying behind, who is vulnerable to transient poverty spells or is subject to chronic poverty, especially in times of overall economic reform.

We take stock from the existence of repeated household surveys in Vietnam, where a subset of households were interviewed three times, in 2002, 2004 and 2006. Thus, we are able to follow these households over time and relate their fate to change in contextual trade-related changes.

Previous papers looked at poverty in Vietnam during the 90s, using another available panel dataset which stretched over 1993-1998. We update the results of these papers for the period 2002-2006. The bulk of domestic and export liberalization occurred in the 90s and deepened in the 2000s: textile industry soared, major trade agreements were signed and implemented, beginning with the free trade agreement with the United-States in 2001, and foreign direct investment (FDI) flew in. On the import side, liberalization started only after 2000. This policy turn can matter on income distribution for households up to then protected from foreign competition.

We characterize extensively the nature of the contextual trade-related variables that influence households. We distinguish first between self-employed and wage earners and we take also into account the fact that in a developing country such as Vietnam, an individual might have multiple activities and work part-time for wage, while also being self-employed. We distinguish the trade orientation of the sector one is working in: export industry, import-competing industry, and non-traded services. Moreover, based on a previous paper on rural households [START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF], we extend this characterization to farmers. We thus define agricultural households depending on the market orientation of the crops they produce: import-competing, non-traded crops (subsistence) or exported crops. The latter group is further divided between the main export crops (coffee, pepper, cashew nuts, and tea) and other cash crops. Rice producers appear as a separate category, as rice, which is the main staple in Vietnam, is exported, imported and locally consumed either on the farm or sold on domestic markets.

We relate the change in real per capita expenditure between 2002 and 2006 to household characteristics, location and farm characteristics and change in the trade-related contextual variables.

We then consider specifically as a dependent variable the change in expenditures for households who were poor in 2002. We perform different types of robustness checks. First, we redo the first regression not with the change in the contextual variables between 2002 and 2006, but with their level in 2002.

Second, we consider an alternative definition of job categories. Third, we use a multinomial logit on poverty transitions, and we consider in particular, households who were poor in 2002 and escaped from poverty since then.

We find that in Vietnam, new opportunities that improved the welfare of the general population did not systematically reach the poor. For instance, the extension of formal wage earnings and the rise in exports, both in industry and in agriculture, as well as the growth of the services sector improved the living condition of the population in general. However, those who were poor in 2002 were mostly rural and depending on agriculture. Hence, cash crops exports were important indeed for them, as well as new opportunities in self-employed non agricultural activities, and they also kept relying on importcompeting crops.

Two decades of trade liberalization in Vietnam and its likely impact on household welfare and poverty

The two steps of trade liberalization Economic reform in Vietnam started in 1986 (the Doi Moi). The process involved domestic liberalization, from a state economy to a market oriented one. Agriculture was promoted through decollectivization and a land reform [START_REF] Gallup | The Wage Labor Market and Inequality in Vietnam in the 1990s World Bank Policy Research Working Paper[END_REF], [START_REF] Benjamin | Agriculture and Income Distribution in Rural Vietnam under Economic Reforms: A Tale of Two Regions[END_REF], [START_REF] Minot | Rice Market Liberalization and Poverty in Viet Nam IFPRI Research Report[END_REF] [START_REF] Edmonds | Product Market Integration and Household Labor Supply in a Poor Economy: Evidence from Vietnam[END_REF].

On the trade side, Vietnam gradually turned from an import-substitution policy to an exportpromoting policy. Liberalization occurred in two steps. During the first period, the 1990s, multiple exchange rates were unified, enterprises were allowed to export outside the socialist countries of the Council of Mutual Economic Assistance (CMEA), pro-FDI legislation was passed and a number of regional and multilateral agreements were negotiated. Vietnam joined the ASEAN, the AFTA and became a member of the GATT in 1995. Export quotas were eliminated in 1995 for all commodities except rice. In the process of accession to the WTO, import quotas were gradually transferred into tariffs, except for eight categories of goods (Athukorala 2002;[START_REF] Auffret | Trade Reform in Vietnam Opportunities with Emerging Challenges[END_REF]. The transfer from Non tariff barriers to tariff protection resulted actually in an increase in the level of tariffs, even though some important inputs, such as fertilizer, or later, industrial machinery, experienced a drop in tariffs.

Overall, during the nineties, import tariffs and to a lesser extent export tax, remained complex and subject to temporary rises; import protection of final goods remained at a high level (Figure 1). As a consequence, during this first period, the effects of openness mostly occurred through exports [START_REF] Niimi | Trade Liberalisation and Poverty Dynamics in Vietnam[END_REF][START_REF] Justino | Poverty Dynamics During Trade Reform: Evidence From Rural Vietnam[END_REF][START_REF] Coello | Agriculture and trade liberalization in Vietnam[END_REF].

The signing in 2001 of the bilateral trade agreement with the United States can be seen as the start of the second stage of liberalization. Import protection on final goods started to decline, leading to a competition between domestic and imported products. This trend was further exacerbated with the entry of Vietnam into the WTO in 2007. As a result, the share of trade in Vietnam GDP boomed in the 2000s. Exports and imports of goods and services represented respectively 55% and57% of GDP in 2000, 76% and90% in 2006. FDI also rose substantially, after the requirement of a joint-venture with domestic investors was suppressed after 2000.

Trade liberalization and households: the different channels

In this paper, we focus on the micro linkages going from trade liberalization to households' income (surveyed in [START_REF] Hertel | Predicting the Poverty Impacts of Trade Liberalization: A Survey[END_REF] and [START_REF] Goldberg | Inequality, and Poverty: What Do We Know? Evidence from Recent Trade Liberalization Episodes in Developing Countries[END_REF]). We do not consider macro linkages that would go through the overall stabilization of the economy and growth. We follow and precise the framework described in [START_REF] Winters | Trade Liberalization and Poverty: A Handbook[END_REF]. Trade liberalization hits households through direct and indirect effects. Direct effects go through products (their prices, quantities and number of varieties) and factors markets (wages, employment, and new job opportunities). The indirect effects (not examined in this paper) concern changes in government revenues and social spending. The general framework has been widely applied, and in particular to Vietnam during the 90s [START_REF] Justino | Poverty Dynamics During Trade Reform: Evidence From Rural Vietnam[END_REF]Niimi, Vasudeva-Dutta and Winters, 2007). In the following, we precise this framework in the case of Vietnam during the second stage of trade liberalization.

In the case of Vietnam, the economic structure has changed indeed, but more on the production side than on employment. Despite a rise of industry share in GDP from 23% in 2000 to 40% in 2006, the share of industry in total employment remained barely the same, at around 20%.

Even with stable employment, factor earnings might have increased in industry. However, we must add here a caveat: households where a majority of members are working in export industries count less than 4% of the dataset, almost as much as households involved in import-competing industries. Most households (66%) are dependent on agriculture, even if this proportion is decreasing over time. Last, around one household out of four is dependent on (non-traded) services, and this share is increasing.2 Domestic and trade liberalizations might also have altered the job pattern, namely the share of formal wage jobs [START_REF] Mccraig | Exporting out of poverty : provincial poverty in Vietnam and US market access[END_REF]. Unfortunately, we do not know if a job is informal or not. However we know in the dataset we will be using in this paper, that a mere 11% of households have a majority of their members working for wages (an average household counts four adult members). This proportion increases slightly between 2002 and 2006 (table 1). Most households have a majority of their members in self-employed farm activities (33%), even if this proportion is decreasing over time.

Households with members self-employed in non-farm activities are as numerous as households with wage earners. Last, over 40% of households members engage in multi-activity jobs and this proportion is increasing over time. Typically, this might concern farmers diversifying their activities with petty trading or transport on a part-time basis. Thus, the evolution of self-employment as well as multipleactivity jobs matters for households, and as we will see, more for the poorest.

A particularly significant crop in Vietnam is rice. Rice is the main staple and accounts for more than 68% of the average calories intake in 2006 and even 78% for the poor [START_REF] Glewwe | Impact of rising food prices on poverty and welfare in Vietnam[END_REF].

Rice in Vietnam has a special status, as it is at the same time, exported and imported, sold on domestic market and retained for own consumption by rural households. Besides rice, trade liberalization has promoted export crops such as coffee, pepper or cashew (labeled hereafter, the "main export crops") and farmers who could afford it took advantage of these new opportunities by switching their crop mix [START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF]. For instance, many farmers in Central Highlands have switched to coffee and more recently to cashew (Benjamin and[START_REF] Benjamin | Agriculture and Income Distribution in Rural Vietnam under Economic Reforms: A Tale of Two Regions[END_REF][START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF]. However, half of total agricultural households still live mostly from rice production, 6% from the main export crops, and 29% from other export crops. In addition, 9% of these households are dependent on importcompeting crops (such as maize) that could be affected by the import liberalization in the years to come.

The panel data

Our analysis is based on data from the Vietnam Household Living Standards Surveys (VHLSS) in 2002, 2004 and in 2006. The sample of households interviewed is very large: 30,000 households in the first survey, 9,000 households in the second and 9200 households in the third. All surveys include two questionnaires, one on households and one on the district of residence at the village level. 3 We focus on the panel subset of 1947 households who were followed through 2002-2004-2006. 4 The panel dataset compares well in terms of poverty with national figures and with the entire VHLSS dataset (table A1). According to the General Statistic Office, 28.9% of the population was below the poverty line in 2002. The figures for the same year are similar in the entire household survey (28.4%) and in the panel dataset (29.4%). The evolution of poverty is also similar.. Another hint of the good fit of the panel sample is given with respect to education (table A2). In 2002, 30.9% of the households' heads in the entire survey had no education; they were 31% in the panel sample.

Characterizing household economic activities

We start with the main sector of activity reported by each individual during the last twelve months. We then sum for each household the number of individuals who reported working in different sectors. For that purpose, the ISIC code of any sector was (manually) matched with the SITC classification used in trade data (COMTRADE and GSO statistics). A given sector is then classified as a net exporter or a net importer according to trade flows in 2002. Sectors that could not be matched with the trade data (mostly services) are classified as non-traded. The sector classification is given in table A3.

Household members also report whether they are wage earners or self employed. The latter category is divided between self-employed working on farm and those working in non-farm activities.

Unfortunately due to the questionnaire design, the answers are not exclusive. For instance, among 133 individuals who worked in aquaculture, 32 reported themselves as wage earners, 84 as self-employed and 17 declared themselves both wage earners and self employed.

3 The household questionnaire collects information on household composition, expenditures (disaggregated by types), sources of income, employment and labor force participation, education (literacy, highest diploma, fee exemption), health of (use of health services, health insurance), housing (type of housing, electricity, water source, toilet), assets and durable goods and participation in poverty programs.

We thus define four categories: i) wage earners ii) self-employed on farm iii) self-employed in non-farm activities and iv) "multi-activity". The latter includes all combinations of the former categories: being a wage earner and self-employed on farm; being a wage earner and self-employed in non-farm activities; being self-employed both on farm and out of the farm, etc. As a robustness check, we test an alternative grouping where categories are allowed to be non exclusive (section 7).

As no data relate directly farmers' production to external trade, we use the detailed list of crops grown on farm, as well as their share in total harvest and in total marketed output, and relate them to trade statistics (COMTRADE and GSO). Hence, crops are classified as export-oriented, import-competing or non-traded internationally (those are subsistence crops, often retained for own consumption).

Among export crops, we further distinguish the main export crops which represent the bulk of Vietnam agricultural exports (such as tea, coffee, rubber, pepper and cashew). 5 Rice, the main staple in Vietnam, is classified as a category on its own, as it is at the same time, exported, imported, locally consumed and retained for own consumption.

We are quite confident that households who grow main export crops are indeed mostly producing for international markets. [START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF] has shown that in 2002, cash crop producers sold on average more than 78% of their harvest, while households growing subsistence crops sold only 30% of their harvest, retaining the rest for own consumption. The corresponding share for rice producers is even lower, at 24% on average.

Consumer price index

Expenditures are deflated using an index that we have computed specifically. We start from regional and monthly indices of the cost of living, so as to take into account the spatial and time variation that occurred during the period the survey was conducted. 6 The structure of expenditures and hence, the cost of living differ according to the position of a given household in the income distribution. Thus the shares of food and non-food consumption in the consumer price index differ by expenditures quintiles.

The method

Poverty

We use the concept of absolute poverty. Households are defined as poor if their real per capita expenditure is lower than the official poverty line. 7 The Foster-Greer-Thorbecke (FGT) class of poverty indices writes: where N is the population size, z is the poverty line, the per capita expenditures of the i th household, I a dummy variable that takes the value of one if the condition is true and zero otherwise and α a poverty aversion parameter.

The headcount ratio represents the share of poor in total population. It is a particular case of the FGT index, where α is set to 0. Hence, it does not take into account the degree of poverty, and will not be affected by a policy that would further impoverish the poor. We also examine the severity of poverty, that is, the FGT index with α=2 (also named the squared poverty gap) that puts a greater weight on the poorest and is sensitive to the distribution below the poverty line. 8 We also look at poverty dynamics: a household can be either poor or not poor in 2002 and transit in or out poverty in 2004 and in 2006. The panel dataset provides a rare opportunity to compute these poverty transitions.

Econometric analysis

The econometric framework relates real per capita expenditures to households and local districts' characteristics as well as trade-related contextual variables. We estimate a linear regression on panel data, in a reduced form, such as:

where is the level of real per capita expenditure of household i in year t, its change between 2002 and 2004, or 2004 and 2006. is a household fixed effect, are household variables that do not vary over time and control for initial endowments, is a vector of districts controls (that can be seen as the endowment in public goods). are the contextual variables that 7 In 2002 the official poverty line was set at 1,916,000 Dongs; in 2004, at 2,077 000 Dongs and in 2006 at 2,559 000 Dongs.

8 Another usual index is the poverty-gap (FGT with α=1), which represents the share of income needed in order to bring all poor at the level of the poverty threshold. Poverty gap provides similar results (not reported here).

vary over time and relate to households' sources of income (type of occupation, sector, and crops grown).

Regressions are performed first on the whole population of the panel dataset, and next, specifically on farmers.9 Contextual variables are first introduced per se (job types and sectors separately), then, as interacted variables (e.g. "wage earners working in export industries").

The continuous approach, with the change in expenditures as the dependent variable, allows studying the impact of trade liberalization (here, taken as the change in the level of trade-related contextual variables). However, it assumes the same coefficients throughout the distribution. Thus, we also run the continuous regression on a sample restricted to households who were poor in 2002.

Table 2 details the variables and gives some descriptive statistics, with variables considered as the base category in the regression marked in parenthesis. Trade-related variables at the household level might of course be linked to other household characteristics. However, it is not in a linear and simple way. Table A4 shows households' sector and job types by the level of education of the household head (as a proxy for each household member's education). As could be expected, households with a majority of members earning wages are better educated (53.6% of household head have more than a primary education). However, households specialized in self-employed non-farm activities are not far below (47%). Regarding sectors, households with a majority of members in nontraded services are the most educated; households in import industries and agriculture share the same polarized pattern with respect to education of the head: they have either more than a primary education or on the contrary have not even completed primary education. Surprisingly, households specialized in export industries are the less skilled of all.

Robustness

We perform various robustness checks. First, we regress the change in expenditures to the level of all variables in 2002, including the contextual ones. We have also mentioned in the previous section, a second robustness check, which consists in changing the classification of job types and allowing them to be non exclusive (the "multi-activity" category disappears).10

A third robustness check uses a discrete regression, with poverty transitions as the dependent variable. This discrete form is usual in the literature and allows different coefficients depending on the poverty status. However, results may not be robust to a change in the level of the poverty line itself or to measurement errors that are frequent in household surveys [START_REF] Glewwe | How much of observed economic mobility is measurement error ? a method to reduce measurement error bias, with an application to Vietnam[END_REF][START_REF] Glewwe | Was Vietnam's Economic growth in the 1990's pro-poor ? an analysis of panel data from Vietnam[END_REF]. Moreover, crossing the poverty line changes the headcount, and hence, the type of transition, despite the fact that it could not mean much for the actual household [START_REF] Ravallion | Issues in Measuring and Modelling Poverty[END_REF]. That explains why our preferred specification is the continuous one.

In the discrete approach, we use a multinomial logit regression on the probability of staying, exiting or entering into poverty. The multinomial logit model states that the probability that a household i is in state k is given by:

We examine the poverty transitions between Vietnamese regions (figure A1) are historically very different: the South has been inhabited by Northern pioneers and was deeply influenced by the French and the American. Thus, regional differences mattered for economic growth in the 1990s (Brandt and [START_REF] Benjamin | Agriculture and Income Distribution in Rural Vietnam under Economic Reforms: A Tale of Two Regions[END_REF]; [START_REF] Coello | Agriculture and trade liberalization in Vietnam[END_REF]).

As 12 At least 19 people were killed and 10 others were left missing, the damages from the storm were estimated to be at least $11 million (2005 USD) (Source Emergency Events Database EM-DAT).

period 1993-98, [START_REF] Glewwe | Who gained from Vietnam's boom in the 1990's[END_REF] found that 28.7% of the population was "permanent" poor; 39% were "permanent" non poor, 27.4% exited poverty and 4.8% entered into poverty. Hence, in the 2000s, most of the population has escaped poverty "permanently" at least in a four-year period.

However, the share of "permanent" poor is not negligible, and the share of entry into poverty is quite constant in the 1990s and in the 2000s. And there is still a huge discrepancy between rural and urban areas (lines 10 and 11). 91% of urban households stay out of poverty during the period, while only 61% of rural households did so. 5% of rural households entered into poverty while it was the case for only 1.6% of urban households. 13The percentage of households going out of poverty

Trade liberalization and change in household expenditures

We now turn to the determinants of the expenditure growth in 2002-06 (table 5). The summary With respect to household characteristics, the estimation results are in line with the descriptive statistics and with previous studies for the period 1993-98. The number of adults (male and female) has a positive impact on the increase in per capita expenditure between 2002 and 2006, contrary to the number of children. Being married is associated positively with income change, while belonging to an ethnic minority (non Kin) is negatively linked to income change. Other variables are less intuitive: having a woman as a household head, or having only completed primary education are associated positively with income changes. This positive effects could be related to the extent of overall growth in Vietnam which gave a chance to everybody. Location characteristics are also understandable: North Central region (hit by the typhoon) is associated with a negative income change, while the South (South East and the Mekong River) is associated with a positive income change. On the subsample of farmers, an increase in expenditure is associated with formal ownership (a larger share of land protected by a formal title of property) and with crops diversification.

We now turn to the effect of the change in trade-related contextual variables. As expected, households with a larger number of persons working in export manufacturing industries, or farmers who have increased their specialization in export crops experience a rise in per capita expenditure.

However, it is also the case for households involved in import-competing manufacture, or non-tradedservices, as well as for farmers producing subsistence (non-traded) crops. Rice is a special case, as every farmer grows some rice. Thus, being a net producer of rice is associated negatively to income change. However, if the rice net producer owns a large plot, he is likely to experience a rise in income.

Hence, trade openness has a distributional impact in the rice sector, differentiating between large and small producers. Overall, it seems that the benefit of the general growth of the economy exceeded the differential sectoral impact entailed by trade openness. In that context, it is interesting to note that households who increased their participation in multi-activity jobs experienced a decrease in their consumption growth. Thus, some specialization was needed to reap the benefits of overall growth, at least for the population as a whole.

When we restrict the analysis to households who were poor in 2002, the picture is somewhat different (table 6). The main results of the determinants of the consumption of the poor are presented in the summary table below, which also highlights the differences in the determinants of the consumption of the poor, compared to those of the general population.

Regarding household characteristics, gender seems to matter specifically on the consumption of poor households: having a larger share of adult female in the family is now clearly negatively correlated with expenditures; and having a woman as a household head has no longer a significant positive impact. Concerning the type of jobs, poor benefit indeed, as the total population, from export oriented industry and agriculture. However, for them, having some members earning wages is clearly linked to a decrease in income per capita (though the impact is still negative, but not significant anymore when variables interacting wage earnings and sector are added). In addition, poor farmers benefit not only from export crops, but also from import-competing crops (such as maize), which was not the case for the average household. Interestingly enough, even on the subsample of poor households, being a net producer of rice is still associated negatively to income. What matters for income change is the size of the plot. Finally, poor households benefit from being not specialized in one type of jobs and pursuing part-time multiple activities, contrary to the ordinary household in the total population. bold and * : sign changes when poor compared to total population. italics and in parenthesis : not significant anymore in the subsample of the poor, compared to total population. a positive when variables interacted with sector are added. b : not significant when interacted variables are added

The picture that emerges from the econometric exercise is more complex than what a simple trade theory would predict. Indeed, exports both in industry and in agriculture matters. But poverty is not directly alleviated by the rise of a formal wages sector in for instance textile industry. As most of the poor are in rural areas and rely on agriculture, they benefit from market opportunities for the crops they produce as well as from new job opportunities in rural areas, such as transport or trading, in which they can involve on a part-time basis.

Robustness analysis

The first robustness check replicates the main regression, on all variables as of 2002 (table A5).

Contextual variables are not anymore taken as changes between 2002 and 2006, but simply as their levels in 2002. Thus in this regression, we test how much the initial exposure to trade explains later performances. Actually, initial characteristics explain little of the subsequent change in expenditures: the R-squared drops from 54% in table 5 to 5%. Most contextual variables change sign even though they are not anymore significant. Working in the export industry in 2002 has a significant negative impact on subsequent consumption change. There are only two exceptions. First a specialization in main export crops still benefit farmers. Second, farmers involved in multi-activity jobs experience a decrease in their consumption growth. What can be inferred from this exercise is that the change in job opportunities in Vietnam during 2002 and 2006 in a broad sense (job types and sectors) was so significant that it has somewhat leveled the playing field. Initial positions in 2002 did not matter in determining subsequent income gains.

A second robustness check consists in running the main estimation with an alternative definition of the types of jobs that allow for overlaps: an individual can be counted twice in two different categories (table A6). Results are similar to table 5 when no interacted variables are added. When the latter are added, the positive effect of self-employed non-farm activities attenuates. In parallel, wage jobs (but now, possibly mixed with self-employed profits) appear as having a strong positive impact, in any sector. Earning wages in import-competing industries and in services is positive for all households and not only for the sole farmers as in the main estimation. And wage jobs in export industry have now a positive impact for farmers. These results add to the point made above, of the complementing role of part-time activities.

The third robustness analysis examines the determinants of poverty transitions (table A7). In the multinomial logit, all results are given relative to the base category, which is a household who stays poor in both periods. Among the three poverty transitions, we will be particularly interested in the transition out of poverty of households who were initially poor. This transition compares quite well to the evolution of households who were poor in 2002, examined in table 6, even though they concern both the 2002-04 and the 2004-06 transitions. This notwithstanding, the main results of the transition out of poverty is presented in the summary table below.

variables that increase the probability of escaping poverty variables that decrease the probability of escaping poverty household characteristics share of adult male share of adult female household head has a primary education share of children household head has a secondary education being of an ethnic minority The determinants of the transition out of poverty fit quite well with the determinants of consumption growth of poor households. In both specifications, the share of adult male in the household, the education of household head (primary or secondary education) or living in the southern region (South East or Mekong river) are associated either with consumption growth or with a transition out of poverty. On the contrary, the share of adult female, the share of children, being of an ethnic minority, living in the North Central coast either impact negatively consumption growth or decrease the chance of escaping poverty.

The contextual variables give also similar results in both specifications. The number of wage earners in the family decrease the probability of escaping poverty, a paradoxical result already noted in the main estimation with poor's consumption growth as the dependent variable. More precisely, wage earnings in services and import-competing industries raise the chances of getting out of poverty.

Farmers owning a large plot, growing main export crops or rice or even import-competing crops have also a higher chance of escaping poverty. Hence, the significance of import-competing crops on poverty alleviation that was stressed in the consumption regression seems confirmed here. What is not confirmed in the multinomial logit is the role of self-employed non-farm activities and multi-activity jobs in the transition out of poverty. Coefficients have the right sign but are no longer significant.

Actually, these variables matter significantly for households who stayed out of poverty all the time. First, as in the decade before, all activities (in industry as well as in agriculture) related to exports benefitted from trade openness. Moreover, unexpectedly, households involved in non-traded services and even in import-competing industry also gained.

Conclusion

Trade openness increased inequality among rice producers: it benefitted large producers, while it had a negative impact on small net producers. Farmers who intensified their specialization in the main exported crops (such as coffee, tea, cashew, pepper and rubber) obviously gained. But poor households also were better off if they were growing other crops such as maize, which was still protected at that time.

A robust and un-expected result is the negative effect of wage earnings per se on household consumption growth. The positive effect of trade openness on households did not occur through textbook channels such as the rise in (formal) unskilled wage jobs. Most households in Vietnam are still living in rural areas and working in agriculture. For them, poverty alleviation went through a rise in export crops production and a diversification of income sources, for instance, to non-farm selfemployed (and often part-time) jobs. Wage earnings benefitted households not on all circumstances, but only depending on the sectors of employment. Last, besides exports, the import-competing sectors (in industry and in agriculture) played also a positive role in poverty alleviation. The latter channel could be hindered in the near future, as Vietnam is now in the process of decreasing its import protection.

TABLES

  Figures 2 to 4 show the distribution of household expenditures per capita in Vietnam, in 2002, 2004 and 2006. The curves shifted to the right, especially between 2004 and 2006, the more so for food expenditures.

Figure 5

 5 Figure5shows the kernel distribution of the relative distance of the per capita expenditure of the poor (in logarithm) to the poverty line. The relative distance to the poverty line is constructed exclusively on poor households. Within the poor, we measure the absolute difference between the households' expenditure per capita and the official poverty line, divided by the official poverty line.The curve clearly shifts to the right in 2002-2006, meaning that the poor are moving farther below the poverty line. In other words, and in contradiction with the picture given by the headcount index alone, the poor in 2006 are less well off than the poor in 2002.

  Vietnam trade liberalization occurred in two sub-periods. The first stage corresponded to the initial opening of the country in the nineties. It has been crucial for poverty alleviation and has been extensively studied. However this first stage of trade opening concerned mostly exports, while domestic production and import-competing sectors were largely unaffected. In this paper, we explore the impact of the second stage of trade liberalization in the 2000s, as Vietnam deepens its openness to foreign competition, because of its involvement in a network of reciprocal trade agreements and its accession to the WTO.This paper shows the evolution of poverty in Vietnam during the deepening of trade liberalization and examines the impact of trade-related contextual variables, on occupational and crops choice, at the household level. Poverty decrease significantly during 2002 and 2006. However, this overall change hides a worsening of living conditions among the poor themselves especially in some regions (the North Central Coast) and some categories, among them, households involved in export and import industries.In 2002-2006, Vietnamese households were impacted by external trade through different channels.

FIGURESFigure 1 .

 1 FIGURES

Figure 2 .

 2 Figure 2. Kernel density function of the expenditure per capita by year

  Figure 4. Kernel density function of the non food consumption per capita by year

Figure A1 .

 A1 Figure A1. Vietnam administrative regions

  regards poverty incidence, the poorest regions in 2002 were the North West (57% of the population were below the poverty line) and Central Highlands (57.9%) followed by North Central coast (41.4%) and North East (38.9%). In 2006, the North West has still a poverty incidence of 40.2%, but the other regions, and especially, the Central Highlands, have experienced a tremendous drop in poverty. This can be related to the specialization of Central Highlands in cash crop production[START_REF] Benjamin | Vietnam crop output report 1993-2006[END_REF][START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF]). The Central Coast in general and North Central Coast in particular is often affected by natural disasters, for instance, in 2005 by the Kai-Tak typhoon. 12 As a result, the headcount decreased only slightly between 2004 and 2006 in North Central Coast and in the North East, and increased slightly in the South East. The severity of poverty even increased in 2004-2006 in the North What is more unintuitive, is that the distribution among the poor matters. Poverty incidence decreased from 19 % in 2002 to 13% in 2006 for households working in export industries. However, the same households saw the severity of poverty increase in the meantime, from 0.6% in 2002 to 1.5% in 2006, particularly in 2004-2006. Households working in import industries also saw the severity of poverty slightly increase during this period.

	Central Coast.
	Table 4 shows the transitions in and out poverty during 2002-2006. Almost 13% of the
	population remains poor during the four years under study (third line). At the other extreme,
	"permanent" non-poor represent more than 71% of the panel households. The share of transitions out
	of poverty (11.2%) is more than double the share of transition into poverty (4.3%). In the 90s, for the

Poverty seems also related to low education, being in a household whose head is a woman and being from an ethnic minority. As regards activity, poverty is linked to being a farmer, growing main export crops (coffee, cashew, nuts, tea, pepper), as well as import-competing crops or rice. Again, poverty drops most among farmers growing export crops. It also dropped hugely for households in non-traded services, while it actually increased in 2004-2006 for households involved in import competing industries. These descriptive correlations seem to be in line with the expected effects of trade liberalization.

11

Comparable figures in 1993 are 66.4% in rural areas and 25.5% in urban areas

(resp. 45.5% and 9.2% in 1998)

.

Table 2 :

 2 Variables definition and statistics

			2002		2004	2006
	in percentage	P0	P2	P0	P2	P0	P2
	All	29.38	2.50	19.05	1.61	15.46	1.28
	Rural	34.83	2.97	22.68	1.93	18.32	1.55
	Urban	8.82	0.74	5.39	0.39	4.66	0.27
	Red River Delta	21.77	1.21	12.37	0.57	8.06	0.51
	North East	38.95	3.21	25.96	2.16	24.91	1.73
	North West	57.32	9.90	52.44	6.43	40.24	5.11
	North Central Coast	41.39	2.75	26.64	2.16	25.00	2.27
	South Central Coast	22.40	1.61	15.10	1.68	11.98	0.88
	Central Highlands	57.94	7.36	35.71	4.21	25.40	3.30
	South East	15.42	1.15	5.73	0.56	6.17	0.46
	Mekong River Delta	19.33	1.27	13.37	0.64	8.83	0.38
	no diploma	40.16	4.50	31.34	3.27	26.30	2.42
	Primary	30.71	2.30	19.60	1.24	14.75	1.32
	secondary and upper	20.20	1.08	9.18	0.54	7.47	0.38
	Kinh	22.69	1.33	12.98	0.70	10.32	0.65
	Ethnic minority	67.59	9.23	53.79	6.80	44.83	4.92
	Consumer	15.50	1.20	10.71	0.63	8.75	0.62
	Producer	38.53	3.36	24.91	2.30	20.62	1.80
	Hsld head is a male	23.11	1.78	15.33	1.06	12.97	1.25
	Hsld head is a female	31.12	2.71	20.09	1.76	16.15	1.29
	Export industry	19.75	0.83	11.96	0.62	13.46	1.48
	Import industry	9.09	0.55	3.45	0.40	7.69	0.57
	Non-traded services	7.74	0.46	4.30	0.24	2.99	0.13
	Agriculture	38.20	3.39	26.15	2.28	21.84	1.86
	Wage earner	9.57	0.88	10.14	0.40	9.64	0.51
	Self employed on farm	38.58	3.84	25.99	2.38	19.90	1.93
	Self employed non-farm	8.66	0.37	3.54	0.21	1.27	0.03
	Multi-activity	32.32	2.34	20.12	1.69	17.93	1.40
	Main export crops	40.50	3.57	20.93	1.53	10.62	0.74
	Rice	38.22	3.21	24.15	2.26	20.56	1.62
	Non traded crops	18.18	1.70	14.12	1.04	11.65	0.79
	Import-competing crops	38.55	3.87	28.13	2.41	22.35	2.85
	Other export crops	12.48	0.90	8.32	0.42	6.62	0.44
	Table 3. Poverty indices by socioeconomic characteristics
		Note : P0 headcount P2 severity of poverty

Table 4 .

 4 Poverty transitionsNote: The year reported on the second column is the initial year of the transition. Thus row one shows the transition from year 2002 to year 2004 and row two from year 2004 to year2006. A row sums up to 100. Number of households in each category is in parenthesis.

	No	No	Yes	No	Yes

Table 5 .

 5 Determinants of consumption growth (2002Determinants of consumption growth ( -2006) ) Note : dependent variable : real per capita expenditures. A * (resp ** and ****) show significance at 90% (95%, 99%) of confidence. Standard errors in brackets.

Table A4 :

 A4 Households' sector and education

		no education	primary	more than primary
	Majority of household members in:
	Export industry	45.68	24.69	29.63
	Import industry	33.33	28.79	37.88
	Non traded industry and services	21.24	22.79	55.97
	Agriculture	35.61	26.19	38.2
	Total	32.61	25.42	41.96
	Majority of household members are:
	Wage earners	25.84	20.57	53.59
	Self employed on farm	35.65	27.3	37.05
	Self employed in non-farm activities	28.14	24.68	47.19
	Multi-activity	32.95	25.22	41.83
	Total	32.61	25.42	41.96

The dataset is detailed in the next section.

The panel linkage dataset was provided by Brian McCraig. The one provided by the statistical institute (GSO) showed some inconsistencies.

Harvests are valued in Vietnamese dongs, following[START_REF] Coello | Impact of exports liberalization and specialization in cash crop what are the expected gains for Vietnamese households[END_REF] and Brandt,[START_REF] Benjamin | Vietnam crop output report 1993-2006[END_REF].

The regional and monthly consumer price indices were provided by Loren Brandt.

We also ran the same estimations on farmers controlling for the type of crops grown (such as cereals, fruits, annuals, perennials and vegetables). Results are similar and can be provided on request.

Regressions (not presented in the paper) were also performed without any contextual variables and generated similar results for the household and location characteristics.

The corresponding figures for rural areas in the same years(Justino and Lichfield 2003) were respectively, 33.9% (permanent poor), 31.1% (permanent non poor), 29.7% (out of poverty) and 5.4% (into poverty).

[0.0321]

 (2002-2004, or 2004-2006)as the dependent variable. p np (poor in the first year, non poor in the last year) ; np p (non poor in the first year poor in the last year) ;np np (remaining out of poverty on both years), base category is remaining poor. real per capita expenditures. . The table shows the relative risk ratios. A * (resp ** and ****) show significance at 90% (95%, 99%) of confidence. Standard errors in brackets.

Columns 2 and 5 are the basis of the summary table in the text.


Mariusz Grech
email: mariusz.grech@math.uni.wroc.pl

Andrezj Kisielewicz
email: andrzej.kisielewicz@math.uni.wroc.pl

The Černý conjecture for automata respecting intervals of a directed graph

Keywords:

The Černý's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n -1) 2 . We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.

In this paper we consider finite (deterministic complete) automata A = Q, Σ, δ with the state set Q, the input alphabet Σ, and the transition function δ : Q × Σ → Q. The transition function defines the action of the letters in Σ on Q, which, in this paper, is denoted simply by concatenation: δ(q, a) = qa. The action extends in a natural way to the words in Σ * , and we use the same notation qw = δ(q, w). Accordingly, we write Qw = {qw : q ∈ Q}.

The automaton A is called synchronizing if there exists a word w ∈ Σ * such that |Qw| = 1 (in other words, w resets A sending all the states into one particular state). Such a word w is called synchronizing (or a reset word) for A. The problem of synchronization is very natural and its various aspects are considered in the literature (see e.g. [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF][START_REF] Mateescu | Many-valued truth functions, Černý's conjecture and road coloring[END_REF][START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF] for general information and further references). The most famous is the following conjecture due to Černý.

Conjecture (Jan Černý 1964, [START_REF] Černý | Poznámka k. homogénnym experimentom s konecnými automatmi[END_REF]) If a deterministic finite n-state automaton A = Q, Σ, δ is synchronizing, then it has a reset word of length ≤ (n -1) 2 . This conjecture is considered as one of the most longstanding open problems in the theory of finite automata. The consequent research includes verifying the conjecture for various classes of automata, establishing bounds for the length of reset words, investigating natural algorithmic and complexity questions, and many other related problems. For more detailed discussion we refer the reader to the most recent survey [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF] by Volkov. Here, we mention only the most important results proving the conjecture in special cases.

In 1978, Pin [START_REF] Pin | Sur un cas particulier de la conjecture de Černý[END_REF] proved the conjecture for circular automata with a prime number of states (an automaton is circular if it has a letter acting as a cyclic permutation of all the states). In 1990, Eppstein [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] proved the conjecture for orientable automata (preserving a given cyclic ordering of all the states). In 1998, Dubuc [START_REF] Dubuc | Les automates circulaires et la conjecture de Černý[END_REF], completing his earlier research, has verified the conjecture for all circular automata. In 2001, Kari [START_REF] Kari | Synchronizing finite automata on Eulerian digraphs[END_REF] verifies the conjecture for eulerian automata (whose transition digraph is eulerian). In 2003, Ananichiev and Volkov [START_REF] Ananichev | Synchronizing monotonic automata[END_REF] prove the conjecture for monotonic automata (preserving a linear order of the states), and in 2005 they generalize their result to a broader class given by a certain multi-level construction [START_REF] Ananichev | Synchronizing generalized monotonic automata[END_REF]. In 2007, Trahtman [START_REF] Trahtman | The Černý Conjecture for Aperiodic Automata[END_REF] demonstrates that the conjecture is true for aperiodic automata (ones with the transition monoid having no nontrivial subgroups). In 2008, Almeida, Margolis, Steinberg, and Volkov [START_REF] Almeida | Representation theory of finite semigroups, semigroup radicals and formal language theory Trans[END_REF] verify the conjecture for another class of automata related to the formal language theory: those with monoids belonging to DS class. In 2009, Volkov [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF] proves the conjecture for the so-called weakly monotonic automata, a certain strong generalization of generalized monotonic automata including the automata preserving a connected partial order. Most recently, in 2011, Steinberg [START_REF] Steinberg | The Černý conjecture for one-cluster automata with prime length cycle[END_REF] verifies the conjecture for automata having a letter inducing a connected digraph with the cycle of prime length (thus generalizing the mentioned Pin's result). In addition, various classes of small automata have been verified using computer programs. In particular, Trahtman [START_REF] Trahtman | An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture[END_REF], in 2007, has announced checking all the automata on 2 letters with n ≤ 10 states. Some of the above results involve assumptions on preserving by an automaton a certain structure. In this paper, we show that this kind of results may be unified and generalized. We introduce the notions of an interval for a directed graph, respecting the intervals of a digraph by an automaton, and the congruence induced by such a relation. Then, we prove a reduction theorem of the form that if an automaton A respects intervals of a directed graph and the induced quotient automaton satisfies the Černý conjecture, then so does A. Our result implies that the Černý conjecture is true for a large class of automata that includes, in particular, orientable automata [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF], monotonic and generalized monotonic automata [START_REF] Ananichev | Synchronizing monotonic automata[END_REF][START_REF] Ananichev | Synchronizing generalized monotonic automata[END_REF], aperiodic automata [START_REF] Trahtman | The Černý Conjecture for Aperiodic Automata[END_REF], and weakly monotonic automata [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF].

Preliminaries

There are two structures connected with an automaton A = Q, Σ, δ giving possibilities of viewing the automaton in various ways. The transition digraph T = T (A) is defined on Q by (q, s) ∈ T if and only if qa = s for some a ∈ Σ. The transition monoid M = M (A) is one generated by transformations on Q corresponding to letters in Σ. Then, the words in Σ * correspond to compositions of generating transformations.

Automaton A = Q, Σ, δ is strongly connected if its transition digraph is strongly connected. In general, one can consider strongly connected components of T (A). These are partially ordered by the relation of the existence of a directed edge in T (A) from one component to another. It is clear that if A is synchronizing, then T (A) has to have a unique minimal strongly connected component C. In such a case, the restriction A| C of A to C forms a reduced automaton. It is easy to prove (and it is considered as a folklore result) that if A| C satisfies the Černý conjecture, then so does A. Thus, it is enough to consider only strongly connected automata.

In terms of monoids, this is just a reduction to transitive monoids, since it is clear that A is strongly connected if and only if M (A) is transitive. A further natural reduction would be one to transition monoids which are primitive in the sense of permutation group theory.

Given

A = Q, Σ, δ , an equivalence relation ∼ on Q is called a congruence (on A) if it is preserved by A.
More precisely, q ∼ s implies qa ∼ sa for all a ∈ Σ. If ∼ is a congruence, then the quotient automaton A/∼ = Q ′ , Σ, δ ′ is defined in the natural way: Q ′ = Q/∼ is the set of the equivalence classes of ∼, and δ([q] ∼ , a) = [qa] ∼ , where [q] ∼ denotes the equivalence class containing q. One may conjecture that for all congruences the following equivalence holds: A satisfies the Černý conjecture if and only if the quotient automaton does. If the Černý conjecture is true then, of course, this equivalence is also true. Yet, we see no natural way to prove it, and according to our experience, this problem in general may be as hard as the Černý conjecture itself. Yet, we have attempted to find special kinds of congruences, for which the problem would be more naturally linked to the Černý conjecture and a reduction step would be possible. Here we have one easy and natural result.

Proposition 1.1 Let ∼ be a congruence on a strongly connected automaton A = Q, Σ, δ such that one of its equivalence class is a singleton. Then, A satisfies the Černý conjecture, whenever A/∼ does.

Proof: Let |Q| = n and k be the number of the equivalence classes in ∼. We may assume that k < n, since otherwise the result is trivial. By assumption, there exists a word w ∈ Σ * of length ≤ (k -1) 2 resetting A/∼. This word sends all the states of A into one ∼-class B.

Let s be the unique element of a singleton ∼-class. Since A is strongly connected, there exists a word u ∈ Σ * that sends a fixed state q ∈ B into s. Moreover, we may assume that the length |u| ≤ k -1, since if u = a 1 . . . a t is the shortest word with qu = s, then the path corresponding to applying successive letters of w visits every ∼-class at most once. Indeed, suppose to the contrary that qa 1 . . . a i and qa 1 . . . a j are in the same ∼-class, and i < j < t. Then, since ∼ is a congruence, qa 1 . . . a i a j+1 j . . . a t = s, a contradiction.

It follows that the word u sends all the states of the ∼-class B into s, and therefore uw resets A. The length |uw| ≤ (k -1) 2 + k -1 < (n -1) 2 , as required. ✷

In the sequel, the argument used in this proof will be treated as routine.

Intervals in digraphs

Apart from the transition digraph T = T (A) determined by the automaton A Q, Σ, δ , we shall consider also another digraph D on the the set of the states Q with the property that certain structures on D, called intervals, are preserved by the transition function δ of A.

Let D = Q, E be an arbitrary directed graph. We say that a vertex z ∈ D lies on a directed path from x to y (in D) if there is a directed path x = x 0 , x 1 , . . . , x n = y such that z = x i for some i = 0, 1, . . . , n and x, y / ∈ {x 1 , . . . , x n-1 }. In short, we say that the path xy contains z. Note that the path in question may have repeated occurrences of vertices except for end vertices x, y each of which occurs only once. In the sequel, we assume that all considered paths have this property. Only if necessary, we stress this calling such paths singular. (Note also that we allow trivial paths with x = y).

The set of all vertices z lying on a directed path between x and y will be denoted by

[x, y]. Such a set is called a (directed) interval of D. Note, that by definition, if [x, y] = ∅, then x, y ∈ [x, y].
Note also that due to the singularity assumption on paths, even for strongly connected digraphs the intervals [x, y] and [y, x] usually differ from each other. For example, if D is a simple directed cycle, then the intervals yield a division of the cycle into two arcs. If D is acyclic, then one of the intervals [x, y] and [y, x] is empty, and the other one is the usual interval in the induced partial ordering (the transitive closure of D). The interval [x, x], by definition, is the strongly connected component of the vertex x in D. In the sequel, we shall use the abbreviation sc-component.

We say that an automaton A = Q, Σ, δ respects the intervals of a digraph D defined on Q, if for every letter a ∈ Σ, and all x, y ∈ Q, the following conditions holds:

(i) if [x, y] = ∅, then [xa, ya] = ∅, (ii) if both [x, y] = ∅ and [y, x] = ∅, then [x, y]a ⊆ [xa, ya],
(iii) if xa = ya, then one of the sets [x, y]a or [y, x]a has at most one element.

The first condition means that A preserves existence of a directed path between vertices. The second condition means that in case when there are directed paths between x and y in both directions, z ∈ [x, y] implies za ∈ [xa, ya], which means that the relation of lying on a directed path between vertices is preserved. The third condition deals with the special case when the endpoints of the interval are mapped into the same vertex. What is happening with the two intervals [x, y] and [y, x] in such a situation? We assume a sort of continuity: when x approaches y then one of the intervals is getting smaller while the other is getting larger.

We will consider both strongly connected digraphs (where for each pair of vertices x, y there exists a directed path from x to y) and weakly connected digraphs (where each pair of vertices is connected by some undirected path) (that is the underlying undirected graph is connected). Both the properties induce equivalence relations giving partitions into strongly connected components or weakly connected components, respectively. Note, that the condition (i) above means, in particular, that A preserves both the partition into strongly connected components of D and the partition into weakly connected components of D. Thus the corresponding equivalence relations are congruences, which will be referred to as congruences induced by the strongly (or weakly) connected components of D, respectively. Lemma 2.1 If A = Q, Σ, δ respects the intervals of a digraph D = Q, E , then the conditions (i-iii) above hold for every word w, as well (that is, with a replaced by w, and Σ replaced with Σ * ).

Proof: For the condition (i) the claim is obvious. For (ii), we note that the condition implies that both [xa, ya] and [ya, xa] are nonempty. The claim for w = a 1 . . . a n follows by successive application of (ii) for letters a 1 , . . . , a n . For (iii), if one of [x, y] or [y, x] is empty, then one of [x, y]w or [y, x]w is empty, as well, and thus satisfies (iii). Otherwise, successive application of (ii), yields that [x, y]u ⊆ [xu, yu] for every prefix u of w. Taking u to be the largest prefix of w such that xu = yu, and applying (iii) for xu and yu, yields the required result for w. ✷

Example. If D is a simple directed cycle, then respecting intervals means preserving the orientation of the cycle. Indeed, the interval [x, y] consists of consecutive vertices on the cycle. Let us make use of the comments after the definition (i)-(iii). If vertices x, y, z occur on the cycle in this very order, then by (i), the relation of lying on a directed path between vertices is preserved. Conversely, if this relation is preserved, then (ii) holds, while (i) and (ii) are trivial for the cycle. If D is an acyclic digraph, then respecting intervals means preserving the partial order induced by D. Indeed, it is enough to observe that the interval [x, y] is the set of all z such that x ≤ z ≤ y, that is, the usual interval of the induced partial order. If we denote this order by ≤, then the condition [x, y] = ∅ is equivalent to x ≤ y. Thus, the condition x ≤ y implies xa ≤ ya is equivalent to (i). The condition (ii) is trivial for acyclic digraphs, and

(iii) holds since if x = y, then one of [x, y] or [y, x] is empty. In the remainder of the paper, we show that these are in fact the extreme cases of a general situation. Under assumptions as above, let ∼ denote the equivalence relation on Q induced by sc-components of D, and let Q ′ = Q/∼ be the quotient set. Then the relation induced on Q ′ by D is an acyclic digraph, which we denote by D ′ = D/∼. The quotient automaton A/∼ respects the intervals of D ′ , that is, in view of the remark above, it preserves the partial order induced by D ′ . The property of respecting the intervals of a digraph may be now characterized as follows.

Lemma 2.2 An automaton A = Q, Σ, δ respects the intervals of a digraph D on Q if and only if A/∼ preserves the partial order induced by D/∼ and for all x, y belonging to the same sc-component of D the conditions (ii) and (iii) above holds.

We say that the strongly connected components of a digraph D are dense, or that D is scc-dense, if for all x, y, z belonging to the same sc-component C of D either z ∈ [x, y] or z ∈ [y, x]. Note that a simple directed cycle is dense in that sense. The property is not as strong as it may seem at the first sight. Let us call a vertex z ∈ C a check-point for the pair x, y ∈ C (x, y = z) if each directed path from x to y contains z and each directed path from y to x contains z, as well. Similarly, supposing that z / ∈ [y, x], we have that either (c) every path yz contains x, or (d) every path zx contains y. Now, (a) and (c) contradicts the fact that there is a path form x to z, while (a) and (d) means that y is a check-point. The situation for the remaining two possibilities is similar. Consequently, there is always a check-point, as required.

✷

Now we prove a crucial property of the automata respecting the intervals of an scc-dense digraph connected with synchronization. We will be interested in the situation when the image Xw of the subset X of Q under the word w collapses, by which we mean that |Xw| = 1. We may assume also that there are t ∈ [x, z] and s ∈ [z, y] such that tw = zw = xw and sw = zw = yw.

Lemma 2.4 Let

A = Q, Σ, δ respects the intervals of an scc-dense digraph D on Q. If X is a nonempty subset of Q, |X| > 1,
We show that among paths xz containing t there exists one not containing y. Suppose to the contrary that each path xz containing t contains y, as well. If the segment xt of such a path (that is the part from x to t) does not contain y, then neither does the segment tz (otherwise, we would have a path xy containing t, and since by induction hypothesis |[x, y]w| = 1, it follows that tw = xw, a contradiction). Similarly, if the segment tz of such a path does not contain y, then neither does the segment xt (otherwise, we would have a path yz containing t, and since, by assumption above, [y, z] collapses, we have tw = zw, a contradiction). Choose a path xz that contains t. Let yt and ty be the segments of this path that has only one occurrence of y, each. Let xt be a path that does not contain y. Combine it with the segment ty, we have a path from x to y that contains t, and as before, this leads to a contradiction. Similarly, Let tz be a path that does not contain y. Combine it with the segment yt, we have a path from y to z that contains t, and again, a contradiction. It follows that every path xt contains y, and every path tz contains y. Since y is not a check-point, there is a path zt not containing y, and therefore not containing x either. Similarly, there is a path tx not containing y, and therefore not containing z either. This yields a (singular) path zx containing t, which (since [z, x] collapses) yields tw = zw, a contradiction.

In a completely analogous way we show that among paths zy containing s there exists one not containing x. Combining it with a path xz containing t and not containing y, we obtain a (singular) path xy containing z, which contradicts the assumption that z / ∈ [x, y], and thus completes the proof. ✷

Main result

We start from a preliminary result. Let A = Q, Σ, δ be a synchronizing automaton and let C be a subset of Q. A family F = {X 1 , . . . , X m } of subsets of Q is called a Černý family for C, if for every image Y = Cu by a word u ∈ Σ * and every w ∈ Σ * the following implication holds: if |Y | > 1 and |Y w| = 1, then there exists i ≤ m such that Y ⊆ X i and |X i w| = 1. In other words, if C collapses under uw, then the image Cu, if nontrivial, may be extended to a member of F that still collapses under w. Proof: Since A is synchronizing, there is a word v = a 1 • • • a t such that C collapses under v. We assume that v is the shortest possible word with this property. Denote

Y i = Qa 1 • • • a i for i ∈ {1, . . . , t -1}, and Y 0 = C. Then, for all i ≤ t -1, |Y i | > 1. For each i ∈ {0, . . . , t -1} choose Z i ∈ F such that Y i ⊆ Z i and |Z i a j+1 • • • a t | = 1. We show that if i < j, then Z i = Z j . Indeed, if i < j and Z i = Z j , then we have Ca 1 • • • a i = Y i ⊆ Z j , and consequently, |Ca 1 • • • a i a j+1 • • • a t | = 1
, contradicting the fact that v is the shortest word with this property. Thus, t ≤ m, as required. ✷

Our main result is the following Theorem 3.2 Let A = Q, Σ, δ be a strongly connected automaton respecting the intervals of an sccdense digraph D on Q, and let ∼ denote the congruence on A induced by weakly connected components of D. Then, if A/∼ satisfies the Černý conjecture, then so does A.

Proof: Denote by n the number of strongly connected components, and by k the number of weakly connected components (wc-components). If there is a wc-component of D consisting of a single vertex, then by Proposition 1.1 the theorem is true. Hence we may assume that each wc-component has at least two vertices. Assume also that A/∼ is synchronizing and satisfies the Černý conjecture. Recall that, since A respects the intervals, wc-components are mapped by transformations of A into wc-components, and sc-components are mapped into sc-components. We first show that Claim 1. There exists a word v ∈ Σ * of length not exceeding (n -1) 2 such that Qv is contained in a single sc-component of D.

By assumption on A/∼, there is a word w of the length at most (k -1) 2 that resets A/∼. The word w maps all the states of A into one wc-component B of D. Since A/∼ is strongly connected there is a word u of the length at most k -1 mapping B on any chosen wc-component B i . In particular, if there exists a wc-component consisting of a single sc-component, we are done. Indeed, in such a case wu maps Q into a single sc-component and it has length

(k -1) 2 + (k -1) = (k -1)k < (n -1) 2 .
(We note that for k = 1 w is simply the empty word and the argument works, as well).

Thus, we may assume that every wc-component of D has at least two sc-components. The sc-components are partially ordered by D, so we may speak of maximal and minimal sc-components. Let B 1 , . . . , B k denote the wc-components of D (this set includes B defined above). Then, by M i we denote the number of maximal sc-components in B i , and by m i the number of minimal sc-components of B i . Since each B i has at least two sc-components, no sc-component is both maximal and minimal. Therefore

k i=1 (M i + m i ) ≤ n. Let us define p = min{M i , m i : i ∈ {1, . . . , k}}.
Then, p ≤ n/2k. To fix attention, we may assume without loss of generality that p = M 1 , and that the word u of length at most k -1, mentioned above, maps B into B 1 .

Let C 1 , . . . , C p denote the maximal sc-components of B 1 . We define inductively a sequence of words u 0 , . . . , u t , with t ≤ p, and such that B 1 u t is contained in a single sc-component of D. Let u 0 be the empty word. Given the word u i , we define J i to be the set of those j ∈ {1, . . . , p} for which none of the images C j u 1 , C j u 2 , . . . , C j u i is contained in a minimal sc-component of D. Further, let X i be the set of those sc-components of D that contain C j u i for some j ∈ J i . In particular, we have J 0 = {1, 2, . . . , p} and X 0 = {C 1 , . . . , C p }. The word u i+1 is now defined as follows.

We look first for a word v i+1 that maps at least one sc-component in X i into some minimal sccomponent of D, Such a word exists, since A is strongly connected. We may assume that the length of v i+1 is at most n -(m -1) -|X i |, where m = k j=1 m i . Indeed, let I 1 , I 2 , . . . , I r be the sequence of images of an sc-component in X i obtained by applying successive letters of word v i+1 . Obviously, each such image is contained in an sc-component, so we have a sequence of corresponding sc-components. We may assume that in this sequence no sc-component appears twice, no sc-component of X i occurs, and except for the last term, no minimal sc-component occurs. This yields the length bound above. We define u i+1 = u i v i+1 . Then obviously |X i+1 | < |X i |, unless X i is empty. It follows that X t is empty for some t ≤ p, and consequently, for each j ∈ {1, 2, . . . , p} there exists i ≤ t such that C j u i is contained in a minimal sc-component of D.

Claim 2. The image B 1 u t is contained in a single sc-component.

Let denotes the partial ordering of sc-components in D. Since B 1 is weakly connected, it is enough to show that for every pair of sc-components Z, Y ∈ B 1 such that Z covers Y in , the images Zu t and Y u t are contained in the same sc-component. To this end, let C j ∈ X 0 be the maximal sc-component of B 1 with Z C j . Now, since for some i, C j u i is contained in a minimal sc-component, and A preserves , the images Zu i and Y u i are contained in the same minimal sc-component. Since u t = w 1 u i w 2 , for some w 1 , w 2 , the claim follows.

Thus, the word v = wuu t maps Q into a single sc-component. Let us denote this component by C. To complete the proof of Claim 1 we need to prove now the following.

Claim 3. The length |v| ≤ (n -1) 2 .
By construction, we have

|v| ≤ (k -1) 2 + k -1 + p-1 i=0 (n -m -p + i + 1) ≤ k(k -1) + pn -kp 2 - p(p -1) 2 .
(In the later inequality, we have used the fact that m =

k j=1 m i ≥ kp). If p = 1, then |v| ≤ k(k -2) + n ≤ n 2 n 2 -2 + n ≤ (n -1) 2 .
So, we may assume that p ≥ 2. Since 2kp ≤ n, we have

p(n -kp) ≤ n 2 2k . It follows that |v| ≤ k(k -1) + n 2 2k . Consider the function f (k) = k(k -1) + (n 2 /2k). We know that 1 ≤ k ≤ n/2, yet we consider it on the interval [1, n -1]. Since f ′ (k) is continuous and increasing on the interval [1, n -1], f (k) have the maximal value, in this interval, either for k = 1 or for k = n -1. For k = 1, since n ≥ 2kp ≥ 4, we have |v| ≤ n 2 2 < (n -1) 2 .
For k = n -1, we have

|v| ≤ (n -1)(n -2) + n 2 2(n -1)
, and again, using n ≥ 4, |v| < (n -1) 2 .

This completes the proofs of Claim 3 and Claim 1.

Now, if all the sc-components in D are trivial (one-element), then the proof of the theorem is finished. Otherwise, let N denote the number of vertices in D (states in A). Then N > n. If there is at least one trivial sc-component consisting of a single state q, then there is a word v 0 of length ≤ (n -1) mapping the sc-component C containing B 1 u t onto q. Consequently, the word vv 0 resets A and it has the length not exceeding

(n -1) 2 + (n -1) = n(n -1) < (N -1) 2 ,
as required. Hence, we may assume that each sc-component contains at least two vertices. Then N ≥ 2n.

We show that there exists a small enough Černý family of sets for C. Suppose that Y = Cu is an image of C by a word u. Then, Y is contained in some sc-component of D. Let w be such that |Y w| = 1. By Lemma 2.4, there exist x, y ∈ Y such that Y ⊆ [x, y] and [x, y] collapses under w. This means that the family F of sets [x, y] with x = y belonging to the same sc-component in D forms a Černý family of sets for C. We estimate the cardinality m = |F| of this family.

Let

c i = |C i |. Then m = n i=1 c i (c i -1).
Clearly, for a fixed n and N , this sum has the maximal value when c 1 is as large as possible and the remaining values of c i are as small as possible. Since, by assumption c i > 1, we have

m = n i=1 c i (c i -1) ≤ (N -2(n -1))(N -2n + 1) + 2(n -1),
and consequently,

m ≤ N 2 -4N n + 4n 2 + 3N -4n.
This may be written as

m ≤ (N -1) 2 -(n -1) 2 -(4N n -5n 2 -5N + 6n).
The latter term in parentheses equals

(3N -5n)(n -1) + N n -2N + n,
and since N ≥ 2n and n > 1, it is positive. Therefore,

m ≤ (N -1) 2 -(n -1) 2 .
Combining Lemma 3.1 with Claim 1 completes the proof. ✷

Corollaries and applications

First note that if an scc-dense graph D on Q is weakly connected, then A/∼ in Theorem 3.2 has one element and trivially satisfies the Černý conjecture (see a remark at the beginning of the proof of Theorem 3.2 concerning the case k = 1). Therefore we have the following Obviously, a (simple directed) cycle is scc-dense, and so, as a particular case of the corollary above, we obtain Eppstein's result [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] that oriented automata (called in [START_REF] Eppstein | Reset sequences for monotonic automata[END_REF] monotonic) satisfy the Černý conjecture. The following is a natural generalization of the Eppstein result.

Let us call a directed graph D a digraph with unique return paths, if whenever there is a path from x to y in D, and there is a return path from y to x, then the latter is unique, and in consequence the former is also unique. Since we allow on paths repeated occurrences of vertices (other than end vertices), it means that on each of the paths every next step is uniquely determined until we reach the end vertex. This leads easily to the conclusion that every two cycles in D are disjoint. Thus, a digraph with unique return paths consists of a collection of disjoint cycles and, possibly, additional edges between them inducing a partial ordering on the cycles. In a sense, this is a class of digraphs next to the acyclic digraphs (and thus a natural generalization of simple cycles). Note that preserving intervals of D in this case means that cycles are mapped into cycles, orientation of vertices on each cycle is preserved and the existence of a directed path between cycles is preserved. We abbreviate it saying that the induced partial order and orientation of cycles are preserved. Then we may formulate the following simple generalization of Eppstein result. Corollary 4.2 Let D be a weakly connected digraph on Q with unique return paths. If a strongly connected automaton A = Q, Σ, δ preserves the partial ordering on the cycles induced by D and orientation of the cycles, then A satisfies the Černý conjecture. Now, it is easy to construct examples of automata (using, for instance, Černý automata as components) that are neither orientable nor weakly monotonic and satisfy the Černý conjecture due to the corollary above.

We proceed to show that our results also include all weakly monotonic automata. This leads to a different (and perhaps simpler) way to handle weakly monotonic automata and to a generalization of these constructions. First let us recall the definition from [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF]. Given an automaton A = Q, Σ, δ , a binary relation ρ on Q is stable if (p, q) ∈ ρ implies (pa, qa) ∈ ρ for all p, q ∈ Q and a ∈ Σ. Then, A is called weakly monotonic of level ℓ ≥ 1 if there exists a strictly increasing chain of stable binary relations

ρ 0 ⊂ ρ 1 ⊂ . . . ⊂ ρ ℓ ,
such that ρ 0 is the equality relation, the transitive closure of ρ ℓ is the universal relation, and for each i = 0, . . . , ℓ -1 the following condition is satisfied:

( * ) the transitive closure π i of ρ i is contained in ρ i+1 and the relation ρ i+1 /π i induced by ρ i+1 on the set of equivalence classes Q/π i is a partial ordering.

Note that the equivalence classes of the transitive closure of a partial ordering relation τ are just the weakly connected components of any digraph D inducing τ . Recall that if A = Q, Σ, δ preserves the partial order τ (defined on Q) then the weakly connected components of τ form a congruence on A. It is natural to write simply A/τ to denote the corresponding quotient automaton. Then, we may define weakly monotonic automata by recursion as follows.

(i) The trivial automata with one state are weakly monotonic of level 0;

(ii) for ℓ > 0, A = Q, Σ, δ is a weakly monotonic of level ℓ, if there exists a partial order τ on Q, such that A/τ is a weakly monotonic automaton of level ℓ -1.

A = Q, Σ, δ is a weakly monotonic automata of level 1, if if there exists a weakly connected partial order τ on Q preserved by A;

It should be clear that in both the definitions the classes of weakly monotonic automata of level not exceeding ℓ coincide. In particular, the weakly monotonic automata of level 1 are just the automata preserving a connected partial order. The fact that each strongly connected weakly monotonic automaton of level ℓ satisfies the Černý conjecture follows now by ℓ-fold application of Theorem 3.2. We note, that Volkov [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF] proved this result for all (not necessarily strongly connected) weakly monotonic automata. This can be also obtained using the proof of Theorem 3.2 (since the assumption that the automaton in question is strongly connected is necessary only for the case when D has cycles). It should be noted however, that in [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF], for strongly connected automata a stronger bound for a reset word is established. It has been also observed in [START_REF] Volkov | Synchronizing automata preserving a chain of partial orders[END_REF] that Trahtman [START_REF] Trahtman | The Černý Conjecture for Aperiodic Automata[END_REF] proved that each aperiodic automaton preserves a nontrivial partial order, and therefore each such automaton is weakly monotonic (the latter can be seen immediately from our recursive definition).

These observations may be generalized for strongly connected automata as follows. For an automaton A = Q, Σ, δ respecting the intervals of a digraph D, by A/D we denote the quotient automaton of the congruence induced by the weakly connected components of D. For an arbitrary class of strongly connected automata C, we define recursively the class I ℓ (C): In particular, if C 0 consists of one-element automata, then the class I ℓ (C 0 ) contains, in particular, all strongly connected weakly monotonic automata of level ℓ. Yet, one may start from a broader class of automata C for which the Černý conjecture has been already verified. Then, one may easily construct many new examples of strongly connected automata not covered by the results on the Černý conjecture established so far.

Lemma 2 . 3

 23 A digraph D is scc-dense if and only if contains no check-point in any sc-component of D. Proof: Suppose first D has a check-point z in an sc-component C. So, there are x, y ∈ C such that any directed singular path between x and y goes through z. It follows that y / ∈ [z, x] and y / ∈ [x, z]. Conversely, suppose that z / ∈ [x, y]. Then, one of the following holds: either (a) every path xz contains y, or (b) every path zy contains x.

  contained in an sc-component of D such that |Xw| = 1, then there exist different x, y ∈ X such that X ⊆ [x, y] and the whole interval [x, y] collapses under w.Proof:The proof is by induction on the cardinality of X. For |X| = 2 the claim follows trivially from the condition (iii) of Lemma 2.1. Otherwise, let us fix z ∈ X. By induction assumption, there are different x, y ∈ X \ {z} such that X \ {z} ⊆ [x, y] and [x, y] collapses under w. If z ∈ [x, y], then we are done. So, we may assume z / ∈ [x, y]. Since D is scc-dense, it follows that z ∈ [y, x]. This means that there is a path yx containing z, and consequently, there is a path yz containing no x. This path may be added to every path xy yielding a path from x to z. It follows that [x, y] ⊆ [x, z]. Similarly (since there is a path zx containing no y),[x, y] ⊆ [z, y]. If any of [x, z] or [z, y] collapses under w, we are done. Hence, we may assume, by condition (iii) of Lemma 2.1, that both [z, x] and [y, z] collapse under w, that is, |[z, x]w| = |[y, z]w| = 1.

Lemma 3 . 1

 31 If F = {X 1 , . . . , X m } is a Černý family for a set C ⊂ Q, |C| > 1, then there exists w ∈ Σ * of length not exceeding m = |F| such that |Cw| = 1.

Corollary 4 . 1

 41 If a strongly connected automaton A = Q, Σ, δ respects the intervals of an scc-dense weakly connected digraph D on Q, then A satisfies the Černý conjecture.

  (i) I 0 (C) = C; (ii) for each ℓ > 1, I ℓ (C) is the class of all strongly connected automata A = Q, Σ, δ such that, for some digraph D on Q, A respects the intervals of D and A/D ∈ I ℓ-1 (C). Our main result Theorem 3.2 yields Corollary 4.3 If C is a class of strongly connected automata satisfying the Černý conjecture, then every automaton A ∈ I ℓ (C), for some ℓ ≥ 0, satisfies the Černý conjecture.