Ludovic Coupaye

What's the Matter with Technology?

"What's the Matter with Technology? Long (and Short) Yams Materialisation and Technology in Nyamikum village, Maprik district, East Papua New Guinea." (9074 words)

Within the recent re-emergence of material culture and materiality within the field of anthropology, the very process of making things ("that make people" as rightly pointed out by Miller 2005: 5) -in other words, "technology"occupies a revealing position. As rightly outlined by the authors of the introduction to this volume, Hocart's statement on canoe-making [START_REF] Hocart | The Canoe and the Bonito in Eddystone Island[END_REF] indeed seems to echo functionalist and reductionnist views on the place material culture has occupied in subsequent anthropological fields of enquiry. Even more, I would argue, it also directly evokes the reluctance that anthropologists have since developed regarding the study of technology, notably in Anglo-Saxon literature.

In the collective attempt from participants to this volume to address materialisation as a process, it is interesting to note how 'technology' and techniques are pervasive to most examples: Guo on Solomon island shell-money making, Veys in the ways in which barkcloath and mats are imbued of feminine potency, Geismar in the very process of making photographs or Bonshek in the importance given to the loss of technical knowledge in Santa-Cruz, all mention at some stage of their discussions how the making of things impart them with sets of values, and properties. To complement their demonstrations, my own contribution

The Australian Journal of Anthropology Ludovic Coupaye D r a f t will be focussing less on artefacts themselves than on technical systems that materialise them. 1 "Technology", "labour", and "modes of production" are familiar terms in anthropology. However, as a starting claim, I would advocate that both vocabulary and disciplinary boundaries have contributed to give specific connotations to these terms, and seem, indeed, to have cast them within specific forms of determinism: technology with matter, labour with value, and production with social conditions. In the current discussion on materiality of things (Miller 2005, Ingold 2007), I would situate the present argument on the ground that objects do not stem fully-armed and fully-clad with their properties before being injected in the different sets of transactions they are integrated into. Be it in exchange, consumption or phenomenal engagements with them, things are also perceived as the material -or at least perceptual -results of processes and agencies which origins might not be known or only imagined, but which are nevertheless, consciously or not, presumed. Among all these engagements and processes, that the contributors to this volume agreed to define as materialisation, I would stress technology as being, in way a foundational one.

In this paper, I will first explore this idea of materialisation, through a brief review of the elements from the study of technologies in anthropology, and then turn towards an example taken from the Abelam area, in Papua New Guinea. 2 1 This paper is based on a fieldwork done between January 2002 and September 2003, leading to PhD submitted at the Sainsbury Research Unit for the Arts of Africa, Oceania and the Americas [START_REF] Coupaye | Growing Artefacts, Displaying Relationships: Outlining the technical system of Long Yam cultivation and display among the Abelam of Nyamikum village (East Sepik Province, Papua New Guinea)[END_REF]. Fieldwork has been funded by both the AHRC, and the Robert Sainsbury Scholarship. Subsequent research has been conducted at the SRU, and is currently the subject of postdoctoral fellowship at the Research Department of the Musée du Quai Branly, Paris, leading to the publication of a book. I am deeply grateful for the help and support from Steven Hooper, Pierre Lemonnier, Philippe Peltier as well as Josh Bell, for our discussions, his friendship and encouragements. I am also thankful to the members of the 2007 ASAO session for their remarks and comments, notably Wonu Veys, Liz Bonsheck and Haidy Geismar. 2 I do not address here the question of historical and dynamic aspects of Nyamikum yam cultivation. Far from considering the yam cultivation system as a static elements, I have chosen to focus here on the current picture of this phenomenon. Although early ethnography [START_REF] Kaberry | The Abelam Tribe, Sepik District, New Guinea: A Preliminary report[END_REF] pays some attention to the relationships between yam ceremonies and now absent social featuresnotably initiations cycles, war, and ceremonial exchanges with neighbouring groups -my aim here is not to try to come back to a 'mere technical' approach of yam, synchronic and a-historical, but to illuminate some aspects of the contemporary relationality of yam growing as a sociotechnical system.

The Australian Journal of Anthropology

Ludovic Coupaye D r a f t

From body techniques to technical systems: Materialisation as technology. 3

The place given to techniques in anthropology is sometimes coined as one of the main distinctions between English and French anthropology (Chevalier 1998, Faure-Rouesnel 2001). Indeed, while Mauss's essay Body Techniques (1950a[1935]), and his Manuel d'ethnographie (1947) both pointed directly towards material culture and physical interactions between people and their surrounding world, Lemonnier notices (1992: 3, 5) that it is rather surprising that this aspect of his legacy in the English-speaking literature remained underexamined especially when compared to the treatment given to The Gift (Mauss 1950b(Mauss [1923(Mauss -1924]]; see also Bray 1997: 12-13). Most of developments in this trend come from the works of one of Mauss's student, the prehistorian [START_REF] Leroi-Gourhan | Le Geste et la Parole I: Techniques et Langage ; II La Mémoire et les Rythmes[END_REF][START_REF] Leroi-Gourhan | Le Geste et la Parole I: Techniques et Langage ; II La Mémoire et les Rythmes[END_REF][1943[START_REF] Leroi-Gourhan | Le Geste et la Parole I: Techniques et Langage ; II La Mémoire et les Rythmes[END_REF][START_REF] Leroi-Gourhan | Le Geste et la Parole I: Techniques et Langage ; II La Mémoire et les Rythmes[END_REF]; Ingold 1999), and of the agronomist and anthropologist André-George [START_REF] Haudricourt | Vergleichende Studien zu Kulthaüsern im Sepik-Gebiet und an der Nordküste[END_REF]. While the former, up until recently, was best known in the Anglo-Saxon world for writing on prehistoric art (Leroi-Gourhan 1967), the latter might have been read for his works on ethnobotany [START_REF] Haudricourt | Vergleichende Studien zu Kulthaüsern im Sepik-Gebiet und an der Nordküste[END_REF][START_REF] Miller | Material Culture and Mass-Consumption[END_REF]. However, the position of what Haudricourt called la technologie culturelle (1968, 'cultural technology') had some difficulties to find its proper place, even in France, in spite of the creation of the CNRS laboratory "Technique & Cultures", where it has known its most interesting developments, through the work of, notably, Robert Cresswell (see [START_REF] Cresswell | Prométhée ou Pandore? Propose de Technologie Culturelle[END_REF] and Pierre Lemonnier (1982Lemonnier ( , 1983Lemonnier ( , 1986Lemonnier ( , 1992)). A more complete history of the reasons for this distinction between French and English-speaking regions, as well as the resistance to integrate the study of technical systems within anthropology, still remains to be discussed, but elements can be found in writings on ethnography of techniques (Lemonnier 1992[START_REF] Bray | Technology and Gender: Fabrics of Power in Late Imperial China[END_REF][START_REF] Dobrès | Technology and Social Agency[END_REF], Schiller 2001).

In the English literature, the focus on technical systems has retained some attention through studies in archaeology and its ethnoarchaeological developments, such as in study of pottery or iron working (e.g. Van der Leeuw 1976, 1991;[START_REF] Edmonds | Description, Understanding and the Chaîne Opératoire[END_REF][START_REF] Rowlands | The magical production of iron in the Cameroon Grassfield[END_REF][START_REF] Gosselain | In Pots We Trust: The Processing of Clay and Symbols in Sub-Saharan Africa[END_REF][START_REF] Dobrès | Technology and Social Agency[END_REF][START_REF] Sillar | The Challenge of 'Technological Choice' For Materials Science Approaches in Archaeology[END_REF]. In contrast, anthropological studies come mostly from the French-speaking area (Creswell 1996, Lemonnier 1992[START_REF] Jamard | La Technologie Culturelle peut-elle se tromper? Entretien avec Robert Cresswell[END_REF], along with Warnier's recent focus on praxeology, in relation to the research group "Matière à Penser" -'matter to think' (Warnier 2002). However, Anglo-Saxon literature was not completely reluctant to analyse technology from an ethnographic point of view (e.g. Pfaffenberger 1988, 1992, Sillitoe 1998, 3 Regarding the definitions of the term "technology", Sigaut (1985) has rightly pointed out the how the term can be confusing. Lemonnier considers it embracing "all aspects of the process of action upon matter, whether it is scratching one's nose, planting sweet potatoes, or making jumbo jets" (Lemonnier 1992: 4). Lemonnier suggest to call 'technological' an action which must "involve at least some physical intervention which leads to a real transformation of matter, in terms of current scientific laws of the physical world" (Lemonnier 1992: 5). Pfaffenberger's definition (1992: 497): "Technique […] refers to the system of material resources, tools, operational sequences and skills, verbal and nonverbal knowledge, and specific modes of work coordination that come into play in the fabrication of material artefacts. Sociotechnical systems, in contrast refers to the "distinctive technological activity that stems from the linkage of techniques and material culture to the social coordination of labour. The proper and indispensable subjects of a social anthropology of technology, therefore, include all three: techniques, sociotechnical systems, and material culture." Sigaut (2002) restricts the use of technology for the science studying technical activities.

8/26/2009

The Australian Journal of Anthropology Ludovic Coupaye D r a f t [START_REF] Mackenzie | Androgynous Objects: String Bags and Gender in Central New Guinea[END_REF], especially in the U.S. where the inherently cultural aspects were perhaps easier to integrate in a discipline that still had connections with archaeology (see notably Lechtman and Merill 1977).

Concerning processes of materialisation, and for the purpose of this paper, three major interrelated aspects outlined by these studies have been selected. First, technology as being a black box in anthropological analysis; second its systemic nature; and third its sociogenic properties.

Just as material culture is understood to be humble and invisible in its contribution to social life (Miller 1987: 85-108), the social component of technology is inherently invisible (Pfaffenberger 1992: 500-502), a characteristic that could be held responsible for its exclusion from anthropological enquiries. Not only does this property explain how technology can be qualified as a "black box" (Lemonnier 1996), but it also outlines what Sillar, borrowing Karl Polanyi's statement about economy, calls the embeddedness of technology4 . This intimate relationship between technology and society has been notably highlighted by sociologists of scientific knowledge and STS (Science and Technology Studies; see Pfaffenberger 1992: 495-502, Latour 1993[START_REF] Cresswell | Prométhée ou Pandore? Propose de Technologie Culturelle[END_REF], who pointed out the "sociality of human technological activity" (Pfaffenberger 1992: 492, 493). This sociality is such that the relationship between technology and society has sometimes been qualified has a seamless web were "the social is indissolubly linked wit the technical and the economic" (Hughes 1990: 112;but see Cresswell in Jamard 1999: 551). "Sociotechnical systems are heterogeneous constructs that stem from the successful modification of social and non-social actors so that they work together harmoniously -that is, so that they resist dissociation" (Pfaffenberger 1992: 498;500). This "seamless web" also constitutes both one of the major characteristics and one of the major difficulties for those who study these "technical systems". Their systemic nature not only gears any technical activity to cultural and social phenomena, but also associates several domains of activities together (Lemonnier 1992: 7). Observing that planting yams amongst the Abelam is related to social organisation is no surprise; that it implies also other technical activities such as digging, rope-making, fence and house building can be more easily perceived; but that actual body techniques and technical operations on material involved can be geared to local -emicconceptions of labour, matters and substances, which in turn appears as embodied elements of the habitus, can be difficult to perceive unless one records the operational sequences, as some of the clues cannot be found in verbal explanations of the actors themselves.

This systemic aspect has two main consequences. First, interrelations between different operations, through similar materials or techniques that intervene at different moments of the process, associate several domains and artefacts together. Second, the obvious non-linearity of this system defies evolutionist or "technicist" determinism (Pfaffenberger 1992: 510-513, Coupaye 2004: 135-160). For instance, as recorded in the case of Maori [START_REF] Schaniel | New Technology and Cultural Change in Traditional Societies[END_REF], in spite of narratives about "primitive tools", and supposed technical improvement, the shovel has not replaced the digging-stick in Abelam context. In this example, not only do theoretical elements on consumption intervene -the symbolic identity

The Australian Journal of Anthropology Ludovic Coupaye D r a f t value that the digging stick materialises -but so does also phenomena that belong to the sociotechnical system of gardening: the organisation of a work party corresponds also to the embodied ways in which one does this type of activity (Coupaye 2004: 168-169;178-181; Appendix 1; see also [START_REF] Mcguigan | Wosera Abelam Digging Sticks: An Example of Art in Action[END_REF].

The third aspect follows logically from the two previous ones. What stems from studies of techniques and technology, is their profound sociogenic properties (Pfaffenberger 1992: 500). Mauss's premises offer is the possibility to perceive that sociality is also physically embodied through the performance of physical action in relation to the physical world, in a non-verbal form. While military drilling can be considered as the most obvious example (Mauss 1950a: 367, 384), daily engagements with the material world -itself created by sociotechnical interactions with the environment -also form physical occasions of re-enactment of social values. Rules of conduct, proper (or improper) ways of doing things, be it how one forms a queue in a supermarket, or how one makes a pot, or uses a digging stick to plant a garden in the foothills of the Prince Alexander Range, all can be evaluated and formalised in term of appropriateness, either from the angle of efficacy or even aesthetics of action (see [START_REF] Hardin | The Aesthetics of Action: Continuity and Change in a West African Town[END_REF]. These embodied, nonverbal body practices outlined by Mauss, and underlying Bourdieu's examination of "generative schemes of practical logic" (Bourdieu 1977: 114-124), are socialization processes, not only of the body of the actor, but of his/her person, as well as of the artefact manipulated and created. Materialisation is per se socialization.

Exploring these properties requires two observations which must be recognised as related in our interpretations. Firstly, things can be considered indeed as representatives of "congealed labour" (Damon 1980: 284-286), but as long as labour is understood not as an ontological reality, as the marxist vulgate tended to do (Bonte 1999: 16), but as a concretion or a materialisation process of cultural values. Secondly, things, through their silent presence, are always assumed to be the phenomenal indexes of the efficacy of such invisible processes, even when the process is unknown [START_REF] Gell | The Technology of Enchantment and the Enchantment of Technology[END_REF]. In this perspective, the sociogenic potential of things, released through engagements with them, comes from the properties -one could say the 'materiality' -they acquired through the processes which has led to their materialisation. "Things are parts of persons because they are creation of them" recalls Damon (1980: 284) in his discussion of kula valuables.

In the example of Nyamikum, an Abelam 5 village of Maprik district of the East Sepik Province, Papua New Guinea, I am not concerned with aspects of 'cultural technology' such as technical choices, technological styles, or relationships between tradition and innovation, (see [START_REF] Van Der Leeuw | Tradition and Innovation[END_REF]Papousek 1992, Lemonnier 1993;[START_REF] Sillar | The Challenge of 'Technological Choice' For Materials Science Approaches in Archaeology[END_REF]. I will rather focus on the production 5 Inasmuch as the very term "Abelam" is a construct coming from the encounters between actual people of the Maprik area, colonial administrator and ethnographers, people from Nyamikum do define their own language as "Abulës", and acknowledge the entire area as part of the same group, with further divisions such as Samukundi, within which they identify a disappearing local language called Arenyëm, distinct from the Maaje-Kundi (or Manje Kundi), quoted in the literature (cf. [START_REF] Mcguigan | Wosera Abelam Digging Sticks: An Example of Art in Action[END_REF], Losche 1999: 215). Similarly the description of such entity in the following section cannot be taken much farer than the imperfect reduction of several variations and blurring distinctions between neighbouring groups.

The Australian Journal of Anthropology

Ludovic Coupaye D r a f t of yam tubers, and on how the properties of these artefacts stem from the ways in which they are constructed through cultivation. I will describe some components of the technical system, as well as selected parts of the operational sequence that leads from the opening of the garden, to the consumption of yam. This will allow me to suggest how yams are composite objects, whose materiality is made of the intertwining of several layers of relationships, wrought together by a sociotechnical system, informing how this materiality affects their 'consumption'.

Setting

Located between the villages of Nyelikum [START_REF] Scaglion | Seasonal Patterns In Western Abelam Conflicts Managements Practices: the Ethnography of Law in the Maprik Sub-District Province, East-Sepik Province, Papua New Guinea[END_REF]) and Kimbangwa (Huber-Greub 1988), Nyamikum village's borders (disputed) follow roughly the course of one of the tributaries of the Mitpëm river ('Midpum' in older maps) on the west and the course of the Wutpam ('Odpum') river on the east. At the time of my stay, and based on the 2000 census, the population was slightly above 1100 people. The village is composed of about 25 to 30 hamlets, three of them regularly used as centres for fortnightly meetings organised by the Councillor and ceremonies such as the annual long yam display. Playing an important role in the cultivation process, social organisation can be broadly described as a patrilineal-clan based organisation with exogamic and virilocal rules of marriage. Lineages are components of some twenty-five këm, a term alternatively used as 'clan' and 'place'6 , who co-operate in operations such as the cleaning of the footpaths, the planting of gardens, and the preparation of ceremonies.

Each of these këm has a special relationship with a whole list of totemic species -such as birds, called jaabë, but also trees, insects and leaves (Forge 1966: 29). These ties also relate këm with specific spirits, notably the n Gwaal n du, the clan's mythical ancestor, as well as with potentially dangerous spirits dwelling in specific places in the surrounding bush and forests, such as the waalë living in water holes. Both ancestors and spirits, especially because of their material anchoring in the land belonging to their clan, are said to actively participate in the growth of food, tying together landownership, personhood, spiritual powers and cosmology [START_REF] Huber-Greub | Kokospalmenmenschen: Boden und Alltag und ihre Bedeutung im Selbstverständnis der Abelam von Kimbangwa (East Sepik Province, Papua New Guinea)[END_REF], 1990). Also fuelling the dynamics of food production and exchange, the entire village is divided into ceremonial moieties that cross-cut through the organisation in këm. These two moieties, (ara), are officially engaged in competitive exchanges involving mainly yams of the long variety, and confront each man with his ceremonial partner (saabëra) in the other moiety (cf. notably Losche 1982: 80-85). This dualist system, present in every village of the Abelam area, is also organised to form a web that ties Nyamikum to villages as far as Apangai, in the West and Kalabu in the East (Forge 1970: 273-274). This partnership, which used

The Australian Journal of Anthropology Ludovic Coupaye D r a f t to be the underlying principle organising the initiations, is often compared locally to two football teams engaged in a game, and reflects the nature of political alliances. Intra-village ceremonial exchanges are based more on friendly competition, saabëra actually having a joking and motivating relationship with one another. Inter-village ceremonial exchanges were considered to be more aggressive, with the possible outcome of brawls or even feuds (Forge 1990: 162). This dualistic system is presented by Nyamikum people themselves as an integrated part of what growing food is about, and an individual without ceremonial partners would present himself as being "alone" -without challenge or support, both said to be necessary to the production of food in particular, and excellence in general.

Nyamikum is thus included within wider networks of relationships that connect it to other villages, both in and beyond the Abelam-speaking area, depending on the geopolitical map of allies and enemies. These networks relate ceremonial practices such as initiations, but also secret networks of connections between cultivators for material and non-material support, notably through the relation with sacred stones, owned and controlled by each këm. Linking together all villages, through kinship, friendship and moiety affiliations, they serve as the conduits for the circulation of cultivars, techniques, things, knowledge and 'magical' substances [START_REF] Forge | Paint: A Magical Substance[END_REF]) on which the success of yam cultivation is said to depend [START_REF] Lea | Abelam land and sustenance horticulture in an area of high population density, Maprik[END_REF], Forge 1966[START_REF] Losche | Male and female in Abelam Society[END_REF][START_REF] Huber-Greub | Kokospalmenmenschen: Boden und Alltag und ihre Bedeutung im Selbstverständnis der Abelam von Kimbangwa (East Sepik Province, Papua New Guinea)[END_REF][START_REF] Coupaye | Growing Artefacts, Displaying Relationships: Outlining the technical system of Long Yam cultivation and display among the Abelam of Nyamikum village (East Sepik Province, Papua New Guinea)[END_REF]). Other 'components', which I will briefly outline in the following description, include cultivators' bodily substances and magical support from land through the co-operation and support of the series of totemic spirits, who are able to recognise the legitimate owner of the land, as well as the quality of social relationships between genders, kin, moieties and other villagers.

The Australian Journal of Anthropology

Ludovic Coupaye D r a f t Long Yam Cultivation as a materialisation process

In spite of the increasing presence of a capitalism economy in the area, through a combination of cash earning activities such as cash-crop growing, 7 access to store food such as (like elsewhere in Papua New Guinea) rice, cannedmeat and canned-fish, and chinese noodles, and a better road system, food production in Nyamikum is mostly based on shifting cultivation, 8 notably of yams. 9 Two main species of yams are cultivated: short ones, Dioscorea esculenta ('mami' in Tok Pisin; ka in Abelam) form the main diet; and long ones, Dioscorea alata ('yam' in Tok Pisin; waapi in Abelam) usually grown by men for what is generally described as ceremonial purpose. In particular, long yams waapi have been the most documented, due the spectacular annual ceremonies 10 , where gigantic tubers are decorated, and displayed, before being exchanged between ceremonial partners [START_REF] Kaberry | The Abelam Tribe, Sepik District, New Guinea: A Preliminary report[END_REF]: 355-356, Tuzin 1972, 1995;Huber-Greub 1988: 347;90: 274;[START_REF] Coupaye | Growing Artefacts, Displaying Relationships: Outlining the technical system of Long Yam cultivation and display among the Abelam of Nyamikum village (East Sepik Province, Papua New Guinea)[END_REF]Coupaye , 2007a).

An inventory in the village of Nyamikum gives a list of approximately 40 cultivars of D. esculenta, and 20 of D. alata (Coupaye 2004: 94-97). Both types of yams gardening are perceived as both cosmologically and technically linked. Long yams, are said to be the sine qua non condition for the success of short yam gardening: the harvest of long yams is first to come and the activity of waapi cultivation is what 'opens the road to all food'. This causal association not only forms the underlying justification of the cultivation of both species, in parallel, but also invites us to understand the materiality of ka and waapi in relation to one another, and to approach their cultivation as a whole.

Turning to 'technographic' aspects (Sigaut 2002: 425), the basic sequence of operations of shifting cultivation can be summarized as follow.

(1) Opening of the garden → (2) Clearing → (3) Planting → (4) Tending → (5) Cropping → (6) Fallowing 11

This simple succession of operations can be decomposed in several techniques, each of which combines matters (earth, wood, water, bodies, etc.), energies (the forces which moves objects and transform matter), objects (tools, artefacts, 'means of work'), gestures (prodding, splitting, hitting, flattening, etc.) and knowledge (Lemonnier 1992: 5-9). 12 Regarding short yam gardens, steps 2 to 7 These include notably coffee, cocoa and recently vanilla. In March-April 2000, the hurricane Hudah destroyed the vanilla gardens of Madagascar, the world's primary producer. Vanilla quickly spread over Papua New Guinea, notably in the Sepik. At the time of my departure, in September 2003, one kilogram of dried vanilla beans was sold between Kina 600 and K800 (then roughly equivalent to ₤120 to ₤160). 8 For other studies of shifting cultivation, as a case of indigenous techniques, and their relations with magic, ritual, environment, cosmology, food production, or time, cf. inter alia Malinowski, Concklin 1961, Lea 1964; Rappaport 1968; Sigaut 1982; Juillérat 1986, 1999; Bonnemaison 1991; Sillitoe 1999; Gross 1998. 9 Taro (Colocasia esculenta), Aibika (Hibiscus (Abelmoschus) manihot) along with sago (Metroxylon spp.) are also an important part of the diet, however, Nyamikum people describe yams as being the most important crop(See [START_REF] Lea | Abelam land and sustenance horticulture in an area of high population density, Maprik[END_REF][START_REF] Coupaye | Growing Artefacts, Displaying Relationships: Outlining the technical system of Long Yam cultivation and display among the Abelam of Nyamikum village (East Sepik Province, Papua New Guinea)[END_REF] 10 According to Nyamikum gardeners, short yams were also the subjects of a display ceremony set after the long yams one. However, no ceremony of the sort has been performed during the time of my own stay. 11 Compare with Concklin 1961: 29, figure 1. 12 See Coupaye 2004: 143-153, for a detail of these components within the yam production system, and a discussion of the systemic aspects. From a methodological point of view, let me

8/26/2009

The Australian Journal of Anthropology Ludovic Coupaye D r a f t 5 of the sequence are in fact repeated between 2 and four times before leaving the land going back to fallow for twenty years [START_REF] Lea | Abelam land and sustenance horticulture in an area of high population density, Maprik[END_REF]Allen1982, 1985[START_REF] Lory | Les Jardins Baruya[END_REF]. In contrast, waapi gardens are in general used only once as such and usually left to fallow.

The systemic nature of technical activities allows us to deploy the sequence and to show several layers of material activities (see also Kaberry 1941: 354;[START_REF] Lea | Abelam land and sustenance horticulture in an area of high population density, Maprik[END_REF]. The opening of the garden involves tools (axes and bush-knives), the use and mastering of fire, networks of social cooperation (the landowner with a party made of his kin and the people of his hamlet). Clearing will be made by men (heavy remains of trees) and women (cleaning smaller parts). Planting requires techniques such as carrying the yam setts (the full yams or cuts that will be used as "seeds"), digging the soil or placing and covering the sett in its mound. Regarding tending, in order to profit from both sun and water, yams vines (kutë) are usually staked or put on a trellis that elevates them above the level of the ground [START_REF] Johnston | Productivity of Lesser Yam (Dioscorea esculenta) in Papua New Guinea as influenced by sett weight and staking[END_REF]. Along with yams, several species are planted (and thus harvested) at different moments of the year, such as taro, bananas, tobacco, edible cane, beans or peanuts. Finally, gardening itself requires many other operations that might not be directly linked to the garden or the growing of crops. House-making, such as the storage house (ka n diga), or the garden house ( m baarë), and in the past, fence-building, are integral parts of the operations that people present as related to gardening. These in turn call for woodcutting (for timber), rope making (to tie the timber together, in combination with nails), sago-tending (to get the leaves for thatching), and so forth.

My description would however be incomplete if I did not include other elements usually considered as peripheral to most agronomic concerns (Coupaye 2004: 51-53), but which are viewed as essential to the entire process. Technical activities, defines Sigaut (2002: 424), are characterised from other activities, by the fact that "they are not simply material, they are intentionally material". This brings in the notion of efficacy, that was part of Mauss's definition of a technical gesture (1950a: 371), but also calls for the inclusion of elements generally dismissed from 'pure' technological or agronomical concerns, such as rites and magic, which, from an anthropological angle, have always been part of technical activities (see [START_REF] Hocart | The Canoe and the Bonito in Eddystone Island[END_REF][START_REF] Malinowski | Coral Gardens and their Magic: A Study of the Methods of Tilling the Soil and of Agricultural Rites in the Trobriand Islands[END_REF][START_REF] Malinowski | Coral Gardens and their Magic: A Study of the Methods of Tilling the Soil and of Agricultural Rites in the Trobriand Islands[END_REF]; [START_REF] Forge | Paint: A Magical Substance[END_REF]Gell 1988[START_REF] Gell | The Technology of Enchantment and the Enchantment of Technology[END_REF][START_REF] Rowlands | The magical production of iron in the Cameroon Grassfield[END_REF]. Not only are these elements locally perceived to be materially effective, but they also inform the type of causalities mobilised to constitute the final artefact, and the properties attributed to materials. Authors such as [START_REF] Forge | Paint: A Magical Substance[END_REF] or [START_REF] Malinowski | Coral Gardens and their Magic: A Study of the Methods of Tilling the Soil and of Agricultural Rites in the Trobriand Islands[END_REF][START_REF] Malinowski | Coral Gardens and their Magic: A Study of the Methods of Tilling the Soil and of Agricultural Rites in the Trobriand Islands[END_REF]) have outlined the role of substances or chants, but I wish to focus here on two main elements that are considered part of the growing process and integrated in the materiality of yams:

(1) gardeners and their body substances and qualities; (2), social behaviours requirements.

The yam growing process involves the circulation of substances, seen to be essential to its success. First, cultivators must submit themselves to specific emphasize that such simple definition of the components of a given technique, should not conceal the complexity of practical reality it encompasses, and that it should not be restrained to the elements relevant only from the angle of Eurocentric conceptions of "technology". This precision not only seems necessary to temper the etic nature of such descriptive method, but also to be able to make visible what are the constructing principles of the material result, in other words the materiality fabricated.

8/26/2009

The Australian Journal of Anthropology Ludovic Coupaye D r a f t prescriptions and proscriptions, in Nyamikum called yakët (TP: 'bilip', English: "belief" or in anthropological terms: taboos), which includes behavioural, alimentary, and physical requirements. Restriction from sexual intercourse is pointed out as the main proscription, to avoid the diffusion of the menstrual blood of the gardener's partner within his body. This blood is considered dangerous and inimical not only to the growth of things, but to many other activities such as war -before the Pax Australiana 13 -, painting, building, football, and such, that is any activity of which the success must be secured. While less performed today, penis bloodletting was considered as the only way to get rid of the nefarious substance contained in the menstrual blood. During my stay, some younger people, between 20 and 30, told me that this practice could be replaced by going to the Maprik medical centre to give blood.

Yakët is more a process intervening in than a factor of cultivation. Its contents depends on the këm and the individual, and is often seen as a sort of family recipe, combining recurrent elements. These are aimed to make the body 'light' (yëpwi, Coupaye 2004: 113-121), a quality said to make gestures and the spirit 'sharp' and efficient. In fact, yakët is aimed both at avoiding nefarious consequences, and at increasing the chances of success. The quality and nature of the yakët is said to have direct consequences on the cultivation of long yams, notably on the material result itself, especially the length and shape of the waapi. This was the result of the role, within the growing process, of tutelary spirits who would 'smell' the menstrual substance and withdraw their support from the gardener, rendering him unable to obtain a proper result, whatever his other qualities and skills were. In addition, the menstrual substance itself could directly affect the tubers, through contagion resulting from the gardener's touching the earth, the sett or the vines, or through the sweat resulting from labour falling on the ground, or on the yam mound. This would make the tubers shrivel and die, or at least remain small, and without taste. Finally, through the 'heaviness' ( n gumëk) of the body of the human actor, resulting from both the natural exhaustion following a sexual activity and from the effect of menstrual blood itself, the gardener would be weakened and feeble, making him prone to spiritual dangers, vulnerable to sorcery attacks, and fumbling in each technical action.

A second component fuelling the technical system is the body substance jëwaai -which must be comprehended in relation with the Yakët. Alternatively, 'blood', 'scent' and 'flesh', the jëwaai is a substance that forms the basis of an ability that can be compared to the English notion of a 'green thumb', but also influences the success of activities other than gardening, notably the performance of magic (kus). Three types of jëwaai, listed here from the best to the worse in terms of effects on crops, are inherited from either the mother's or the father's line: Bird, Pig, and Wallaby 14 . One's jëwaai could be tested by planting a banana tree and checking both the speed and the quality of its growth, but the main material result of one's jëwaai could be seen in the size of the yam tubers. Jëwaai 13 During the years following WWII, Australian administration set out to put an end to "tribal warfare" in PNG, notably in the Highlands, through a mixture of colonial power and development of economic structure. 14 This classification system was systematically considered to be equivalent to the "waitman " classification of blood. The rules of transmission of jëwaai from either the mother or the father did not seem to be governed by any specific reason other than luck. Like a fluid, mixing a good jëwaai with a bad one could either result in a medium one, or a good or a bad. In fact, the quality of somebody's jëwaai was ascertained post hoc, ergo proper hoc, through the test described below.

8/26/2009

The Australian Journal of Anthropology Ludovic Coupaye D r a f t is equally distributed in both men and women. In fact, certain gardeners considered that depending on the type of jëwaai, of the wife, and provided that she followed the same Yakët as her husband's, or was past menopause, she could assist her husband in tasks not directly related to long yams (such as weeding other crops in the long yams garden, making fire, etc.). As for the role of menstrual substance, both old women and young girls, because of the absence of menstruation are more commonly allowed in the garden. Certain gardeners consider that young girls (even more than young boys) can administrate the magical substances on waapi tubers, as they are the only people who are definitely not sexually active.

The jëwaai is usually constituent of both invisible and visible body fluids such as breath, smell, sweat, blood, saliva, and sperm, which explains its contagious properties. It both forms the signature of an individual, as land and bush spirits are able to recognise one's jëwaai -another means to affirm landownership, as these spirits are in control of an important part of the land's fertility -and the means to successfully perform activities related to the spiritual domains. Specific operations such as the making of magical substances or the utterance of chants and words, requires specific jëwaai, and people mention lineages specialised in spiritual or technical activities because of the exceptional qualities of their substance (Coupaye 2004: 121-126).

These two notions yakët and jëwaai, relate to local conceptions about bodily fitness, and how one can harness the energies required to processes essential to build one's -and per extension the këm's (clan) or even the village's -fame ('having a name'). But through behavioural requirements, it is the individual's sociality which is also integrated as a component of the production system. However the association of yam cultivation with social dynamics is not solely grounded on the necessity to avoid disputes and conflicts within and between communities (and in previous times, war with neighbours), nor is it based solely on seasonal patterns [START_REF] Scaglion | Seasonal Patterns In Western Abelam Conflicts Managements Practices: the Ethnography of Law in the Maprik Sub-District Province, East-Sepik Province, Papua New Guinea[END_REF][START_REF] Scaglion | Abelam Yam Beliefs and Sociorhythmicity: A Study in Chronoanthropology[END_REF].

During fortnightly meetings, organised by the Councillor, recommendations from the local government are transmitted, and internal conflicts, either territorial or domestic, are publicly mediated, these being pointed out as endangering the village's capacity to produce long yams, and consequently food. These public occasions also see the performance of rituals of peacemaking, unmasking of sorcery and payment of compensations, all accompanied by metaphorical discourses on the necessity to keep the peace within the community to avoid troubling the growth of the yams (Coupaye 2007b). Recruiting seemingly heterogeneous elements, such as vanilla, national elections, World Cup, waapi, God, n gwaals spirits, sorcery and Yakët, these metaphoric discourses (aa n jaku n di, or "veiled speech"), publicly performed, and worked out by the audience, are also said to be essential elements meant to heat the 'place' and accelerate the growth of yams.

Embodied sociality intervenes differently, according to the type of gardens. Ka gardens entail the cooperation of the entire hamlet, with possible affines and partners (with whom the garden is shared), for the planting is usually performed in one day, which is a fundamental step in the process. In contrast, waapi gardens are planted rather secretly, by the gardener, accompanied with few of his friends, also in a strict state of Yakët. The long yam gardens into which I

8/26/2009

The Australian Journal of Anthropology Ludovic Coupaye D r a f t was allowed, presented between five to eight waapi -of different cultivars, but always included a Maa m butap -all planted during a months' period. Harvest of ka is made by the household, and sometimes affines, while waapi are harvested by the same group of men who planted it.

Finally, the material aspects of harvested yams themselves also differ in terms of size, shape and constitution. This is a result not only of the different cultivars, but also of the techniques used to make them grow. Short yams are grown in holes that do not exceed 0.4 m. The full yam is used as sett, and is placed at the bottom of the hole, and recovered by finely hand-broken soil. A tuber is harvested after six to seven months and yields, depending on the cultivars, between three to six new tubers that vary between 0.005 to 0.025 m. diameter in size. As discussed, a planter's jëwaai also influences the size of the tubers. These variations in size are a calculated effect by the garden's owners, as people need tubers of different sizes for various purposes (to feed the pigs, to be re-planted, for daily food, or for festive occasions). Thus, the involvement of a work party of up to forty people is a way to mix the jëwaai of individuals within the garden, so that a wider range of tubers can be harvested. In contrast, waapi are planted in individual mound, and only a cut is used. The hole is dug before, reaching up to two metres, filled with finely cleaned and broken soil, on top of which a rounded mound of up to one metre high is made (Lea 1966, Coupaye 2004: 166-178). Once the mound is ready, the sett is placed on the top of the mound, and the new tuber is able to grow deeper through the softened soil. An average size of 1.8 to 2 m. is usually obtained, with an average weight of 45 to 50 kg. This technique can also be used to obtain ka tubers of up to one metre, called jaa m bi, that are also used for ceremonial occasions.

The shape, size and texture even more than the quantity of yams produced are thus seen as the materialisation of a combination of bodily, social, spiritual and moral qualities of their cultivators. However, the ethnographically famous long yams waapi are perhaps the main manifestations of such qualities. In fact, while both ka and waapi gardening imply precise behaviours and rituals, the cultivation of waapi requires the gardener to follow a precise and more arduous Yakët. This is combined with the fact that while in the ka garden, both men and women operate together, only men perform most of the technical operations in the waapi garden, and take care of the entire process. While all long yams cultivated within the waapi garden are submitted to the same requirements, they are especially applied when one wants to obtaining the 'head of food', the Maa m butap long yam cultivar, around which the main ceremony, Waapi Saaki ("the Lining Up of the Long Yams") is elaborated. Growing Maa m butap, and the Maa m butap itself, materialises the necessity to behave properly because, if men were to fail growing long yams, then food could not come out of other gardens, as people not in a Yakët state will most likely act foolishly, committing adultery, engaging in sorcery business or brawling unnecessarily.

Such judgments and comments indicate how the very technical process of cultivation is perceived as a socialisation process, but also how the yam is perceived as the result of the process itself. During a Waapi Saaki in June 2003, a man in his thirties was exhibiting a long yam he had himself cultivated, having been "fined" the year before by the influential men of the village for provoking a brawl during a long yam ceremony. During the public discourse he made, the man metaphorically referred to his waapi as his 'penalty', but also as the 'road' he had used to learn how to behave. The yam he was presenting today, decorated with feathers, flowers, shell, and mask, was the material index of him being, now, a "man", and not a child anymore.

The sociality of sequences

Turning finally to the performance of the process itself, local perceptions reveal features that confirm the inherent social component of food production, reaffirming, if needed, the validity of the notion of sociotechnical system (Figure 1). o Giving the substances to the Maabutap (on the head).

o Sënaba: when the yam vine starts to turn yellow or brown, 'fertilisers' are given to the tuber. Then, the tuber is really starting to grow.

o Kwaat Baalë ('Pit-Pig'). When leaves are drying. A hole is dug underneath the mound to check the growing point of the tuber. Depending on the gardener's evaluation, an extension of the waagu (hole) is made ('extension': sabakara). If the tuber has not reached the end of the waagu, the soil is removed (waagu jagët: 'emptying the hole'), and new soil is put: kulë taapu wëlikwe ('New 'bed' [using the name of the coconut sheath: taapu] placed'), made of top soil (makwalkëpma).

o Lëraa: one moon after the Kwaat baalë. Another hole is dug under the tëkët to check the size of the tuber. Depending on the evaluation, extension of the hole or addition fertilisers can be made. These two summary accounts in figure 1 illustrate the different levels of interlacements that contribute to the materialisation of yams.

Kulang's sequence of phases corresponds to the operations he himself performed during the 2001-2002 season and which allowed him to harvest a Maa m butap that was considered to be the best during the June 2002 Waapi Saaki. He focused on the different moments when one had to give the Maa m butap the two substances (cf. Forge 1962) essential to help their growth: a vegetal-based liquid called the gunyë n gi (lit. 'water-stinging') and another liquid, but sometimes only powder/mineral-based, kusbawu (lit. 'magic ash').

Gayinigi and Kitnyora's sequence is different and appears less detailed, even though coming from acknowledged Nëma n du (Big/Great Men). What is relevant here is that the different phases are less concerned with primarily material operations, and not only include different types of operations, but also cover different types of domains. Actually, the two Nëma n du's focus is on phases that deal with the negotiation aspects of the process: the account stresses interactions notably between and with the different villages' Nëma n du and or Kajatu n du of different villages -individuals whose identity is kept secret, wardens of secret stones that control the fertility of crops (Coupaye 2004: 128-133) -, and notably on secret negotiations with and between the stone-wardens and negotiations within the community to decide the type of ceremony to be held. One can also notice the stress on the importance of the 'cleaning of the place', both before the planting and after, and the importance of settling disputes and the avoidance of conflicts. When I asked, both appeared as two distinct moments, marking the two thresholds of the year, each one marked by the killing of pigs. However, during my stay, because of the scarcity of pigs, I have not been able to observe such a ceremony. Pig meat was reserved for the Waapi Saaki itself and this gift of meat seemed to act for both phases of 'cleaning'.

What emanates from these accounts is that long yam growing constitutes both a mythic-technical frame for food production, while simultaneously constituting a technical synecdoche for gardening. Growing waapi and displaying them is more than about the phallic cult it was first compared to [START_REF] Kaberry | The Abelam Tribe, Sepik District, New Guinea: A Preliminary report[END_REF][START_REF] Kaberry | The Abelam Tribe, Sepik District, New Guinea: A Preliminary report[END_REF](Kaberry -1942;;[START_REF] Tuzin | Yam symbolism in the Sepik : an Interpretation Account[END_REF]Tuzin , 1995)), while simultaneously evoking spirits and initiates (Hauser-Schäublin 1995: 41-43, Coupaye 2007a). It corresponds to the intricate perception of what yam production is about, and how it weaves together social relationships with the performance of material activities. To materialise a yam requires intertwining substances, material actions, social interactions and symbolic negotiations. Nyamikum gardeners's perceptions and interpretations of the process regarding the factors essential for the success of the process force us to consider that growing of long yams implies a wider system which calls upon and makes manifest types of relationalities in forms of interlacements and networks of what is usually considered as material and non-material aspects. It also re-adjusts our conception of "technical systems" as only functional and practical aspects of human agency intended to have a physical result on reality. However, questioning what type of reality we are dealing with here allows us in fact to extend the notion of technical systems towards domains that are actually usually considered only as symbolical, or purely social or cultural, and analyse processes of production that bring materiality at the same level as sociality. This paper dealt more with the ways in which peoples of Oceania materialise themselves, rather than with processes by which anthropological or museum discourses and practices contribute materialising Oceania. What is argued for is the need to investigate the inherent relationality of things and activities -in a similar sense that the relationality of personhood demonstrated elsewhere [START_REF] Strathern | The Gender of the Gift: Problems With Women and Problems With Society in Melanesia[END_REF](Strathern , 1999) ) -not only through their use and consumption, but through how they are made. Analysis of sociotechnical systems such as Cresswell's, Lemonnier's, Latour's or Pfaffenberger's demonstrate that technology is as much about the making of relations, as it is about the materialisation or, I suggest, the objectification of successful relations. Material and non material, social and technical, all are wrought together in the making of an artefact, which instantiates always more than what is visible on its surface, and even more than what is made of it, while being consistent with the material nature of the thing itself. Yams as artefacts are thus more than "congealed labour", they can be seen as "condensed networks… [which] work as summation or stop" (Strathern 1996: 523), that is materialised moments when properties acquired from the materialisation process as a system, can be engaged with, in consumption or use. 16 It also gives an insight about how certain categories of objects can be considered not as bounded entities, but shifting ones, and processual ones that have the ability to generate new sets of relations, to have an agency.

The very notion of "artefact" itself might be central and, I agree, goes beyond the mere idea of manufactured object (Miller 1987: 112-115) as it always implies agencies and intentionalities that are perceived as having been encapsulated within its very material form [START_REF] Gell | The Technology of Enchantment and the Enchantment of Technology[END_REF](Gell , 1998)), or better: made of materials. Take a piece of rock brought back from the moon by Apollo 17, for instance. Susan Pearce rightly insists on the selection process and the "cultural value it is given and not primarily the technology which has been used to give it form of content, although this is an important mode of value creation". I would argue that maintaining such distinction between cultural value and technology obviates the entire sociotechnical process that includes the making of a rocket, the training of astronauts, the gathering of fuel, and material resources to launch them into space, the body technique (learned through hours of drilling) of the astronaut walking on a low gravity environment, and the processes that make them land safely. Had I the piece of rock on my desk (Ingold 2007), its materiality would definitely stem from its materials, as well as from the network of relations it would materialise. I suspect Abelam people finding stones in the river to make the heap central to their ceremonial ground would not argue with me, notably because it implies carrying them back all the way up to the hamlet,

The Australian Journal of Anthropology Ludovic Coupaye D r a f t in the night so that everybody would think it appeared through the agency of ancestors.

I suggest that things' capacities to participate to social life, in other words their properties, are not only made visible through the ways in which people engage with them once they are made, but also stem from how they are made, produced, fabricated, worked out, all these terms taken in a non metaphorical sense. Things' properties stem from the material and sensual qualities they have acquired, or are thought to have acquired, through processes now invisible. These technological processes, by definition socialising ones, be they known or unknown, always intertwine several levels of reality. If "sociality" increasingly replaces the notion of 'society', 'materiality' could be the relational definition of 'material' outlining how things are as composite and fluid as those of persons. But this fluidity, this multivalence, or what makes things 'hybrids' in our eyes [START_REF] Latour | Nous n'avons jamais été modernes: Essai d'anthropologie symétrique[END_REF], comes from the systemic nature of the process, and of the multiplicity of domains to which their creation resorts. Even when the technology is unknown, or foreign, even metaphorically speaking, the origin of things is always presumed by those who encounter them, as the result of processes: money is assumed to be grown in the same manner as food (Bell, this volume), or, as I was myself told, coming from specific machines that every white man has in his home. Things are concretions of relations, and their materiality also stems on how they came into being, not only from how they are used. This brings us briefly back to "labour", "technology" or "modes of production": to approach the materialisation of artefacts from the angle of the sociotechnical system itself is not only a methodological choice to attain an emic understanding of indigenous materiality. It is also grounded on the material validity (one could be tempted of speaking of multiples validities) of representational -or ideological -components of technological phenomena. Indeed, I argue that such components not only contribute to shaping how human beings construe their relationships with each other and with the material world, but correspond at the same time to what is moulded by and how these relationships are materialised in the form of new products of these representations. Objectification as Miller's defined it is a powerful tool to understand how materialisation is close to socialisation. However, human beings' technical ability to concretise social values in artefacts, to condense their networks of relations, and to surround themselves with such materialised results of socialisation could indeed constitute one of the main reasons why things still matter: not only because of how we consume them, but also because of how we make them consumable.

o

  Fig. 1: Three local accounts of the long yam growing process (short version). Kulang in his early forties and both Gayiningi and Kitnoyra are over sixty, and are considered to be Nëma n du. Nyamikum 2002. NB: in the transcription, for the sake of clarity, I removed the superscripted consonants in local terms.

8/26/2009 The Austra 8/26/ lian Journal of Anthropology Ludovic Coupaye D r a f t 2009 13

From the moment the vines climb the vertical trellis (taawu) o

  Gathering the ingredients for the two main 'magical' substances/fertilisers: gunyëgi (lit. 'water-stinging') and kusbawu (lit. 'magic ash)'.

	The Austra	lian Journal of Anthropology	Ludovic Coupaye
			D r a f t
	Edward Kulang's account	Gayiningi and Kitnyora's account
	Part I: From before the planting
	o Beginning of the Yakët.
	o Clearing then burning the long yam garden
	o Ends when the yam vine reaches the base of the vertical trellise
	Part II:
	8/ 26/2009		14

8/26/2009 The Australian Journal of Anthropology Ludovic Coupaye D r a f t Conclusion: "things are parts of persons, because they are creation of them" 15

The Australian Journal of Anthropology Ludovic Coupaye D r a f t

  Lechtman, H. & R. Merrill (eds) 1977. Material Culture: Styles, Organization, and Dynamics of Technology. St Paul: Xest.

Cf. the title of the 2006 workshop organised by Bill Sillar at the department of archaeology, UCL, May 2006.

8/26/2009

The SIL transcription këm is the equivalent of the term kum found in literature (for example,[START_REF] Huber-Greub | Kokospalmenmenschen: Boden und Alltag und ihre Bedeutung im Selbstverständnis der Abelam von Kimbangwa (East Sepik Province, Papua New Guinea)[END_REF] or kim(Hauser-Schaüblin 1989). Its translation as 'place' has become part of names of villages, such as Nyami-këm, Nyeli-këm or Sara-këm. However, earlier transcriptions have often led to the use of the spelling '-kum' or even '-gum', such as the official map spelling for Neligum, Gweligum or Waigagum. As it interfered quite often with the actual names of the clans, such as Tatmëkëm, or Sarëkëm -notably while I was myself collecting genealogies, with people giving me the name of their hamlet instead of their clan and reversely -I use '-këm' when referring to clans, and '-kum' when referring to villages..8/26/2009

Damon 1980: 204.

However, although this approach of sociotechnical phenomena does evoke the holistic notion of "social total fact"(Mauss 1950) or systemic studies such as the one conducted by Rappaport (1968), it does not entirely subscribed either to the complete reliance on actor-network theory or on temptations of materialistic or functionalist explanations (for a critique of Rappaport see Hornborg 1996). If anything, I would perhaps consider an approached based on the non-linearity of complex systems (cf. Lee 1997).8/26/2009


Richard Moot
email: richard.moot@labri.fr

Signes

Graph Algorithms for Improving Type-Logical Proof Search

Keywords: Automated Deduction, Floyd-Warshall Algorithm, Lambek Calculus, Proof Net, Ranked Assignments

Proof nets are a graph theoretical representation of proofs in various fragments of type-logical grammar. In spite of this basis in graph theory, there has been relatively little attention to the use of graph theoretic algorithms for type-logical proof search.

In this paper we will look at several ways in which standard graph theoretic algorithms can be used to restrict the search space. In particular, we will provide an O(n 4 ) algorithm for selecting an optimal axiom link at any stage in the proof search as well as an O(kn 3 ) algorithm for selecting the k best proof candidates.

Introduction

Type-logical grammar [START_REF] Morrill | Type Logical Grammar: Categorial Logic of Signs[END_REF][START_REF] Moortgat | Categorial type logics[END_REF] is an attractive logical view of grammatical theory. Advantages of this theory over other formalisms include a simple, transparent theory of (λ term) semantics thanks to the Curry-Howard isomorphism and effective learning algorithms for inducing grammars from linguistic data [START_REF] Buszkowski | Categorial grammars determined from linguistic data by unification[END_REF].

Proof nets, first introduced for linear logic by [START_REF] Girard | Linear logic[END_REF], are a way of presenting type-logical proofs which circumvents the redundancies present in, for example, the sequent calculus by performing all logical rules 'in parallel'.

The only non-determinism in trying to prove a theorem consists of selecting pairs of axiom links. Each possible selection -if correct -will result in a different proof. However, many of these possible selections can never contribute to a proof net, while a naive algorithm might try these selections many times. It is the goal of this paper to provide algorithms for filtering out these possibilities at an early stage and selecting the axiom link which is most restricted, thereby improving the performance of proof search.

Given that the problem we are trying to solve is known to be NP complete, even in the non-commutative case, it would be too much to hope for a polynomial algorithm [START_REF] Kanovich | The multiplicative fragment of linear logic is NPcomplete[END_REF][START_REF] Pentus | Lambek calculus is NP-complete[END_REF]. However, we will see an algorithm for computing the best possible continuation of a partial proof net in O(n 4 ).

A second aim is to develop a polynomial algorithm by means of approximation. If we consider only the best k axiom links, then we can find these in O(kn 3 ). When best is defined as 'having axiom links with the shortest total distance' this algorithm converges with results on proof nets and processing [START_REF] Johnson | Proof nets and the complexity of processing centerembedded constructions[END_REF][START_REF] Morrill | Incremental processing and acceptability[END_REF].

Proof Nets and Essential Nets

In this section we will look at two ways of presenting proof nets for multiplicative intuitionistic linear logic (MILL) together with their correctness criteria and some basic properties.

Though the results will be focused on an associative, commutative system, it is simple to enforce non-commutativity by demanding the axiom links to be planar [START_REF] Roorda | Resource logics: A proof-theoretical study[END_REF] or by labeling, either with pairs of string positions [START_REF] Morrill | Higher order linear logic programming of categorial deduction[END_REF] or by algebraic terms [START_REF] De Groote | An algebraic correctness criterion for intuitionistic proofnets[END_REF]. In order to have more flexibility in dealing with linguistic phenomena, other constraints on the correctness of proof nets have been proposed [START_REF] Moot | Proof nets for the multimodal Lambek calculus[END_REF], but given that the associative, commutative logic is the worst case (in the sense that it allows the most axiom links) with respect to other fragments of categorial grammars there are no problems adapting the results of this paper to other systems. However, we leave the question of whether it is possible to perform better for more restricted type-logical grammars open.

The choice of presenting the logic with two implications which differ only in the order of the premisses of the links is intended to make the extensions to the non-commutative case more clearly visible.

A ⊢ A [Ax] ∆ ⊢ A Γ, A, Γ ′ ⊢ C Γ, ∆, Γ ′ ⊢ C [Cut] Γ, A, B, ∆ ⊢ C Γ, A • B, ∆ ⊢ C [L•] Γ ⊢ A ∆ ⊢ B Γ, ∆ ⊢ A • B [R•] ∆ ⊢ B Γ, A, Γ ′ ⊢ C Γ, A / B, ∆, Γ ′ ⊢ C [L/] Γ, B ⊢ A Γ ⊢ A / B [R/] ∆ ⊢ B Γ, A, Γ ′ ⊢ C Γ, ∆, B \ A, Γ ′ ⊢ C [L\] B, Γ ⊢ A Γ ⊢ B \ A [R\]
Table 1 The sequent calculus for L/MILL with commutativity implicit

np ⊢ np [Ax] s ⊢ s [Ax] np, np \ s ⊢ s [L\] np ⊢ s / (np \ s) [R/] s ⊢ s [Ax] np, (s / (np \ s)) \ s ⊢ s [L\] (s / (np \ s)) \ s ⊢ np \ s [R\] s ⊢ s [Ax] s / (np \ s), (s / (np \ s)) \ s ⊢ s [L/]

Sequent Calculus

Table 1 shows the sequent calculus for the Lambek calculus L, first proposed by [START_REF] Lambek | The mathematics of sentence structure[END_REF]. The commutative version, the Lambek-van Benthem calculus LP, is also known as the multiplicative fragment of intuitionistic linear logic MILL. An example sequent derivation is shown in Figure 1.

Proof Nets

Proof nets are an economic way of presenting proofs for linear logic, which is particularly elegant for the multiplicative fragment. When looking at sequent proofs, there are often many ways of deriving essentially 'the same' proof.

Proof nets, on the other hand, are inherently redundancy-free.

We define proof nets as a subset of proof structures. A proof structure is a collection of the links shown in

A + A - A + A - B - A - A • B + B - A - A / B - A + B - B \ A + A + B + A • B + A - B + A / B - B + A + B \ A Table 2
Links for proof structures this paper. A cut link has two premisses, which can appear in any order, and no conclusions. All other links have an explicit left premiss and right premiss.

We also distinguish between negative (antecedent) and positive (succedent) formulas and between tensor (solid) and par (dotted) links.

Definition 1 A proof structure S is a collection of links such that:

(1) every formula is the conclusion of exactly one link, (2) every formula is the premiss of at most one link, formulas which are not the premiss of a link are called the conclusions of the proof structure, (3) a proof structure has exactly one positive conclusion.

Given a proof structure, we want to decide if it is a proof net, that is, if it corresponds to a sequent proof. A correctness criterion allows us to accept the proof structures which are correct and reject those which are not. In this section, we will look at the acyclicity and connectedness condition from [START_REF] Danos | The structure of multiplicatives[END_REF], which is perhaps the most well-known correctness condition for proof nets in multiplicative linear logic. We will look at another condition in the next section.

Definition 2 For a proof structure S, a switching ω for S is a choice for every par link of one of its premisses.

Definition 3 From a proof structure S and a switching ω we obtain a correction graph ωS by replacing all par links Proof search in a proof net system is a rather direct reflection of the definitions. Given a sequent Γ ⊢ C we unfold the negative formulas in Γ and the positive formula C, giving us a proof frame. Note that given a polarized formula, exactly one link will apply, making this stage trivial. An example proof frame for the sequent

(np \ s), (s / (np \ s)) \ s ⊢ s of Figure 1 is given in Figure 2.
We have given the atomic formulas an index as subscript only to make it easier to refer to them; the numbers are not formally part of the logic. The matrix next to the proof frame in the figure represents the possible linkings: the rows are the negative formula occurrences, whereas the columns are the positive formula occurrences. White entries represent currently impossible connections whereas colored entries represent the current possibilities.

The next stage consists of transforming the proof frame into a proof structure by linking atomic formulas of opposite polarity. It is this stage which will concern us in this paper. This is a matter of putting exactly one mark in every row and every column of the table. Finally, we need to check the correctness condition. Though there are many correction graphs for a proof structure, [START_REF] Guerrini | Correctness of multiplicative proof nets is linear[END_REF] shows we can verify the correctness of a proof structure in linear time. The proof structure in Figure 3 is indeed a proof net, which we can verify by testing all correction graphs for acyclicity and connectedness. Of the 5 alternative linkings, only one other produces a proof net.

Essential Nets

For out current purposes, we are interested in an alternative correctness criterion proposed by [START_REF] Lamarche | Proof nets for intuitionistic linear logic I: Essential nets[END_REF]. This criterion is based on a different way of decomposing a sequent, this time into a directed graph, with conditions on the paths performing the role of a correctness criterion. A net like this is called an essential net. The links for essential nets are shown in Table 3 on the next page, though we follow de Groote (1999) in reversing the arrows of [START_REF] Lamarche | Proof nets for intuitionistic linear logic I: Essential nets[END_REF].

Definition 5 Given an essential net E its positive conclusion is called the output of the essential net and the negative conclusions, as well as the negatives premisses of any positive / or \ link, are called its inputs.

Definition 6 An essential net is correct iff the following properties hold.

(1) it is acyclic, (2) every path from the negative premiss of a positive / or \ link passes through the conclusion of this link, (3) every path from the inputs of the graph passes reaches the output of the graph.

-

A + A ? - A + A 6 - A - B - A • B ] - A + B - A / B ] + B - A - B \ A - + A + B + A • B ^-B + A + A / B + A - B + B \ A Table 3 Links for essential nets - s 1 + \ 10 - / 9 ] + s 4 - np 7 ^+ np 8 - s 2 - \ 11 - + s 5 + / 12 - s 3 - \ 13 - + s 6 ? s 1 s 2 s 3 s 4 s 5 s 6 np 8 np 7 Fig. 4. Example essential net Theorem 7 (Lamarche (1994)) A sequent Γ ⊢ C is provable in MILL iff its essential net is correct.
Condition (1) reflects the acyclicity condition on proof nets, whereas conditions (2) and (3) reflect the connectedness condition. The formulation of 'every path' exists only to ensure correctness of the negative • link; in all other cases there is at most one path between two points in a correct essential net.

Figure 4 gives the essential net corresponding to the proof frame we have seen before, but this time with the np axiom link already performed. Remark that we have simply unfolded the formulas as before, just with a different set of links.

It will be our goal to eliminate as many axiom links as possible for this example.

Though the correctness criterion was originally formulated for the multiplicative intuitionistic fragment of linear logic only, [START_REF] Murawski | Dominator trees and fast verification of proof nets[END_REF] show -in addition to giving a linear time algorithm for testing the correctness of an essential net -that we can transform a classical proof net into an essential net in linear time. So our results in the following sections can be applied to the classical case as well.

Basic Properties

In order to better analyze the properties of the algorithms we propose, we will first take a look at some basic properties of proof nets.

Axiom Links

Since we will be concerned with finding an axiom linking for a partial proof structure P which will turn P into a proof net, we first given some bounds on the number of proof structures we will have to consider. Given that the problem we are trying to solve is NP complete, it is not surprising these bounds are quite high.

Proposition 8 Let P be a proof net and f an atomic formula, then the number of positive occurrences of f is equal to the number of negative occurrences of f . This proposition follows immediately from the fact that every atomic formula is the conclusion of an axiom link, where each axiom link has one positive and one negative occurrence of a formula f as its conclusion.

Proposition 9 Every proof frame F has O(a!) axiom linkings which produce a proof structure, where a is the maximum number of positive and negative occurrences of an atomic formula in F .

If we have a positive atomic formulas, we have a possibilities for the first one, since all negative formulas may be selected, followed by a -1 for the second etc. giving us a! possibilities.

Proposition 10 Every proof frame F has O(4 a ) planar axiom linkings which produce a proof structure, where a is the maximum number of positive and negative occurrences of an atomic formula in F . This follows from the fact that a planar axiom linking is simply a binary bracketing of the atomic formulas and the fact that there are C a-1 such bracketings, where C k , the kth Catalan number, approaches 4 k / √ πk 3/2 .

Proposition 11 For every partial proof structure with a atomic formulas which are not the conclusion of any axiom link there are O(a 2 ) possible axiom links.

Given that every positive atomic formula can be linked to every negative atomic formula of the same atomic type this gives us a 2 pairs.

Graph Size

Proposition 12 For every proof structure S with h negative conclusions, 1 positive conclusion, p par links and t tensor links, the following equation holds.

p + h = t + 1 = a
Given Proposition 8, the number of positive and negative atomic formulas is both a. Suppose we want to construct a proof structure S with h negative conclusions and 1 positive conclusion from these atomic formulas. When we look at the links in Table 2 we see that all par links reduce the number of negative conclusions by 1 and all tensor links reduce the number of positive conclusions by 1.

Proposition 13 Every essential net

E has v = h+1+2(t+p) = O(a) vertices and 2t + p ≤ e ≤ 2(t + p) + a = O(a) edges.
This follows immediately from inspection of the links: all conclusions of the essential net (h negative and 1 positive) start out as a single vertex and every link adds two new vertices. For the edges: the minimum number is obtained when we have no axiom links and all par links are positive links for \ or / which introduce one edge, the maximum number includes a axiom links and par links which are all negative links for •.

Corollary 14 An essential net is sparse, ie. the number of edges is proportional to the number of vertices, but if we add edges for all possible axiom links it will be dense, ie. e is proportional to v 2 , Immediate from Proposition 11 and Proposition 13.

Acyclicity

We begin by investigating the acyclicity condition, condition (1) from Definition 6, which is the easiest to verify.

In order to select the axiomatic formula which is most constrained with respect to the acyclicity condition we can simply enumerate all a 2 possible axiom links However, this means we will visit the vertices and edges of the graph many times. It is therefore a practical improvement to compute the transitive closure of the graph in advance, after which we can perform the acyclicity queries in constant time.

In this paper we will use the Floyd-Warshall algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] for computing the transitive closure, which computes the transitive closure of a directed graph in O(v 3 ) time. Though there are algorithms which perform asymptotically better for sparse graphs, it is hard to beat this algorithm in practice even for sparse graphs because of the small constants involved, while for dense graphs, which we will consider in the next section when we take all possible axiom links into account, it is the algorithm of choice [START_REF] Sedgewick | Algorithms in C: Graph Algorithms[END_REF].

The Floyd-Warshall algorithm is based on successively eliminating the intermediate vertices c from every path from a to b. Given a vertex c and the paths a → c → b for all a and b we create a direct path a → b if it didn't exist before. That is to say, there is a path from a to b if either there is a path from a to c and from c to b or if there is a path from a to b which we already knew about (Figure 5).

path(a, b) := path(a, b) ∨ (path(a, c) ∧ path(c, b)) (1)
After eliminating c, for every path in the original graph which passed through c there is now a shortcut which bypasses c. After we have created such shortcuts for all vertices in the graph it is clear that the resulting graph has an edge a → b iff there is a path from a to b in the original graph. (right of the figure). A square in the matrix is colored in iff there is a link from the row to the column in the graph.

The relevant part of the graph for the acyclicity test is marked by a square around columns 1 -3 of row 4 -6. We see here, for example, that given the existence of a path 4 → 1 an axiom link between s 1 and s 4 would produce a cycle (via node 10 in the original graph) and is therefore to be excluded. A similar observation can be made for s 5 and s 3 .

Connectedness

Verifying conditions (2) and (3) from Definition 6 is a bit harder. The question we want to ask about each link is: does this link contribute to a connected proof structure? Or, inversely, does excluding the other possibilities for the two atomic formulas we connect mean a connected proof structure is still possible.

To check the conditions we need to verify the following:

(1) for every negative input of the net we verify there exists a path to the positive conclusion, (2) for every negative • link we verify that both paths leaving from it reach their destination, (3) for every positive / or \ link we check the existence of a path from its negative premiss to its positive conclusion continuing to the positive conclusion of the essential net.

Given that we are already computing the transitive closure of the graph for verifying acyclicity, we can exploit this by adding additional information to the matrix we use for the transitive closure. There are many ways of storing this extra information, the simplest being in the form of an ordered list of pairs. Given that, for a atomic formulas, each possible connection allows (a -1) 2 other connections (ie. it is agnostic about all possibilities not contradicting this one) but excludes 2(a -1) possibilities, it is more economic to store the connections which are excluded. For example, the ordered set associated to the edge from 1 to 4 will be {1 -5, 1 -6, 2 -4, 3 -4}, meaning "there is an edge from 1 to 4 but not to anywhere else and the only edge arriving at 4 comes from 1".

Note that in the description of the Floyd-Warshall algorithm, we made use only of the logical 'and' and 'or' operators. For ordered sets, the corresponding operations are set union and set intersection. For eliminating vertex c from a path from a to b, we first take the union of the ordered set representing the links which are not in a path from a to c with that representing the links not in a path from c to b (any vertex in either set couldn't be in a path from a via c to b). Then, we take the intersection of this set with the old set associated to the path from a to b.

path(a, b) := path(a, b) ∩ (path(a, c) ∪ path(c, b)) (2)
Note that Equation 2 is simply Equation 1 with both sides negated, the negations moved inward and set union and intersection in the place of the logical 'or' and 'and' operators.

Given that we can implement the union and intersection operations in linear time with respect to the size of the input sets, the total complexity of our algorithm becomes O(v 3 2(a -1)) = O(a 4 ). Every entry from the previous graph is now divided into 9 subentries -one for each possible axiom link. We read the entry for 1 -4 as follows: the first row indicate the link between 1 and 4, and thereby the absence of a link 1 -5 and 1 -6, the second row indicates the possibilities for linking 2, which just excludes 2 -4 and the third row indicates that for 3 just the 3 -4 connection is impossible. Again, we have marked the table entries relevant for our correctness condition by drawing a black border around them.

When we look at the transitive closure, we see that, should we choose to link s 2 to s 6 , this would make it impossible to reach vertex 6 from vertices 4, 5, 9 or 13. Remark also that cycles need to be excluded separately. For example, the path from 5 to 1 in Figure 7 does not mean we need to exclude the s 1 -s 5 axiom link.

Figure 8 shows the proof frame of Figure 4 with all constraints taken into account. We see that, whatever choice we make for the first axiom link, all other axiom links will be fixed immediately, giving us the two proofs s 1 -s 5 , s 2 -s 4 , s 3 -s 6 (ie. the proof shown in Figure 3) and s 1 -s 6 , s 2 -s 5 , s 3 -s 4 .

Extensions and Improvements

An interesting continuation of the themes explored in this paper would be to look at dynamic graph algorithms, where we maintain the transitive closure under additions and deletions of edges. This would avoid recomputing the transitive closure from scratch after every axiom link and would allow us to take advantage of the information we have already computed. [START_REF] King | A fully dynamic algorithm for maintaining the transitive closure[END_REF] propose an algorithm with O(n 2 ) update time based on keeping track of the number of paths between two vertices, which is easy enough to adapt to our current scenario in the case of acyclicity tests, though it remains unclear if it can be adopted to check for connectedness.

Another improvement would be to represent the ordered sets differently. Given that their structure is quite regular, it may be possible to improve upon linear time union and intersection. However, given that for each iteration the size of the sets either remains the same or decreases (the principal operation in Equation 2 being intersection), it remains to be seen if this will result in a practical improvement.

Finally, we can consider the work in the two previous sections as using a sort of 'lookahead' of one axiom link, which is to say we exclude all axioms links which, by themselves, would produce a cyclic or disconnected proof structure. This can be extended quite naturally to doing k axiom links at the same time, though each extra axiom link will multiply the required space by O(n 2 ), the required time for acyclicity by O(n 3 ) and the required time for connectedness by O(n 4 ) (this is relatively easy to see because we are in effect substituting n(n -1) for the old value of n).

Polynomial Time

If we add weights to the different connections, the situation changes. The simplest way to add weights to our graph is to use the distance between two atomic formulas as their weight and prefer the total axiom linking with the least total weight. This choice of assigning weights is closely related to work on left-toright processing of sentences, proposed independently by [START_REF] Johnson | Proof nets and the complexity of processing centerembedded constructions[END_REF] and [START_REF] Morrill | Incremental processing and acceptability[END_REF]. The claim they make is that the complexity of a phrase depends on the number of 'open' or unlinked axiom formulas a reader/listener will have to maintain in memory to produce a parse for this sentence.

Finding a minimum-weight solution to this problem is known as the assignment problem. [START_REF] Murty | An algorithm for ranking all the assignments in order of increasing cost[END_REF] was the first to give an algorithm for generating the assignments in order of increasing cost. His O(kn 4 ) algorithm for finding the k best assignments can be improved to O(kn 3 ), even though tests on randomly generated graphs have shown the observed complexity to be O(kn 2 ) [START_REF] Miller | Optimizing Murty's ranked assignment method[END_REF].

Because using the distance as weight tends to favor cyclic connections, it is preferable to make one pass of the algorithm described in the previous section and assign a weight of infinity to all edges which are either cyclic or disconnected. Figure 9 shows a weighted graph corresponding to an example from [START_REF] Morrill | Incremental processing and acceptability[END_REF], the sentence 'someone loves everyone', which has a preferred reading where the subject has wide scope. Of the four readings of this sentence (two if we enforce planarity) there is a preference for connecting s 1 -s 2 , s 3 -s 6 , s 5 -s 4 , with a total weight of 11, as compared to connecting s 1 -s 6 , s 3 -s 4 , s 5 -s 2 , with a total weight of 19. There is an important difference between using distance weights like we do here and keeping track of the open axiom links like Johnson and Morrill, which is that we select a linking which is best globally. It is therefore to be expected that we will make different predictions for some 'garden path' sentences (ie. sentences where a suboptimal local choice for the axiom links will be made).

Finding an appropriate value of k and fragments of type-logical grammar for which this k is guaranteed to find all readings remains an interesting open question. Cautious people might select k = n!, given that in any type-logical grammar there are at most n! links possible, to generate all readings in increasing order of complexity. It seems tempting to set k to n 3 , because many interesting grammar formalisms have O(n 6 ) complexity [START_REF] Joshi | The convergence of mildly contextsensitive grammar formalisms[END_REF], and find type-logical fragments for which we can show proof search using this strategy is complete.

Conclusion

We have seen how standard graph algorithms can be modified to aid in proof search for type-logical grammars by rejecting connections which can never contribute to a successful proof.

We have also seen how weighing the connections allows us to enumerate the links in increasing order and linked this with processing claims.

Fig. 1 .

 1 Fig. 1. Example sequent derivation

Fig. 3 .

 3 Fig. 3. Example proof net linkings next to the matrix which corresponds to it.

Fig. 5 .

 5 Fig. 5. Eliminating node c from the path from a to b and reject those which produce a cycle.We can easily verify whether a graph contains a cycle in time proportional to the representation of the graph, v + e, using either breadth-first search or depth-first search (e.g.Cormen et al., 1990, Section 23.2 and 23.3 respectively), giving us an O(a 2 (v + e)) = O(a 3 ) algorithm for verifying all pairs.

Figure 6 Fig. 6 .

 66 Figure 6 on the next page shows the essential net of Figure 4 on page 7 in adjacency matrix representation (left of the figure) and its transitive closure

Fig. 7 .

 7 Fig. 7. Initial graph (left) and its transitive closure (right)

Fig. 8 .

 8 Fig. 8. Essential net with acyclicity and connectedness taken into account Figure 7 on the page before shows the initial graph and its transitive closure.Every entry from the previous graph is now divided into 9 subentries -one for each possible axiom link. We read the entry for 1 -4 as follows: the first row indicate the link between 1 and 4, and thereby the absence of a link 1 -5 and 1 -6, the second row indicates the possibilities for linking 2, which just excludes 2 -4 and the third row indicates that for 3 just the 3 -4 connection is impossible. Again, we have marked the table entries relevant for our correctness condition by drawing a black border around them.

Fig. 9 .

 9 Fig. 9. Minimum Weight Linking for 'someone loves everyone'

  Table 2 which satisfies the conditions of Definition 1. A link has its conclusions drawn at the bottom and its premisses at the top. The axiom link, top left of the table, has no premisses and two conclusions which can appear in any order. The cut link, top right of the table, is mentioned only for completeness; we will not consider cut links in

	-