Isabelle Dangeard
email: isabelle.dangeard@univ-brest.fr2022@june.

The Fulfilling Intensity of Nature-Based Activities -Construction of a Model based on a Hybrid Lifestyle

Keywords: Nature-based, Activity, Intensity, Diversity, Needs, Time use

This paper relates the emergence of a concept of the intensity of human activities as a way to explain the interest of nature-based activities. This concept emerged through attempts to solve a paradox I faced after my lifestyle evolved over a few decades, from a modern lifestyle made up of work and leisure, to a hybrid one including a significant proportion of direct living from nature: although I felt my life had improved, the comments I faced indicated it was considered non-rational. Attempts to solve this paradox resulted in a grounded model highlighting the reasons why I felt the change was, on the contrary, totally rational. The core of the explanation relies on a concept of the intensity of human activities, defined as the diversity of needs satisfaction resulting from their time use. Nature-based activities are usually intense activities, as they satisfy multiple needs, such as nature needs, physical activity, and free creativity. Some of these needs were previously satisfied by specific activities, usually performed successively, and mediated by work. This was time-consuming and addressed few needs simultaneously. On the contrary, the intensity of a hybrid nature-based lifestyle was more fulfilling and time-efficient.

The first part is a narrative of the evolution of my lifestyle and highlights the event which triggered the change and the following evolutions. I conclude this part with the paradox I faced and solve it in the second part with a model of needs satisfaction based on time use and the ensuing concept of intensity of human activities.

Part 1. Lifestyle change: the paradox A few decades ago, I lived a classical modern lifestyle. I was working as a teacher and researcher in management sciences and enjoyed my job. Extra hours led me to work more than full time, but I liked the associated challenges and social interactions. My job did not require any physical effort, so I used to play tennis to make up for this, although the time I spent with my children meant I did this much less than earlier in my life. As playing tennis was often an indoor activity and in any case, like my job, took place in artificial settings, I also felt the need for a more natural environment. Therefore, I spent time hiking, and sometimes beach fishing or blackberry picking. However, these walks and sports did not involve creativity, and my job only required a little. So, I still felt the need to make my own mark on something. The activity that offered me this chance was basketry, an activity I had learned as a teenager and had occasionally practiced since then using store-bought materials. When my family settled in a remote area, blackberry picking could be done on our land, sports gave way to maintenance of the outdoors and production of firewood, fueling relaxing evenings around the fireplace.

During one discussion with friends around the wood-burning stove, we agreed on the interest of an autonomous heating system in case of power cuts. However, you still need matches or a lighter to start the fire, unless you are able to do this using more primitive techniques. I had to confess that all my attempts at this had failed, even after I had read a book dedicated to making fire like our ancestors and carefully watched the video that came with the book. Then my English friend told me she knew where I could learn how to make fire by friction on a "bushcraft" course. I asked her to explain this word, which has no French translation, and noted down the name of the course organizer. As the course was in the UK, I looked for a similar one in France, but without success. Thus, I registered for one of the next sessions of the one-week course in the UK. I arrived there at the end of April, with all the equipment needed for this week in the woods. The very first evening, I realized that I had misunderstood one point: I thought the evening meals would be taken indoors, while it was an entirely outdoor week. If I had understood this point, I would probably not have registered for such a course. I started thinking "What am I doing here? How long will I be able to cope with such an environment?" Indeed, the weather was cold, with frost in the morning showing there had been negative temperatures during the night. However, as the days went by, I learned a great deal, even though I failed to light a fire by friction. On the drive back home, I stopped in the city where I was to take the ferryboat to cross the channel back to France. Here there was a fair, with many merry-go-rounds and other amusements, loud music, smells of candy and sun cream, and people dressed in the latest fashions, with make-up and sunburns. Still wearing my comfortable outdoor clothes, I once more found myself thinking "What am I doing here?" After one week in the woods, the outdoors had become a familiar life environment, and all these man-made artifacts seemed strange to me.

Once back home, I started using my new skills. At first, I practiced making fire by friction with materials I had picked up on my way back. Finally, I succeeded. Then I started to regularly carve, forage, and weave strings and I made a shelter where I could sleep. For all these activities, I used the bushcraft knife I had brought back, and sometimes a small folding saw. What I had also brought back from the course were thoughts about the art of bushcraft, which is how to live outdoors with a minimal kit, typically only a knife: the versatile bushcraft knife.

Over the following years, my activities evolved. These changes fall into three dimensions.

Firstly, my panel of activities expanded. I pushed my bushcraft skills further with new carving and weaving projects. When I realized that the mud that I was walking on everyday was clay, I learned pottery techniques from a ceramic artist who gave courses and accepted to help me make useful pots rather than the artistic pieces he favored. Then I learned wool spinning on courses provided by an association, and rapidly became able to transform fleece into products such as hats or cushions, with a self-made drop spindle. I then explored the art of soap making, which is just basic chemistry. Finally, I started to combine these techniques to produce goods with which I replaced store-bought ones. As for my everyday life, I was now spending more time outdoors doing activities like cooking, having a shower, or sleeping.

Secondly, the destination of my productions evolved. From outdoor products, to be used when living in nature, I started making home products, still processing in the outdoors materials I picked in my natural environment. For example, a broom, which is clearly something you don't need when you live in nature. All my personal ornaments (necklaces, bracelets, and earrings) gave way to self-made and nature-sourced ones, and some pieces of furniture met the same fate. I thought of this evolution as a bushcraft lifestyle: still living most of the time indoors, but among many productions sourced from the surrounding nature, and therefore spending a lot of time in nature.

Thirdly, my evolution as regards the technical dimension was twofold: very often I used other hand tools than my bushcraft knife, such as pruning shears, hand saws with large blades, a few containers and sieves, which made the processes easier. But sometimes I didn't use any industrial artifact, for example making pots, cordages, or a sun hat in a primitive way. And I realized it gave a specific value to the products made this way, maximizing the connection with the environment, as no unknown processes were obscuring the results.

At this point I faced external perspectives on a lifestyle I called hybrid: for I still worked in a built environment, although only part time by this point; and I still had a car, a phone and an Internet connection, and my life relied on many industrial products sourced from global distribution systems; but part of my needs were directly satisfied from my natural environment through basic techniques and simple tools. I had opened a guest room, offering my guests a discovery of the techniques I had recently mastered, and teaching them some basic skills whenever they wanted. During these interactions, I got an outsider's perspective that I hadn't requested, as some of these visitors asked if what I was doing was a passion. The answer I gave, saying that this was a lifestyle, rather than an after-work hobby, was probably not totally convincing as I was surprised by these comments. If passion is to be opposed to reason, for me it was clearly a rational choice, which made me spend less time working to spend money to satisfy my needs, and more time directly satisfying my needs from my close natural environment. But the most crude questioning came from one of my nephews, who one day asked: "Why do you bother making a broom? With the money you gain from work, you could buy many brooms from the time you spend making one!". For a teacher in management sciences, this was a major objection about labor productivity and time-efficiency. With all these comments, I had discovered that for other people, it seemed I was acting out of passion, or in an antieconomic manner, and overall, in a non-rational way. On the contrary, I felt my choices were totally rational. This was a paradox I had to explain.

Part 2. Solving the paradox with a concept of intensity of human activities

Human decisions involve both an emotional system and a deliberative one [START_REF] Kahneman | Thinking, Fast and Slow[END_REF], reflecting the old philosophical opposition between the heart, with its emotions and passions, and the head, with its reason, which interfere during decision making [START_REF] Luo | Follow the heart or the head? The interactive influence model of emotion and cognition[END_REF]. Here I define rational choices as decisions that can be explained with a cognitive model. It does not mean that this cognitive process was conscious when the decision was made, as a decision can be driven by emotions, and still be rational.

The criticisms I faced were about the absence of rationality of my choices -the impossibility to find cognitive explanations. Therefore, an explanatory model could solve the paradox.

Building the model

At first, I just wanted to explain the paradox for myself, not as a researcher. The explanation I had found was the following: my new activities had reduced the time I previously spent playing sports, walking in a natural environment, and indulging in creative hobbies. Thus, I saved time directly, as I no longer spent time on these activities, but I also saved time indirectly, which was the time I previously spent working to pay for the goods and services that supported these activities (costs of travel to a hiking site, sports equipment and entry to amenities, materials for creative hobbies, etc.). Indeed, my new activities were satisfying needs such as immersion in nature, physical activity, and free creativity, in addition to the needs for the products I made. This generated moments that I felt more intensely. Furthermore, this approach also rapidly led to material satiety: it curbed my appetite for material goods, producing the feeling that I had enough. For something was stemming from the products I had made, rendering industrial products tasteless and the ones I had made sufficient. I used to say that once you've spent three hours of hard work piercing a carefully chosen stone with another one to make a necklace ornament, you don't feel any need to make another one. Similarly, my home-made soap and selfmade washing liquid (from wood ashes) swept away all my previous needs for storebought cleaning products. The cherry on the cake -not my primary motivation -was the feeling that I was respecting the natural environment I was living from: little or no waste, energy use, pollution or loss of biodiversity. Overall, more with fulfilling activities, less time needed: this was totally rational.

Once these first thoughts were clear, I considered what I already knew from the literature. I re-examined Maslow's hierarchy of needs that I had learned a long time ago, but it could not easily reflect my need to be in a natural environment nor my need for physical activity. I knew the latter activity was a determinant of health, for example, promoted by the World Health Organization in a global action plan on physical activity for healthier people (WHO, 2018). And there were justifications for the former ones in a French book I had been given about why nature benefits us, which is a literature review for non-academic readers [START_REF] Gueguen | Pourquoi la nature nous fait du bien[END_REF]. During the sustainability courses I gave, I presented alternative indicators to Gross National Product, such as Bhutan's Gross National Happiness (GNH), where I had found interesting elements. Indeed, one of the nine domains of the GNH index is "Cultural diversity and resilience", and this domain includes an indicator of "Artisan skills" also named "Indigenous knowledge literacy" or "arts" in the survey. It is measured in thirteen skills including weaving and carving. The contribution of these skills to happiness, as defined in this study, could reflect my need for free creativity. Besides this, the book "Our Common Future", also known as the Brundtland Report (WCED, 1987), offered a definition of sustainable development based on needs satisfaction, which I regularly used when giving my courses. To my students, I often posed the question "What do we need?", and the discussions we had on this topic suggested a useful distinction between needs and the ways needs are satisfied. For example, this can be illustrated by the historical evolution of work, from physical work to office work, which has left us with an unsatisfied need for physical activity, fulfilled in the modern world by a variety of sports. However, although all this background supported some of the ideas I had, it didn't make a global model that would solve my paradox.

A model of needs satisfaction from time-use patterns

The concept of lifestyle has been characterized by both practices and meaning in field studies (Evans and Abrahamse, 2008;[START_REF] Lorenzen | Going Green: The Process of Lifestyle Change[END_REF]. It relies on theoretical work defining a lifestyle as "a more or less integrated set of practices which an individual embraces, not only because such practices fulfill utilitarian needs, but because they give material form to a particular narrative of self-identity" [START_REF] Giddens | Modernity and Self-Identity: Self and Society in the Modern Age[END_REF]. Nevertheless, a theoretical review of the concept [START_REF] Veal | The concept of lifestyle: a review[END_REF] concludes on a strict definition of lifestyle as "the distinctive pattern of personal and social behaviour characteristic of an individual or a group", because this definition gives "a clear, operationalizable and theoretically useful identity". I define a lifestyle as a pattern of activities describing the use of time for an individual or a group. I define activity as a time-use schedule, indicating what is done and when. A unique time interval characterizes simple activities, for example a walk outdoors. More complex time schedules can be necessary for more complex activities, for example, when delays such as drying times in pottery or basketry are necessary steps of a process. Some activities have material inputs, such as tools, equipment, and raw materials used during the activity, and some have material outputs. An activity also results in outcomes as regards groups of needs, as it generates more or less satisfaction in terms of different needs.

Lifestyles include broad categories of activities such as work and leisure. The understanding of work has evolved throughout history: "In the pre-modern domestic familybased economy, the household was a living and working community. In the industrial system, only paid employment outside the home was considered work, while unpaid household work was devalued" [START_REF] Komlosy | On the historical development of work. In Post-Growth Work, Employment and Meaningful Activities within Planetary Boundaries[END_REF].

Here I define work as paid employment, using the narrow sense of the concept. I call a lifestyle "modern" when it includes a significant share of work activities.

Leisure studies were initially based on the work-leisure relationship and, although this relationship later weakened and it is now argued that that the only secure future for this field of study is to re-focus on work [START_REF] Roberts | A Future for UK Leisure Studies: Back to Work[END_REF]. For anthropologists, who mainly study non-western countries, leisure is a "universal human phenomenon". Many activities can be identified as leisure by external observers, although the word as a category has no straightforward translation in many cultures (Chick, 1998). All this makes the "leisure" category typical of modern societies. I, therefore, define leisure as an activity undertaken within a modern market culture, which means it has some cost for the person who engages in it.

Modern societies are market societies, but they still present the characteristics of traditional non-market societies. Work and leisure apply to activities undertaken within a market societal culture. On the contrary, I refer to as "life" any activity undertaken as part of a non-market societal culture.

Consequently, the same activity can be life, work, or leisure, depending on the context. For example, land art can be work for an artist, leisure for someone paying to attend land art classes, and life for someone simply practicing land art in the neighborhood.

The concept of nature-based solutions (NBS) is highly relevant to my present lifestyle. Two definitions of NBS are widely used. The European Commission defined NBS as "actions inspired by, supported by, or copied from nature" (European Commission, 2015, Annex 1).

The International Union for Conservation of Nature (IUCN) defined NBS as "actions to protect, sustainably manage, and restore natural or modified ecosystems, that address societal challenges effectively and adaptively, simultaneously providing human well-being and biodiversity benefits" (Cohen-Shacham et al., 2016). This second definition characterizes actions directed towards ecosystems and adds properties of those actions to the definition. This, however, makes it difficult to use, as the properties would have to be checked for the concept to be properly used. The first definition includes actions inspired by or copied from nature, which is just a small deviation from the literal meaning of "nature-based" and for me meant simply supported by nature. It could be argued that everything comes from nature, after a greater or lesser amount of transformation and transport. The typology of [START_REF] Eggermont | Nature-based Solutions: New Influence for Environmental Management and Research in Europe[END_REF] is, therefore, helpful in distinguishing three main types of naturebased solutions, depending on the level of engineering of biodiversity and ecosystems, and on the number of ecosystem services and stakeholder groups targeted. The first type, "better use of natural/protected ecosystems", is the closest to the common idea about nature-based solutions that nature is not transformed a great deal, as the other types of NBS include more intensively or even intrusively managed ecosystems as well as artificial ones.

"Nature-based" is an attribute of activities, here defined by the key role played by nature, especially the nearby natural environment, as the sourcing place and/or the setting of the activity. This natural environment can be wild nature or a slightly transformed natural ecosystem, like most gardens.

I define "nature-based living" as a lifestyle made of nature-based life activities. Hybridization of modern lifestyles (defined above) with nature-based living creates hybrid nature-based lifestyles.

As regards human needs, Max-Neef's Human Scale Development (Max-Neef, 1991) offered a clearly relevant framework, plainly dissociating fundamental needs from the different ways they can be satisfied. Hence, "Satisfiers" can contribute to the satisfaction of one or more fundamental needs. They are "Synergic Satisfiers" if they "satisfy a given need, simultaneously stimulating and contributing to the fulfillment of other needs". Fundamental needs are classified in a two-dimensional matrix. The first dimension, named "existential categories", includes being, having, doing, and interacting. The second dimension, named "the axiological categories", includes subsistence, protection, affection, understanding, participation, idleness, and creation. Max-Neef states that "Satisfiers are not the available economic goods". Economic goods are "in a strict sense the means by which individuals will empower the satisfiers to meet their needs". For example, books and laboratory instruments are artifacts, and "the function of these goods is to empower the Doing of Understanding". This framework includes many detailed elements relevant to the actualization of needs. Despite this, time use is not straightforward in the framework, as the "doing" dimension includes items that are not, strictly speaking, time use (for example, "be different from") and some of the "doing" items (for example, to choose, cooperate, and build) can be aspects of the same activity. I, therefore, needed to adapt the framework to reflect my thoughts, which I did following Max-Neef's statement that the framework was an "open proposal".

My model is based on a primary classification of human needs into two categories: material needs and immaterial needs.

I further divide material needs into three secondary categories, according to the short, medium, or long lifetime of the goods, respectively consumption goods (including consumables such as food or cleaning products), equipment (including tools), and the home. This does not mean we need ownership of durable goods, but only the ability to use some of these goods.

As regards immaterial needs, none of the previously mentioned texts provide an encompassing framework including the items I felt relevant to explain the paradox I described in part 1, namely a natural setting, physical activity, and self-expression. Other groups of needs, whose satisfaction did not change very much, are not explicit elements of my specific model. However, some of them could be relevant elements of other specific models.

A general model of needs satisfaction from time-use patterns relates activities, representing the use of time to groups of needs classified into material and immaterial categories. It can be implemented in specific models, depending on the goals of the modeling processes.

In such models, work, as paid employment, indirectly satisfies some needs, through the goods and services that it enables us to pay for, and directly satisfies other needs depending on the job.

It should be noted that the material outputs of some activities can be the inputs of other activities, but this differs from the outputs as regards the satisfaction of material needs. For example, when an activity produces a tool, it satisfies some need for equipment, but the tool (not the satisfied need for tools) is an input of other production activities. These material loops exist around work, leisure, and nature-based life, but material flows are not represented in the following graphical representation, which is a representation of needs satisfaction from time use.

The intensity of an activity is the diversity of the needs it satisfies, given its time use. Intense activities are time-use schedules generating a significant amount of needs satisfaction from different groups of needs. Simply speaking, an activity satisfies an array of needs from a given time use. The diversity of these needs and the limited amount of time used are the basis of its intensity. These different needs are not necessarily satisfied simultaneously, but the needs associated with one same activity add-up to make its diversity.

Graphical representation

Figure 1 is a simplified representation of my initial lifestyle. The time use is made up of work and leisure activities. Needs for consumables, equipment (like cars, digital devices, seats, or tools), and the home are funded by the money gained from work (thin lines). Immaterial needs for nature, physical activity, and self-expression are satisfied by leisure activities (thin lines), themselves funded by some money gained from work (bold arrows).

Comparison

The intensity of the resulting hybrid lifestyle is increased, because part of the work activity and all leisure activities, which otherwise address needs separately -thus tending to reduce the intensity, have been replaced by nature-based activities (NBA). These are more intense because they simultaneously satisfy a wide diversity of needs, always addressing nature needs, but often also satisfying needs for physical activity and free creativity, in addition to the material needs they directly aim to meet in most cases. They are also more intense because they more easily fulfill the satisfaction of needs, for the satiety resulting from self-production leaves little space for additional material needs.

The resulting hybrid lifestyle has a greater intensity, being made up of more intense activities, and requires less time for the same level of satisfaction of needs. It is a rational choice, and this solves the paradox.

This can be illustrated by the example of the broom mentioned above. Making this broom involved outdoor physical activity and some creativity. It is now hung in the room where I live, as a decorative item. Therefore, I no longer spend time moving it to and from the broom closet. I calculated that the time I saved rapidly overcame its production time. The double function of cleaning and decoration finally made it time-efficient, in addition to other benefits like the pleasant smell of pine-needles it gives off during use, and the interest it attracts from my visitors who want to try it out, both of which appeared after it was made.

The efficiency also stems from the reduced need for specific decoration elements. Overall, a limited time investment satisfied an array of different needs.

Discussion

The general model and its implementation I propose a general model of satisfaction of human needs from time spent doing activities.

It emphasizes the interest of engaging in activities offering synergistic satisfaction of different types of needs. The concept of intensity, qualitatively defined as the diversity of needs satisfied by the time spent on an activity, is an attribute of all human activities, and therefore of lifestyles, which are described as patterns of activities. I adapted this general model into a specific one in order to explain a paradox described in the narrative (part 1). This adapted model only includes the relevant elements that are common to most of my nature-based activities, for this is more appropriate to the clarity of the core elements of my explanations, namely a natural environment, physical activity, and free creativity.

Figures 1 and2 are, therefore, simplified representations, voluntarily omitting the satisfaction of other needs such as those described in the broom example. My central concept of intensity is linked to Max-Neef's concept of synergies between satisfiers. Many satisfiers among those revealed by Max-Neef (social environment, communities, etc.), are not represented, as I experienced no major evolution in this domain. Some satisfiers evidenced by Max-Neef, like autonomy, consistency, getting to know oneself, and selfesteem, are not included in the specific model of the present paper, because they made only a little difference, clearly not a major one. They could obviously be key elements of other specific models.

For example, it's clear that the familiarity I came to feel in an outdoor environment, thanks to my bushcraft course, satisfies some need for security. Bushcraft education makes a place "no longer wild but home" [START_REF] Fenton | Bushcraft Education as Radical Pedagogy[END_REF]. The absence of perceived threats could be an important element of transition towards nature-based lifestyles.

Connectedness also matters, and hand-made things create relationships with people and materials [START_REF] Pike | Rewilding Hearts and Habits in the Ancestral Skills Movement[END_REF]. I only mentioned the satiety I felt as the result of these connections, but other specific models could explicitly include a need for connectedness.

As an emerging model from a personal life experience, the present model is a rooted one reflecting feelings and thoughts. It is proposed as a basis of discussion, criticism, and evolution about theory building in the field of human needs and their satisfaction, and the importance of nature in this domain. This applies to the concept of intensity of activities and to the grouping of needs into broad categories. Further theory building could be done through critical thinking, confrontation with other patterns of time use and needs fulfillment, or more extensive studies.

The status of nature-based activities

I have presented my nature-based activities as life activities because they are moments of life directly from nature, as opposed to life through markets. Indeed, the cost to me is almost nothing, being limited to a few tools and equipment, and I need no traveling time to be in a natural environment. For other people, however, nature-based activities require transport. Outdoor clothing is another cost and a type of purchase that has its own fashion addicts. Likewise, some people avidly collect tools like knives. These increasing costs could make nature-based activities look more like leisure than life. On the contrary, if urban green spaces were managed as productive resources dedicated to local residents, naturebased life activities could be free options even for city dwellers. Overall, the status of nature-based activities varies from leisure to life, and work of course because some jobs are nature-based. For traditional communities, these activities are necessary life activities. The level of choice to engage in these activities can range from necessary to optional and from free to expensive, depending on the context.

The time-efficiency of activities

Time is a key determinant of the intensity of activities. The dilution of time use with the separation of work and leisure activities tends to reduce the intensity of each, while naturebased life activities tend to be intense because they concentrate the satisfaction of diverse needs: some nature needs, a minimum amount of physical activity, some creativity, in addition to the life need that they aim to fulfill. This time efficiency, as regards the joint outcomes of activities from one main time input, are typical key elements of my initial academic background in management sciences. If the present model is shown to be relevant, this would confirm the interest of bringing together scientists from different fields, and would help to remove the traditional frontiers between disciplines enabling the building of new areas of knowledge.

A rationale for trends in movements

In a study of the ancestral skills movement, also named "primitive skills, wilderness survival skills, Stone Age living, or bushcraft", [START_REF] Pike | Rewilding Hearts and Habits in the Ancestral Skills Movement[END_REF] describes the history of the movement and of related trends: self-sufficiency movements such as the Shakers, Arts and Crafts, and Woodcraft Folk in the 18th, 19th, and 20th centuries were followed by a "quintessentially American" back-to-the-land movement started in the late 1960s and 1970s. The ancestral skills movement, which grew up in the last decades of the 20th century, was also influenced contemporary trends such as such as experimental archeology and the wilderness skills movement. At this time, there were overlaps with media-promoted trends like survival shows and paleo diets programs. The more recent makers movements started in the early 2000s.

in France, [START_REF] Rouvière | Retourner à la terre -L'utopie néo-rurale en Ardèche depuis les années 1960[END_REF] studied the Ardèche department, a symbol of the back-to-theland movement, including four waves since the 60s, each of them with different motivations. Although this work was published after I attended my bushcraft course, I had heard about "neo-ruraux", people moving from cities to rural areas, and the main reason for this was the quality of life. This was precisely the reason my family settled in a remote rural area. The context I had grown-up in was, therefore, a general idea about the quality of rural lives. My research topics had made me conscious of the negative environmental and social impacts of the modern world, and I admired the French thinker Pierre Rabhi, who promoted a "happy sobriety" [START_REF] Rabhi | Vers la sobriété heureuse[END_REF].

Nevertheless, the context I lived in had not offered me any idea about the skills I could use to develop some form of living from the land, apart from growing vegetables, but I did not want to replace the organic food baskets I bought from local producers. Moreover, apart from making fire by friction, I did not recognize the skills mentioned in the program of the bushcraft course I attended.

Regarding these movements, my model offers a rational explanation about why naturebased activities are more fulfilling. It also questions their degree of integration into modern lifestyles, resulting in hybrid lifestyles. There may be an optimum level of hybridization, ranging from 0% to 100% depending on the culture and individual characteristics, which could become the subject of further study.

Nature-based activities also usually have limited negative environmental and social impacts, which arise for two reasons: they involve low-impact transformation processes, and they generate satiety. This reduction of impacts could be canceled out, if they are practiced as leisure, by the impacts of transport and of store-bought equipment. However, if they are practiced as life activities, they reduce impacts. Such activities also contribute to degrowth by satisfying some needs directly, rather than with products and services paid for with money gained from work. In the process, they enhance well-being, by offering an art of living from nature to integrate into our lives. This confirms the possibility and interest of degrowth, as a source of alternatives: an "art of living with art" [START_REF] Latouche | Que sais-je / Humensis[END_REF].

Social change

If there are better lifestyles with reduced impacts, we need to ask whether social influence techniques could favor the adoption of such lifestyles. First, let us examine the change process described in part 1.

The evolution of my lifestyle changes described in part 1 was triggered by a primary decision (to learn how to make fire), followed by a consequent secondary decision (to attend a week-long course in the woods), and later multiple tertiary decisions resulting in a hybrid nature-based lifestyle, which offered a major lifestyle enhancement. The primary decision can be explained within the theory of planned behavior [START_REF] Ajzen | The theory of planned behavior[END_REF], for a conscious intention resulted from a desire for autonomy, and this lasting desire could have played a role in the tertiary decisions. Ajzen's model also emphasizes the perceived behavioral control, which increased in my case due to the material opportunities I had and the trust I progressively gained about my ability to master skills. This could have contributed to the rapid sequence of tertiary decisions. Nevertheless, the secondary decision, based on a misunderstanding about the setting of the course, does not easily fit into the framework, and nor does the fact that the immaterial outcomes of the tertiary decisions were not consciously expected, apart from an enduring desire for autonomy, which I did not feel like a major motivation. I would rather say that the tertiary decisions were a series of exploratory steps. The evolution following the secondary decision fits better into commitment theories [START_REF] Kiesler | The Psychology of Commitment: : Experiments Linking Behaviour to Belief[END_REF][START_REF] Joule | La soumission librement consentie[END_REF][START_REF] Joule | La soumission librement consentie[END_REF]: the commitment resulting from the secondary decision (to attend a week-long bushcraft course) paved the way for the development of similar activities during the following years, until I finally received skeptical comments. Only then did I start thinking about what appeared to me as criticism. Even then, the result was a reinforcement of my behavior, through the explanations that I found. This reinforcement following attack is a classical sequence within commitment theories. Overall, both rational decisions and commitmentdriven steps were relevant elements of my lifestyle change.

As a consequence, different strategies could be used to develop the adoption of naturebased lifestyles. As my model sets a rational justification for some hybridization of lifestyles, social change could be targeted by social influence strategies promoting a process of hybridization, which could lead to a panel of different outcomes, depending on contexts, and on cultures. This variability probably makes it easier to simply trigger changes using commitment techniques by creating opportunities to freely discover naturebased activities. These would engage people in a nature-based course of action, which would then develop in an autonomous way. This could be done by creating easy-access, low-cost opportunities, for example, as part of sustainability agendas of local governments and businesses.

Conclusion

I used the evolution of my personal lifestyle towards more nature-based activities to propose a rooted framework reflecting the changes I felt had taken place. The combined satisfaction of different types of needs, resulting in a greater intensity of activities and a consequent reduction in the time needed for a similar satisfaction of needs. I made a categorization of needs into three material and three immaterial categories, which I then used to illustrate the concept of the intensity of activities, defined as the diversity of needs satisfied by a given time use. This constitutes a step towards the introduction of time into theories of needs satisfaction, and highlights the importance of the dissociation or, conversely, the synergistic combination of needs satisfaction in our lives. It also emphasizes the saturation of needs satisfied by nature-based activities. As an attempt at theory building, it offers a generic model and a specific implementation that leaves out many types of satisfiers, especially those reflecting social interactions and citizenship, that can be key elements of other modeling processes. The present model can explain the rising interest in nature-based activities, especially if these are part of life from nature rather than leisure.

My ultimate conclusion will be the next chapter of my narrative. The Covid-19 crisis caused inter-related health safety and job-security risks, above all because vaccination could have become mandatory and to refuse it would have led to redundancy. My safety and security needs were, therefore, decoupled from the other needs satisfied by my work. I opted for early retirement, which will unite these needs with the array of those satisfied by an increased investment in a nature-based life.

Figure 2

 2 Figure2is a simplified representation of my hybrid nature-based lifestyle. Part of the working time and all the leisure time of the previous modern lifestyle are replaced by selfproduced, self-sourced, low-tech activities requiring very little work (salaried) time to pay for a few basic pieces of equipment (one bold arrow), and no money in the case of primitive techniques. Each of these activities satisfies many needs (multiple thin lines). The satisfaction of material needs by nature-based activities tends to generate satiety, so these needs are represented by smaller ellipses. All these activities constitute a hybrid naturebased lifestyle.

Figure 1 .

 1 Figure 1. Initial modern lifestyle

Figure 2 .

 2 Figure 2. Hybrid nature-based lifestyle

Authorship confirmation statement: I confirm that I am the author and the only author of this manuscript.

Author(s') disclosure statement(s): No competing financial interests exist.

Funding statement: No funding was received for this work.


Florian Renkin
email: frenkin@lrde.epita.fr

Philipp Schlehuber-Caissier
email: philipp@lrde.epita.fr

Alexandre Duret-Lutz

Adrien Pommellet
email: adrien@lrde.epita.fr

Effective Reductions of Mealy Machines

We revisit the problem of reducing incompletely specified Mealy machines with reactive synthesis in mind. We propose two techniques: the former is inspired by the tool MeMin [1] and solves the minimization problem, the latter is a novel approach derived from simulationbased reductions but may not guarantee a minimized machine. However, we argue that it offers a good enough compromise between the size of the resulting Mealy machine and performance. The proposed methods are benchmarked against MeMin on a large collection of test cases made of well-known instances as well as new ones.

Introduction

Program synthesis is a well-established formal method: given a logical specification of a system, it allows one to automatically generate a provably correct implementation. It can be applied to reactive controllers (Fig. 1a): circuits that produce for an input stream of Boolean valuations (here, over Boolean variables a and b) a matching output stream (here, over x and y).

The techniques used to translate a specification (say, a Linear Time Logic formula that relates input and output Boolean variables) into a circuit often rely on automata-theoretic intermediate models such as Mealy machines. These transducers are labeled graphs whose edges associate input valuations to a choice of one or more output valuations, as shown in Fig. 1b.

Since Mealy machines with fewer states result in smaller circuits, reducing and minimizing the size of Mealy machines are well-studied problems [START_REF] Alberto | Minimization of incompletely specified finite state machines based on distinction graphs[END_REF][START_REF] Paull | Minimizing the number of states in incompletely specified sequential switching functions[END_REF]. However, vague specifications may cause incompletely specified machines: for some states (i.e., nodes of the graph) and inputs, there may not exist a unique, explicitly defined output, but a set of valid outputs. Resolving those choices to a single output (among those allowed) will produce a fully specified machine that satisfies the initial specification, however those different choices may have an impact on the minimization of the machine. While minimizing fully specified machines is efficiently solvable [START_REF] Hopcroft | An n log n algorithm for minimizing states in a finite automaton[END_REF], the problem is NP-complete for incompletely specified machines [START_REF] Pfleeger | State reduction in incompletely specified finite-state machines[END_REF]. Hence, it may also be worth exploring faster algorithms that seek to reduce the number of states without achieving the optimal result. Consider Fig. 1b: this machine is incompletely specified, as for instance state 0 allows multiple outputs for input ab (i.e., when both input variables a and b are true) and implicitly allows any output for input āb (i.e., only b is true) as it isn't constrained in any way by the specification. We can benefit from this flexibility in unspecified outputs to help reduce the automaton. For instance if we constrain state 2 to behave exactly as state 0 for inputs ab and a b, then these two states can be merged. Adding further constraints can lead to the single-state machine shown in Fig. 1c. These smaller machines are not equivalent, but they are compatible: for any input stream, they can only produce output streams that could also have been produced by the original machine.

We properly define Incompletely specified Generalized Mealy Machines in Section 2 and provide a SAT-based minimization algorithm in Section 3. Since the minimization of incompletely specified Mealy machines is desirable but not crucial for reactive synthesis, we propose a faster reduction technique yielding "small enough" machines in Section 4. Finally, in Section 5 we benchmark these techniques against the state-of-the-art tool MeMin [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF].

Definitions

Given a set of propositions (i.e., Boolean variables) X, let B X be the set of all possible valuations on X, and let 2 B X be its set of subsets. Any element of 2 B X can be expressed as a Boolean formula over X. The negation of proposition p is denoted p. We use ⊤ to denote the Boolean formula that is always true, or equivalently the set B X , and assume that X is clear from the context. A cube is a conjunction of propositions or their negations (i.e., literals). As an example, given three propositions a, b and c, the cube a ∧ b, written a b, stands for the set of all valuations such that a is true and b is false, i.e. {a bc, a bc}. Let K X stand for the set of all cubes over X. K X contains the cube ⊤, that stands for the set of all possible valuations over X. Note that any set of valuations can be represented as a disjunction of disjoint cubes (i.e., not sharing a common valuation). Definition 1. An Incompletely specified Generalized Mealy Machine (IGMM) is a tuple M = (I, O, Q, q init , δ, λ), where I is a set of input propositions, O a set of output propositions, Q a finite set of states, q init an initial state, δ : Q, B I → Q a partial transition function, and λ : Q, B I → 2 B O \ {∅} an output function such that λ(q, i) = ⊤ when δ(q, i) is undefined. If δ is a total function, we then say that M is input-complete.

It is worth noting that the transition function is input-deterministic but not complete with regards to Q as δ(q, i) could be undefined. Furthermore, the output function may return many valuations for a given input valuation and state. This is not an unexpected definition from a reactive synthesis point of view, as a given specification may yield multiple compatible output valuations for a given input.

Definition 2 (Semantics of IGMMs). Let M = (I, O, Q, q init , δ, λ) be an IGMM. For all u ∈ B I and q ∈ Q, if δ(q, u) is defined, we write that q u/v --→ δ(q, u) for all v ∈ λ(q, u). Given two infinite sequences of valuations

ι = i 0 • i 1 • i 2 • • • ∈ (B I ) ω and o = o 0 • o 1 • o 2 • • • ∈ (B O ) ω , (ι, o) |= M q if and only if:
either there is an infinite sequence of states (q j ) j≥0 ∈ Q ω such that q = q 0 and q 0 i0/o0

---→ q 1 i1/o1 ---→ q 2 i2/o2 ---→ • • • ; -or there is a finite sequence of states (q j ) 0≤j≤k ∈ Q k+1 such that q = q 0 , δ(q k , i k ) is undefined, and q 0 i0/o0 ---→ q 1 i1/o1 ---→ • • • q k .
We then say that starting from state q, M produces output o given the input ι.

Note that if δ(q k , i k ) is undefined, the machine is allowed to produce an arbitrary output from then on. Furthermore, given an input word ι, there may be several output words o such that (ι, o) |= M q (in accordance with a lax specification).

As an example, consider the input sequence ι = ab • āb • ab • āb • • • applied to the initial state 0 of the machine shown in Figure 1b. We have (ι, o) |= M 0 if and only if for all j ∈ N, o 2j ∈ x and o 2j+1 ∈ ȳ, where x and ȳ are cubes that respectively represent {xy, xȳ} and {xȳ, xȳ}. Definition 3 (Variation and specialization). Let M = (I, O, Q, q init , δ, λ) and M ′ = (I, O, Q ′ , q ′ init , δ ′ , λ ′ ) be two IGMMs. Given two states q ∈ Q, q ′ ∈ Q ′ , we say that q ′ is a:

-

variation of q if ∀ι ∈ (B I ) ω , o | (ι, o) |= M ′ q ′ ∩ {o | (ι, o) |= M q } ̸ = ∅; -specialization of q if ∀ι ∈ (B I ) ω , o | (ι, o) |= M ′ q ′ ⊆ {o | (ι, o) |= M q }. We say that M ′ is a variation (resp. specialization) of M if q ′ init is a variation (resp. specialization) of q init .
Intuitively, all the input-output pairs accepted by a specialization q ′ in M ′ are also accepted by q in M . Therefore, if all the outputs produced by state q in M comply with the original specification, then so do the outputs produced by state q ′ in M ′ . In order for two states to be a variation of one another, for all possible inputs they must be able to agree on a common output behaviour.

We write q ′ ≈ q (resp. q ′ ⊑ q) if q ′ is a variation (resp. specialization) of q. Note that ≈ is a symmetric but non-transitive relation, while ⊑ is transitive (⊑ is a preorder).

Our goal in this article is to solve the following problems:

Reducing an IGMM M : finding a specialization of M having at most the same number of states, preferably fewer. Minimizing an IGMM M : finding a specialization of M having the least number of states. Consider again the IGMM shown in Figure 1b. The IGMM shown in Figure 1c is a specialization of this machine and has a minimal number of states.

Generalizing inputs and outputs. Note that the output function of an IGMM returns a set of valuations, but it can be rewritten equivalently to output a set of cubes as λ : Q, B I → 2 K O . As an example, consider I = {a} and O = {x, y, z}; the set of valuations

v = {xyz, xyz, xȳz, xȳz} ∈ 2 B O is equivalent to the set of cubes v c = {xy, xȳ} ∈ 2 K O .
In the literature, a Mealy machine commonly maps a single input valuation to a single output valuation: its output function is therefore of the form λ : Q, B I → B O . The tool MeMin [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF] uses a slight generalization by allowing a single output cube, hence λ : Q, B I → K O . Thus, unlike our model, neither the common definition nor the tool MeMin can feature an edge outputting the aforementioned set v (or equivalently v c ), as it cannot be represented by a single cube or valuation. Our model is therefore strictly more expressive, although it comes at a price for minimization.

Note that, in practice, edges with identical source state, output valuations, and destination state can be merged into a single transition labeled by the set of allowed inputs. Both our tool and MeMin feature this optimization. While it does not change the expressiveness of the underlying model, this more succinct representation of the machines does improve the efficiency of the algorithms detailed in the next section, as they depend on the total number of transitions.

SAT-Based Minimization of IGMM

This section builds upon the approach presented by Abel and Reineke [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF] for machines with outputs constrained to cubes, and generalizes it to the IGMM model (with more expressive outputs).

General approach

Definition 4. Given an IGMM M = (I, O, Q, q init , δ, λ), a variation class C ⊆ Q is a set of states such that all elements are pairwise variations, i.e. ∀q, q ′ ∈ C, q ′ ≈ q. For any input i ∈ B I , we define:

the successor function Succ(C, i) = q∈C {δ(q, i) | δ(q, i) is defined}; the output function Out(C, i) = q∈C λ(q, i).

Intuitively, the successor function returns the set of all states reachable from a given class under a given input symbol. The output function returns the set of all shared output valuations between the various states in the class.

In the remainder of this section we will call a variation class simply a class, as there is no ambiguity. We consider three important notions concerning classes, or rather sets thereof, of the form S = {C 0 , . . . , C n-1 }.

Definition 5 (Cover condition). We say that a set of classes S covers the machine M if every state of M appears in at least one of the classes. Definition 6 (Closure condition). We say that a set of classes S is closed if for all C j ∈ S and for all inputs i ∈ B I there exists a C k ∈ S such that Succ(C j , i) ⊆ C k .

Definition 7 (Nonemptiness condition). We say that a class C has a nonempty output if Out(C, i) ̸ = ∅ for all inputs i ∈ B I .

The astute reader might have observed that the nonempty output condition is strictly stronger than the condition that all elements in a class have to be pairwise variations of one another. We will see that this distinction is however important, as it gives rise to a different set of clauses in the SAT problem, reducing the total runtime.

Combining these conditions yields the main theorem for this approach. This extends a similar theorem by Abel and Reineke [1, Thm 1] by adding the nonemptiness condition to support the more expressive IGMM model.

Theorem 1. Let M = (I, O, Q, q init ,
δ, λ) be an IGMM and S = {C 0 , . . . , C n-1 } be a minimal (in terms of size) set of classes such that (1) S is closed, (2) S covers every state of the machine M and (3) each of the classes C j has a nonempty output. Then the IGMM M ′ = (I, O, S, q ′ init , δ ′ , λ ′ ) where:

-q ′ init = C for some C ∈ S such that q init ∈ C; -δ ′ (C j , i) = C k for some k s.t. Succ(C j , i) ⊆ C k if Succ(C j , i) ̸ = ∅ undefined else; -λ ′ (C j , i) = Out(C j , i) if Succ(C j , i) ̸ = ∅ ⊤ else;
is a specialization of minimal size (in terms of states) of M .

Figure 2a illustrates this construction on an example with a single input proposition I = {a} (hence two input valuations B I = {a, ā}), and three output propositions O = {x, y, z}. To simplify notations, elements of 2 B O are represented as Boolean functions (happening to be cubes in this example) rather than sets.

States have been colored to indicate their possible membership to one of the three variational classes. The SAT solver needs to associate each state to at least one of them in order to satisfy the cover condition (5), while simultaneously respecting conditions ( 6)- [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF]. A possible choice would be: C 0 = {0}, C 1 = {1, 3, 6}, and C 2 = {2, 4, 5}. For this choice, the violet class C 0 has only a single state, so the closure condition ( 6) is trivially satisfied. All transitions of the states in the orange class C 1 go to states in C 1 , also satisfying the condition. The same can be said of the green class C 2 .

0 1 2 3 5 4 4 6 a/z ā/xȳz a/z ā/z a/⊤ ā/z a/z ā/⊤ ā/⊤ a/⊤ ā/⊤ a/z a/⊤ ā/⊤ (a) Original IGMM M 0 1 2 ā/xȳz a/z ā/z a/z a/z ā/z a/⊤ (b) Minimal specialization of M
Fig. 2: Minimization example Finally, we need to check the nonempty output condition [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF]. Once again, it is trivially satisfied for the violet class C 0 . For the orange and green classes, we need to compute their respective output. We get

Out(C 1 , a) = z, Out(C 1 , ā) = z, Out(C 2 , a) = z and Out(C 2 , ā) = z.
None of the output sets is empty, thus condition ( 7) is satisfied as well. Note that, since the outgoing transitions of states 4 and 6 are self-loops compatible with all possible output valuations, another valid choice is:

C 0 = {0, 4, 6}, C 1 = {1, 3, 4, 6}, and C 2 = {2, 4, 5, 6}.
The corresponding specialization, constructed as described in Theorem 1, is shown in Figure 2b. Note that this machine is input-complete, so the incompleteness of the specification only stems from the possible choices in the outputs.

Proposed SAT Encoding

We want to design an algorithm that finds a minimal specialization of a given IGMM M . To do so, we will use the following approach, starting from n = 1:

-Posit that there are n classes, hence, n states in the minimal machine.

-Design SAT clauses ensuring cover, closure and nonempty outputs.

-Check if the resulting SAT problem is satisfiable.

-If so, construct the minimal machine described in Theorem 1.

-If not, increment n by one and apply the whole process again, unless n = |Q| -1, which serves as a proof that the original machine is already minimal.

Encoding the cover and closure conditions. In order to guarantee that the set of classes S = {C 0 , . . . , C n-1 } satisfies both the cover and closure conditions and that each class C j is a variation class, we need two types of literals:

s q,j should be true if and only if state q belongs to the class

C j ; -z i,k,j should be true if Succ(C k , i) ⊆ C j for i ∈ B I .
The cover condition, encoded by Equation (1), guarantees that each state belongs to at least one class.

q∈Q 0≤j<n s q,j (1)
0≤j<n q,q ′ ∈Q q̸ ≈q ′ s q,j ∨ s q ′ ,j

Equation ( 2) ensures that each class is a variational class: two states q and q ′ that are not variations of each other cannot belong to the same class.

The closure condition must ensure that for every class C i and every input symbol i ∈ B I , there exists at least one class that contains all the successor states: ∀k, ∀i, ∃j, Succ(C k , i) ⊆ C j . This is expressed by the constraints (3) and (4).

0≤k<n i∈B I 0≤j<n z i,k,j (3)
0≤j,k<n q,q ′ ∈Q,i∈B I q ′ =δ(q,i)

(z i,k,j ∧ s q,k ) → s q ′ ,j (4)
The constraint (3) ensures that at least one C j contains Succ(C k , i), while (4) ensures this mapping of classes matches the transitions of M .

Encoding the nonempty output condition. Each class in S being a variation class is necessary but not sufficient to satisfy the nonempty output condition. We indeed want to guarantee that for any input i, all states in a given class can agree on at least one common output valuation. However it is possible to have three or more states (like 0 a/{xy, xȳ}, 1 a/{xy, xȳ}, and 2 a/{xy, xy}) that are all variations of one another, but still cannot agree on a common output.

This situation cannot occur in MeMin since their model uses cubes as outputs rather than arbitrary sets of valuations as in our model. A useful property of cubes is that if the pairwise intersections of all cubes in a set are nonempty, then the intersection of all cubes in the set is necessarily nonempty as well.

Since cubes are not expressive enough for our model, we will therefore generalize the output as discussed earlier in Section 2: we represent the arbitrary set of valuations produced by the output function λ as a set of cubes whose disjunction yields the original set. For q ∈ Q and i ∈ B I , we partition the set of valuations λ(q, i) into cubes, relying on the Minato [START_REF] Minato | Fast generation of irredundant sum-of-products forms from binary decision diagrams[END_REF] algorithm, and denote the obtained set of cubes as CS(λ(q, i)).

Our approach for ensuring that there exists a common output is to search for disjoint cubes and exclude them from the possible outputs by selectively deactivating them if necessary; an active cube is a set in which we will be looking for an output valuation that the whole class can agree on. To express this, we need two new types of literals:

a c,q,i should be true iff the particular instance of the cube c ∈ CS(λ(q, i))

used in the output of state q when reading i is active; sc q,q ′ should be true iff ∃C j ∈ S such that q ∈ C j and q ′ ∈ C j

The selective deactivation of a cube can then be expressed by the following: q,q ′ ∈Q 0≤j<n (s q,j ∧ s q ′ ,j ) → sc q,q ′

(5)

q∈Q, i∈B I δ(q,i) is defined c∈CS(λ(q,i)) a c,q,i (6) q,q ′ ∈Q, i∈B I δ(q,i) is defined δ(q ′ ,i) is defined c∈CS(λ(q,i)) c ′ ∈CS(λ(q ′ ,i)) c∩c ′ =∅ (a c,q,i ∧ a c ′ ,q ′ ,i ) → sc q,q ′ . (7)
Constraint [START_REF] Duret-Lutz | Spot 2.0 -a framework for LTL and ω-automata manipulation[END_REF] ensures that sc q,q ′ is true if there exists a class containing both q and q ′ , in accordance with the expected definition.

Constraint [START_REF] Etessami | Optimizing Büchi automata[END_REF] guarantees that at least one of the cubes in the output λ(q, i) is active, causing the restricted output to be nonempty. Constraint [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF] expresses selective deactivation and only needs to be added for a given q, q ′ ∈ Q and i ∈ B I if δ(q, i) and δ(q ′ , i) are properly defined. This formula guarantees that if there exists a class to which q and q ′ belong to (i.e., sc q,q ′ is true) but there also exist disjoint cubes in the partition of their respective outputs, then we deactivate at least one of these: only cubes that intersect can be both activated. Thus, this constraint guarantees the nonempty output condition.

Since encoding an output set requires a number of cubes exponential in |O|, the above encoding uses O(|Q|(2

|I|+|O| + |Q|) + n 2 • 2 |I| ) variables as well as O(Q 2 (n+2 2|O| )+n 2 •2 |I| +|δ|(2 |O| +n 2 ))
clauses. We use additional optimizations to limit the number of clauses, and make the algorithm more practical despite its frightening theoretical worst case. In particular the CEGAR approach of Section 3.3 strives to avoid introducing constraints ( 5)-( 7).

Adjustment of Prior Optimizations

Constructing the SAT problem iteratively starting from n = 1 would be grossly inefficient. We can instead notice that two states that are not variations of each other can never be in the same class. Thus, assuming we can find k states that are not pairwise variations of one another, we can infer that we need at least as many classes as there are states in this set, providing a lower bound for n. This idea was first introduced in [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF]; however, performing a more careful inspection of the constraints with respect to this "partial solution" allows us to reduce the number of constraints and literals needed.

The nonemptiness condition involves the creation of many literals and clauses and necessitates an expensive preprocessing step to decompose the arbitrary output sets returned by output function (λ :

Q, B I → 2 B O \ {∅}) into disjunctions of cubes (λ : Q, B I → 2 K O \ {∅}).
We avoid adding unnecessary nonempty output clauses in a counter-example guided fashion. Violation of these conditions can easily be detected before constructing the minimized machine. If detected, a small set of these constraints is added to SAT problem excluding this particular violation. In many cases, this optimization greatly reduces the number of literals and constraints needed, to the extent we can often avoid their use altogether.

From now on, we consider an IGMM with N states Q = {q 0 , q 1 , . . . , q N -1 }.

Variation matrix. We first need to determine which states are not pairwise variations of one another in order to extract a partial solution and perform simplifications on the constraints. We will compute a square matrix of size N ×N called mat such that mat[k][ℓ] = 1 if and only if q k ̸ ≈ q ℓ in the following fashion:

1. Initialize all entries of mat to 0.

Iterate over all pairs

(k, ℓ) with 0 ≤ k < ℓ < N . If the entry mat[k][ℓ] is 0, check if ∃i ∈ B I such that λ(q k , i) ∩ λ(q l , i) = ∅. If it exists, mat[k][ℓ] ← 1.
3. For all pairs (k, ℓ) whose associated value mat[k][ℓ] changed from 0 to 1, set all existing predecessor pairs (m, n) with m < n under the same input to 1 as well, that is, ∃i ∈ B I such that δ(q m , i) = q k and δ(q n , n) = q l . Note that we may need to propagate these changes to the predecessors of (m, n).

As "being a variation of" is a symmetric, reflexive relation, we only compute the elements above the main diagonal of the matrix. The intuition behind this algorithm is that two states q and q ′ are not variations of one another if either:

-There exists an input symbol for which the output sets are disjoint.

-There exists a pair of states which are not variations of one another and that can be reached from q and q ′ under the same input sequence.

The complexity of this algorithm is O(|Q| 2 •2 |I| ) if we assume that the disjointness of the output sets can be checked in constant time; see [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF]. This assumption is not correct in general: testing disjointness for cubes has a complexity linear in the number of input propositions. On the other hand, testing disjointness for generalized Mealy machines that use arbitrary sets of valuations has a complexity exponential in the number of input propositions. This increased complexity is however counterbalanced by the succinctness the use of arbitrary sets allows.

As an example, given 2m output propositions o 0 , . . . , o 2m-1 , consider the set of output valuations expressed as a disjunction of cubes 0≤k<m o 2k o 2k+1 ∨ o 2k o 2k+1 . Exponentially many disjoint cubes are needed to represent this set. Thus, a non-deterministic Mealy machine labeled by output cubes will incur an exponential number of computations performed in linear time, whereas a generalized Mealy machine will only perform a single test with exponential runtime.

Computing a partial solution. The partial solution corresponds to a set of states such that none of them is a variation of any other state in the set. Thus, none of these states can belong to the same (variation) class. The size of this set is therefore a lower bound for the number of states in the minimal machine.

Finding the largest partial solution is an NP-hard problem; we therefore use the greedy heuristic described in [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF]. For each state q of M , we count the number of states q ′ such that q is not a variation of q ′ ; call this number nvc q . We then successively add to the partial solution the states that have the highest nvc q but are not variations of any state already inserted.

CEGAR approach to ensure the nonempty output condition. Assuming a solution satisfying the cover and closure constraints has already been found, we then need to check if said solution satisfies the nonempty output condition. If this is indeed the case, we can then construct and return a minimal machine.

Algorithm 1: SAT-based minimization

If the condition is not satisfied, we look for one or more combinations of classes and input symbols such that Succ(C k , i) = ∅. We add for the states in C k and the input symbol i the constraints described in Section 3.2, and for these states and input symbols only. Then we check if the problem is still satisfiable.

If it is not, then we need to increase the number of classes to find a valid solution. If it is, the solution either respects condition [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF] and we can return a minimal machine, or it does not and the process of selectively adding constraints is repeated. Either way, this counter-example guided abstraction refinement (CE-GAR) scheme ensures termination, as the problem is either shown to be unsatisfiable or solved through iterative exclusion of all violations of condition [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF].

Algorithm

The optimizations described previously yield Algorithm 1.

Further optimizations and comparison to MeMin. The proposed algorithm relies on the general approach outline in [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF], as well as the SAT encoding for the cover and closure conditions. We find a partial solution by using a similar heuristic and adapt some optimizations found in their source code, which are neither detailed in their paper nor here due to a lack of space.

The main difference lies in the increased expressiveness of the input and output symbols that causes some significant changes. In particular, we added the nonemptiness condition to guarantee correctness, as well as a CEGAR-based implementation to maintain performance. Other improvements mainly stem from a better usage of the partial solution.

For instance, each state q of the partial solution is associated to "its own" class C j . Since the matching literal s q,j is trivially true, it can be omitted by replacing all its occurrences by true. States belonging to the partial solution have other peculiarities that can be leveraged to reduce the number of possible successor classes, further reducing the amount of literals and clauses needed.

We therefore require fewer literals and clauses, trading a more complex construction of the SAT problem for a reduced memory footprint. The impact of these improvements is detailed in Section 5.

The Mealy machine described by [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF] come in two flavors: One with an explicit initial state and a second one where all states are considered to be possible initial states. While our approach does explicit an initial state, it does not further influence the resulting minimal machine when all original states are reachable.

Bisimulation with Output Assignment

We introduce in this section another approach tailored to our primary use case, that is, efficient reduction of control strategies in the context of reactive synthesis. This technique, based on the ⊑ specialization relation, yields non-minimal but "relatively small" machines at significantly reduced runtimes.

Given two states q and q ′ such that q ′ ⊑ q, one idea is to restrict the possible outputs of q to match those of q ′ . Concretely, for all inputs i ∈ B I , we restrict λ(q, i) to its subset λ(q ′ , i); q and q ′ thus become bisimilar, allowing us to merge them. In practice, rather than restricting the output first then reducing bisimilar states to their quotient, we instead directly build a machine that is minimal with respect to ⊑ where all transitions going to q are redirected to q ′ . Note that if two states q and q ′ are bisimilar, then necessarily q ′ ⊑ q and q ⊑ q ′ : therefore, both states will be merged by our approach. As a consequence, the resulting machine is always smaller than the bisimulation quotient of the original machine (as shown in Section 5).

Reducing Machines with ⊑

Our algorithm builds upon the following theorem: Theorem 2. Let M = (I, O, Q, q init , δ, λ) be an IGMM, and r : Q → Q be a mapping satisfying r(q) ⊑ q. Define M ′ = (I, O, Q ′ , q ′ init , δ ′ , λ) as an IGMM where Q ′ = r (Q), q ′ init = r(q init ) and δ ′ (q, i) = r(δ(q, i)) for all states q and input i. Then M ′ is a specialization of M .

Intuitively, if a state q is remapped to a state q ′ ⊑ q, then the set of words w that can be output for an input i is simply reduced to a subset of the original output. The smaller the image r(Q), the more significant the reduction performed on the machine. Thus, to find a suitable function r, we map each state q to one of the minimal elements of the ⊑ preorder, also called the representative states. q r(q) Definition 8 (Specialization graph). A specialization graph of an IGMM M = (I, O, Q, q init , δ, λ) is the condensation graph of the directed graph representing the relation ⊑: the vertices of the specialization graph are sets that form a partition of Q such that two states q and q ′ belong to the same vertex if q ⊑ q ′ and q ′ ⊑ q; there is an edge {q 1 , q 2 , ...} -→ {q ′ 1 , q ′ 2 , ...} if and only if q ′ i ⊑ q j for some (or equivalently all) i, j. Note that this graph is necessarily acyclic. Fig. 3 shows the specialization graph associated to the machine of Fig. 2a. Definition 9 (Representative of a state). Given two states q and q ′ of an IGMM, q ′ is a representative of q if, in the specialization graph of M , q ′ belongs to a leaf that can be reached from the vertex containing q. In other words, q ′ is a representative of q if q ′ ⊑ q and q ′ is a minimal element of the ⊑ preorder.

0 → 0 1 → 1 2 → 2 3 → 1 4 → 1 5 → 5 6 → 1
Note that any state has at least one representative. In Fig. 3 we see that 0 represents 0, 3, 4, and 6. States 3, 4, and 6 can be represented by 0 or 1.

By picking one state in each leaf, we obtain a set of representative states that cover all states of the IGMM. We then apply Theorem 2 to a function r that maps each state to its representative in this cover. In Fig. 3, all leaves are singletons, so the set {0, 1, 2, 5} contains representatives for all states. Applying Th. 2 using r from Fig. 4 yields the machine shown in Fig. 5. Note that while this machine is smaller than the original, it is still bigger than the minimal machine of Fig. 2b, as this approach does not appraise the variation relation ≈.

Implementing ⊑

We now introduce an effective decision procedure for q ⊑ q ′ . Note that ⊑ can be defined recursively like a simulation relation. Assuming, without loss of generality, that the IGMM is input-complete, ⊑ is the coarsest relation satisfying:

q ′ ⊑ q =⇒ ∀i ∈ B I , λ(q ′ , i) ⊆ λ(q, i) δ(q ′ , i) ⊑ δ(q, i)
As a consequence, ⊑ can be decided using any technique that is suitable for computing simulation relations [START_REF] Henzinger | Computing simulations on finite and infinite graphs[END_REF][START_REF] Etessami | Optimizing Büchi automata[END_REF]. Our implementation relies on a straightforward adaptation of the technique of signatures described by Babiak et al. [START_REF] Babiak | Compositional approach to suspension and other improvements to LTL translation[END_REF]Sec. 4.2]: for each state q, we compute its signature sig(q), that is, a Boolean formula (represented as a BDD) encoding the outgoing transitions of that state such that sig(q) ⇒ sig(q ′ ) if and only if q ⊑ q ′ . Using these signatures, it becomes easy to build the specialization graph and derive a remapping function r. Note that, even if ⊑ can be computed like a simulation, we do not use it to build a bisimulation quotient. The remapping applied in Th. 2 does not correspond to the quotient of M by the equivalence relation induced by ⊑.

Benchmarks

The two approaches described in Sections 3 and 4 have been implemented within Spot 2.10 [5], a toolbox for ω-automata manipulation, and used in our Synt-Comp'21 submission [START_REF] Renkin | Improvements to ltlsynt[END_REF]. The following benchmarks are based on a development version of Spot 1 that features efficient variation checks (verifying whether q ≈ q ′ ) thanks to an improved representation of cubes.

We benchmark the two proposed approaches against MeMin, against a simple bisimulation-based approach, and against one another. The MeMin tool has already been shown [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF] to be superior to existing tools like Bica [START_REF] Pena | A new algorithm for exact reduction of incompletely specified finite state machines[END_REF], Stamina [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF], and Cosme [START_REF] Alberto | Iterative minimization of partial finite state machines[END_REF]; we are not aware of more recent contenders. For this reason, we only compare our approaches to MeMin.

In a similar manner to Abel and Reineke [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF], we use the ISM benchmarks [START_REF] Kam | A fully implicit algorithm for exact state minimization[END_REF] as well as the MCNC benchmark suite [START_REF] Yang | Logic synthesis and optimization benchmarks user guide: version 3[END_REF]. These benchmarks share a severe drawback: they only feature very small instances. MeMin is able to solve any of these instances in less than a second. We therefore extend the set of benchmarks with our main use-cases: Mealy machines corresponding to control strategies obtained from SYNTCOMP LTL specifications [START_REF] Jacobs | The 5th reactive synthesis competition-syntcomp[END_REF].

As mentioned in Section 2, MeMin processes Mealy machines, encoded using the the KISS2 input format [START_REF] Yang | Logic synthesis and optimization benchmarks user guide: version 3[END_REF], whose output can be chosen from a cube. However, the IGMM formalism we promote allows an arbitrary set of output valuations instead. This is particularly relevant for the SYNTCOMP benchmark, as the LTL specifications from which the sample's Mealy machines are derived often fail to fully specify the output. In order to [START_REF] Abel | MeMin: SAT-based exact minimization of incompletely specified Mealy machines[END_REF] show the benefits of the generalized formalism while (2) still allowing comparisons with MeMin, we prepared two versions of each SYNTCOMP input: the "full" version features arbitrary sets of output valuations that cannot be processed by MeMin, while in the "cube" version said sets have been replaced by the first cube produced by the Minato algorithm [START_REF] Minato | Fast generation of irredundant sum-of-products forms from binary decision diagrams[END_REF] on the original output set. The ACM and MCNC benchmarks, on the other hand, already use a single output cube in the first place.

Figure 6 displays a log-log plot comparing our different methods to MeMin, using only the "cube" instances. 2 . The label "bisim. w/ o.a." refers to the approach outlined in Section 4, "bisim.", to a simple bisimulation quotient, and "SAT ", to the approach of Section 3. Points on the black diagonal stand for cases 1 For instructions to reproduce, see https://www.lrde.epita.fr/~philipp/forte22/ 2 A 30 minute timeout was enforced for all instances. The benchmarks were run on an Asus G14 with a Ryzen 4800HS CPU with 16GB of RAM and no swap where MeMin and the method being tested had equal runtime; cases above this line favor MeMin, while cases below favor the aforementioned methods. Points on the dotted line at the edges of the figure represent timeouts. Only MeMin fails this way, on 10 instances. Figure 7 compares the maximal number of literals and clauses used to perform the SAT-based minimization by MeMin or by our implementation. These two figures only describe "cube" instances, as MeMin needs to be able to process the sample machines.

To study the benefits of our IGMM model's generic outputs, Table 1 compares the relative reduction ratios achieved by the various methods w.r.t. other methods as well as the original and minimal size of the sample machines. We use the "full" inputs everywhere with the exception of MeMin.

Interpretation. Reduction via bisimulation solves all instances and has been proven to be by far the fastest method (Fig. 6), but also the coarsest, with a mere 0.94 reduction ratio (Tab.1). Bisimulation with output assignment achieves a better reduction ratio of 0.83, very close to MeMin's 0.81.

In most cases, the proposed SAT-based approaches remain significantly slower than approaches based on bisimulation (Fig. 6). Our SAT-based algorithm is sometimes slower than MeMin's, as the model's increased expressiveness requires a more complex method. However, improving the use of partial solutions and increasing the expressiveness of the input symbols significantly reduce the size of the encoding of the intermediate SAT problems featured in our method (Fig. 7), hence, achieve a lower memory footprint. Points on the horizontal line at the bottom of Figure 7 correspond to instances that have already been proven minimal, since the partial solution is equal to the entire set of states: in these cases, no further reduction is required. 1: Statistics about our three reduction algorithms. The leftmost pane counts the number of instances where algorithm (y) yields a smaller result than algorithm (x); as an example, bisimulation with output assignment (2) outperforms standard bisimulation (1) in cases. The middle pane presents mean (avg.) and median (md.) size ratios relative to the original size and the minimal size of the sample machines. The rightmost pane presents similar statistics while ignoring all instances that were already minimal in the first place.

Finally, the increased expressiveness of our model results in significantly smaller minimal machines, as shown by the 1.27 reduction ratio of MeMin's cube-based machines compared to the minimisation of generic IGMMs derived from the same specification. There are also 74 cases where this superior expressiveness allows the bisimulation with output assignment to beat MeMin.

Conclusion

We introduced a generalized model for incompletely specified Mealy machines, whose output is an arbitrary choice between multiple possible valuations. We have presented two reduction techniques on this model, and compared them against the state-of-the-art minimization tool MeMin (where the output choices are restricted to a cube).

The first technique is a SAT-based approach inspired by MeMin [1] that yields a minimal machine. Thanks to this generalized model and an improved use of the partial solution, we use substantially fewer clauses and literals.

The second technique yields a reduced yet not necessarily minimal machine by relying on the notion of state specialization. Compared to the SAT-based approach, this technique offers a good compromise between the time spent performing the reduction, and the actual state-space reduction, especially for the cases derived from SYNTCOMP from which our initial motivation originated.

Both techniques are implemented in Spot 2.10. They have been used in our entry to the 2021 Synthesis Competition [START_REF] Renkin | Improvements to ltlsynt[END_REF]. Spot comes with Python bindings that make it possible to experiment with these techniques and compare their respective effects 3 . This appendix contains supplementary material that we could not fit into the main text. It was part of our submission, but has not been explicitly reviewed.

A Additional Data from our Benchmark

Figures 8a-10a plot the total runtime per instance of the three different benchmark suites (SYNTCOMP, MCNC, ISM) and provide a deeper insight into the results.

Even on "cube" instances, the two bisimulation-based (without and with output assignment) approaches outperform both MeMin and the proposed SAT approach of Section 3 at the cost of sometimes producing larger non-minimal machines. The detailed improvements are shown in Figures 8b-10b. The y axis represents here the ratio size min , where min is the minimal size of Mealy machines computed on the "cube" instances (not the "full" ones).

As shown by their size ratio, SYNTCOMP instances (Fig. 8b) significantly benefit from our bisimulation with output assignment approach compared to the other benchmark suites, even when the sample machines are restricted to "cube" instances, Tables 2-3 complete Table 1 by displaying the corresponding runtime. Since the average runtime is heavily biased towards the largest instances, we also provide a geometric mean and a median runtime.

Finally Figure 12 shows sizes ratio of the reduction with the full instances, for all combined benchmarks. And Figure 11 shows how many instances each technique can solve under a given time.

Fig. 1 :

 1 Fig. 1: Minimizing a Mealy machine that models a reactive controller

Fig. 3 :

 3 Fig. 3: Specialization graph of the IGMM of Fig. 2a

Fig. 4 :

 4 Fig. 4: Chosen representative mapping.

Fig. 5 :

 5 Fig.5: IGMM obtained by reducing that of Fig.2a

Fig. 6 :

 6 Fig. 6: Log-log plot of runtimes. The legend a/b stands for a cases above diagonal, and b below.

Fig. 7 :

 7 Fig. 7: Comparison of the number of literals and clauses in the encodings.

  / o.a.(b) Size ratios for instances derived from SYNTCOMP.

Fig. 8 :

 8 Fig. 8: Details for SYNTCOMP instances

  / o.a. (b) Size ratios for MCNC instances.

Fig. 9 :

 9 Fig. 9: Details for MCNC instances

  / o.a. (b) Size ratios for ISM instances.

Fig. 10 :

 10 Fig. 10: Details for ISM instances

Fig. 11 :

 11 Fig. 11: Size ratios of the resulting machines of the full instances of all combined benchmarks.

Fig. 12 :

 12 Fig. 12: Cactus plot of the different reduction techniques.

Table 2 :

 2 Arithmetic means (a.mean), geometric means (g.mean), and medians of the runtimes (in ms) of the four approaches on the set of 634 cases that MeMin was able to minimize.

		a.mean g.mean median
	bisim.	1.3 0.16	0.14
	bisim. w/ o.a. 21.9 0.23	0.17
	SAT	347.7 0.39	0.18
	MeMin	239.6 0.56	0.28
		a.mean g.mean median
	bisim.	1.1 0.21	0.18
	bisim. w/ o.a. 11.6 0.32	0.21
	SAT	602.5 0.73	0.28
	MeMin	375.8 0.83	0.37

Table 3 :

 3 Arithmetic means (a.mean), geometric means (g.mean), and medians of the runtimes (in ms) of the four approaches on the set of 314 non-minimal cases that MeMin was able to minimize.

See: https://spot.lrde.epita.fr/ipynb/synthesis.html.