Psychological Particularities of Tourism

Keywords: social acculturation, ways of thinking, intercultural exchanges, desires, prejudices, stereotypes, ethnocultural diversity

The main objective of our article is to highlight the psychological particularities of tourism in contemporizing society by making the link between the management of tourism, the psychology of tourists (goals, motivations and desires of persons travelling) and the host-countries that focus their economies on the tourism industry. In describing the advantages and disadvantages of tourism, we also examine the causes and consequences of cultural shock deriving from these intercultural exchanges between visitors and hosts during tourist displacement.

The-twenty-one century proves to be the booming century of other ideological, technological, cultural or industrial innovations. The high technology of means of communication and the digitization condition now condition all social activities of the peoples with which the nature of tourism and the tourist curiosity also evolve. These changing perspectives also make the research on tourism dependent on the economic, international, social-psychological or political conjunctures of our time. But we must also take into account that throughout the history of human civilization, the motilities and the original displacement of peoples have allowed the emergence of the earliest forms of human sociability, which have developed with the trade of the cultural, diplomatic exchanges and the family alliances between different communities and also the ambitions thought scientific expeditions. The first geographer scientists have therefore questioned the measurements and representations of the Earth's space. These questions logically led them to the necessity of discovering the Earth and exploring the continents. The terrestrial movements that followed them undeniably led them to come into contact and to exchange with different societies and cultures. This first type of encounter with the other has presupposed its modification, through its psychosocial acculturation. The conquests of the new world, the colonial empires as well as the great earthly expeditions have allowed the European man to discover, to meet and to come into contact with new and hitherto unknown peoples. At present, ethnologists, psychologists, sociologists and anthropologists are interested in the closest and most distant cultures by focusing on studying them from the inside and through the different methods of research. Specifically, the psychological analysis of tourism is centred on several aspects (in particular, on the management of human resources in the tourist business, on the psychology of tourism marketing and on the relationship between travellers and countries-hosts, etc.) and aims on the one hand to study their links through the different ways of thinking specific to each society, but on the other hand it calls on the psychic functions responsible for human behaviors , which guide the action of these partners to tourism . In other words, it is to show how psychic functions (perception, attention, thought, memory, speech, motivation, etc.) intervene or elicit the tourist activity and to understand the mechanisms of operation of these. Specifically, [START_REF] Dann | Theoretical Advances in the Sociological Treatment of Tourism[END_REF] describes that "... how tourism studies would have gone from essentially descriptive approaches to the study of motivations, from the emphasis on relations between hosts and tourists to issues of otherness and similarity in gender relations, young and old people, socially advantaged or socially disadvantaged backgrounds, etc." [START_REF] Dann | Theoretical Advances in the Sociological Treatment of Tourism[END_REF]. [START_REF] Ryan | The Tourist Experience. A New Introduction[END_REF] develops the idea"... a psychology based on the tourist experience with the analysis of motivation, of the satisfaction of the people " [START_REF] Ryan | The Tourist Experience. A New Introduction[END_REF]. For [START_REF] Raboteur | Introduction à l'économie du tourisme[END_REF] "The psychology of tourism is directly linked to the economy and both are articulated around the notions of supply and demand of tourist travel choices and so impacts, economic accounts and industrial themes, managerial and societal tourism " [START_REF] Raboteur | Introduction à l'économie du tourisme[END_REF]. From our point of view, these authors emphasize that the science of tourism is intrinsically linked to economics and psychology, presented as principal developers of the theoretical and methodological tools necessary to study these issues. The themes of displacement and recreation still remain very strong, the temptation of "natural man" and "from nature to nature" still remains prevalent in the study of the psychology of tourism. Whether it is the economic, geographic, social, cultural, sporting, environmental or political aspect, the opinions greatly diverge. In this sense, tourism and leisure are granted the same functions; more importantly, the tourism singularity is approached according to the same reference framework on cultural interests. MacCannel (1976) analyzes the sociology of leisure in an attempt to identify the tourist phenomenon. He writes: "The development of modern societies must be reported to the development of mass recreation, whose international tourism, recreation and sightseeing are the main figure of human activities. To this we must add the question of the internationalization of space" [START_REF] Maccannell | The Tourist. A New Theory of the Leisure Class[END_REF]. It is the notions of "displacement" and "space", then "territory", which come to the rescue of defenders of the specificity of tourism in relation to any other phenomenon. For Wackerman (2007): "The temptation of a certain definition of the natural man is very close: this one would have an innate propensity to travel, it would naturally need to see, need to know, need to discover" [START_REF] Wackermann | mondialisation et risques territoriaux[END_REF].The notions of displacement and space, in particular, constitute a more or less explicit attempt to delimit a scientific field to be conquered. Much like in the case of leisure studies, which have long attempted to define its specificity, the intrinsic nature, the irreducible character, the geography has started in the same way to conquer the field of tourism. This Homos touristicus would therefore be a being of endless curiosity, madly in search of elsewhere renewed knowledge. According to [START_REF] Urry | The Tourist Gaze. Leisure and Travel in Contemporary Societies[END_REF] "Tourism gradually comes to dissolve in characteristics of contemporary societies. Man is recognized by his achievements" [START_REF] Urry | The Tourist Gaze. Leisure and Travel in Contemporary Societies[END_REF]. If he contented himself with "being determined", he could no longer exchange his knowledge, his tools, and his feelings only with words. Man needs to realize his desires, to be able to think and choose the form that answers it best, to find the necessary strength to persevere in action. Thus, tourism relates men who interact with the physical and cultural environment and interact with each other on a specifically human level, through interindividual or organisational exchanges that they are free (as in the context of a fortuitous encounter between a tourist and an autochthonous passer) or currency (services rendered after the purchase of the tour organized by the tourist agency). It is therefore evident that scientific, technical, economic and societal developments oblige to mobilize different scientific knowledge in tourism practices that are constantly diversifying and exploiting themselves. Tourism combines physical, geographical and environmental conceptual data with conceptual data from the humanities. However, if the physical data have tools that are intended to be more objective, the data of the human experience are analyzed with the phenomenal interpretation of the researcher and by the communication. Also to study the social actors of tourism is to go back in time and search in space what participates in their dynamism. The changes we are operating and forcing us to reconsider our relationship to the world. Collective, group, family, entrepreneurial, political action succeeds only through the pooling of knowledge, decisions, implementation by members and consensus and support of the necessary partners. In the face of this observation, it must be thought that in many countries the lack of culture and tourist psychology is a major obstacle to the emergence of tourism. The knowledge of the psychology of tourism, or of the tourism culture, both by States, providers and host populations, remains for this an essential and fundamental asset, in the investigation of a possible promotion of this industry, thus guaranteeing a better economic future for the countries that send tourists and countries that receive tourists. It is about emanating from the different models and their imaginations. They are the source of a phenomenon of considerable mobility of men in tourism. They generate it, orient it and redefine it continually, depending on the historical contexts, variations or transformations of our worldview, and the influence of these variables on the collective psychology of the peoples in particular and humanity in general. The contribution of linguistics to psychology is also considerable. Linguistics began to emphasize the different types of languages, and therefore the diversity of linguistic universes. Language, as a conceptual system of social origin, conveys culture, and thus its psychological affects. The reference to a society as it is, refers not only to a specific linguistic area, but also to a particular cultural area, and therefore to a certain type of mentality or behaviour. Fine arts also require and reveal an apparently specific order of conduct, which can be studied by the artist and his audience. The aesthetic thus leads to research on the production and specific action of the works of a particular ethnocultural society. The psychology of tourism emphasizes above all the subject with its dreams, its reasons, its passions, its basic desires and its willingness to renew the experience or diversify its life. For the psychology of tourism, man is not only a consumer of travel. It is the traveller's imagination, modelled by these desires, which determines his vision of the world (urbanism and environments) and also his experience of travel (course or stay), his relationship between others and himself). The various researches (quoted in the bibliographical references of our article) have distinguished the different psychological polarities which are the origin of contemporary tourist practices, whether direct or indirect (during the business travel, family gatherings, cultural events or sports competitions) in short or distant circuits, travelling or residential, discovery or resort trips. I have synthesized and adapted the most well-known psychological polarities with the consideration of several criteria (sensitivity to people or landscapes, immersion in native life or the superficial relationships between visitor-hospitable, sensitivity or not to comfort, search for deep or distracting experiences, preferences for organized or improvised travel, etc.); precisely : 1) the call of the desert is this desire of the immense, silent, uninhabited spaces: (e.g. Sahara, Siberia, Iceland, Himalayas, Patagonia, etc.); hot or cold, the desert tends to become such a popular destination that it is the trading fund of travel agencies specializing in adventure and exploration; 2) the shared temptation -this desire corresponds to an urge of gregarity and effervescence, of human density and warmth and doves in festive events, major sporting and cultural appointments (such as the Olympic Games, the Championships World of football, Universal cultural exhibitions, etc.) ; 3) the attractiveness of prestigethis desire is turned to city-breaks, visits to major cities and capitals of the world's mighty countries through urban and cultural tourism (for example, visits to New York, Paris, London, Rome, Berlin, Moscow, Tokyo, Beijing, etc.); 4) the patriotic impulse-this desire is geared towards national cohesion and adherence to the traditional values of its people with displacement in symbolic and meaningful places of its country (for example, visits of churches and monasteries important, excursions in heritage spaces, great historical battles, national museums, very historical or typical towns or villages, etc.), 5) the sinobite inclination-this desire is the envy of the holidays, in a homogeneous group but often international to relax recreating in the seaside resorts and ski resorts; the emblematic places of this phenomenon are hotels, residences, cruises, holiday clubs, campsites or even the guesthouse; 6) the romantic dream-this desire is clearly linked to the dreams of the beauty of sublime landscapes and architectural, archaeological and geographical spaces celebrated (for example, travels to Venice, Florence, St. Petersburg; or escapades to-Phuket-Thailand, Luxor-Egypt, Jerusalem-Israel, Agra-India, Tahiti-Polynesia, etc.) ; 7) the altruistic tendency-this desire is entirely directed towards others, to the peoples and civilizations that appear radically different, the distant journeys in the lands of adventure and exoticism (in Africa, Mongolia, Peru, in Pacific Islands, etc.). This classification, admittedly incomplete and in the process of elaboration, but it already implies a definition of principal desire of the tourist, built according to the standards of the tourist guides, in its double psychoanalytic dimension: look and voice but to which unquestionably add nose, hearing, skin, mouth. According to [START_REF] Assoun | Leçons de psychanalyse[END_REF] "The psychoanalytic dimension is required to take into account the notion of a scoping prescription, which designates what is supposed to be seen. Besides its informative function, the tourist guide reveals a prescriptive function by drawing what, during the voyage, is worthy to be "seen", as they say. There is in this sense an authority of the g tourist guide " [START_REF] Assoun | Leçons de psychanalyse[END_REF]. In "Inhibition, Symptom and Anxiety" [START_REF] Freud | Inhibition, symptom and anxiety[END_REF], suggested that Weltanschauungen (conception of the Universe) should be left to philosophers: "Such activities may be left to philosophers, who avowedly find it impossible to make their journey through life without a Baedeker of the kind to give the information on every subject" [START_REF] Freud | Inhibition, symptom and anxiety[END_REF]. Baedeker was the famous German tourist guide of the time but the alleged contempt of the philosophers towards the psychoanalyst was Freud's projection. This tool of guidance for collective use comes to resonate with a phenomenology of space that implies an unconscious dimension. This allows to show the scope of a research on these documents, index of the relationship to space, especially in its urban dimension, distinctive of modernity. The culture is spatialized: first in the musicological and architectural space and then in the geographical area. The Guide became therefore a control of the space but also of the gaze, designating what to look. He relieves him of the trouble of seeing by organising a geographic, cartographic and textual landscape. Currently, in digital era make the tourist guide, it is explore texts, images and audio, practical information of a real, a knowledge and a discovery and it is even organize about a displacement to the space of the virtual journey in its contemporary condition. The tourist guide therefore presents itself as a kind of empirical a priori: it has as its function to make the tourist space clearer by placing the necessary scales. It should also be clarified that, according to the different viewpoints of psychologists, the tourist practice generates many advantages and disadvantages under these conditions. Thus, for some, tourism is a factor of rapprochement between peoples and terrestrial cultures, in particular through interactions and intercultural encounters that it induces. Under the conditions that these well-regulated and accommodated interactions, tourism can even contribute to the acceptance of global cultural diversity by leading to the recognition and respect of the socio-cultural particularities of each society or of each people. It is also considered a national, ethical, cultural and patriotic awakening factor as well as a real vehicle for progress, democracy and development. Likewise, tourism can contribute to the improvement of the living conditions of the society in which it develops in terms of new housing construction, water purification and channelling, renovation and modernization of infrastructure, etc. It also creates a number of jobs linked directly or indirectly to tourism and thereby contributes to economic growth in developed countries and the reduction of poverty in emerging countries. However, for other psychologists, tourism presents itself as a particularly deconstructing and denting activity for the host population. It is often accused of damaging and destroying the natural and cultural heritage, of abusing and exercising natural resources, of generating economic inflation, etc. The tourism and intercultural relations that derive from it, thus undoubtedly produce positive or negative impacts on the host communities. By modifying, sometimes sustainably, the socio-cultural realities of the countries that concentrate their activity mainly on the tourism industry, which impact the balance of ethnic identities (national and local). From this point of view, tourism undeniably destabilizes the fragile balances of host societies, often poorly prepared and not conditioned to cultural shock. And in this sense, tourism, a cultural shock-bearer, is likely to influence the cultural identity of the society where it develops. The clash of cultures (which has for other names the clash of civilizations), is the result of the evolution of the phenomenon of contact between the different peoples of the world, which has considerably spread to the whole planet. Remember, we talk about "cultural shock" to characterize the experience, usually painful and confrontational, that an individual challenged to manage social interactions while he is brutally immersed in an unknown cultural environment, without having the cultural codes necessary for its adaptation. Ethnocentrism is at the origin of social representations that have largely contributed to the creation of prejudices and stereotypes. The abandonment of ethnocentric positions, which is necessary for the recognition of others and the cultural diversity of the world, is undeniably through overcoming prejudices and stereotypes. "Prejudices" and "stereotypes" are two notions that stem from the human sciences, including psychology and sociology. They represent mental manifestations emanating from the collective consciousness and tend to generalization and socio-cultural schematization. Prejudices and stereotypes are revealed to other cultural groups, sometimes unconscious and often on trips or tourist trips. In the context of psychology, "prejudice" represents a negative attitude which refers classically to three components: 1) that of affects and evaluations to which they lead (contempt, rejection, denial, hatred, love, ambivalence); (2) that of the domain of cognitions and the modes of organization of the world they assume, based principally on stereotype and categorization; 3)the space of practices and acts (the cognitive level) that should be derived, directly or indirectly, from prejudice and which could possibly give it an inspiration and a form. As a general rule, prejudice is always based on a stereotype. The term "stereotype" is applied in 1922, in the humanities, by Lippmann. "The stereotype is defined as a set of beliefs resulting from images built cognitively, on the individual. It therefore appears evident that stereotypes (negative, positive or mixed) guide the perception of social categories and thus orient the cultural categorization" [START_REF] Lippmann | Public opinion[END_REF]. From the point of view of Radtchenko-Draillard (2014) "stereotypes are sensitive to the nature of social interactions to ensure the cohesion of which its members overwhelmingly adhere to dominant stereotypes in relation to its group or the endogroup (US) and to other groups or exogroup (THEM) and the results obtained allows us to consider that there are four assessed reports on the scale-good/positive or bad/negative: 1) the favouritism of the exogroup and the endogroup (principle: "they are good and we are good too "); 2) the disadvantage of the exogroup and the favouritism of the endogroup (principle: "they are bad but we are good"); 3) the favouritism of the exogroup and the disadvantage of the endogroup (principle: "they are good but we are bad"); 4) the disadvantage of the endogroup and the exogroup (principle: "we are bad and they are bad, too")" [START_REF] Radtchenko-Draillard | Le rôle des stéréotypes nationaux dans les interactions interpersonnelles et intergroupales// Cahiers de psychologie politique[END_REF]. Indeed, the acceptance or nonacceptance of the other in its diversity and its difference is far from being a spontaneous attitude; it is often the result of a difficult journey that goes through the realization of the intrinsic ethnocentrism of the gaze on oneself and on the other, as well as the adoption of a cultural relativism. Cultural relativism is therefore the thesis that cultures must be described in their cultural reality. In order to better understand the intercultural interaction Vinsonneau (2012) divides these studies into three groups: "1) those concerning the relationship between the psyche and culture in situations within a single culture (cultural situation homogeneous to understand individual or collective behaviours within the same community); 2) those relating to the processes of interaction of several cultures (heterogeneous cultural situation to understand individual or collective behaviours in a context of cultural heterogeneity); (3) those made from comparisons of different cultures " [START_REF] Vinsonneau | Mondialisation et identité culturelle[END_REF]. For Radtchenko-Draillard (2016): "It can be said that the cultural tradition must therefore retain the formal concepts of social and subjective worlds, but it must also accept differentiated requirements to the validity of the decision-truth normative correctness, subjective sincerity, joint goals and it must, above all, encourage the corresponding differentiation of the positions of each one " [START_REF] Radtchenko-Draillard | L'étude psychanalytique de la résolution des conflits dans les interactions internationales et la négociation[END_REF]. In summary, universal acceptance of cultural diversity allows the different peoples and cultures of the world to respect each Other, without rigid judgement on each Other and finally presents itself as the necessary condition the smooth running of intercultural exchanges and tourism at the international level.


Paulin Jacobé De Naurois
email: denaurois@lipn.univ-paris13.fr

Pointers in Recursion: Exploring the Tropics

Keywords: 2012 ACM Subject Classification Software and its engineering → Recursion, Theory of computation → Complexity theory and logic, Theory of computation → Complexity classes Keywords and phrases Implicit Complexity, Recursion Theory Digital Object Identifier 10.4230/LIPIcs.FSCD.2019.25

come

Introduction

Characterizing complexity classes without explicit reference to the computational model used for defining these classes, and without explicit bounds on the resources allowed for the calculus, has been a long term goal of several lines of research in computer science. One rather successful such line of research is recursion theory. The foundational work here is the result of Cobham [START_REF] Cobham | The intrinsic computational difficulty of functions[END_REF], who gave a characterization of polynomial time computable functions in terms of bounded recursion on notations -where, however, an explicit polynomial bound is used in the recursion scheme. Later on, Leivant [START_REF] Leivant | A foundational delineation of computational feasiblity[END_REF] refined this approach with the notion of tiered recursion: explicit bounds are no longer needed in his recursion schemes. Instead, function arguments are annotated with a static, numeric denotation, a tier, and a tiering discipline is imposed upon the recursion scheme to enforce a polynomial time computation bound. A third important step in this line of research is the work of Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF], whose safe recursion scheme uses only syntactical constraints akin to the use of only two tier values, to characterize, again, the class of polynomial time functions.

Cobham's approach has also later on been fruitfully extended to other, important complexity classes. Results relevant to our present work, using explicitly bounded recursion, are those of Lind [START_REF] Lind | Computing in logarithmic space[END_REF] for logarithmic space, and Allen [START_REF] Allen | Arithmetizing uniform NC[END_REF] and Clote [START_REF] Clote | Sequential, machine-independent characterizations of the parallel complexity classes ALOGTIME, AC k , NC k and NC[END_REF] for small parallel classes.

Later on, Bellantoni and Cook's purely syntactical approach proved also useful for characterizing other complexity classes. Leivant and Marion [START_REF] Leivant | Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space[END_REF][START_REF] Leivant | A characterization of alternating log time by ramified recurrence[END_REF] used a predicative version of the safe recursion scheme to characterize alternating complexity classes, while Bloch [START_REF] Bloch | Function-algebraic characterizations of log and polylog parallel time[END_REF], Bonfante et al [START_REF] Bonfante | Two function algebras defining functions in NC k boolean circuits[END_REF] and Kuroda [START_REF] Kuroda | Recursion schemata for slowly growing depth circuit classes[END_REF], gave characterizations of small, polylogtime, parallel complexity classes. An important feature of these results is that they use, either Subsequently, the use of different, classical recursion schemes over this new tropical tiering discipline yields characterizations of other, sub-polynomial complexity classes such as polylogtime, NC, and the full polynomial time class. Following the approach of Bellantoni and Cook, we furthermore embed the tiering discipline directly in the syntax, with only finitely many different tier values -four tier values in our case, instead of only two tier values for the safe recursive functions, and provide purely syntactical characterizations of these complexity classes in a unified, simple framework. Compared to previous works, our framework uses a unique, and rather minimal set of unit-cost basic functions, computing indeed basic tasks, and a unique and also simple data structure. While the syntax of our tropical composition and recursion schemes may appear overwhelming at first sight, it has the nice feature, shared with the safe recursion functions of [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF], of only adding a fine layer of syntactic sugar over the usual composition and primitive recursion schemes. Removing this sugar allows to retrieve the classical schemes. In that sense, we claim our approach to be simpler than the previous ones of [START_REF] Bloch | Function-algebraic characterizations of log and polylog parallel time[END_REF][START_REF] Bonfante | Two function algebras defining functions in NC k boolean circuits[END_REF][START_REF] Kuroda | Recursion schemata for slowly growing depth circuit classes[END_REF].

The paper is organized as follows. Section 1 introduces the notations, and the framework of pointer recursion. Section 2 applies this framework to primitive recursion. Pointer partial/primitive recursive functions are proven to coincide with their classical counterparts in Theorem 2. Section 3 applies this framework to safe recursion on notations. Pointer safe recursive functions are proven to coincide with polylogtime computable functions in Theorem 3. Tropical tiering is defined in Section 4. Proposition 4 establishes the tropical interpretation induced by tropical tiering. Tropical recursive functions are then introduced in Subsection 4.3. Section 5 gives a sub-algebra of the former, capturing logspace/polylogtime computable functions in Theorem 9. Finally, Section 6 explores tropical recursion with substitutions, and provides a characterization of P in Theorem 11 and of NC in Theorem 13.

Recursion

Notations, and Recursion on Notations

Data structures considered in our paper are finite words over a finite alphabet. For the sake of simplicity, we consider the finite, boolean alphabet {0, 1}. The set of finite words over {0, 1} is denoted as {0, 1} * . Finite words over {0, 1} are denoted with overlined variables names, as in x. Single values in {0, 1} are denoted as plain variables names, as in x. The empty word is denoted by ε, while the dot symbol "." denotes the concatenation of two words as in a.x, the finite word obtained by adding an a in front of the word x. Finally, finite arrays of boolean words are denoted with bold variable names, as in x = (x 1 , • • • , x n ). When defining schemes, we will often omit the length of the arrays at hand, when clear from context, and use bold variable names to simplify notations. Similarly, for mutual recursion schemes, finite arrays of mutually recursive functions are denoted by a single bold function name. In this case, the width of this function name is the size of the array of the mutually recursive functions.

Natural numbers are identified with finite words over {0, 1} via the usual binary encoding. Yet, in most of our function algebras, recursion is not performed on the numerical value of an integer, as in classical primitive recursion, but rather on its boolean encoding, that is, on the finite word over {0, 1} identified with it: this approach is denoted as recursion on notations.

Turing Machines with Random Access

When considering sub-polynomial complexity class, classical Turing Machines often fail to provide a suitable cost model. A crucial example is the class DLOGTIME: in logarithmic time, a classical Turing machine fails to read any further than the first k. log(n) input bits. In order to provide a suitable time complexity measure for sub-polynomial complexity classes, Chandra et al [START_REF] Ashok | [END_REF] introduced the Turing Machine with Random Access (RATM), whose definition follows.

Definition 1. RATM A Turing Machine with Random Access (RATM) is a

Turing machine with no input head, one (or several) working tapes and a special pointer tape, of logarithmic size, over a binary alphabet. The Machine has a special Read state such that, when the binary number on the pointer tape is k, the transition from the Read state consists in writing the k th input symbol on the (first) working tape.

Recursion on Pointers

In usual recursion theory, a function computes a value on its input, which is given explicitly as an argument. This, again, is the case in classical primitive recursion. While this is suitable F S C D 2 0 1 9

25:4

Pointers in Recursion: Exploring the Tropics for describing explicit computation on the input, as, for instance for single tape Turing Machines, this is not so for describing input-read-only computation models, as, for instance, RATMs. In order to propose a suitable recursion framework for input-read-only computation, we propose the following pointer recursion scheme, whose underlying idea is pretty similar to that of the RATM.

As above, recursion data is given by finite, binary words, and the usual recursion on notation techniques on these recursion data apply. The difference lies in the way the actual computation input is accessed: in our framework, we distinguish two notions, the computation input, and the function input: the former denotes the input of the RATM, while the latter denotes the input in the function algebra. For classical primitive recursive functions, the two coincide, up to the encoding of integer into binary strings. In our case, we assume an explicit encoding of the former into the latter, given by the two following constructs.

Let w = w 1 . • • • .w n ∈ {0, 1} * be a computation input. To w, we associate two constructs, the Offset: a finite word over {0, 1}, encoding in binary the length n of w, and the Read construct, a 1-ary function, such that, for any binary encoding i of an integer 0 < i ≤ n, Read(i) = w i , and, for any other value v, Read(v) = ε.

Then, for a given computation input w, we fix accordingly the semantics of the Read and Offset constructs as above, and a Pointer Recursive function over w is evaluated with sole input the Offset, accessing computation input bits via the Read construct. For instance, under these conventions, Read(hd(Offset)) outputs the first bit of the computational input w. In some sense, the two constructs depend on w, and can be understood as functions on w. However, in our approach, it is important to forbid w from appearing explicitly as a function argument in the syntax of the function algebras we will define, and from playing any role in the composition and recursion schemes. Since w plays no role at the syntactical level -its only role is at the semantical level-we chose to remove it completely from the syntactical definition of our functions algebras.

Pointers Primitive Recursion

Let us first detail our pointer recursive framework for the classical case of primitive recursion on notations.

Basic pointer functions.

Basic pointer functions are the following kind of functions:

1. Functions manipulating finite words over {0, 1}. For any a ∈ {0, 1}, x ∈ {0, 1} * ,

hd(a.x) = a tl(a.x) = x s 0 (x) = 0.x hd(ε) = ε tl(ε) = ε s 1 (x) = 1.x 2. Projections. For any n ∈ N, 1 ≤ i ≤ n,
Pr n i (x 1 , • • • , x n ) = x i
3. and, finally, the Offset and Read constructs, as defined above.

Composition.

Given functions g, and h 1 , • • • , h n , we define f by composition as

f (x) = g(h 1 (x), • • • , h n (x)).
Paulin Jacobé de Naurois

25:5

Primitive Recursion on Notations.

Let ⊥ denote non-terminating computation. Given functions h, g 0 and g 1 , we define f by primitive recursion on notations as

f (ε, y) = h(y) f (s a (x), y) = g a (x, f (x, y), y) if f (x, y) =⊥ ⊥ otherwise.

Minimization

For a function s, denote by s (n) its n th iterate. Then, given a function h, we define f by minimization on x as

µx(h(x, y)) = ⊥ if ∀t ∈ N, hd(h(s (t) 0 (ε), y)) = s 1 (ε) s (k) 0 (ε) where k = min{t : hd(h(s (t) 0 (ε), y)) = s 1 (ε)} otherwise.
In other words, a function f defined by minimization on h produces the shortest sequence of 0 symbols satisfying a simple condition on h , if it exists.

Let now P R point not be the closure of basic pointer functions under composition and primitive recursion on notations, and REC point not be the closure of basic pointer functions under composition, primitive recursion on notations, and minimization. Then, as expected, Proof. It is already well known that primitive recursive functions on notations are the classical primitive recursive functions, and recursive functions on notations are the classical recursive functions. Now, for one direction, it suffices to express the Read and Offset basic pointer functions as primitive recursive functions on the computation input. For the other direction, it suffices to reconstruct with pointer primitive recursion the computation input from the Read and Offset basic pointer functions.

A Simple Example

Let us define the following functions.

if ε (ε, y, z) = y if ε (s a (x), y, z) = z RmvLastBit(ε) = ε RmvLastBit(s a (x)) = if ε (x, ε, s a (RmvLastBit(x)))
Then, Read(RmvLastBit(Offset)) reads the middle bit of the computation input, in logarithmic time. This exemplifies the purpose of recursion on pointers: this simple task cannot be performed in less than linear time by the usual primitive recursion on notations, nor by the classical Turing machine. However, switching the model definition from Turing machines to RATMs, and from primitive recursion to pointer primitive recursion, allows to perform this simple task in logarithmic time, in a straightforward way.

Pointer Safe Recursion

We recall the tiering discipline of Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF]: function arguments are divided into two tiers, normal arguments and safe arguments. Notation-wise, both tiers are separated by a semicolon symbol in a block of arguments, the normal arguments being on the left, and the safe arguments on the right. We simply apply this tiering discipline to our pointer recursion framework.

Basic Pointer Safe Functions.

Basic pointer safe functions are the basic pointer functions of the previous section, all their arguments being considered safe.

Safe Composition.

Safe composition is somewhat similar to the previous composition scheme, with a tiering discipline, ensuring that safe arguments cannot be moved to a normal position in a function call. The reverse however is allowed.

f (x; y) = g(h 1 (x; ), • • • , h m (x; ); h m+1 (x; y), • • • , h m+n (x; y)).
Calls to functions h m+i , where safe arguments are used, are placed in safe position in the argument block of g. A special case of safe composition is f (x; y) = g(; x, y), where a normal argument x is used in safe position in a call. Hence, we liberally use normal arguments in safe position, when necessary.

Safe Recursion.

The recursion argument is normal. The recursive call is placed in safe position, a feature that prevents nesting recursive calls exponentially.

f (ε, y; z) = h(y; z) f (a.x, y; z) = g a (x, y; f (x, y; z), z).
Let now SR point not be the closure of the basic pointer safe functions under safe composition and safe recursion.

Theorem 3. SR point not is the class DT IM E(polylog) of functions computable in polylogarithmic time.

Proof. The proof is essentially the same as for the classical result by Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF]. Here however, it is crucial to use the RATM as computation model. Simulating a polylogtime RATM with safe recursion on pointers is very similar to simulating a polytime TM with safe recursion -instead of explicitly using the machine input as recursion data, we use the size of the input as recursion data, and access the input values via the Read construct, exactly as is done by the RATM model. The other direction is also similar: the tiering discipline of the safe recursion on pointers enforces a polylog bound on the size of the strings (since the initial recursion data -the Offset -has size logarithmic in the size n of the computation input), and thus a polylog bound on the computation time.

Tropical Tiering

We present here another, stricter tiering discipline, that we call tropical Tiering. The adjective "tropical" refers to the fact that this tiering induces a polynomial interpretation in the tropical ring of polynomials. This tiering discipline takes some inspiration from Hofmann's work on non-size increasing types [START_REF] Hofmann | Linear types and non-size-increasing polynomial time computation[END_REF], and pure pointer programs [START_REF] Hofmann | Pure pointer programs with iteration[END_REF]. The idea however is to use here different tools than Hofmann's to achieve a similar goal of bounding the size of the function outputs. We provide here a non-size increasing discipline via the use of tiering, and use it in the setting of pointer recursion to capture not only pure pointer programs (Hoffman's class), but rather pointer programs with pointer arithmetics, which is in essence the whole class Logspace.

Basic Pointer Functions.

We add the following numerical successor basic function. Denote by E : N → {0, 1} * the usual binary encoding of integers, and D : {0, 1} * → N the decoding of binary strings to integers. Then,

s(x) = E(D(x) + 1)
denotes the numerical successor on binary encodings, and, by convention, ε is the binary encoding of the integer 0.

Primitive Recursion on Values.

Primitive recursion on values is the usual primitive recursion, encoded into binary strings:

f (ε, y) = h(y) f (s(x), y) = g(x, f (x, y), y).

Tropical Tier

As usual, tiering consists in assigning function variables to different classes, called tiers. In our setting, these tiers are identified by a numerical value, called tropical tier, or, shortly, tropic. The purpose of our tropical tiers is to enforce a strict control on the increase of the size of the binary strings during computation. Tropics take values in Z ∪ {-∞}. The tropic of the i th variable of a function f is denoted T i (f ). The intended meaning of the tropics is to provide an upper bound on the linear growth of the function output size with respect to the corresponding input size, as per Proposition 4. Tropics are inductively defined as follows.

1. Basic pointer functions:

T j =i (Pr n i ) = -∞ T 1 (hd) = -∞ T 1 (Read) = -∞ T 1 (tl) = -1 T i (Pr n i ) = 0 T 1 (s 0 ) = 1 T 1 (s 1 ) = 1 T 1 (s) = 1 2. Composition: T t (f ) = max i {T i (g) + T t (h i )}.

Primitive recursion on notations. Two cases arise:

T 2 (g 0 ) ≤ 0 and T 2 (g 1 ) ≤ 0. In that case, we set F S C D 2 0 1 9

25:8

Pointers in Recursion: Exploring the Tropics a. T 1 (f ) = max {T 1 (g 0 ), T 1 (g 1 ), T 2 (g 0 ), T 2 (g 1 )}, and, b. for all t > 1, T t (f ) = max{T t+1 (g 0 ), T t+1 (g 1 ), T t-1 (h), T 2 (g 0 ), T 2 (g 1 )}. the previous case above does not hold, T 2 (g 0 ) ≤ 1, and T 2 (g 1 ) ≤ 1. In that case, we also require that T 1 (g 0 ) ≤ 0, T 1 (g 1 ) ≤ 0, and, for all t ≥ 2,

T t (g 0 ) = T t (g 1 ) = T t-2 (h) = -∞. Then, we set T 1 (f ) = max{T 1 (g 0 ), T 1 (g 1 ), T 2 (g 0 ) -1, T 2 (g 1 ) -1, c h },
where c h is a constant for h given in Proposition 4 below, and, for t > 1, T t (f ) = -∞. Other cases than the two above do not enjoy tropical tiering.

Primitive recursion on values. Only one case arises:

T 2 (g) ≤ 0 . In that case, we set a. and, b.

T 1 (f ) = max {T 1 (g), T 2 (g)},
for all t > 1, T t (f ) = max{T t+1 (g), T t-1 (h), T 2 (g)}.
Again, other cases than the one above do not enjoy tropical tiering. Furthermore, when using tropical tiering, we use mutual recursion schemes.

For f = (f 1 , • • • , f n ), mutual primitive recursion (on values) is classically defined as follows, f (ε, y) = h(y) f (s(x), y) = g(x, f (x, y), y) if ∀i (f i (x, y) =⊥) ⊥ otherwise.
and similarly for mutual primitive recursion on notations. Tropical tiering is then extended to mutual primitive recursion in a straightforward manner. We define the set of L-primitive pointer recursive functions as the closure of the basic pointer functions of Sections 2 and 4 under composition, (mutual) primitive recursion on notations and (mutual) primitive recursion on values, with tropical tiering.

Tropical Interpretation

Tropical tiering induces a non-size increasing discipline. More formally,

Proposition 4. The tropical tiering of a L-primitive recursive function f induces a polynomial interpretation of f on the tropical ring of polynomials, as follows.

For any L-primitive recursive function f with n arguments, there exists a computable constant c f ≥ 0 such that

|f (x 1 , • • • , x n )| ≤ max t {T t (f ) + |x t |, c f }.
Proof. The proof is given for non-mutual recursion schemes, by induction on the definition tree. Mutual recursion schemes follow the same pattern. 1. For basic pointer functions, the result holds immediately.

2.

Let f be defined by composition, and assume that the result holds for the functions g,

h 1 , • • • , h n . Then, for any i = 1, • • • , n, |h i (x)| ≤ max t {T t (h i )+|x t |, c hi }. Moreover, there exists by induction c g such that |g(h 1 (x), • • • , h n (x))| ≤ max i {T i (g) + |h i (x)|, c g }. Com- posing the inequalities above yields |g(h 1 (x), • • • , h n (x))| ≤ max i {T i (g) + max t {T t (h i ) + |x i |, c hi }, c g } = max t {T t (f ) + |x t |, max i {c fi , c g }}. 3.
Let f be defined by primitive recursion on notations, and assume that the first case holds.

Let f (a.x, y) = g a (x, f (x, y), y), for a ∈ {0, 1}, and assume T 2 (g 0 ) ≤ 0 and T 2 (g 1 ) ≤ 0.

We apply the tropical interpretation on g, and we show by induction the result for f on the length of a.x. Since the first case does not hold, T 2 (g 0 ) = 1 or T 2 (g 1 ) = 1: assume that T 2 (g 0 ) = 1 (the other case being symmetric). Assume also that, T 1 (g 0 ) ≤ 0 and T 1 (g 1 ) ≤ 0, and

for all t ≥ 2, T t (g 0 ) = T t (g 1 ) = T t-2 (h) = -∞. Then, we set T 1 (f ) = max{0, c h }.
We apply the tropical interpretation on g, and prove by induction on the length of a.x that |f (a.x,

y)| ≤ |a.x| + max{c g1 , c g2 , c h }. a. If max t≥2 {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t (g a ), c ga } = |x| + T 1 (g a ). Since T 1 (g a ) ≤ 0 and T 1 (f ) ≥ 0, |f (a.x, y)| ≤ |x| ≤ T 1 (f ) + |x|, and the result holds. b. If max t≥2 {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t (g a ), c ga } = |f (x)| + T 2 (g a ). Since T 2 (g a ) ≤ 1, |f (a.x)| ≤ 1 + |f (x)|
, and the induction hypothesis allows to conclude. c.

If max t≥2 {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t (g a ), c ga } = c ga , the result holds immediately. d. The case max t≥2 {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t (g a ), c ga } = |y t | + T t (g a ) is impossible since T t (g a ) = -∞ for t ≥ 2. e.
The base case f ( , y) is immediate. 5. Let now assume f is define by primitive recursion on values. Then, the only possible case is similar to the first case of primitive recursion on notation.

The proof by induction above emphasizes the critical difference between recursion on notation and recursion on values: the second case of the safe recursion on notations correspond to the linear, non-size increasing scanning of the input, as in, for instance,

f (a.x) = s a (f (x)).
This, of course, is only possible in recursion on notation, where the height of the recursive calls stack is precisely the length of the scanned input. Recursion on values fails to perform this linear scanning, since, for a given recursive argument x, the number of recursive calls is then exponential in |x|.

Proposition 4 proves that the tropical tiering of a function yields actually a tropical polynomial interpretation for the function symbols: The right hand side of the Lemma inequality is indeed a tropical interpretation. Moreover, this interpretation is directly given by the syntax.

Furthermore, the proof also highlights why we use mutual recursion schemes instead of more simple, non-mutual ones: non-size increasing discipline forbids the use of multiplicative constants in the size of the strings. So, in order to capture a computational space of size k. log(n), we need to use k binary strings of length log(n), defined by mutual recursion. A structural induction on the definition of f yields the result. The only critical case is that of a recursive construct. When evaluating a recursive construct, one needs simply to store all non-recursive arguments (the y i 's) in a shared memory, keep a shared counter for keeping track of the recursive argument x, and use a simple while loop to compute successively all intermediate recursive calls leading to f (x, y). All these shared values have logarithmic size. The induction hypothesis ensures then that, at each step in the while loop, all computations take logarithmic space. The two other cases, composition and basic functions, are straightforward.

Corollary 5. L-primitive pointer recursive functions are computable in logarithmic space.

In the following section, we prove the converse: logarithmic space functions can be computed by a sub-algebra of the L-primitive pointer recursive functions.

Tropical Recursion

In this section we restrict our tropical tiering approach to only four possible tier values: 1, 0, -1 and -∞. While doing so, we still retain the same expressiveness. The rules for tiering are adapted accordingly. More importantly, the use of only four tier values allows us to denote these tropics directly in the syntax, in an approach similar to that of Bellantoni and Cook, by adding purely syntactical features to the composition and primitive recursion schemes. Let us take as separator symbol the following symbol, with leftmost variables having the highest tier. As with safe recursive functions, we allow the use of a high tier variable in a low tier position, as in, for instance, f (x y z t) = g( y x, z t).

Our tropical recursive functions are then as follows.

Basic tropical pointer functions.

Basic tropical pointer functions are the following.

hd( a.x) = a tl( a.x ) = x hd( ε) = ε tl( ε ) = ε s 0 (x ) = 0.x s 1 (x ) = 1.x s(x ) = E(D(x) + 1) Read( x) = a ∈ {0, 1} Pr n i ( x i x 1 , • • • , x i-1 , x i+1 , • • • , x n ) = x i

Tropical composition.

Define t = t 1 , t 2 , t 3 , t 4 . The tropical composition scheme is then

f (x y z t) = g(h 1 ( x y t), • • • , h a ( x y t) h a+1 (x y z t), • • • , h b (x y z t) h b+1 (y z t), • • • , h c (y z t) h c+1 (t 1 t 2 t 3 t 4 ), • • • , h d (t 1 t 2 t 3 t 4 ))
Paulin Jacobé de Naurois

25:11

Tropical Recursion on Notations -case 1.

f (x ε, y z t) = h(x y z t) f (x s a (r ), y z t) = g a (x r, f (x r, y z t), y z t)

Tropical Recursion on Notations -case 2. (Linear scanning)

f ( ε t) = ε f ( s a (r ) t) = g a (f ( r t) r t)
Tropical Recursion on Values.

f (x ε, y z t) = h(x y z t) f (x s(r ), y z t) = g(x r, f (x r, y z t), y z t)
As above, we use the mutual version of these recursion schemes, with the same tiering discipline. Note that, unlike previous characterizations of sub-polynomial complexity classes [START_REF] Bloch | Function-algebraic characterizations of log and polylog parallel time[END_REF][START_REF] Bonfante | Two function algebras defining functions in NC k boolean circuits[END_REF][START_REF] Kuroda | Recursion schemata for slowly growing depth circuit classes[END_REF], our tropical composition and recursion schemes are only syntactical refinements of the usual composition and primitive recursion schemes -removing the syntactical sugar yields indeed the classical schemes.

Definition 6. L-tropical functions The class of L-tropical functions is the closure of our basic tropical pointer functions, under tropical composition, tropical mutual recursion on notations, and tropical mutual recursion on values.

The restriction of only four tier values suffices to capture the computational power of RATMs. More precisely,

Theorem 7. The class of L-tropical functions is the class of functions computable in logarithmic space, with logarithmic size output.

Proof. L-tropical functions are L-primitive pointer recursive functions with tropics 1, 0, -1 and -∞. Following Corollary 5, they are computable in logspace. The converse follows from the simulation of a logarithmic space RATM, as follows.

Some Assumptions on the RATM being simulated

Let f be a function computable in deterministic space k log(n), with output of size k log(n), computed by a RATM M . We assume the following.

The machine M uses one pointer tape, of size log(n + 1) , and exactly one computation tape. For every input x of length n, the machine uses exactly k. log(n + 1) cells on the computation tape. At the start of the computation, the computation tape is as follows. The computation tape is on a cell containing the 0 symbol, followed by k. log(n+1) -1 0 cells on the right. 2. The cells on the left of the computation head, and the cells on the right of the k. log(n + 1) 0 symbols, contain only blank symbols. Moreover, during the computation, the following holds. 1. The computation head never goes on any cell on the left of its initial position. 2. The machine never writes a blank symbol. The same assumptions are made for the pointer tape.

It is easy to check that these assumptions are benign. They enable us to ignore the blank symbol in the simulation, and have a strict correspondence between the binary symbols of the RATM and those of the L-tropical algebra.

Encoding the machine configurations.

Assume the machine M works in space k log(n + 1) . A configuration of M is then encoded by 2k + 3 binary strings of length less than log(n + 1) : 1. one string, of constant length, encodes the machine state, 2. one string, of length log(n + 1) , encodes the pointer tape, 3. one string, of length log(n + 1) , encodes the head of the pointer tape. It contains 0 symbols everywhere, but on the position of the head (where it contains a 1). 4. k strings, of length log(n + 1) , encode the content of the work tape, and 5. k strings, of length log(n + 1) , encode the position of the work tape head, with (as for the pointer tape) 0 everywhere but on the position of the head.

Reading and Updating a configuration.

Linear scanning of the recursive argument in tropical recursion, corresponding to case 2 of the definition of tropical recursion on notations, is used to read and to update the encoding of the configuration. In order to do so, 1. we encode booleans false and true with s 0 (ε ) and s 1 (ε ) respectively. We define the following match construct match x with

| s 0 (r ) → A | s 1 (r ) → B | ε → C
as the following degenerate tropical recursion on notations.

match( s 0 (r ), a, b, c ) = a match( s 1 (r ), a, b, c ) = b match( ε, a, b, c ) = c
Then, if then esle, and AND and OR boolean functions are obtained by trivial applications of the match construct above. We also use a function isempty, for testing if a string equals ε.

2.

we define the following function, which adds one-bit in first position.

1BC(y x ) = match x with | s 0 (t ) → s 0 (y ) | s 1 (t ) → s 1 (y ) | ε → y
For notational purposes we sometimes use hd( x).y instead. 3. we define the following tail extraction, extracting the tail of a string, for a given prefix length.

Te( s a (x ) e ) = tl( Te( x e ) ) Te( ε e ) = e 4. we define the following bit extraction, extracting one bit of a string, for a given prefix length.

Be(

x, e) = hd( Te( x e ))

5. we define the following head extraction, extracting the head of a string, for a given prefix length.

He( s a ( x) e) = Be( s a ( x), e).He( x e)

He( ε e) = ε 6. we define the prefix length computation, which extracts the initial subsequence of 0 only symbols, followed by the first 1. This function is used for computing the prefix length corresponding to the position of the head in our encoding of the tapes of the RATM.

Prefix( ε ) = ε Prefix( s 0 ( x) ) = s 0 (Prefix( x ) ) Prefix( s 1 ( x) ) = s 1 (ε )
7. we define a predicate for comparing string lengths SameLength( x, y ) =

AND( isempty( Te( x y)

), isempty( Te( y x) ) ).

8. we define the one bit replacement function: Replacing exactly one bit in a string e by the first bit of b, for a given prefix length x. for any s with |s| = |e|. With all these simple bricks, and especially with the in-place one-bit replacement, one is then able to read a configuration, and to update it, with L-tropical functions. None of these L-tropical functions uses recursion on values. Given the functions above, the transition map Next of the machine is then computed by a simple L-tropical function of width (2k + 3): For a recursive argument s of size log(n + 1) , Next( s,c ) computes the configuration reached from c in one transition step. The Prefix function above computes the prefix corresponding the position of the head of the pointer and of the computation tapes in our encoding. Used in conjunction with the boolean constructs on the k strings encoding the computation tape, and in conjunction with the bit extraction function Be above, it allows to read the current symbol on the computation tape, and on the pointer tape, of the encoding of the RATM. Updating these two symbols is performed with the ChBit in-place one-bit replacement function.

Cb( s a (x ) y, e, b) = if SameLength( s a (x ), y ) then hd( b).Cb( x y,
Similarly, moving the heads of these two tapes can easily be performed with this ChBit, in conjunction with the tl and s 1 basic tropical functions.

Let us now describe how we can read and update the machine state: This machine state is encoded in binary by a string of length log(S + 1) , where S is the number of the states of M . The length of this string is fixed, and does not depend on the input. Therefore, we can safely assume that we have a fixed decision tree of depth log(S + 1) , for reading each bit of this string. The leaves of this decision tree are in one-to-one correspondence with the states of M . This decision tree can moreover be encoded with basic tropical functions and tropical composition only. Similarly, overwriting the machine state can be done with basic tropical functions and tropical composition only.

Finally, when in an input reading state, the input tape symbol is obtained simply by using the basic tropical function Read, with the pointer tape as argument.

The transition map Next of the RATM is then obtained by a boolean composition of the above functions. Similarly, computing an encoding of the initial configuration, and reading a final configuration, is simple.

Simulating the RATM.

The simulation of the RATM is then obtained by iterating its transition map Next a suitable number of times. The time upper bound is here obtained by nesting k tropical recursive functions on values: on an input of size log(n + 1) , the unfolding of these recursive calls takes time n k . At each recursive step, this function needs to apply the transition map. The transition map having width (2k + 3), we use here a mutual recursion scheme, of width (2k + 3). Again, for a recursive argument s of size log(n + 1) , we define

Step 1 ( ε, s, c ) = c Step 1 ( s(t ), s, c ) = Next( s, Step 1 ( t, n, c ) )
Step

2 ( ε, s, c ) = c Step 2 ( s(t ), s, c ) = Step 1 ( s, s, Step 2 ( t, s, c ) ) . . . Step k ( ε, s, c ) = c Step k ( s(t ), s, c ) = Step k-1 ( s, s, Step k ( t, s, c ) ).
Replacing s by the Offset in the above gives the correct bounds. Finally, one simply needs to use simple L-tropical functions for computing the initial configuration, and reading the final configuration. Logarithmic Space, Polylogarithmic Time

The polynomial time bound in Theorem 7 relies on the use of tropical recursion on values, for clocking the simulation of the RATM. Restricting the algebra to tropical recursion on notations only yields a straightforward time bound restriction, as follows.

Definition 8. LP-tropical functions

The class of LP-tropical functions is the closure of our basic tropical pointer functions, under tropical composition and tropical mutual recursion on notations. Theorem 9. The class of LP-tropical functions is the class of functions computable in logarithmic space, polylogarithmic time, with logarithmic size output.

Proof. Mutual recursion on notations, with recursive arguments of logarithmic size, are computable in polylogarithmic time, following similar arguments as in the proof of Theorem 7. The follows from the simulation in the proof of Theorem 7 above, where mutual recursion on values for the functions Step i is replaced by mutual recursion on notations.

Alternation

In this section we extend the approach of Leivant and Marion [START_REF] Leivant | Ramified recurrence and computational complexity ii: Substitution and poly-space[END_REF] to our setting. Let us define a similar tropical recursion on notations with substitutions. Note that the tropical tiering discipline prevents using substitutions in case 2 of the tropical recursion on notations. Substitutions are therefore only defined for case 1 of this recursion scheme, and only in non-size increasing position.

Tropical Recursion with substitutions on Notations.

Given functions h, g 0 , g 1 , k 1 and k 2 , f (x ε, u, y z t) = h(x u, y z t) f (x s a (r ), u, y z t) = g a (x r, f (x r, k 1 ( u ), y z t), f (x r, k 2 ( u ), y z t), u, y z t) .

Tropical Recursion with substitutions on Values.

Given functions h, g, k 1 and k 2 ,

f (x ε, u, y z t) = h(x u, y z t) f (x s(r ), u, y z t) = g(x r, f (x r, k 1 ( u ), y z t), f (x r, k 2 ( u
), y z t), u, y z t) .

Again, as above, we assume these recursion schemes to be mutual. Tropical Recursion with substitutions allows two recursive calls, where one parameter (u) is modified by the so-called substitution function k 1 or k 2 . This allows to denote branching, or parallel computations, where a given configuration being accepting or rejecting depends on two distinct transition steps. This is precisely the definition of an alternating Turing machine, whose relation with parallel computation is well documented [START_REF] Ashok | [END_REF][START_REF] Walter | On uniform circuit complexity[END_REF]. Proof. The result follows from Alogspace = P [START_REF] Ashok | [END_REF], and Theorem 7. Substitutions in the tropical recursion scheme on notations amounts to alternation. Restriction to decision classes instead of function classes comes from the use of alternating Turing machines, which compute only decision problems.

Definition 10. P-tropical functions The class of P-tropical functions is the closure of our basic tropical pointer functions, under tropical composition, tropical recursion on notations and on values, and tropical recursion with substitutions on notations and on values.

Let us first see how to simulate a logspace alternating machine with P-tropical functions. Recall the notations and functions of the proof of Theorem 7. Since we now need to simulate a non-deterministic, alternating machine, we assume without loss of generality that we now have two kinds of machine states: non-deterministic universal non-deterministic existential and that non-deterministic transitions have at most two branches. Therefore, we also assume that we have one predicate that determines the kind of a state in a configuration c: IsUniversal( s,c ). This predicate is assumed to output false or true. We also assume that we have two transition maps, Next 0 ( s, c

), and Next 1 ( s, c ), for computing both branches of non-deterministic transitions. For deterministic transitions, we assume both branches are the same. Finally, we also assume we have a predicate isPositive( s, c

), which returns true if the configuration c is final and accepting, and false otherwise.

We define now, with substitutions, the following:

Accept( ε, s, c ) = isPositive( s, c ) Accept( s(t), s, c )) = match IsUniversal( s, c ) with |true → AND ( Accept( t, Next 0 ( s, c ), c ), Accept( t, Next 1 ( s, c )) ) |false → OR ( Accept( t, Next 0 ( s, c
)), c ), Accept( t, Next 1 ( s,c ))

) .

Then, for t and s large enough, and an initial configuration c, Accept( t, s, c ) outputs the result of the computation of the machine. Finally, nesting up to k layers of such recursion on values schemes allows, as in the proof of Theorem 7, to simulate a polynomial computation time.

The other direction is pretty straightforward: For any instance of a recursion scheme with substitutions, for any given values r, u, x, y and z, each bit of g(x r, f (x r, k 1 ( u ), y z t), f (x r, k 2 ( u ), y z t), u, y z t) is a boolean function of the bits of f (x r, k 1 ( u ), y z t) and f (x r, k 2 ( u ), y z t). Hence, it can be computed by an alternating procedure. The space bound follows from the bound on the size of the strings, provided by the tiering discipline.

Recall now that the time bound in Theorem 9 follows from 7 by removing recursion on values from the algebra. The same applies here, as follows.

Definition 12. NC-tropical functions

The class of NC-tropical functions is the closure of our basic pointer tropical functions, under tropical composition, tropical recursion on notations and tropical recursion with substitutions on notations.

Theorem 13. The class of NC-tropical functions with binary output is NC.

Paulin Jacobé de Naurois 25:17

Proof. The result follows from A(logspace, polylogtime) = N C [START_REF] Walter | On uniform circuit complexity[END_REF], and Theorem 7. Substitutions in the tropical recursion scheme on notations amounts to alternation. The proof is similar to that of Theorem 11, where additionally,

The time bound on the computation of the machine needs only to be polylogarithmic, instead of polynomial. As in Theorem 9, tropical recursion on notations suffices to obtain this bound, and tropical recursion on values is no longer needed. For the other direction, any bit of g a (x r, f (x r, k 1 ( u ), y z t), f (x r, k 2 ( u ), y z t), u, y z t) is again a boolean function of the bits of f (x r, k 1 ( u ), y z t) and f (x r, k 2 ( u ), y z t). Here, this boolean function can be computed by a boolean circuit of polylogarithmic depth, hence, by an alternating procedure in polylogarihtmic time. The arguments behind this remark are the same as the ones in the proof of A(logspace, polylogtime) = N C.

Concluding Remarks

Theorems 7, 9, 11, and 13 rely on mutual recursive schemes. As stated above, we use these mutual schemes to express a space computation of size k log(n) for any constant k, with binary strings of length at most log(n) + c. If we were to use only non-mutual recursion schemes, we would need to have longer binary strings. This can be achieved by taking as input to our functions, not simply the Offset, but some larger string # k (Offset), where # k is a function that appends k copies of its argument.

It also remains to be checked wether one can refine Theorem 13 to provide characterizations of the classes NC i as in [START_REF] Leivant | A characterization of alternating log time by ramified recurrence[END_REF]. A first step in this direction is to define a recursion rank, accounting for the nesting of recursion schemes: then, check wether NC-tropical functions of rank i are computable in NC i . Conversely, check also whether the simulation of Theorem 7 induces a fixed overhead, and wether NC i can be encoded by NC-tropical functions of rank i + c for some constant c small enough.

Finally, note that we characterize logarithmic space functions with logarithmically long output (Theorem 9), and NC functions with one-bit output (Theorem 13). As usual, polynomially long outputs for these classes can be retrieved via a pointer access: it suffices to parameterize these functions with an additional, logarithmically long input, denoting the output bit one wants to compute. In order to retrieve functions with polynomially long output, this approach could also be added to the syntax, with a Write construct similar to our Read construct, for writing the output.

Theorem 2 .

 2 Modulo the binary encoding of natural integers, P R point not is the classical class of primitive recursive functions, and REC point not is the classical class of recursive functions.

F

a. 4 .

 4 If max x,f (x,y),t {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ),|y t | + T t+2 (g a ), c ga } = |x| + T 1 (g a ): |f (a.x, y)| ≤ |x| + T 1 (g a ) ≤ |x| + T 1 (f ), and the result holds. b. If max x,f (x,y),t {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t+2 (g a ), c ga } = |f (x, y)| + T 2 (g a ):Since T 2 (g a ) ≤ 0, |f (a.x, y)| ≤ |f (x, y)|, and the induction hypothesis applies.c. If max x,f (x,y),t {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t+2 (g a ), c ga } = |y t | + T t+2 (g a )for some t: the result applies immediately by structural induction on g a . d. If max x,f (x,y),t {|x| + T 1 (g a ), |f (x, y)| + T 2 (g a ), |y t | + T t+2 (g a ), c ga } = c ga , the result holds immediately. e. The base case f ( , y) is immediate. Let f be defined by primitive recursion on notations, and assume now that the second of the two corresponding cases holds. Let f (a.x, y) = g a (x, f (x, y), y), for a ∈ {0, 1}.

F S C D 2 0 1 9 25: 10

 910 Pointers in Recursion: Exploring the TropicsProof. Proposition 4 ensures that the size of all binary strings is logarithmically bounded.

F

  e, b) else Be( Te( s a (x ) e ), e).Cb( x y, e, b) Cb( ε y, e, b) = ε and ChBit( s x, e, b) = Cb( s Te( x e), e, b)

F S C D 2 0 1 9 25: 14

 914 Pointers in Recursion: Exploring the Tropics Computing the Transition map of the Machine.

F 11 .

 11 The class of P-tropical functions with binary output is the class P.

Funding Paulin Jacobé de Naurois: Work partially supported by ANR project ELICA -ANR-14-CE25-0005 Acknowledgements I am grateful to the anonymous referees for their insightful and useful feedback