Juliette Rouchier
email: juliette.rouchier@univmed.fr

BE STABLE IN AN OPEN NETWORK WITH HIERARCHY? AN AGENT-BASED MODEL OF THE COMMERCIAL COURT OF PARIS *

CAN OPINION BE STABLE IN AN OPEN NETWORK WITH HIERARCHY? AN AGENT-BASED MODEL OF THE COMMERCIAL COURT OF PARIS

The co-evolution of social networks and opinion formation has received increasing attention in recent years. As a contribution to the growing literature on this topic, we explore connections between empirical data representing the advice network of judges at the Commercial Court in Paris and an agent-based simulation protocol testing various hypotheses on the motives that drive agent behaviors. A previous work [START_REF] Rouchier | Articulation of hierarchy and networks as an evolving social structure[END_REF]) had already modeled the dynamics of advice-seeking among judges and studied the implications of different rationality assumptions on the shape of the emerging network. Here, we add an influence model to the previously examined advice-seeking relationships in order to explore the possibility that there is a form of "culture" at the Court that harmonizes the opinions of members over time; we identify a set of relevant stylized facts, and we use new indicators to evaluate how agents choose with whom to interact within this framework. The basic assumptions we analyze are that they seek advice from senior judges who are higher up in the hierarchy, who enjoy high reputation, or who are similar to them. Our simulations test which criterion -or which combination of criteria-is most credible, by comparing both the properties of the emerging network and the dynamics of opinion at the Court to the stylized facts. Our results single out the combination of criteria that most likely guide individuals' selection of advisors and provide insight into their effects on opinion formation.

The paper is organized as follows. Section 1 briefly presents our case study, the Commercial Court of Paris, and derives relevant stylized facts. Section 2 illustrates the main features and overall structure of the model, while section 3 outlines our main results on indegree centrality and section 4 focuses on our findings on opinion. Section 5 concludes.

1.

The case study: the Commercial Court of Paris (CCP).

The CCP as a judicial institution

The Commercial Court of Paris (CCP) is a five-century old judicial institution which handles about 12% of commercial litigation and bankruptcy cases in France, including complex and politically sensitive ones. Interestingly, CCP members are not career magistrates but experienced businesspeople or top-level company managers who are elected by their peers and exercise their functions as unpaid volunteers. In this sense the CCP is an example of "joint regulation" of markets [START_REF] Falconi | Le contrôle social du monde des affaires : une étude institutionnelle[END_REF][START_REF] Lazega | Interlocking judges: On joint external and self-governance of markets[END_REF] integrating representatives of the private sector with the public sector.

The structure of the institution needs to be briefly presented as our model reproduces its main features. First, the fact that mandates are for a fixed term of up to 14 years implies a regular turnover, with joiners and leavers every year. Second, the Court is composed of about 21 specialized and generalist Chambers in charge of different forms of commercial litigation and bankruptcy, with an average of 7 judges in each of them; to reduce the risk of corruption and conflict of interest, a formal rotation rule reassigns judges to a new Chamber every year. Finally, the CCP is a hierarchical institution which ascribes significant power to the President of the Court and Presidents of Chambers. Hierarchy is closely related to seniority as Presidents must have been at the Court for at least 8 years; an appointment as President confers a status that is conserved even after this role is passed to someone else.

Judges face multifaceted tasks requiring multiple competencies -legal, economic, managerial among others. Conflict resolution often calls for detailed knowledge of the norms, customs, and expectations of the particular industry concerned. Unlike career magistrates, CCP members have hands-on experience in a variety of trade sectors. One argument to legitimize this lay institution is precisely that it pools and shares experience and expertise. Indeed, CCP judges intensely exchange advice and information with one another.

Together with specialized information, advice ties channel normative orientations on how to deal with situations in which judges have discretion. Different views may coexist and be discussed on, say, the merits of the free market, the respective roles of the public and private sectors, and the perimeter of regulation.

Stylized facts: network formation and opinion dynamics

To identify stylized facts, we rely on data on advice-seeking among CCP members which were collected by Emmanuel Lazega and Lise Mounier in 2000[START_REF] Deffuant | How can extremism prevail? A study based on the relative agreement interaction model[END_REF][START_REF] Falconi | Le contrôle social du monde des affaires : une étude institutionnelle[END_REF] Judges were asked about their advice ties to one another, and a high response rate enabled to reconstitute the complete advice network among them at each wave.

First, the data reveals that the degree distribution is asymmetric, particularly regarding indegrees1 , as can be seen in Figure 1. There is a correlation between degree and seniority: junior judges, including newcomers, have low indegrees (i.e. are little sought out), while seniors and Presidents have high indegrees (i.e. are much sought out). The reverse is true for outdegrees 2 , which are higher for junior than for senior judges, indicating that the former seek more advice than the latter.

In 2005, judges were also interviewed about their normative views, particularly the extent to which they believed they should be punitive in their decisions on matters of unfair competition between entrepreneurs. For the purposes of this paper, we interpret punitivity as severity in their interpretation of the law in cases in which they have discretion 3 .

Our second empirical fact is that opinion appears to be correlated with seniority in that junior judges are on the whole more severe than senior judges; it is also related to degree, as severe judges have relatively low indegrees and high outdegrees. In fact the most central advisors are senior judges, often with a formal role as President of Chamber, and typically non-punitive.

These observations suggest that some process may lead judges to become less severe over time, and that it may depend on judges' advice-seeking activity, at least to some extent. The model we are now going to outline aims at reproducing these stylized facts so as to provide insight into the processes that lead to them.

The model

Our model represents an evolving social network with an exogenously given hierarchy which defines progress up the ladder, a regular flow of newcomers and leavers, and an internal rotation rule. The model addresses the question of who interacts with whom, and is evaluated with two indicators: evolution of opinion over time and a measure of convergence of opinion towards shared values. It simulates the advice-seeking interactions of a population of artificial Agents4 , and the ensuing changes in individual opinion. Agents are defined by attributes that represent their position in the hierarchy (current Chamber, role as current or former President, seniority), others that define their opinion, and their indegree centrality which is computed at each step.

We draw on a widely applied (abstract) influence model [START_REF] Deffuant | How can extremism prevail? A study based on the relative agreement interaction model[END_REF]. While the original version assumes random pair matching during which Agents may influence each other, the choice of communication partners may not be random in our case but rather follow a systematic pattern. Thus, in what follows we first outline our hypotheses for the choice of communication partners and their empirical and theoretical bases, then we describe the model itself: the influence mechanism and our implementation of the choice of partners. We conclude with an overview of the simulation dynamics and its main parameters.

Hypotheses about the choice mechanism

Our assumption is that Agents have three basic ways to choose whom to communicate with:

• Authority: seek advice from judges higher up in the hierarchy (Presidents).

• Reputation: seek advice from those who are most sought out by others.

• Homophily: seek advice from similar judges (i.e. who share the same opinions).

These representations of choice mechanisms are grounded in the sociological and organizational literature. Support for the authority argument stems primarily from [START_REF] Blau | The Dynamics of Bureaucracy[END_REF][START_REF] Blau | Exchange and Power in Social Life[END_REF] social exchange theory, according to which status recognition tends to be given in exchange for advice in organizations. Thus, members high up in the formal hierarchy are most likely to be consulted. Blau's prediction is confirmed by the empirical observation that advice networks often exhibit a pecking order that closely follows hierarchy; evidence of such a mechanism was found for the Court advice network database by [START_REF] Lazega | A spinning top model of formal structure and informal behaviour: Dynamics of advice networks in a commercial court[END_REF].

The case for reputation draws from the fact that with imperfect information, reputation can be taken as an indicator of the competency of an advisor and approximated by indegree centrality in the advice network. Indeed the latter measures the extent to which an individual is consulted, presumably for work-related input [START_REF] Klein | How do they get there? An examination of the antecedents of centrality in team networks[END_REF]); thus, it helps to infer his/her degree of expertise. Indegree-dependent effects are often self-reinforcing, with the most popular advice-givers being increasingly sought out over time [START_REF] Lazega | A spinning top model of formal structure and informal behaviour: Dynamics of advice networks in a commercial court[END_REF]).

The tendency towards homophilous choices, i.e. to form ties to similar others, is well documented [START_REF] Mcpherson | Birds of a feather: homophily in social networks[END_REF]. Various dimensions of homophily have been investigated in the literature, for instance based on gender, education, or nationality; similarity of opinions may also generate homophilous choices of advisors (this is the dimension we focus on). Homophily may attenuate or reinforce the effects of hierarchy and reputation, sometimes in complex ways as shown by [START_REF] Lazega | Réseaux et controverses: de l'effet des normes sur la dynamique des structures et les processus sociaux[END_REF].

Agents: attributes and processes

Influence

Our representation of opinion change follows the "relative agreement" model of [START_REF] Deffuant | How can extremism prevail? A study based on the relative agreement interaction model[END_REF], to which the reader should refer since we have little space to describe it thoroughly. Agent j is characterized by two continuous variables on [0, 1], namely its opinion x j and its uncertainty u j ; its "opinion segment" is defined as the segment of length 2.u j around x j . Continuous values allow opinion to vary smoothly between the two extremes of the acceptable range; uncertainty is a measure of lack of individual self-confidence. At initialization, Presidents and senior Agents have "low" opinion (0.1 to 0.3, i.e. not too severe, consistently with empirical data) and low uncertainty (0.1, to suggest that experience and position in the hierarchy may increase self-confidence). For other Agents and newcomers, uncertainty is higher (0.7) and opinion is uniformly picked between 0 (non severe) and 1 (severe). These values are tested in the simulations presented below.

When an Agent meets another, it can be influenced only if the opinion of the other is included in its opinion segment. If there is influence, it is both in opinion and uncertainty, and it is proportional to the overlap between the two Agents' opinion segments (the agreement), divided by the uncertainty of the influencing Agent (expressing relativity in the sense that a more confident advisor has stronger influence). Notice that relativity makes the mechanism non-symmetric: only in some cases do the opinion and uncertainty of both Agents vary.

Choice mechanism

Agents' attributes determine their actions according to the following three-step process.

First, an Agent chooses whether to seek advice or not. To do so, it picks a number randomly from a uniform distribution and compares it to its uncertainty (between 0 and 1): if it is lower, this Agent will seek advice. The higher the uncertainty, the more advice is sought; hence with the aforementioned differentiation between juniors and seniors, the former are more likely to seek advice than the latter, consistently with the empirical fact that those with lower seniority at the CCP have higher outdegrees.

Second, if an Agent seeks advice, it must select an advisor, with criteria that depend on the type of simulation we run: a "pure" or "mixed" choice, both based on the hypotheses exposed earlier, or random choice. More precisely, we consider six options:

• Authority: 60%5 chance of selecting the President of its own Chamber; then 24% probability of selecting another President and a 16% probability of simply drawing a non-president more senior Agent 6 .

• Reputation: 60% probability of picking up from the subset of the 10 advisors who have the highest indegree centrality levels, and a 40% probability of picking up a more senior advisor.

• Homophily: more senior advisors whose opinion is close enough for influence to take place (according to the Deffuant model).

• Mixed strategies are Authority-Reputation and Authority-Homophily with 50% probability of choosing one of these two choice procedures.

• Random: Any Agent with higher seniority.

Third, once an Agent has sought advice according to one of these criteria, it may be influenced by its advisor; in this case, it updates its opinion and uncertainty as explained above.

Simulation dynamics

A simulation is organized around two different time units. A step represents a year in the real Court, and a sub-step represents a month, with 10 months per year. 147 Agents belong to 21 Chambers of 7. Each year, all Agents who have been there for 14 years leave the Court and an equal number of newcomers replace them, while all remaining Agents are re-allocated randomly to a new Chamber. Agents that have been at the Court for more than 8 years can be President of a Chamber, with only one President per Court at each step. Newcomers are given uncertainty and opinion as described earlier, and an "age" (seniority) of 0 at entry.

At initialization, Agents' age is randomly picked between 0 and 14; those with age of at least 8 are given low uncertainty and low opinion, whereas those with age of 7 or less are given high uncertainty.

Each month, Agents decide whether to seek advice; if they do, they also choose an advisor. Then, centrality and opinion are observed for all. We run the simulation for multiples of 14 steps, so that we have several "generations" in a row (agents that are there at start will all be gone after 14 years).

Parameters for a simulation are: the type of choice for interaction (1), the initial opinion (2) and uncertainty (3) of initial senior agents (more than 8 years), the opinion (4) and uncertainty (5) of initial junior agents and of subsequent newcomers. In this paper we develop precise results that correspond to 18 simulation protocols with all six values for parameter 1 and three values for parameter 2.

First set of results: Centrality

To evaluate our hypotheses on how judges select their advisors, let us first compare simulated and empirical indegrees (Figure 2). Our purpose is to identify which of the six options under scrutiny best approximates real-world data, in the hope to provide insight into the underlying social processes. It appears that pure choices do not fit the data well. Both authority and homophily produce a relatively large group of middle-level advisors with indegrees between 10 and 20 and maxima of about 30, much lower than observed values. Reputation divides Agents into two groups, a large one with lower indegrees than in the data, and a tiny one with indegrees of more than 70, much higher than empirical levels. Random choice is also unsatisfactory: while it follows the empirical distribution rather closely for low-rank agents, it yields a relatively low maximum that hardly fits the data. Mixed strategies perform better, particularly Authority-Reputation which separates agents into three groups, one with bottom-level indegrees (0-10), one with intermediate-level values (10-20), and one with high values (about 35-50, very close to observed values). Instead, the Authority-Homophily mechanism produces a maximum lower than 20, inconsistent with the data.

The Authority-Reputation mechanism enables both exogenous factors (seniority and formal roles) and endogenous mechanisms to affect the evolution of the advice network. [START_REF] Rouchier | Articulation of hierarchy and networks as an evolving social structure[END_REF] note that, if we start from pure reputation and add formal hierarchy, we observe an increase in the number of central actors and a reduction of the gap between those with the highest indegrees and the others. In sociological perspective, this result sheds light on the importance of a formalized hierarchy for the distribution of knowledge and power.

Conversely, if we take pure hierarchy as our starting point, adding reputation allows some non-senior, non-president agents to acquire centrality, which reflects the fact that informal networks may deviate from official organizational charts, with a potential impact on performance (see e.g. [START_REF] Krackhardt | Informal Networks: the Company behind the Chart[END_REF]. The difference between results obtained with the mixed strategy and its two pure components suggests that although formal positions at the CCP are sometimes correlated with high centrality, it is not always the case, and informal mechanisms also operate.

The fact that the authority-reputation mechanism prevails over authority-homophily confirms the finding of [START_REF] Lazega | Réseaux et controverses: de l'effet des normes sur la dynamique des structures et les processus sociaux[END_REF] that at the CCP, status is decisive but there is no pure effect of norm similarity on advisor selection.

Opinion dynamics

To assess agents' criteria for selection of advisors, we also need to account for the possibility of a kind of organizational "culture" that may transform the opinion of members over time.

We use two main indicators to characterize the system: the evolution of average opinion and the opinion of agents at the last time step relative to their age. For the latter indicator, two typical situations can arise: 1/ either all Agents converge to the same opinion after they have been in the Court for some years or 2/ they display two diverging opinions and the distance between these opinions is larger than the uncertainty of newcomers. These two situations are similar to the possible equilibria described in [START_REF] Deffuant | How can extremism prevail? A study based on the relative agreement interaction model[END_REF]. As said before, for each choice procedure, we study three initial settings: when initial senior members are very tolerant (with a low opinion of 0.1) and increasingly less tolerant (opinions of 0.2 and 0.3). What we observe in this setting is that results depend both on the choice procedure and on the initial opinion of Senior Agents. In table 1, this result is made more precise. The data are given for 10 simulations per case, as an average which is statistically significant. Two situations can be observed in the system, either there is just one opinion among Senior Agents at the end of the simulations or two opinions cohabit. Remarkably in most cases, the average opinion of seniors remains very close to the initial Senior opinion. In most cases as well, the number of Agents that deviate is very low. This means that even after 5 generations, Agents who stay for more than 8 years in the Court are led to think similarly to those who left the organization 70 years before. The initial opinion has an impact, as well as the way of choosing who to communicate with. The lower the initial opinion of Seniors, the more often one can witness the formation of two groups, because a higher number of newcomers cannot communicate with those who are attracted by, or are at, the lower opinion of the beginning.

Two separated groups appear most often when Homophily is used for choosing other Agents, which means that there is a reinforcement among Agents who deviate from the low opinion. In all other cases, one can consider that extremely few Agents deviate, and that they have almost no impact on the average final opinion. Hence, almost all of our current choice procedures are in line with the data collected in the study. In particular, this is true of the Authority-Reputation procedure (which has been shown above to be particularly relevant for indegree centrality). It has to be noted that the reproduction of culture in a group of this kind has not been produced with such a simple algorithm until now.

Conclusions

For the moment, the mix of Authority and Reputation gives the best result in the simulation compared to field data. It corresponds to important observed features of our case study and gives rise to plausible results on opinion, showing the combined importance of both the formal structure of the Court and of endogenous reinforcement effects.

For future work, homophily has to be defined differently for two reasons. First, it gives outlying results in terms of evolution of opinion. Second, the algorithm itself may be little credible, since the information needed for Agents to choose whom to ask advice, requires information that is unlikely to be available before communication takes place (opinion). As a consequence, we plan to redefine homophily and make it more dependent on structure (age classes for example).

6.

Figure 1 :

 1 Figure1: Observed indegree centrality at waves 1, 2, 3. Indegrees are on the y-axis and judges' position in the ranking of indegrees (in ascending order) on the x-axis; it emerges that the majority of judges receive very few requests for advice, if any, while a core of highly central advisors are much sought out by others. It can be noted that the three waves are slightly different in values but share the same qualitative shape.

Figure 2 :

 2 Figure 2: Simulated vs. empirical indegree centrality. Simulated values are obtained with pure forms of choice, randomness, and mixed forms, at the end of a simulation period of 70 time-steps (i.e. five "generations"), corresponding to the medium-long run. Empirical indegrees are taken at the last date of observation (wave 3). Agents' indegrees are on the ordinate and their position in the global ranking of indegrees is on the abscissa. Pure forms: A, H, R

Figure 3 :

 3 Figure 3 : represents the opinion of Agents present at the Court after 70 time-steps. Age is on the abscissa and opinion on the ordinate, and we observe the number of clusters of opinion for Senior Agents, those who have been in the Court long enough to learn. Two cases can be identified: two opinions (for Homophily and initial Senior opinion of 0.1); one opinion (for Authority and initial Senior opinion of 0.3).Homophily when initial Senior Agents' opinion is 0.1

Table 1 : Opinion of Senior Agents at final time step, by initial Senior opinion and mode of advisor selection. The results are given for 10 simulations for each case -i.e. initial Senior opinion of 0.1, 0.2, and 0.3. With Homophily, two groups always emerge and the larger one in all cases is the one with high value opinion (as in figure 3 above). With Authority or Random, which give high importance to the structure of interaction, when the initial value is low a small group of high-opinion Seniors emerges as well.

 1

	Average	0.1 0.2 0.3 Percentage of Senior Agents	0.1	0.2 0.3
	opinion	with high opinion
	Authority 0.3 0.3 0.34 Authority	18	8	0
	Reputation 0.44 0.44 0.47 Reputation	0	0	0

Homophily 0.78 0.76 0.76 Homophily 95 90 92

	Random	0.28 0.29 0.35 Random	15	0	0
	Authority-	0.38 0.39 0.41 Authority-Reputation	0	0	0
	Reputation
	Authority-	0.28 0.30 0.33 Authority-Homophily	15	8	0
	Homophily

Indegrees measure the number of incoming ties, and indegree centrality captures the extent to which an actor is identified by others as one of their contacts[START_REF] Kilduff | Bringing the individual back in: A structural analysis of the internal market for reputation in organizations[END_REF]; it can be interpreted as a form of popularity or prestige(Wassermann and Faust 1994, pp. 174-75,

[202][203].2 Outdegrees measure the number of outgoing ties.3 More precisely, being punitive means awarding the injured party not only "material" damages but also "moral" damages: the former are amounts of money that make up for the losses incurred because of the unfair behavior of the offender, while the latter are solely meant to discourage relapse into such practices. There is no consensus on whether the very concept of moral damages applies to business.

We follow the agent-based literature in noting Agent when referring to artificial entities, and agent in the case of real-world ones.

A probability of

60% was suggested by Lazega and Mounier based on fieldwork. In[START_REF] Rouchier | Articulation of hierarchy and networks as an evolving social structure[END_REF] it was shown to lead to plausible indegree centrality values.6 All random choices in the model are drawn from uniform distributions.

We thank Emmanuel Lazega and Lise Mounier for providing access to the data as well as valuable documentation and information on the case study considered. Tubaro gratefully acknowledges financial support from the European Science Foundation (ESF) under the EUROCORES-ECRP I program.


Bruno Guillon
email: bruno.guillon@uca.fr

Giovanni Pighizzini
email: pighizzini@di.unimi.itcprigioniero@di.unimi.itdprusapa1@cmp.felk.cvut.cz

Luca Prigioniero

Daniel Průša

Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines *

In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and oneway nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases (e.g., restrictions of the class of simulated automata or of the class of simulating automata). However the problem remains open in the general case, the best-known upper bound being exponential. We present a new approach in which unrestricted nondeterministic finite automata are simulated by deterministic models extending two-way deterministic finite automata, paying a polynomial increase of size only. Indeed, we study the costs of the conversions of * This work contains, in an extended form, some material and results which were previously presented in a preliminary form in conference papers [20] and [5].

Introduction

One-way deterministic finite automata (1dfas) are the canonical acceptor for the class of regular languages. By allowing nondeterministic transitions (1nfas) or/and movements of the head in both directions on the input tape, so obtaining two-way deterministic and nondeterministic finite automata (2dfas/2nfas), the computational power does not increase [START_REF] Michael | Finite automata and their decision problems[END_REF][START_REF] Shepherdson | The Reduction of Two-Way Automata to One-Way Automata[END_REF]. Other extensions of finite automata have been proved to capture the same class of languages, such as constant-height pushdown automata [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF][START_REF] Guillon | Non-selfembedding grammars, constant-height pushdown automata, and limited automata[END_REF], straight-line programs [START_REF] Geffert | More concise representation of regular languages by automata and regular expressions[END_REF], 1-limited automata [START_REF] Wagner | Computational Complexity[END_REF][START_REF] Pighizzini | Limited Automata and Regular Languages[END_REF][START_REF] Pighizzini | Limited automata and unary languages[END_REF], or, as will be of interest for this work, linear-time one-tape Turing machines [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF][START_REF] Průša | Weight-reducing Hennie machines and their descriptional complexity[END_REF][START_REF] Guillon | Two-way automata and one-tape machines -read only versus linear time[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. 1A natural question concerning models that share the same computational power is the comparison of the sizes of their descriptions. In particular, the cost of the elimination of nondeterminism is a standard problem. For instance, it is a classical result that an exponential increase in size is sufficient and, in the worst case, necessary for the conversion of 1nfas to 1dfas [START_REF] Michael | Finite automata and their decision problems[END_REF]. However, already for two-way automata, the famous Sakoda and Sipser question concerning the size blowups from 1nfas or 2nfas to 2dfas is a much more intricate problem. For both conversions, Sakoda and Sipser conjectured that the costs are exponential [START_REF] Sakoda | Nondeterminism and the size of two way finite automata[END_REF]. The question has been solved in some special cases that can be grouped in three classes: by considering restrictions on the simulating machines (e.g., sweeping [START_REF] Sipser | Lower Bounds on the Size of Sweeping Automata[END_REF], oblivious [START_REF] Hromkovic | Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser's separation[END_REF], few reversals 2dfas [START_REF] Kapoutsis | Nondeterminism is essential in small two-way finite automata with few reversals[END_REF]), by considering restrictions on languages (e.g., unary case [START_REF] Geffert | Converting two-way nondeterministic unary automata into simpler automata[END_REF]), by considering restrictions on the simulated machines (e.g., outernondeterministic automata [START_REF] Geffert | Two-way automata making choices only at the endmarkers[END_REF][START_REF] Kapoutsis | Two-way automata characterizations of L/poly versus NL[END_REF]). However, in spite of all attempts, in the general case the question remains open (for further references see [START_REF] Pighizzini | Two-way finite automata: Old and recent results[END_REF]). Here, we consider a different approach: in order to obtain a polynomial simulation, we enlarge the family of simulating machines. To this end, we study size blowups for the conversion of 1nfas and 2nfas into several variants of linear-time one-tape deterministic Turing machines, which all characterize regular languages. These variants and their properties have been investi-recurs ively enumera ble (type 0) regular (type 3) context -sensit ive (type 1) d e te rm in is ti c co n te xt -s en si ti ve weight-reducing dHms (wrdHms) deterministic Hennie machines (dHms) halting wrdTms end-marked dTms linear-time dTms weight-reducing dTms (wrdTms) one-tape deterministic Turing machines (dTms)

Figure 1: Variants of one-tape deterministic Turing machines and their expressive power confronted with the Chomsky hierarchy. In particular, endmarked dTms are known as deterministic linear bounded automata in the literature, and recognize the so-called deterministic context-sensitive languages, a subclass of context-sensitive languages, see [START_REF] Daniel | Deterministic context-sensitive languages: Part II[END_REF]. It is still unknown if such inclusion is strict.

gated in [START_REF] Guillon | Two-way automata and one-tape machines -read only versus linear time[END_REF][START_REF] Guillon | Weight-reducing Turing machines[END_REF]. We now give a short description of them (see Figure 1).

As proven by Hennie, linear-time one-tape deterministic Turing machines recognize regular languages only [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF]. However, it cannot be decided whether or not a one-tape Turing machine actually works in linear time. This negative result remains true in the restricted case of end-marked machines, namely one-tape deterministic Turing machines that do not have any extra space, besides the tape portion which initially contains the input. End-marked machines working in linear time will be called deterministic Hennie machines. To overcome the above-mentioned "negative" results, a syntactical restriction on deterministic one-tape Turing machines, called weight-reducing machines, has been considered. This restriction enforces computations to either be infinite or to halt within a linear number of steps in the input length. In contrast to Hennie machines, this model benefits from nice properties. In particular, it can be decided whether a one-tape Turing machine is weightreducing, and whether a weight-reducing Turing machine is halting whence works in linear time. Furthermore, haltingness of the model can always be obtained paying a polynomial size increase only. However, its space is not limited to the portion of the tape that contains the input at the beginning of the computation, namely the device is not end-marked. Considering endmarked linear-time machines satisfying the syntactical restriction of weightreducing machines, we obtain weight-reducing Hennie machines.

Our main result is that each 2nfa A can be simulated by a one-tape deterministic Turing machine which works in linear time (with respect to the input length) and which has polynomial size with respect to the size of A. We point out that the resulting machine can use extra space, besides the tape segment which initially contains the input. Next, the machine is halting and weight-reducing, thus implying a linear execution time. Hence, nondeterminism can be eliminated with at most a polynomial size increase, obtaining a linear execution time in the input length, and provided the ability to rewrite tape cells and to use some extra space.

We then investigate what happens when the latter capability is removed, namely if the machine does not have any further tape storage, i.e., it is a Hennie machine. We prove that even under this restriction it is still possible to obtain a machine of polynomial size, that is each 2nfa can be transformed into an equivalent Hennie machine of polynomial size. However, the machine resulting from our construction is not weight reducing, unless we require that it agrees with the given 2nfa only on sufficiently long inputs. We do not have this problem in the unary case, namely for a one-letter input alphabet, where we prove that each unary 2nfa can be simulated by a weightreducing Hennie machine of polynomial size. Similar results are obtained for the transformation of 1nfas into variants of one-tape deterministic machines.

The paper is organized as follows. In Section 2 we present some fundamental notions and definitions, included those related to the computational models we are interested in, and we state some basic properties. In Section 3 we present our main simulation result: each n-state 2nfa can be transformed into an equivalent halting weight-reducing machine of size polynomial in n.

In Section 4 we discuss how the simulation changes if the resulting machine is required to be a Hennie machine. Finally, in Section 5 we revise the results of Sections 3 and 4 under the assumption that the simulated automata are one-way instead of being two-way.

Preliminaries

In this section we recall some basic definitions and notations. We also describe the main computational models considered in the paper and we give some preliminary results.

We assume the reader familiar with notions from formal languages and automata theory (see, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]). Given a set S, #S denotes its cardinality and 2 S the family of all its subsets. Given an alphabet Σ, |w| denotes the length of a string w ∈ Σ * , w i denotes the i-th symbol of w, i = 1, . . . , |w|, and ε denotes the empty string.

Finite automata are computational devices equipped with a finite control and a finite read-only tape which is scanned by an input head. A one-way nondeterministic finite automaton (1nfa) is defined as a quintuple A = Q, Σ, δ, q 0 , F , where Q is a finite set of states, Σ is a finite input alphabet, q 0 ∈ Q is the initial state, F ⊆ Q is a set of final states, and δ : Q × Σ → 2 Q is a nondeterministic transition function. At each step, according to its current state p and the symbol σ scanned by the head, A enters one nondeterministically-chosen state from δ(p, σ) and moves the input head rightward to the next symbol. The machine accepts the input if there exists a computation starting from the initial state q 0 with the head on the leftmost input symbol and ending in a final state q ∈ F after having read the whole input. A 1nfa A is said to be deterministic (1dfa), whenever #δ(q, σ) ≤ 1, for any q ∈ Q and σ ∈ Σ.

Providing 1nfas (resp., 1dfas) with the ability of moving the head back and forth, we obtain two-way nondeterministic (resp., deterministic) finite automata (2nfas, resp., 2dfas). They are defined by extending the transition function so that a left (-1) or right (+1) head direction is indicated in each instruction. Furthermore, to prevent the head to fall out the input, the device is end-marked , in the following sense. Two special symbols and not belonging to Σ, called the left and the right endmarker , respectively, surround each input word, and enforce the computation to stay between them (except at the end of computation when accepting, as described below). More precisely, on input w the tape contains w , the left endmarker being at position 0 and the right endmarker being at position |w|+1. By Σ , we denote the set Σ∪{ , }. Formally, the transition function of a two-way automaton is δ : Q × Σ , → 2 Q×{-1,+1} such that, for each transition (q, d) ∈ δ(p, σ), if σ = then d = +1, and if σ = then d = -1 or q ∈ F . In this way, the head cannot violate the endmarkers, except at the end of computation to accept. The machine accepts the input if there exists a computation starting from the initial state q 0 with the head on the 0-th tape cell (i.e., scanning the left endmarker) and ending in a final state q ∈ F after violating the right endmarker.

The other main computational model we consider is the deterministic one-tape Turing machine (dTm). Such a machine is a tuple Q, Σ, Γ, δ, q 0 , F where Q is the set of states, Σ is the input alphabet, Γ is the working alphabet including both Σ and the special blank symbol , denoted by b, that cannot be written by the machine, q 0 ∈ Q is the initial state, F ⊆ Q is the set of final states, and δ :

Q × Γ → Q × (Γ \ { b}) × {-1, +1}
is the partial deterministic transition function. In one step, depending on its current state p and on the symbol σ read by the head, a dTm changes its state to q, overwrites the corresponding tape cell with τ and moves the head one cell to the left when d = -1 or to the right when d = -1, if δ(p, σ) = (q, τ, d). Since δ is partial, it may happen that no transition can be applied. In this case, we say that the machine halts. At the beginning of computation the input string w resides on a segment of a bi-infinite tape, called initial segment, and the remaining infinity of cells contain the blank symbol. The computation over w starts in the initial state with the head scanning the leftmost nonblank symbol. The input is accepted if the machine eventually halts in a final state.

Let A = Q, Σ, Γ, δ, q 0 , F be a dTm. A configuration of A is given by the current state, the tape contents, and the position of the head. If the head is scanning a non-blank symbol, we describe it by zqu where zu ∈ Γ * is the finite non-blank contents of the tape, u = ε, and the head is scanning the first symbol of u. Otherwise, we describe it by q bz or zq according to whether the head is scanning the first blank symbol to the left or to the right of the non-blank tape contents z, respectively. If, from a configuration zqu the device may enter in one step a configuration z q u , we say that z q u is a successor of zqu, denoted zqu z q u . A halting configuration is a configuration that has no successor. The reflexive and transitive closure of is denoted by * . On an input string w ∈ Σ * , the initial configuration is q 0 w. An accepting configuration is a halting configuration zq f u such that q f is a final state of the machine. A computation is a (possibly infinite) sequence of successive configurations. It is accepting if it is finite, its first configuration is initial, and its last configuration is accepting. Therefore, L (A) = {w ∈ Σ * | q 0 w * zq f u, where q f ∈ F and zq f u is halting}.

We say that two machines T and H agree on some language L if every string in L is accepted by T if and only if it is accepted by H.

The notions of configurations, successors, computations, and halting configurations naturally transfer to one-way and two-way finite automata.

In the paper we consider the following restrictions of dTms.

End-marked machines. We say that a dTm is end-marked , if at the beginning of the computation the input string is surrounded by two special symbols belonging to Γ, and respectively, called the left and the right endmarkers, which can never be overwritten, and that prevent the head to fall out the tape portion that initially contains the input. Formally, for each transition δ(p, σ) = (q, τ, d), σ = (resp., σ = ) implies τ = σ and d = +1 (resp., d = -1). This is the deterministic restriction of the well-known linear-bounded automata [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF]. For end-marked machines, the initial configuration on input w is q 0 w .

Weight-reducing Turing machines. A dTm is weight-reducing (wr dTm), if there exists a partial order < on Γ such that each rewriting is decreasing, i.e., δ(p, σ) = (q, τ, d) implies τ < σ. By this condition, in a wrdTm the number of visits to each tape cell is bounded by a constant. However, one wrdTm could have non-halting computations which, hence, necessarily visit infinitely many tape cells.

Linear-time Turing machines. A dTm is said to be linear-time if over each input w, its computation halts within O(|w|) steps.

Hennie machines. A Hennie machine (dHm) is a linear-time dTm which is, furthermore, end-marked.

Weight-Reducing Hennie machines. By combining previous conditions, weight-reducing Hennie machines (wr dHm) are defined as particular dHm, for which there exists an order < over Γ \ { , } such that δ(p, σ) = (q, τ, d) implies τ < σ unless σ ∈ { , }. Observe that each end-marked wrdTm can execute a number of steps which is at most linear in the length of the input. Hence, end-marked wrdTm are necessarily weight-reducing Hennie machines.

The size of a machine is given by the total number of symbols used to write down its description. Therefore, the size of a one-tape Turing machine is bounded by a polynomial in the number of states and of working symbols, namely, it is

Θ(#Q • #Γ • log(#Q • #Γ)).
In the case of nondeterministic (resp., deterministic) finite automata, since no writings are allowed and hence the working alphabet is not provided, the size is linear in the number of instructions and states, which is bounded by a function quadratic (resp., subquadratic) in the number of states and linear in the number of input symbols, namely, it is

Θ(#Σ • #Q 2 ) (resp., Θ(#Σ • #Q • log(#Q))).
We now state two preliminary results that will be used in the subsequent sections for building weight-reducing Turing machines and weight-reducing Hennie machines, respectively.

It is known that a dTm works in linear time if and only if there exists a constant k such that in no computation the head visits each tape cell more than k times [START_REF] Hennie | One-tape, off-line Turing machine computations[END_REF]. The following lemma states that, whenever k is known, a weight-reducing Turing machine can be obtained, augmenting linearly the working alphabet only. Indeed, we can enforce the machine to store on each tape cell the number of further visits the head is allowed to perform on the cell. As this number decreases, the overwriting is decreasing. Using k copies of each working symbols is enough to implement this. Therefore, in order to define a wrdTm, it is sufficient to define a dTm and to provide a constant k bounding the number of visits of each tape cell.

Lemma 1 ([6]

). Let T = Q, Σ, Γ, δ, q 0 , F be a dTm such that, for any input, T performs at most k computation steps on each tape cell. Then there is a wr dTm A accepting L(T ) with the same set of states Q as T and working alphabet of size O(k •#Γ). Furthermore, on each input A uses the same space as T . Hence, if T is linear time or end-marked then so is A.

Weight-reducing Turing machines extend weight-reducing Hennie machines by allowing the use of some extra space besides the portion that initially contains the input. Indeed, the former model can use a bi-infinite tape while the latter is end-marked. However, it has been shown that every finite computation of a wrTm uses a constant amount of this extra space [START_REF] Guillon | Weight-reducing Turing machines[END_REF]. We do not know whether the use of this extra space can be avoided in general, while keeping the weight-reducing property and bounding the size increase by a polynomial. Nevertheless, this can be achieved when the inputs are long enough.

Lemma 2. Let T be a weight-reducing Turing machine which uses at most C initially-blank cells in every halting computation. Then, there exists a weightreducing Hennie machine H of size polynomial in the size of T , which agrees with T on every input of length at least C.

Proof. The idea of the proof is the same as the folkloric simulation of Turing machines working on a bi-infinite tape by Turing machines working on a semiinfinite tape. Indeed, we fold the portion of the tape occurring to the left of the initial segment onto the complementary portion of the tape, thus creating a second track. Similarly, we can fold the portion of the tape occurring to the right of the initial segment onto the complementary portion of the tape. Next, as T uses at most C initially-blank cells in total, and providing the input has length at least C, we observe that the additional tracks do not overlap hence only one additional track is sufficient for the simulation. On shorter inputs, the simulation could fail giving an outcome different from those of T . Doing so, we obtain a dHm H that uses twice the number of states of T (two copies of each state of T for indicating which track should be read), and the working alphabet Γ H = Γ∪Γ 2 where Γ is the working alphabet of T . In particular, the size of H is polynomial in the size of T . Finally, we can extend the order < T on Γ witnessing that T is weight-reducing, to an order < H on Γ H witnessing that H is weight-reducing.

Simulating Two-way Automata by Weightreducing Machines

This section is devoted to present our main simulation: we show that every 2nfa A = Q, Σ, δ, q 0 , F can be transformed into an equivalent wrdTm of size polynomial in the size of A. Our construction is based on the classical simulation of 2nfas by 1dfas, inspired from Shepherdson's construction [START_REF] Shepherdson | The Reduction of Two-Way Automata to One-Way Automata[END_REF].

The main idea is to perform forward moves, while updating a table of size n = #Q 2 that describes parts of computations which may occur to the left of the current position. In parallel, an adaptation of the classical powerset construction for converting 1nfas into 1dfas is done, in such a way that the set of states that are accessible from the initial configuration when visiting for the first time the current head position is updated at each move. In the simulation by 1dfas, the table and the set are stored on the finite state control. In our simulation by wrdTms they will be written, under a suitable encoding, in O(n) many tape cells.

To describe computation paths that occur on some restricted part of the tape, we define partial configurations, by relaxing the definition of configurations, as strings xqy where q is a state and xy ∈ { , ε} • Σ * • { , ε} is a factor of the tape content. The successor relation on configurations extends onto partial configurations. In particular, zpX * zXq with |X| = 1 means that there exists a computation path • starting from the rightmost position of zX (with the head scanning the symbol X) in state p,

• ending while entering the cell to the right of this position in state q, and • which visits only cells from the part of the tape containing zX in the meantime.

By storing in a set τ zX the pairs of states (p, q) such that such a computation path exists, we save the possible behaviors of A when moving backward from the current position. Indeed, since acceptance is made after violating the right endmarker, from such a point the device should eventually turn back forward from the current position, in order to reach an accepting configuration. We are going to give the formal definition of the set τ zX for a prefix zX of the tape content, together with the definition of the set γ zX of states that are reachable from the initial configuration, when visiting for the first time the position to the right of the part containing zX. Formally, for

X σ z r 0 s 0 r 1 s 1 r q • • •
Figure 2: A computation path from p = r 0 to q giving (p, q) ∈ τ zσ . For each i, (s i , r i+1 ) ∈ τ z and (s i , -1) ∈ δ(r i , σ), while (q, +1) ∈ δ(r , σ).

a prefix zX ∈ { } • Σ * • {ε, } of the tape content with |X| = 1:

τ zX = {(p, q) ∈ Q × Q | zpX * zXq }, and
γ zX = {r ∈ Q | q 0 zX * zXr }.
Observe that a word w ∈ Σ * is accepted by A if and only if F ∩ γ w = ∅.

In order to simulate A on input w, it is thus sufficient to incrementally compute γ z for each prefix z of w . To do so, we will keep updated the table τ z as well. Indeed, given γ z , τ z and a symbol σ, it is possible to compute γ zσ and τ zσ . This is achieved by observing that (see Figure 2):

1. (p, q) ∈ τ zσ if and only if there exists a sequence r 0 , s 0 , r 1 , s 1 , . . . , r ∈ Q, with ≥ 0, satisfying:

• r 0 = p,

• (q, +1) ∈ δ(r , σ), and

• (s i , -1) ∈ δ(r i , σ) and (s i , r i+1 ) ∈ τ z , for i = 0, . . . , -1.

2. q ∈ γ zσ if and only if there exists p ∈ γ z such that (p, q) ∈ τ zσ .

We represent a pair (γ z , τ z ) as a word uv in {0, 1} * with |u| = n and |v| = n 2 . Each bit of u (resp., v) indicates the membership of some state p (resp., some pair (p, q) of states) to the set γ z (resp., τ z ) through an implicitly fixed bijection from Q to {1, . . . , n} (resp., from Q 2 to {1, . . . , n 2 }). For each input symbol σ, there exists a halting dHm T σ which computes (γ zσ , τ zσ ) from (γ z , τ z ) in the following sense. On input uv ∈ {0, 1} n+n 2 encoding (γ z , τ z ), T σ ends the computation with the tape containing the encoding u v ∈ {0, 1} n+n 2 of (γ zσ , τ zσ ). Notice that this computation does not depend on the entire z, which, indeed, is not given to T σ , but only on the information on z stored in γ z and τ z which are given in input.

Lemma 3. For each σ ∈ Σ ∪ { }, there exists a halting dHm T σ with O(n 6 ) states and O(1) working symbols that on input (γ z , τ z ) halts with the tape containing (γ zσ , τ zσ ) after O(n 5 ) visits to each cell. The input and the output are represented on the tape as strings in {0, 1} n+n 2 .

Proof. Fixed σ, let uv be the input string encoding the pair of tables (γ z , τ z ), of size n and n 2 respectively. In order to update them, T σ uses a second track on the tape, on which it will progressively build the updated tables. At the end of the computation, namely when the updated tables have been determined and written down over the second track, the device performs a projection of the tape on its second track, in order to produce the correct output, and halts. We fix the working alphabet Γ = {0, 1} ∪ {0, 1} 2 . The "simple" symbols from {0, 1} are used only for the input and the output of T σ . From now on, we suppose that the tape contains only symbols from the 2-track alphabet part, i.e., the right side of the union. Moreover, since the length of the input is fixed and it is n + n 2 , we can suppose that T σ keeps updated a state component of size n + n 2 which always stores the position of its head on the tape. This allows it to navigate over the tables.

We divide the tape into two parts: a prefix u of length n (thus covering the factor u which encodes γ z on its first track) and a suffix v of length n 2 (thus covering the factor v which encodes τ z on its first track). As previously explained, the updated table γ zσ can easily be obtained once the updated table τ zσ has been computed. Hence, we first show how to write the table τ zσ on the second track of v. This is achieved using the space n available on the second track of u as temporary memory, to which we refer as temporary table.

As observed above (see Figure 2), a computation path on the segment containing zσ starting from the rightmost position of the segment and exiting the segment to the right at its last step, i.e., a computation of the form zpσ * zσq, can be decomposed into an alternation of computation paths on the segment containing z (described by the table τ z ) and of backward computation steps on σ connecting these paths, followed by a last forward computation step on σ that exits the segment. For each state p, in order to decide which pairs (p, q) belong to τ zσ , the machine T σ first computes the set Z p of states that are reachable at the rightmost position of the segment containing zσ, from the state p at the same position, by visiting only cells from the segment, i.e.,

Z p = {r | zpσ * zrσ}.
Thus, a pair (p, q) belongs to τ zσ if and only if for some r ∈ Z p , we have (q, +1) ∈ δ(r, σ). For a fixed p, T σ can incrementally construct Z p on the temporary table as follows. Initially, all the cells from the table are unmarked (i.e., contain 0) except the one corresponding to state p which contains 1. The update process behaves as follows: for each state r corresponding to a marked cell, each state s such that (s, -1) ∈ δ(r, σ), and each state r such that (s, r ) ∈ τ z , the machine marks the cell corresponding to r with 1 in the temporary table. Since Z p has size bounded by n, after at most n passes, the temporary table is not modified anymore and contains exactly an encoding of Z p .

So done, computing the set Z p uses only a polynomial number of states in n. This is however not sufficient to get a weight-reducing machine of polynomial size. To this end, using Lemma 1, we should indeed prove that the number of visits to each cell is bounded by some polynomial in n. To update Z p , three nested loops on states, namely on r, s, and r , are used. Once such a triple is fixed, the machine navigates on the tape in order to check that r is currently marked in the temporary table, and (s, r ) ∈ τ z (notice that the condition (s, -1) ∈ δ(r, σ) is verified in constant time, since σ is fixed). These two conditions require to read the corresponding cells in the temporary table (on u) and in the table τ z (on v), respectively. This can be performed by visiting each tape cell at most twice. Marking the cell corresponding to r also implies to scan the tape part u twice. As the operation is repeated for each triple, we obtain that the number of visits to each cell in a pass for updating Z p is O(n 3 ). Since the number of passes is at most n, the total number of visits to each cell is O(n 4 ). Moreover, this operation can be implemented by using O(n 3 ) states because we just need to remember the values of r, s, and r , but not the number of the pass: it is sufficient to use a bit to remember if during the last pass at least one state has been added to Z p . This is because if no states are added during a pass, then no states will be added executing further iterations.

Once Z p has been computed, for each state r corresponding to a marked cell in the temporary table, and each state q such that (q, +1) ∈ δ(r, σ), T σ adds the pair (p, q) to the table τ zσ represented on the second track of v. This requires to visit O(n) times each tape cell and can be performed using only a quadratic number of states in n.

By repeating this for each state p, we manage to update the table from τ z to τ zσ . Finally, we can update the table γ z . As observed before, it is sufficient to consider for each state q, whether (p, q) ∈ τ zσ for some p ∈ γ z . This last step requires only a quadratic number of states and a linear number of visits to each cell. Combining the above-described subroutines, and taking into account that the state component which stores the head position has size O(n 2 ), we obtain a dHm with O(n 6 ) states and O(1) working symbols, whose number of visits to each tape cell is in O(n 5 ).

We are now ready to state our main simulation.

Theorem 1. Every n-state 2nfa can be transformed into an equivalent halting wr dTm of size polynomial in n.

Proof. Let A = Q, Σ, δ, q 0 , F be a 2nfa. We build a deterministic Turing machine that mimics the simulation of A by a 1dfa: after reading any prefix z of an input w, the machine stores the tables γ z and τ z and finally checks the existence of a final state in γ w . The tables are stored on a suitable tape track and updated each time a further input symbol is read, using the method presented in Lemma 3. This can be achieved by switching between two tape tracks at each update of the tables. However, as the number of updates is linear in the length of the input, storing and updating the tables on a fixed part of length n + n 2 of the tape would lead to a non-weightreducing Turing machine. To handle this issue, for each prefix z of w, we store the tables γ z and τ z on the n + n 2 cells that precede the last position of z. (Remember that, in a wrdTm, some initially-blank cells to the left of the initial segment are available.) Thus, at each update of the tables made according to Lemma 3, the tables are shifted one cell to the right. Hence, since a fixed cell may occur in n + n 2 successive stored tables, the number of visits to each cell is in O(n 7 ), and the number of states is in O(n 6 ). We thus obtain a halting weight-reducing Turing machine equivalent to A whose size is polynomial in the size of A by Lemma 1. Furthermore, the machine uses only n + n 2 initially-blank cells, that are all to the left of the initial segment.

Simulating Two-way Automata by Hennie Machines

In Section 3 we provided a polynomial size conversion from 2nfas to wrdTms.

The resulting machines use further tape cells, besides the initial segment. In this section we study how to make such a simulation when the use of such extra space is not allowed, namely when we want to obtain a deterministic Hennie machine. We show that a polynomial conversion still exists, but we are not able to guarantee that the resulting machine is weight reducing. Actually this issue is related to "short" inputs, namely to strings of length less than n 2 , where n is the number of states of the given 2nfa. For such inputs we do not have enough tape space to perform the simulation in Theorem 1.

We will deal with them, by using a different technique.

Let us start by considering acceptance of "long" inputs.

Theorem 2. For each n-state 2nfa A, there exists a wr dHm H of size polynomial in n which agrees with A on strings of length at least n 2 .

Proof. The technique used in the proof of Theorem 1 can be exploited, with slight modifications. Indeed, when recovering the tables corresponding to the "short" prefixes z's of the tape content, the wrdTm machine resulting from the above construction uses up to n + n 2 initially-blank cells to the left of the initial segment, that are not any longer available with a wrdHm. By folding n of these cells on an additional track, as in the proof of Lemma 2, we can reduce this space amount to n 2 cells by a polynomial size increasing. Hence, applying Lemma 2, we can obtain a wrdHm which agrees with the original machine on inputs of length at least n 2 .

In the case of unary 2nfas, namely working on a single-letter input alphabet, the number of short inputs that are not handled by Theorem 2 is n 2 . They can be managed in a read-only preliminary phase which uses O(n 2 ) states.

Theorem 3. Every n-state unary 2nfa is equivalent to a wr dHm of size polynomial in n.

Proof. We simulate a given unary 2nfa A as follows. Let X be the finite set {i < n 2 | i = |w| for some w ∈ L}. First, the head of our simulating wrdHm is moved rightward to test whether the input is shorter than n 2 , using a counter from 0 to n 2 -1. In this case, the machine accepts if and only if the counter value belongs to X. Otherwise, the head is moved back to the left endmarker and the simulation from Theorem 2 is performed. With respect to the wrdTm obtained from Theorem 2, our device uses O(n 2 ) additional states and O(1) extra working symbols. Hence, our construction yields a wrdHm equivalent to A of size polynomial in n.

In the nonunary case, since the number of short strings is exponential in n, we cannot apply the same technique as in Theorem 3. However, we are able to obtain a polynomial size Hennie machine (not necessarily weight reducing), using a different technique, which is based on the analysis of the computation graph of the simulated 2nfa. Proof. Let A = Q, Σ, δ, q 0 , F be a 2nfa, with #Q = n. Without loss of generality we suppose F = {q f }. Let w ∈ Σ * be an input word, with m = |w|. We distinguish three cases, depending on m. Observe that the simulating dHm H can decide the case by performing a reading traversal of the input using a polynomial number of states.

If m ≥ n 2 , then H simulates A as in Theorem 2.

If m ≤ log n, then H simulates a 1dfa with a polynomial number of states in n (and in the number of input symbol which is assumed to be a fixed constant), which agrees with A on all strings of length at most log n.

Finally, if log n < m < n 2 , then H checks whether there is an accepting computation of A on w by analyzing the computation graph G = V, E of A on w, defined as follows. The set of vertices of G is V = Q × {0, . . . , m + 1} ∪ {(q f , m + 2)}, where the pair (q, i) ∈ V corresponds to the configuration on input w in which A is in the state q while scanning the i-th symbol of the input tape. The edges in E represent single moves, i.e., there exists an edge from (q, i) to (p, j) if and only if (p, j -i) ∈ δ(q, w i ), where w = w .

The simulating Hennie machine H should check the existence of a computation of A starting from the initial state q 0 with the head on the left endmarker (i.e., at position 0) and ending in the unique final state q f after violating the right endmarker (i.e., at position m + 2). This is equivalent to check the existence of a path from the node (q 0 , 0) to the node (q f , m + 2) in G. Let K = n(m + 2) + 1 be the number of nodes in G. If such a path exists, then there should exist one of length at most K. Hence, checking the existence of an accepting computation reduces to checking the existence of a path of length at most K in G. The recursive function reachable is used to perform this checking by calling reachable(q 0 , 0, q f , m + 2, K).

Let us describe how a call of reachable(p, i, q, j, T ) works. The function has to check if there exists a computation from (p, i) to (q, j) of length at most T . This is done by using a divide-and-conquer technique as in the famous proof of the Savitch's Theorem [START_REF] Walter | Relationships between nondeterministic and deterministic tape complexities[END_REF]. If (p, i) = (q, j), i.e., there is a path of length 0 from (p, i) to (q, j), then the function returns true independently of T (Line 1). Otherwise, if T = 0 but (p, i) = (q, j), then the function returns false (Line 2), while, if T = 1, the function returns true if there is a suitable edge in G (Line 4). In order to verify that, H saves (q, i) and (p, j) in its internal state and then, if the distance between i and j is 1, it moves its head to position i, reads the symbol w i , and checks (q, j -i) ∈ δ(p, w i ). Notice that this read-only process uses only a number of states polynomial in n.

In the recursive case, for checking if there exists a path in the graph from (p, i) to (q, j) of length at most T > 1, H verifies whether there exists a node (r, ) ∈ Q × {0, . . . , m + 1} such that there is a path from (p, i) to (r, )

Considering also how the machine works on inputs of length at least n 2 , this allows us to conclude that the working time of the whole machine H is linear in the input length.

It is natural to ask if Theorem 4 can be improved in order to obtain from a given 2nfa A an equivalent wrdHm of polynomial size. In the light of Theorem 2, to do that it will be enough to obtain a wrdHm of polynomial size which agrees with the 2nfa on "short" inputs. With this respect, we point out that the problem of Sakoda and Sipser seems to be hard even when restricted to strings of length polynomial in the number of states of A [START_REF] Kapoutsis | Two-way automata versus logarithmic space[END_REF].

The One-Way Case

In this section we restrict our attention to one-way automata simulations. A natural question is to ask if in the case of 1nfas results stronger than those presented in Section 4 can be achieved. A simulation of 1nfas by wrdHms was studied in [START_REF] Průša | Weight-reducing Hennie machines and their descriptional complexity[END_REF]Theorem 11], claiming that each n-state 1nfa A has an equivalent wrdHm H of size polynomial in n. Unfortunately, the presented proof is incorrect as it casts the problem of A acceptance as the problem of reachability in an undirected computation graph. Existence of a path connecting the initial and an accepting configuration in such a graph does not guarantee the existence of an accepting computation of A since the path can include "back" edges.

By revising [START_REF] Průša | Weight-reducing Hennie machines and their descriptional complexity[END_REF]Theorem 11], we prove two weakened variants of this result. In the first one, the simulation holds only for long enough inputs. The improvement with respect to Theorem 2 is that, in this case, short inputs are the strings of length less than n rather than n 2 . In the second variant, we show that each 1nfa can be simulated by a deterministic Hennie machine which, however, is not weight-reducing.

Let us start by presenting the weight-reducing simulation for "long" inputs.

Theorem 5. For each n-state 1nfa A, there exists a wr dHm H of size polynomial in n which agrees with A on strings of length at least n.

Proof. In order to obtain H, we build a dTm T equivalent to A with the following properties: (P1) the size of T is bounded by a polynomial in the size of A; (P2) the number of visits to each cell in any computation is bounded by a polynomial in n; (P3) only n tape cells beside the initial segment are used, in any computation.

Then, using (P2) and Lemma 1, T can be turned into an equivalent wrdTm preserving (P1) and (P3). Finally, using (P3) and Lemma 2, the resulting wrdTm is converted to the wanted wrdHm H whose size is polynomial in the size of A.

We build T by adapting the classical powerset construction for converting 1nfas into 1dfas. In this standard construction, the simulating 1dfa scans the input word, while keeping updated, at each step, the subset of states that can be reached by A from the initial configuration while reading input symbols. Our construction uses this technique but, instead of storing the subset in the finite control of the simulating machine, T stores the successive subsets on the tape, exploiting the writing capability of wrdTms in order to avoid an exponential size blowup.

Let A = Q, Σ, δ, q 0 , F with Q = {q 0 , q 1 , . . . , q n-1 }. Following the notations of Section 3, for any input prefix z, we consider the set γ z ⊆ Q of states that are reachable from the initial configuration after having read z. In particular, γ ε is the singleton {q 0 } and an input w is accepted by A if and only if γ w ∩ F is nonempty. In order to store any subset γ z of Q on the tape, we represent it as a word u ∈ {0, 1} n , in which u i is 1 if and only if q i ∈ γ z . Ranging over input prefixes, T iteratively computes γ zσ from γ z , where σ ∈ Σ is the (|z| + 1)-th input symbol. To avoid erasing γ z when writing down γ zσ , T uses two distinct tape tracks: γ z is read from the first track and γ zσ is written on the second one (shifted by one cell to the right with respect to γ z ). The role of the two tracks is inverted after each such update.

At the beginning of the computation, T writes γ ε on the n cells preceding the initial segment (on one track, suppose the first one for ease of exposition). During the simulation, when T reaches a position for the first time, the n tape cells preceding that position will contain the encoding of γ z (on the first track) where z is the input prefix read so far. From such a point, T is able to compute γ zσ , working on the tape portion of length n + 1 that contains both γ z and the current position containing σ, and to which we refer as the current working segment. Indeed, for each q i ∈ Q, we have q i ∈ γ zσ if and only if q i ∈ δ(q j , σ) for some q j ∈ γ z . Since T can test for each q i , q j ∈ Q whether, on the one hand, q j belongs to γ z (by visiting the j-th cell of the current working segment which stores the j-th bit of γ z on the first track), and, on the other hand, q i ∈ δ(q j , σ) (by inspecting the transition table of A), it can write γ zσ on the tape. More precisely, when the two above conditions are satisfied, T writes 1 on the (i + 1)-th cell of the current working segment (on the second track), for storing the i-th bit of γ zσ . Notice that γ zσ is shifted one cell to the right with respect to γ z , so that its last bit is written on the rightmost cell of the current working segment (which initially contains σ). If m > n, the Hennie machine H executes the computation described in the proof of Theorem 5.

In conclusion, the constructed machine H has the number of states and working tape symbols polynomial in n, hence it is of size polynomial in n. Note that the number of transitions performed by H over any tape field is n O(log n) .

Conclusion

Sakoda and Sipser raised the question of the cost of the elimination of nondeterminism from finite automata exploiting the possibility of moving the head in both directions. Though they conjectured that this cost is exponential, we proved that a determinization of polynomial size cost is possible for some simulating machines which are deterministic and have some extra capabilities than 2dfas. The extensions of 2dfas we considered are some special cases of one-tape Turing machines which are not more powerful than 2dfas, namely they recognize the class of regular languages.

In Theorem 4 we showed such a polynomial determinization using Hennie machines. However, this result is not fully satisfying because of known drawbacks of dHms: on the one hand, it is not decidable whether a Turing machine is actually a Hennie machine; on the other hand, no recursive function bounds the size blowup of the conversion of dHms into 1dfas. These drawbacks are avoided when moving to weight-reducing devices [START_REF] Guillon | Weight-reducing Turing machines[END_REF].

We do not know if the simulations of Theorem 4 can be changed in such a way that the resulting dHm is always weight-reducing while keeping the size cost polynomial, and we leave it as an open problem. However, we solve this question in some particular cases. Indeed, when equivalence is required only over long enough inputs, or when the input alphabet is unary, polynomial size determinizations using wrdHms are possible (Theorems 2, 3 and 5). Moreover, our main result states that it is always possible to eliminate nondeterminism from finite automata by using weight-reducing linear-time Turing machines as long as they are not required to be end-marked (Theorem 1), namely when the simulating machine is allowed to use extra tape beside the part that initially contains the input.

Theorem 4 .

 4 Each n-state 2nfa is equivalent to a dHm of size polynomial in n.

  tape cell if O(n 5 ) working tape symbols are provided for this purpose. The function runs in n O(log m) time.

Actually, the model considered by Hennie was deterministic. Several extensions of this result, including that to the nondeterministic case and greater time lower bounds for nonregular language recognition, have been stated in the literature[27, 7, 15, 16,

26].

† Partially supported by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM). ‡ Supported by the Czech Science Foundation, grant 19-21198S.

1

Function reachable(p, i, q, j, T ): boolean Checks the existence of a path from (p, i) to (q, j) of length less than or equal to T in the graph of the configurations of a given 2nfa on input w = w 1 • • • w m 1 if (p, i) = (q, j) then return true 2 if T = 0 then return false 3 if T = 1 then 4 if (q, j -i) ∈ δ(p, w i ) then return true if reachable(r, , q, j, T /2 ) then return true 9 return false of length at most T 2 and a path from (r, ) to (q, j) of length at most T

2

(Lines 6 to 8). This is done by trying all possible nodes (r, ) until finding one satisfying these conditions. If it does not exist, then the procedure returns false (Line 9). Recursive calls to the function reachable can be naturally saved on a pushdown store. More precisely, at the beginning of the simulation the store is empty. When a call to reachable(p, i, q, j, T ) is performed, the activation record, consisting of the parameters p, i, q, j, and T , is pushed on the top of the pushdown. Similarly, when reachable returns, the activation record of the last call is popped off. The function reachable uses seven variables, five of them being arguments saved on the pushdown store, and two being the local variables r and . As these two local variables are arguments of inner recursive calls, their values can be recovered when popping off the inner activation record (after the corresponding call has returned). Hence, the state components saving r and are freed at each recursive call. Therefore, all the checks performed by reachable can be done with a number of states that is polynomial in n, and using the pushdown alphabet

Finally, notice that the maximum recursion depth is log K = O(log n). The stack of recursion calls can be stored in a separated track on log n tape cells, by using standard space compression techniques, that only induce a polynomial increase of the working alphabet. Since the input length m is larger than log n, H has enough space in its initial segment. The number of visits to each cell is super-polynomial in n, hence the machine is not weightreducing. However, because the input lengths are bounded by n 2 , the number of visits to each cell is bounded by a number which only depends on n.

Furthermore, during the update procedure, each cell of the current working segment is visited O(n) times. Finally, when reaching the first cell to the right of the initial segment (containing the blank symbol), T accepts if and only if γ w contains a final state. By slightly modifying the above update procedure, we may assume that this information has been prepared in the finite control. Indeed, when computing γ zσ , T can store in a state component whether γ zσ intersects F .

The described approach implies the use of n extra tape cells to the left of the initial segment, on which T has initially written γ ε . No extra space is necessary, thus (P3) is satisfied. Moreover, the simulating machine uses O(1) working symbols, and O(#Σ • n 3 ) states for simultaneously storing the variables σ, q i , q j , and the head position relative to the current working segment. This implies (P1). Next, each tape cell is used for storing at most n successive subsets of states. Hence, its total number of visits is in O(n 2 ), yielding (P2).

By Theorem 4, every n-state 2nfa can be transformed into an equivalent dHm of size polynomial in n. So, using the same result, we can also transform 1nfas. For this particular case, we now present a more direct simulation which uses a technique similar to that of proof of Theorem 4. Let A = Q, Σ, δ, q 0 , F be an n-state 1nfa. At the cost of one extra state, we suppose F = {q f }. Let w ∈ Σ * be an input to A. Distinguish two cases by m = |w|.

If m ≤ n, the machine H checks whether there is an accepting computation of A on w by calling reachableOneWay(q 0 , 0, q f , m), a slightly modified version of the function reachable presented in the proof of Theorem 4, adapted to deal with 1nfas. Function reachableOneWay(p, i, q, j): boolean Checks the existence of a path from (p, i) to (q, j) of length j-i in the graph of the configurations of a given 1nfa on input w = w 1 • • • w m 10 if (p, i) = (q, j) then return true 11 if j -i = 1 and q ∈ δ(p, w j ) then return true 12 if j -i > 1 then 13 foreach r ∈ Q do 14 if reachableOneWay(p, i, r, (i + j)/2 ) then 15 if reachableOneWay(r, (i + j)/2 , q, j) then return true

return false

The recursion depth is O(log m). At each level of the recursion, the function needs to store states p, q, r and indices i, j. This can be done in a