Cattaert Daniel
email: cattaert@lnf.cnrs-mrs.fr

Cattaert & Le Ray

Keywords: gain control, locomotion, monosynaptic Total numbers : 30 pages, 9 figures, 1 table

An in vitro preparation of the crayfish central nervous system was used to study a negative feedback control exerted by the glutamatergic motor neurons (MNs) onto their presynaptic sensory afferents. This negative control consists in small amplitude, slowly developing depolarizations of the primary afferents (sdPADs) strictly timed with MN bursts. They were not blocked by picrotoxin, but were sensitive to glutamate non-NMDA antagonists.

Intracellular recordings were performed within thin branches of sensory terminals while electrical antidromic stimulation were applied to the motor nerves, or while glutamate (the MN neurotransmitter) was pressure-applied close to the recording site. Electrical motor nerve stimulations and glutamate pressure application had similar effects onto sensory terminals issued from the coxo-basipodite chordotonal organ (CBTs) : like sdPADs, both stimulation-induced depolarizations were picrotoxin-resistant and were dramatically reduced by non-NMDA antagonist bath-application. These results indicate that sdPADs are likely directly produced by MNs during locomotor activity. A functional scheme is proposed.

Introduction

Since the discovery of presynaptic inhibition [START_REF] Dudel | Presynaptic inhibition at the crayfish neuromuscular junction[END_REF][START_REF] Frank | Presynaptic and postsynaptic inhibition of monosynaptic reflexes[END_REF], synaptic efficacy has no longer been considered as immovable and recent studies have described an increasing number of presynaptic control mechanisms. Today, presynaptic inhibition appears to be a widespread phenomenon, largely exploited by nervous systems to select afferent informations during the performing of specific movements [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF][START_REF] Grillner | Neuronal network generating locomotor behavior in lamprey: circuitry, transmitters, membrane properties, and simulation[END_REF][START_REF] Rudomin | Presynaptic inhibition and neural control[END_REF]. Extensively studied (for reviews, see [START_REF] Rudomin | Presynaptic inhibition and neural control[END_REF]Clarac andCattaert, 1996), presynaptic inhibition has been found to share common features in both vertebrate and invertebrate models. The most commonly described inhibitory mechanism was first demonstrated by [START_REF] Eccles | Presynaptic inhibition of the spinal monosynaptic reflex pathway[END_REF][START_REF] Eccles | Pharmacological studies on presynaptic inhibition[END_REF] in cat spinal cord and confirmed by numerous authors in other species [START_REF] Burrows | Synaptic potentials in the central terminals of locust proprioceptive afferents generated by other afferents from the same sense organ[END_REF][START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF]Christenson and Grillner, 1991;Christenson et al., 1991;[START_REF] Davidoff | GABA antagonism and presynaptic inhibition in the frog spinal cord[END_REF]El Manira and Clarac, 1991). It involves the inhibitory neurotransmitter -aminobutyric acid (GABA) which provokes depolarizations in the sensory terminals (therefore termed primary afferent depolarizations : PADs), that have been found to result from a strong increase in chloride conductance, and to induce the shunt of the afferent spikes. However, recent studies demonstrated that GABA was not the only neurotransmitter capable of producing effective presynaptic inhibition. In vertebrates, monoamines such as acetylcholine, noradrenaline or serotonin have been found to control efficiently the afferent signals [START_REF] Seybold | Neurotransmitter receptors sites in the spinal cord[END_REF][START_REF] Singer | Presynaptic inhibition of glutamatergic synaptic transmission to rat motoneurons by serotonin[END_REF]. In the same way, metenkephalin acting through -opioid receptors has been demonstrated to reduce strongly the amplitude of the monosynaptic responses evoked by the stimulation of small diameter primary afferents in the dorsal horn of the rat [START_REF] Hori | Presynaptic inhibitory action of enkephalin on excitatory transmission in superficial dorsal horn of rat spinal cord[END_REF].

Invertebrate models also possess a wide range of neurotransmitters, other than GABA, that are capable of presynaptically filtering the incoming sensory signals : for example, histamine performs such presynaptic inhibitory control in the abdominal ganglia interneurons of Aplysia [START_REF] Kretz | Presynaptic inhibition produced by an identified presynaptic inhibitory neuron. II. Presynaptic conductance changes caused by histamine[END_REF] or in crayfish mechano-sensory afferents [START_REF] El Manira | Presynaptic inhibition is mediated by histamine and GABA in the crustacean escape reaction[END_REF]. In both vertebrates and invertebrates, presynaptic inhibition can originate from various central [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF][START_REF] Kennedy | Presynaptic inhibition: primary afferent depolarization in crayfish neurons[END_REF] or peripheral [START_REF] Burrows | Synaptic potentials in the central terminals of locust proprioceptive afferents generated by other afferents from the same sense organ[END_REF][START_REF] Marchand | Primary afferent depolarizations of sensory origin within contact-sensitive mechanoreceptive afferents of a crayfish leg[END_REF][START_REF] Rudomin | Presynaptic inhibition of muscle spindle and tendon organ afferents in the mammalian spinal cord[END_REF] sources. The idea that some GABA-mediated PADs could be triggered by the central pattern generator was proposed because such PADs have been found to be strictly related with the centrally generated locomotor rhythm [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF][START_REF] Gossard | Intra-axonal recordings of cutaneous primary afferents during fictive locomotion in the cat[END_REF]. Recent investigations demonstrating the increasing role of motor neurons (MNs) in the locomotor network of crayfish (Cattaert et al., 1994;[START_REF] Chrachri | Fictive locomotion in the fourth thoracic ganglion of the crayfish, Procambarus clarkii[END_REF][START_REF] Pearlstein | Inhibitory connections between antagonistic motoneurones of the crayfish walking legs[END_REF], suggest that these MNs are part of the central pattern generator for locomotion. In this report, we present a new mechanism of presynaptic inhibition of the primary afferent signals which originates directly from the MNs, and may involve a kainate-like form of glutamate receptor.

Materials and Methods

Results are based on 73 intracellular recordings from sensory terminals performed on adult male and female crayfish, Procambarus clarkii. Animals were maintained in aquarium at 17-18°C and fed once a week.

The in vitro preparation [START_REF] Chrachri | Fictive locomotion in the fourth thoracic ganglion of the crayfish, Procambarus clarkii[END_REF]) consisted in the last three thoracic ganglia, and the motor nerves innervating the antagonistic muscles of each of the two proximal joints of the 5 th leg : promotor/remotor (Pro/Rem) and depressor/levators (Dep/Lev).

The CBCO, that encodes the vertical movements of the leg, was dissected out together with its sensory nerve which projects within the ipsilateral hemi-ganglion. The preparation was then pinned down dorsal side up in a Sylgard-lined Petri dish and superfused with oxygenated crayfish saline (NaCl: 195 mM, KCl: 5 mM, CaCl 2 : 13 mM, MgCl 2 : 2 mM) buffered with 3 mM Hepes and pH adjusted at 7.7 at 15°C.

In most experiments, divalent cation concentration was raised (CaCl 2 : 34 mM, MgCl 2 : 6.4 mM) with the sodium concentration reduced accordingly, in order to drastically reduce the part of polysynaptic pathways [START_REF] Berry | Criteria for distinguishing between monosynaptic and polysynaptic transmission[END_REF]. A saline with a very low chloride concentration (NaCl replaced by sodium-isothionate), a saline with half-potassium concentration, a half-sodium concentration saline (NaCl accordingly replaced by sucrose) or a calcium-free/high magnesium saline (MgCl 2 being 6-time increased) were used to study the ionic mechanisms of the recorded responses. All saline solutions were buffered with 3 mM Hepes and pH adjusted at 7.7 at 15°C (El Manira et al., 1991).

Glutamate or kainate was pressure-ejected through a thin glass micro-pipette using a Picospritzer II (General Valve Corporation, Fairfield, NJ). In experiments where glutamate and -amino-butyric acid (GABA) responses were compared (Fig. 6), both neurotransmitters were locally pressure applied using a double-barreled micro-pipette [START_REF] Marchand | A simple dual pressure-ejection system and calibration method for brief local application of drugs and modified salines[END_REF]. All chemicals used were from Sigma (Saint Quentin, Fallavier, France).

Extracellular recordings and nerve stimulations were performed using platinum electrodes contacting the nerves, isolated from bath with petroleum jelly (Vaseline), and signals were amplified by a 4-channel differential amplifier (A-M System, Inc., Everett, WA).

Intracellular recordings of the sensory terminals issued from the CBCO (CBTs) were made with thin-walled glass micro-electrodes filled with a potassium chloride solution (3M) and having a 25-30 M resistance. The signals were amplified by an Axoclamp 2B (Axon Instruments, Inc., Foster City, CA). Intracellular current pulses and nerve stimulations were controlled by a 8 channel digital stimulator (A.M.P.I., Jerusalem, Israel). All signals were monitored on a 4-channel digital oscilloscope (Yokogawa DL 1200, Tokyo, Japan) and stored on a digital tape recorder (BioLogics, DTR 1802, Claix, France), and digitized on PC-based computer through an A/D interface (from Cambridge Electronic Design, CED 1401PLUS, Cambridge, UK). Intracellular and extracellular recordings were digitized at 5-10 kHz and written to disk. Signals were analyzed using the CED programs Spike2 for Windows.

Statistical analyses and linear regressions were performed by the GraphPad Prism program (GraphPad Software, Inc., San Diego, CA).

RESULTS

CBTs display slowly developing PADs related to motor bursts.

Intracellular recordings performed on CBTs during fictive locomotion revealed the existence of small depolarizing events, that could be related clearly to the firing activity of one of the proximal motor nerves. In the example presented in Figure 1, rhythmic motor activities were induced by superfusion of the muscarinic cholinergic agonist oxotremorine (10 -5 M). In phase with the levator nerve bursts, the intracellularly recorded CBT displayed small amplitude (31 mV; mean ±SEM) slowly developing PADs (sdPADs). In contrast, classical GABAergic PADs presented larger amplitudes (94 mV; mean ±SEM) and were produced at the transition between depressor and levator bursts. However, the GABAergic PADs are not strictly related to the motor cycle (only two bursts occurred during the four cycles shown in Figure 1); whereas a very strict relationship exists between the time course of sdPADs and the instantaneous frequency of discharge within the levator nerve (Lev n Inst. Freq.; Fig. 1). These observations suggest that, during locomotor activity, afferent CBCO signals are exposed to two sources of presynaptic control, and that motor neurons are able to exert specifically a feedback control onto some of the afferents.

To test the hypothesis that sdPADs and PADs have different origins, and involve different mechanisms, the preparation was superfused with picrotoxin, the blocker of the chloride channel associated to the GABA receptor in crayfish [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF]. When the preparation was superfused with picrotoxin (10 -4 M), all reciprocal inhibitory relationships were blocked between antagonistic motor neurons, and synchronized discharges were recorded from all motor nerves (Fig. 2A). In such conditions, the large GABA-mediated PADs completely disappeared from the recorded CBT while the sdPADs summated in larger depolarizations (42 mV; mean ±SEM) that were produced in phase with the synchronized motor activities (Fig. 2A). On the other hand, as glutamate is the excitatory neurotransmitter used by MNs in crayfish [START_REF] Van Harreveld | L-proline as a glutamate antagonist at a crustacean neuromuscular junction[END_REF], we investigated the possible role of glutamate in the development of the sdPADs. When a mixture of 6-cyano-7-dinitroquinoxaline-2,3-dione (CNQX, 10 -3 M) and 6,7-dinitroquinoxaline-2,3-dione (DNQX, 10 -3 M), two glutamate antagonists, were added to the picrotoxin perfusion, the amplitude of the sdPADs was significantly reduced (see histogram in Fig. 2A; p<0.05). A slight recovery of sdPADs amplitude was observed after removing the mixture of non-NMDA (N-methyl-D-aspartate) glutamate antagonists from the picrotoxin-bath. These results indicate that the sdPADs were likely mediated by glutamate.

In order to test further if sdPADs were produced by MNs, we performed antidromic stimulation of the motor nerves that innervate the proximal muscles of the leg, while intracellularly recording the response in a CBT. As shown in Figure 2B (top trace), an electrical stimulation applied to the anterior levator motor nerve was able to elicit a 1-2 mV depolarizing response in the intracellularly recorded CBT. Perfusing the glutamate non-NMDA antagonist DNQX (10 -3 M) induced a 30-50 %-reduction of the response recorded from the CBT (middle trace). This effect was reversible (bottom trace; each trace is the average of 30 raw data). A similar reduction of the response could be observed during superfusion of CNQX (10 -3 M; data not shown). In the same CBT, comparable results were obtained by applying antidromic stimulation to the depressor nerve (not shown). All CBTs did not respond to the stimulation of motor nerves, and when they did, most of them responded only to the stimulation of one proximal motor nerve. Table 1 summarizes the results obtained from 17 distinct intracellularly recorded CBTs. Although a CBT generally presented a specificity for one motor nerve, some terminals displayed nevertheless depolarizing responses for several antidromically stimulated motor nerves (from 2 to 4). Thus, it appears that crayfish MNs are able to exert directly a glutamate-mediated presynaptic control of their input synapses.

Glutamate-and GABA-induced responses involve distinct mechanisms.

In order to study the properties of the glutamate-mediated sdPADs, we performed direct micro-application of glutamate (10 -2 M) within the neuropile. Micro-ejection of glutamate in the vicinity of the small end branches of the CBTs (Fig. 3A) generally evoked a slow depolarizing response in the recorded sensory terminal (Fig. 3B). The reversal potential of the response to glutamate ejection was investigated by measuring the amplitude of the response at various membrane potentials imposed by continuous current injection (Fig. 3C).

The response of CBTs varied almost linearly with the imposed membrane potential. It reversed at -552 mV, suggesting the involvement of a composite current.

The response to glutamate micro-application is inhibitory (Fig. 4). When the recorded CBT displayed spontaneous spikes, or when the CBCO nerve was stimulated in order to record orthodromic spike from the CBT (Fig. 4A), the glutamate-induced depolarizing response was accompanied by the decrease of the CBT spike amplitude (mean decrease of about 20 %) that lasted throughout the depolarization developed (see inset in Fig. 4A). During the glutamate-induced depolarization, the membrane input resistance, measured by injecting hyperpolarizing current pulses within the recorded CBT, was strongly reduced (50-85 %;

Fig. 4B). The change of input resistance observed during the glutamate-induced response was not voltage-dependent, because when the resting membrane potential of the recorded CBT was maintained above -50 mV by continuous current injection, the response reversed into a hyperpolarizing response without modifying the input resistance variation rate (Fig. 4B).

The depolarizing response to glutamate micro-ejection was unaffected by tetrodotoxin

(5.10 -7 M) added to the perfusion saline (Fig. 5B, compared to control in Fig. 5A), indicating that glutamate acted directly on the recorded CBT. When picrotoxin (2.10 -4 M) was added as well, the glutamate-induced response remained unchanged (Fig. 5C, compared to control in Fig. 5A), suggesting that chloride ions were not implicated in the development of the depolarizing response. This later result demonstrates that glutamate-and GABA-induced PADs involve distinct mechanisms (Cattaert et al., 1994;[START_REF] Eccles | Pharmacological studies on presynaptic inhibition[END_REF][START_REF] Gallagher | Characterization and ionic basis of GABAinduced depolarizations recorded in vitro from cat primary afferent neurones[END_REF].

In order to verify that glutamate and GABA did not activate the same receptor-channel, we used a double-barreled micro-pipette to eject both drugs in the same area. Responses to glutamate and GABA evoked at different locations on the recorded CBT were compared (Fig. 6A). Such a protocol allowed us to determine that GABA and glutamate receptors were localized at distinct sites of the terminal tree (Fig. 6B). When the double-barreled micro-pipette was located near the first branching point of the CBTs (position 1 in Fig. 6A), only GABA succeeded in producing a depolarization, and a decrease in input resistance in the recorded CBT, while glutamate ejection did not elicit any response (Fig. 6B1). In contrast, when the double-barreled ejection pipette was located closer to the endings of CBTs (position 2 in Fig. 6A), a depolarizing response to glutamate and an input resistance decrease occurred in the recorded CBT (Fig. 6B2). Even at these locations, GABA remained able to produce the classical GABA-induced response in the recorded CBT.

Glutamate involves a non-NMDA type of receptor-channels.

Superfusion of various NMDA-receptor antagonists always failed to prevent the development of the depolarizing response to glutamate micro-application. As shown in Figure 7A, adding 2-amino-5-phosphonopentanoic acid (AP5, 10 -2 M) or a mixture of 2-amino-3-phosphonopropionic acid (AP3, 10 -2 M) and 2-amino-7-phosphonoheptanoic acid (AP7, 10 -2 M) to the perfusion saline did not affect the glutamate-induced depolarizing response in the recorded CBT. Ketamine, another NMDA receptor antagonist, did not prevent the glutamatergic response as well (data not shown). The conclusion that NMDA receptors are not involved in the presynaptic inhibition of MN origin is reinforced by the finding that, even in Mg 2+ -free saline, glycine had never any effects (data not shown).

By contrast, non-NMDA receptor antagonists diminished significantly (by a mean of the example presented in Figure 7B1, addition of CNQX (10 -3 M) in the perfusion bath induced a reversible 233 %-decrease in amplitude of the glutamatergic response.

Comparable results were obtained by superfusion of DNQX (10 -3 M), another non-NMDA antagonist of glutamate (data not shown). In addition, kainate, a glutamate non-NMDA agonist, substituted for glutamate in the ejection micro-pipette was capable of producing depolarizing responses with the same characteristics as glutamate : their dose-dependence was comparable to glutamate-induced ones (Fig. 7B2, compare with histogram in Fig. 3B); as was the case for glutamate-evoked response, the kainate response reversed around -55 mV (data not shown); the kainate-evoked depolarization was accompanied by input resistance decrease comparable to the glutamate-induced one (data not shown). These results clearly demonstrate that glutamate responses recorded from CBTs were due to the activation of a non-NMDA type of receptor.

We investigated which ions permeate through the channel associated with this non-NMDA-type receptor, using various salines : a calcium-free saline, a chloride-free saline, and a half-sodium or half-potassium concentration salines (Fig. 8). The calcium-free as well as the chloride-free saline did not alter neither the spike shunt in the recorded CBTs, nor the amplitude of the glutamate-induced depolarization (not significant difference between the three thin lines corresponding to the linear regressions calculated from the values obtained under normal saline, calcium-or chloride-free salines; reversal potential = -533 mV; Fig. 8).

In contrary, when the sodium concentration (thick broken line; reversal potential = -542 mV; Fig. 8) or the potassium concentration was lowered by 50 % (thick line; reversal potential = -582 mV; Fig. 8), the shunting effect on spike amplitude was reduced. Moreover, the slopes of both linear regressions, representing the relationships between the amplitude of the response and the imposed membrane potential, were significantly different from control (p<0.001 and p<0.01 for sodium-free and potassium-free salines, respectively). Taken together, all these results strongly suggest that glutamate activated a kainate-like receptor-channel which was permeable to both Na + and K + ions.

DISCUSSION

The sdPADs are glutamatergic and originate from MNs.

During rhythmic motor activities, sdPADs recorded from CBTs present characteristics identical with glutamate-induced depolarizing responses : small amplitudes (< 5 mV), insensitivity to picrotoxin (10 -4 M) and sensitivity to non-NMDA glutamate antagonists (CNQX and DNQX, 10 -3 M). In addition several facts are strongly in favor of a excitatory MN origin for sdPADs : (1) sdPADs are strictly related to motor bursting activity of one or several MN groups (Fig. 1), (2) glutamate is the excitatory MN neurotransmitter, (3) motor nerve electrical stimulation produces a small amplitude depolarizing response (<5 mV) with the same reversal potential as glutamate-evoked responses (data not shown), and (4) this response to motor nerve stimulation is sensitive to the same non-NMDA glutamate antagonists as sdPADs and glutamate-evoked responses, and insensitive to picrotoxin (data not shown).

These characteristics common to sdPADs and glutamate-evoked depolarizing responses are not shared by GABAergic PADs [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF]. Although a common inhibitory MN has been described in crayfish [START_REF] Bévengut | Synaptic connections of the common inhibitory motoneurone within the fifth thoracic ganglion of crayfish[END_REF], the neurotransmitter of which is GABA, we can exclude the participation of this common inhibitor in the responses observed in CBTs in response to motor nerve electrical stimulation, because sdPADs persist in the presence of picrotoxin.

The sdPADs and GABAergic PADs do not occur at the same location.

Immuno-histochemical studies have shown that locust mechano-sensory afferents possess GABA and glutamate input synapses [START_REF] Watson | GABA and glutamate-like immunoreactivity in processes presynaptic to afferents from hair plates on the proximal joints of the locust leg[END_REF]. These authors demonstrated that both types of synapses were intermingled on most of the primary afferent axonal branches. In crayfish sensory afferents, although such immuno-histochemical studies

have not yet been performed, we have demonstrated here that both input synapses exist too.

However, it seems that glutamate and GABAergic responses occurred at distinct areas of the axonal arborization. Using a double-barreled ejection pipette, glutamate and GABA were applied at the same area [START_REF] Marchand | A simple dual pressure-ejection system and calibration method for brief local application of drugs and modified salines[END_REF]. When the pipette was disposed close to the entry of the sensory axons within the ganglion, only GABA responses were evoked (Fig. 6B1). A similar location for PADs has been found by Cattaert and El Manira (1998a). When the pipette was placed in a more central area, GABA responses were still evoked, and glutamate responses became observable. The more central responses to GABA pressure-ejection may result from the GABA diffusing to the main GABA-receptor site demonstrated to exist in the area of CBT first branching point by immuno-histochemistry (Cattaert and El Manira, 1998a). However, similar diffusion would have also exist for the ejected glutamate, and therefore, glutamate receptor site would have been located even more centrally than the pipette.

The sdPADs involve a kainate-like glutamate receptor.

In this work, we described sensory terminals that present depolarizing inhibitory responses to glutamate micro-application. Although glutamate is generally considered as an excitatory neurotransmitter, it is now well-established that glutamate can also mediate inhibitory interactions in invertebrate nervous system [START_REF] Miwa | Presynaptic glutamate receptor--possible involvement of a K+ channel[END_REF][START_REF] Kehoe | Glutamate activates a K + conductance increase in Aplysia neurons that appears to be independent of G proteins[END_REF][START_REF] Marder | The pharmacological properties of some crustacean neuronal acetylcholine, gamma-aminobutyric acid, and L-glutamate responses[END_REF][START_REF] Miwa | Presynaptic glutamate receptors depress inhibitory postsynaptic transmission in lobster neuromuscular synapse[END_REF]. Nevertheless, in most invertebrate models, glutamatergic inhibition is due to the activation of chloride channels as those involved in GABAergic inhibition and, therefore, shares the same pharmacological properties [START_REF] Dubas | Actions of putative amino acid neurotransmitters on the neuropile arborizations of locust flight motoneurones[END_REF]Franke et al., 1986b;[START_REF] Marder | The pharmacological properties of some crustacean neuronal acetylcholine, gamma-aminobutyric acid, and L-glutamate responses[END_REF]. In our preparation, we showed that the glutamate-mediated inhibition was not affected by the superfusion of picrotoxin (Figs. 2A and5C), and modifying the extracellular concentration of chloride ions did not alter the glutamate-induced response in CBTs (Fig. 8). These results clearly indicate that glutamate did not act through the activation of a chloride channel, as it has been often described in invertebrate nervous system (Franke et al., 1986b;[START_REF] Lingle | A glutamate-activated chloride conductance on a crustacean muscle[END_REF].

In crayfish muscles, [START_REF] Zufall | Acetylcholine activates a chloride channel as well as glutamate and GABA. Single channel recordings from crayfish stomach and opener muscles[END_REF] have shown that glutamate and acetylcholine activated the same receptor-channel. Because CBTs are cholinergic, one could suppose that the glutamatergic response we recorded from CBTs could be due to the activation of such a receptor. This assumption could be rejected because the muscle response was also abolished by picrotoxin. Moreover, each cholinergic antagonist tested always failed to prevent the glutamate-induced depolarization in CBTs (data not shown). In opposition, non-NMDA glutamate antagonists invariably reduced the amplitude of this depolarization (Fig. 7B).

Moreover, kainate mimicked perfectly the action of glutamate when ejected onto CBTs (Fig. 7B) suggesting that the receptor involved in presynaptic inhibition resemble the excitatory kainate-type of glutamate receptor.

One could argue that, in our study, using high concentrations of antagonists resulted in weak effects (e.g., only 30% of blocking with CNQX, 10 -3 M). However, we must keep in mind that pharmacological tools are rarely as efficient in invertebrates as they are in vertebrates. A number of invertebrate pharmacological studies used blocking agents at concentrations 10 to 1000 folds higher than the ones used in vertebrate to get a significant but rarely complete effect [START_REF] Marder | The pharmacological properties of some crustacean neuronal acetylcholine, gamma-aminobutyric acid, and L-glutamate responses[END_REF][START_REF] Parker | Glutamatergic transmission between antagonistic motor neurones in the locust[END_REF]. For example, at the crayfish neuromuscular junction, 10 -2 M glutamate--methylester only resulted in a 60% block of the glutamatergic excitatory junctional potentials [START_REF] Lowagie | Glutamate antahonists at crayfish neuromuscular junction[END_REF].

Similarly, in the locust central nervous system, Sombati and Hoyle (1984) showed that the FETi (fast extensor tibialis motor nerve)-evoked depolarization could only be partially blocked by prolonged bath application of 5.10 -3 M of glutamate diethyl ester. In view of these established results, we can consider that the effects we show in this work are significant and support the demonstration that the glutamate receptors involved in the presynaptic inhibition originating from MN activity share some characteristics of the vertebrate kainate-type glutamate receptors. In opposition AP7 has been shown to efficiently block the crayfish NMDA receptor (Pfeiffer-Linn and Glantz, 1991), while it was totally ineffective in our system even when used at higher concentration (Fig. 7A). We therefore conclude that the glutamate receptor that mediates the presynaptic inhibition in sensory terminals are non-NMDA receptors, and probably of kainate type.

Presynaptic inhibition associated with sdPADs involves a new shunt mechanism.

Different kinds of mechanisms have been proposed for presynaptic inhibition. Several recent studies demonstrated the existence of a metabotropic control of neurotransmitter release, through various intracellular cascades of events [START_REF] Scanziani | Presynaptic inhibition of excitatory synaptic transmission by muscarinic and metabotropic glutamate receptor activation in the hippocampus: are Ca2+ channels involved?[END_REF]Christenson and Grillner, 1991;[START_REF] Schrader | Presynaptic modulation by metabotropic glutamate receptors of excitatory and inhibitory synaptic inputs to hypothalamic magnocellular neurons[END_REF][START_REF] Sladeczek | Presynaptic inhibitory action of a metabotropic glutamate receptor agonist on excitatory transmission in visual cortical neurons[END_REF]. Nevertheless, the most commonly described mechanism of presynaptic inhibition in primary afferent remains the shunt of the afferent action potential, induced by the massive opening of ion channels (Cattaert and El Manira, 1998b). As we described (Figs. 4B and 6B2), glutamate micro-application induced a strong decrease of the input resistance of CBTs, which resulted in the shunt of the afferent spikes (Fig. 4A). In the case of the GABA-mediated presynaptic inhibition, the action potential is shunted by a strong increase in chloride conductance [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF]Cattaert et al., 1994;Cattaert and El Manira, 1998a,b;[START_REF] Gallagher | Characterization and ionic basis of GABAinduced depolarizations recorded in vitro from cat primary afferent neurones[END_REF][START_REF] Segev | Computer study of presynaptic inhibition controlling the spread of action potentials into axonal terminals[END_REF]. In opposite, we demonstrated that glutamate did not involve chloride ions. It seemed that glutamate shunt was due to the increase of a combined sodium-potassium conductance (Fig. 8). Cationic channels coupled to glutamate receptor have previously been reported to mediate inhibitory controls in crustacean neuromuscular junction and in mollusk interneurons [START_REF] Miwa | Presynaptic glutamate receptor--possible involvement of a K+ channel[END_REF][START_REF] Kehoe | Glutamate activates a K + conductance increase in Aplysia neurons that appears to be independent of G proteins[END_REF][START_REF] Marder | The pharmacological properties of some crustacean neuronal acetylcholine, gamma-aminobutyric acid, and L-glutamate responses[END_REF].

However, only K + ions were found to permeate through those receptor-channels, inducing subsequently hyperpolarizing responses. In crayfish sensory terminals, it appears that another type of glutamate receptor is responsible for the presynaptic inhibition of sensory spikes. The fact that kainate reproduced roughly the same response as glutamate suggests that the shunt of afferent action potential resulted from the opening of the non-specific Na + /K + channel associated to the kainate-type of glutamate receptor [START_REF] Ogura | Further evidence for calcium permeability of non-NMDA receptor channels in hippocampal neurons[END_REF][START_REF] Mat | The ionic mechanisms associated with the excitatory response of kainate, L-glutamate, quisqualate, ibotenate, AMPA and methyltetrahydrofolate on leech Retzius cells[END_REF][START_REF] Sonhof | An analysis of glutamate-induced ion fluxes across the membrane of spinal motoneurons of the frog[END_REF][START_REF] Lambert | Actions of excitatory amino acids on membrane conductance and potential in motoneurons[END_REF]. This result is surprising because the kainate receptor has classically been described as involved in excitatory synapses. The glutamateinduced inhibition may be the result from a modification of the relative permeabilities of Na + and K + ions, which would be specific of the presynaptic receptor-channel in crayfish CBTs (compared to the excitatory Na + /K + channel encountered in crayfish muscle; [START_REF] Dudel | Nonlinear voltage dependence of excitatory synaptic current in crayfish muscle[END_REF]Franke et al., 1986a). Such an effect could be due to the channel having a larger permeability for K + ions than the one encountered in excitatory kainate receptor-channel, while Na + permeability would be strongly reduced. Such relative permeabilities to Na + and K + would explain the very small amplitude of the depolarization induced by glutamate in CBTs.

Functionally, such characteristics would exclude any excitatory effect on the presynaptic neurotransmitter release but would allow the shunt of the afferent action potentials.

Considering the efficiency of the shunt performed on spike amplitude by such a small depolarization (a 2mV-depolarization elicited a mean decrease of spike amplitude of around 20 %; Fig. 4A), we can suppose that the amplitude of the depolarization did not completely reflect the increase in conductance. This is confirmed by the observation of large variations of input resistance of CBTs during glutamate micro-ejection (Fig. 4B).

Functional significance of the direct inhibitory control of CBTs by the MNs.

A number of authors investigated the role of presynaptic inhibition in the central nervous system. GABAergic presynaptic inhibition has been described to play a role in interjoint coordination during locomotion in crayfish (El Manira et al., 1991), and in the lamprey [START_REF] Grillner | Neuronal network generating locomotor behavior in lamprey: circuitry, transmitters, membrane properties, and simulation[END_REF]. In both vertebrates and invertebrates, presynaptic inhibition originating from central networks has been proposed to be involved in the selection of the sensory information adapted to the voluntary movement that is executed [START_REF] Asanuma | Function of somesthesic input during voluntary movements[END_REF][START_REF] Rudomin | Presynaptic modulation of spinal reflexes[END_REF]. In crayfish, but similar results were obtain in the cat [START_REF] Gossard | An intracellular study of muscle primary afferents during fictive locomotion in the cat[END_REF], [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF] described bursts of PADs that occurred exclusively at the transition between the activities of depressor MNs and levator MNs during organized fictive locomotion (see also Fig. 1). Le [START_REF] Ray | Neural mechanisms of reflex reversal in coxo-basipodite depressor motor neurons of the crayfish[END_REF] identified a polysynaptic pathway involved in the expression of the assistance reflex in crayfish locomotor network. They proposed that the rhythmic PADs previously described by [START_REF] Cattaert | Direct evidence for presynaptic inhibitory mechanisms in crayfish sensory afferents[END_REF] were one of the control mechanisms that regulate the shift between resistance and assistance reflexes. In the locust, GABA-mediated presynaptic inhibition originates from the sensory afferents of the femoral chordotonal organ [START_REF] Burrows | Synaptic potentials in the central terminals of locust proprioceptive afferents generated by other afferents from the same sense organ[END_REF]. By this mean, afferents accomplish a local gain control of the sensory input [START_REF] Burrows | A presynaptic gain control mechanism among sensory neurons of a locust leg proprioceptor[END_REF]. Here, we described a new type of presynaptic inhibition of the sensory afferents exerted directly by the MNs.

Although the exact function of such retrograde inhibitory control remains to be determined, there exist several observations that may help to understand its role in the locomotor network. First, "physiological" responses to glutamate application could only be met in the CBTs by applying an electrical stimulation to the whole motor nerve (Fig. 2B and Table 1), while it was never possible to observe any depolarizations in the CBTs when a single MN was intracellularly stimulating. These observations indicate the existence of an activation threshold of this negative presynaptic control (Fig. 9). Second, when every reciprocal inhibitions were blocked by picrotoxin superfusion, all MNs fired synchronously which induced large depolarizations in CBTs (Fig. 2A). These two observations suggest that MN-induced presynaptic inhibition could exert an automatic gain control of the sensory input in order not to saturate the MN activity. Contrary to the gain-control system described by Burrow and Matheson (1994) that used the sensory activity as origin of the negative control, the mechanism we describe uses the MN activity. This hypothesis is consistent with the fact that PADs of sensory origin does not seem to exist in CBTs. Consequently, the regulation of the gain of the sensory input synapses is devoted to the other element of sensory-motor loop, the MN itself (Fig. 9).

ABBREVATIONS

  methyl-D-aspartate PAD(s) primary afferent depolarization(s) sdPAD(s) slowly developing PAD(s)

FIG. 2 .

 2 FIG. 2. Pharmacology of sdPADs. (A) Perfusing picrotoxin (PTX, 10 -4 M) blocked the

  FIG. 7. Glutamate-induced depolarizations were affected by the non-NMDA pharmacological

TABLE LEGEND TABLE 1 .

 LEGEND1 Examples of CBT responses to motor nerve antidromic stimulation. The PADs, related to the locomotor rhythm, occurred at the transition between Dep and Lev bursts; second, slowly developing PADs (sdPADs) were recorded in phase with the bursting activity of one of the motor nerve (here the levator). The occurrence and time course of sdPADs were very strictly related to the levator instantaneous frequency (Lev n Inst. Freq.).

	FIGURE LEGENDS
	FIG. 1. Dual presynaptic control of sensory afferent signals. During pharmacologically induced
	effectiveness of the depolarizing response is symbolized by a number of "+", ranging from "0" fictive locomotion, alternated activities are recorded from the levator (Lev n) and the
	(no response) to "+++" (maximum response). (Pro, protractor nerve; Rem, remotor nerve; depressor (Dep n) antagonistic motor nerves. During such motor activity, two distinct
	aLev and pLev, anterior and posterior levator nerves; Dep, depressor nerve). depolarizing events could be recorded from the CBCO sensory terminals (CBT) : first, bursts
	of classically described

ACKNOWLEDGEMENTS

We are grateful to Dr. F. Clarac for laboratory facilities. This work was supported by the Centre National de la Recherche Scientifique (CNRS). D. Le Ray received a fellowship from the Ministère de l'Enseignement Supérieur Français.


Michael Peter Lettmann
email: michael.lettmann@tuwien.ac.at

Nicolas Peltier
email: nicolas.peltier@univ-grenoble-alpes.fr

A Tableaux Calculus for Reducing Proof Size

A tableau calculus is proposed, based on a compressed representation of clauses, where literals sharing a similar shape may be merged. The inferences applied on these literals are fused when possible, which can reduce the size of the proof. It is shown that the obtained proof procedure is sound, refutationally complete and can reduce the size of the tableau by an exponential factor. The approach is compatible with all usual refinements of tableaux.

Introduction

Tableau methods (see for instance [START_REF] De Rijke | Handbook of Tableau Methods[END_REF] or [START_REF] Hähnle | Tableaux and Related Methods[END_REF]) always played a crucial role in the development of new techniques for automated theorem proving. They are easy to comprehend and implement, well-adapted to interactive theorem proving, and, therefore, normally form the basis of the first proof procedure for any newly defined logic [START_REF] Fitting | First-Order Logic and Automated Theorem Proving[END_REF]. Nonetheless, they cannot compete with resolution-based calculi both in terms of efficiency and deductive power (i.e. proof length, see for instance [START_REF] Eder | Relative Complexities of First-Order Logic Calculi[END_REF]). This is partly due to the ability of resolution-based methods to generate lemmas and to simulate atomic cuts 3 in a feasible way. There have been attempts to integrate some restricted forms of cut into tableau methods, improving both efficiency and proof size (see for instance [START_REF] Letz | Controlled integration of the cut rule into connection tableau calculi[END_REF][START_REF] Hähnle | Tableaux and Related Methods[END_REF]). But, for more general forms of cuts, it is difficult to decide whether an application of the cut rule is useful or not, thus the rule is not really applicable during proof search. Instead, cuts may be introduced after the proof is generated, to make it more compact by introducing lemmas and fusing recurring patterns [START_REF] Hetzl | Algorithmic Introduction of Quantified Cuts[END_REF][START_REF] Leitsch | The problem of Π 2 -cut-introduction[END_REF].

In this paper, rather than trying to integrate cuts into the tableau calculus, we devise a new tableau procedure in which a proof compression, that is similar to the compressive power of a Π 2 -cut, is achieved by employing a shared representation of literals. Formal definitions will be given later, but we now provide a simple example to illustrate our ideas. Consider the schema of clause sets: { n i=1 p 0 (a i ), ∀y.¬p n (y)}∪{∀x.¬p i-1 (x)∨p i (x

) | i ∈ [1, n]}. A

closed tableau can

Funded by FWF project W1255-N23. 3 We recall that the cut rule consists in expanding a tableau by adding two branches with ¬φ and φ respectively, where φ is any formula (intuitively φ can be viewed as a lemma). A cut is atomic if φ is atomic.

be constructed by adding n copies of the clauses ¬p n (y j ) and ¬p i-1 (x j i ) ∨ p i (x j i ) (for i, j ∈ [1, n]) and unifying all variables x j i and y j with a j . One gets a tableau of size O(n 2 ). To make the proof more compact, we may merge the inferences applied for each a j , since each of these constants are handled in the same way. This can be done by first applying the cut rule on the formula ∃x.p 0 (x). The branch corresponding the ¬∃x.p 0 (x) can be closed by using the first clause. In the branch corresponding to ∃x.p 0 (x) a constant c is generated by skolemization and the branch can be closed by unifying x i and y with c. This yields a tableau of size O(n). Since it is hard to guess in advance whether such an application of the cut rule will be useful or not, we investigate another solution allowing the same proof compression. We represent the disjunction n i=1 p 0 (a i ) by a single literal p 0 (α), together with a set of substitutions {[α\a i ] | i ∈ [1, n]}. Intuitively, this literal states that p 0 (α) holds for some term α, and the given set of substitutions specifies the possible values of α. In the following, we call such variables α abstraction variables. The clauses are kept as compact as possible by grouping all literals with the same heads and in some cases inferences may be performed uniformly regardless of the value of α. In our example we get a tableau of size O(n) by unifying x j i and y j with α, this tableau may be viewed as a compact representation of an ordinary tableau, obtained by making n copies of the tree, with α = a 1 , . . . , a n . If we find out that an inference is applicable only for some specific value(s) of α (e.g., if one wants to close a branch by unifying p 0 (α) with a clause ¬p 0 (a 1 )), then one may "separate" the literal by isolating some substitution (or sets of substitutions) before proceeding with the inference.

In this paper, we formalize these ideas into a tableau calculus called Mtableau. Basic inference rules are devised to construct M -tableaux and a strategy is provided to apply these rules efficiently, keeping the tableau as compact as possible. We prove that the procedure is sound and refutationally complete and that it may reduce the size of the proofs by an exponential factor. Our approach may be combined with all the usual refinements of the tableau procedure. 4

Notations

We briefly review usual definitions (we refer to, e.g., [START_REF]Handbook of Automated Reasoning[END_REF] for details). Terms, atoms and clauses are built as usual over a (finite) set of function symbols Σ (including constants, i.e. nullary function symbols), an (infinite and countable) set of variables V and a (finite) set of predicate symbols Ω. The set of variables occurring in an expression (term, atom or clause) e is denoted by V(e). For readability, a term f (t) is sometimes written f t. Ordinary (clausal) tableaux are trees labelled by literals and built by applying Expansion and Closure rules, the Expansion rule expands a leaf by n children labelled by literals l 1 , . . . , l n , where a copy of l 1 ∨ • • • ∨ l n occurs in the clause set at hand, and the Closure rule closes a branch by unifying the atoms of two complementary literals. A substitution is a function (with finite domain) mapping variables to terms. A substitution mapping x i to t i (for i ∈ [1, n]) is written [(x 1 , . . . , x n )\(t 1 , . . . , t n )]. The identity substitution (for n = 0) is denoted by id . The image of an expression e by a substitution σ is defined inductively as usual and written eσ.

A Shared Representation of Literals

We introduce the notion of an M -literal, that is a compact representation of a disjunction of ordinary literals with the same shape. The interest of this representation is that it will allow us to perform similar inferences in parallel on all these literals. We assume that V is partitioned into two (infinite) sets V o and V a . The variables in V o are ordinary variables. They may be either universally quantified variables in clauses, or rigid variables in tableaux. The variables in V a are called abstraction variables. These are not variables in the standard sense, but can been seen rather as placeholders for a term that may take different values in different literals or branches. These variables will permit to share inferences applied on different literals. The set of ordinary variables (resp. abstraction variables) that occur in a term t is denoted by

V o (t) (resp. V a (t)). A renaming is an injective substitution σ such that x ∈ V o ⇒ xσ ∈ V o and α ∈ V a ⇒ ασ ∈ V a .
Definition 1 (Syntax of M -Clauses). An M -literal is either true or a triple L, t, S , where:

-L is either a predicate symbol P or the negation of a predicate symbol ¬P , -t is an n-tuple of terms, where n is the arity of P , and S is a set of substitutions σ with the same domain D ⊆ V a ( t) (by convention D is empty if S = ∅) and such that V( tσ) ∩ D = ∅.

An M -clause is a set of M -literals, often written as a disjunction.

With a slight abuse of words, we will call the set D in the above definition the domain of S (denoted by dom(S)). The semantics of M -clauses is defined by associating each M -literal with an ordinary clause (or true): Definition 2 (Semantics of M -Clauses). For every M -literal l, we denote by formula(l) the formula defined as follows (with the convention that empty disjunctions are equivalent to false):

formula( L, t, S ) def = θ∈S L( tθ) formula(true) def = true
For every M -clause C, we denote by formula(C) the clause l∈C formula(l). For every set of M -clauses C, we denote by formula(C) the formula (in conjunctive normal form) C∈C formula(C).

We write E E iff formula(E) = formula(E ) (up to the usual properties of ∨ and ∧: associativity, commutativity and idempotence).

Example 1. Let P be a unary predicate, Q be a binary predicate, c be a constant, f be a unary function, x be an ordinary variable, and α, β, γ be abstraction variables. The triples l 1 = P, α, {[α\f (c)]} and

l 2 = Q, (β, f (γ)), {[(β, γ)\(f (c), c)], [(β, γ)\(c, f (c))]} are M -literals, and formula(l 1 ) = P (f (c)) formula(l 2 ) = Q(f (c), f (c)) ∨ Q(c, f (f (c)))
The common shape Q(•, f (•)) is shared between the two literals in the second clause.

Remark 1. Observe that if S = ∅ then formula( L, t, S ) = false, i.e. L, t, S denotes an empty clause. Moreover, any ordinary literal may be encoded as an M -literal where the set of substitutions is a singleton, e.g., the formula corresponding to P, (a, x), {[α\a]} is P (a, x). Also, an M -literal L, t, {σ} is always equivalent to L, tσ, {id } .

The application of a substitution σ to an M -literal is defined as follows:

(true)σ def = true L, t, S σ def = L, tσ , {θσ | θ ∈ S}
where σ denotes the restriction of σ to the variables not occurring in dom(S). -S = ∅ and formula(l) = false; -S = {id } and formula(l) = L( t).

Proof. The identity is the only substitution with empty domain.

A given ordinary clause may be represented by many different M -clauses, for instance P (a) ∨ P (b) may be represented as P, (a), {id } ∨ P, (b), {id } or P, (α), {[α\a], [α\b]} , or even P, (α), {[α\a], [α\b]} ∨ Q, (β), ∅ . In practice it is preferable to start with a representation in which useless literals are deleted and in which the remaining literals are grouped when possible. This motivates the following:

Definition 3. An M -clause C is in bundled normal form (short: BNF) if it satisfies the following conditions. -For every M -literal L, t, S ∈ C, S = ∅. -If true ∈ C then C = {true}. -For all distinct literals L 1 , t1 , S 1 , L 2 , t2 , S 2 ∈ C, L 1 is distinct from L 2 . An M -clause set C is in BNF if all M -clauses of C are in BNF. Example 3. Let l 1 def = P, α, {[α\f (c)]} , l 2 def = P, β, {[β\f (c)]} , l 3 def = Q, (β, f γ), {[(β, γ)\(f (c), c)], [(β, γ)\(c, f (c))]} , and
l 4 def = Q, (β, γ), {[(β, γ)\(f (c), c)], [(β, γ)\(c, f (c))]} be M -literals. The M -clause {l 3 , l 4 } is not in BNF while the M -clauses {l 1 , l 4 } and {l 2 , l 4 } are in BNF. Definition 4. An M -clause C is well-formed if for all distinct literals l = L 1 , t1 , S 1 and m = L 2 , t2 , S 2 in C, dom(S 1 ) ∩ dom(S 2 ) = ∅. Example 4. Consider the two M -clauses C 1 := {l 1 , l 4 } and C 2 := {l 2 , l 4 } of Example 3. C 1 is well-formed, C 2 is not well-formed. By renaming, C 2 can be transformed into C 1 .
It is clear that every M -clause can be transformed into an equivalent wellformed M -clause by renaming. In the following, we shall implicitly assume that all the considered M -clauses are well-formed.

{[(β, γ)\(f (c), f (c))], [(β, γ)\(c, f (f (c)))], [(β, γ)\(f (c), c)], [(β, γ)\(c, f (c))]}

A Tableaux Calculus for M -Clauses

In this section, we devise a tableaux calculus for refuting sets of M -clauses. This calculus is defined by a set of inference rules, that, given an existing tableau T , allow one to:

1. Expand a branch with new children, by introducing a new copy of an Mclause of the set at hand. 2. Instantiate some of the (rigid) variables occurring in the tableau. 3. Separate shared literals inside an M -clause, so that different inferences can be applied on each of the corresponding branches. The rule can be applied on nodes that are not leaves.

Steps 1 and 2 are standard, but Step 3 is original.

Definition 5 (Pre-Tableau). A pre-tableau is a tree T where vertices are labelled by M -literals or by false. We call the direct successors of a node its children. The root is the (unique) node that is not a child of any node in T and a leaf is a node with no child. A path P is a sequence of nodes

(ν 1 , . . . , ν n ) such that ν i+1 is a child of ν i for i ∈ [1, n -1]
. Furthermore, we call ν 1 the initial node of P and ν n the last node of P . A branch is a path such that the initial node is the root and the last node is a leaf. With a slight abuse of words we say that a branch contains an M -literal l if it contains a node labelled by l.

The descendants of a node ν are inductively defined as ν and the descendants of the children of ν. The subtree of root ν in T is the subtree consisting of all the descendants of ν, as they appear in T .

If ν is a non-leaf node with exactly n > 0 children ν 1 , . . . , ν n labelled by Mliterals l 1 , . . . , l n respectively, then the formula associated with ν is defined as:

n i=1 formula(l i ).
We say that an M -literal L, t, S (resp. a node ν labelled by L, t, S ) introduces an abstraction variable α if α ∈ dom(S) (as shown in Proposition 2, the abstraction variables are introduced by exactly one M -literal or node in an M -tableau). Definition 6. Let T be a pre-tableau and σ be a substitution. Then T σ denotes the result of applying σ to all M -literals labelling the nodes of T . Definition 7 (Tableau for a Set of M -Clauses). An M -tableau T for a set of M -clauses C is a pre-tableau built inductively by applying the rules Expansion, Instantiation and Separation to an initial tableau containing only one node, labelled by true (also called the initial M -literal).

In the following, the word "tableau" always refers to an M -tableau, unless specified otherwise (we use the expression "ordinary tableau" for standard ones).

The rules are defined as follows (in each case, T denotes a previously constructed tableau for a set of M -clauses C).

Expansion Rule. Let λ be a leaf of T , and C be an element of C not containing true. Let C be a copy of C where all variables that occur also in T are renamed such that C share no variable5 with T . The pre-tableau T constructed by adding a new child labelled by l to λ for each l ∈ C is a tableau for C. Instantiation Rule. Let t be a term and x ∈ V o such that for all nodes ν, ν , if ν is labelled by an M -literal containing x and ν introduces an abstraction variable α ∈ V a (t), then ν is a proper descendant of ν . Then T [x\t] is a tableau for C.

Remark 2. Observe that if t contains no abstraction variables then the condition always holds, since no node ν satisfying the above property exists. In practice, the Instantiation rule should of course not be applied with an arbitrary variable and term. Unification will be used instead to find the most general instantiations closing a branch. A formal definition will be given later (see Definition 11).

Example 6. Let T 1 def = true ¬P, x, {id} P, α, {[α\a], [α\b]} T 2 def = true P, α, {[α\a], [α\b]} ¬P, x, {id}
be two tableaux for some set of M -clauses C. The pre-tableau T 1 [x\α] is not a tableau, because x is substituted by a term containing an abstraction variable α, and x occurs above the literal introducing α. On the other hand, T 2 [x\α] is a tableau.

Separation Rule. The rule is illustrated in Figure 1 towards Figure 3. Let ν be a non-leaf node of T . Let µ be a child of ν, labelled by l = L, t, S . Let r = tθ be an instance of t, with dom(θ) = dom(S) and V a ( tθ) ∩ dom(S) = ∅. Let S 1 be the set of substitutions σ ∈ S such that there exists a substitution σ with tσ = rσ and every variable in dom(σ ) is an abstraction variable not occurring in T , and let S 2 def = S \ S 1 . Assume that S 1 = ∅. We define the new literal l def = L, r, {σ | σ ∈ S 1 } . The Separation rule is defined as follows:

1. We apply the substitution θ to T6 . 2. We replace the label l of µ by l . 3. We add a new child to the node ν, labelled by a literal L, t, S 2 .

Observe that if S 2 = ∅ then formula( L, t, S 2 ) = false hence the third step may be omitted, since the added branch is unsatisfiable anyway. The rule does not apply if S 1 is empty.

l 4 := Q, (β, γ), {[(β, γ)\(f c, c)], [(β, γ)\(z, f c)], [(β, γ)\(f z, f c)]}
be M -literals and C = {{l 1 , l 4 }, {l 2 }, {l 3 }} be an M -clause set in BNF. Applying three times the Expansion rule, we can derive the tableau where m is the label of node ν and T1, T2, and T3 are possibly empty subtrees.

true ¬P, α , {[α \f c]} Q, (β, γ), {[(β, γ)\(f c, c)], [(β, γ)\(z, f c)], [(β, γ)\(f z, f c)]} ¬Q, (β , γ ), {[(β , γ )\(f x, y)]} P, α, {[α\f c]}
Fig. 2. The subtree after an application of the Separation rule.

. . .

mθ l T 3 θ L, t, S 2 T 2 θ T 1 θ
where m is the label of node ν and T1, T2, and T3 are possibly empty subtrees.

Fig. 3. The subtree without redundant substitutions after an application of the Separation rule. true

¬P, f c, {id} Q, (f δ, γ * ), {[(δ, γ * )\(c, c)], [(δ, γ * )\(z, f c)]} ¬Q, (β , γ ), {[(β , γ )\(f x, y)]} Q, (β, γ), {[(β, γ)\(z, f c)]} P, f c, {id}
After some further applications of the Separation and Expansion rules, we are able to construct the following tableau by applying the Instantiation rule with the substitutions

[z\f x ], [y\f c], [x\δ], [y\γ * ]. true ¬P, f c, {id} Q, (f δ, γ * ), {[(δ, γ * )\(c, c)], [(δ, γ * )\(f x , f c)]} ¬Q, (f δ, γ * ), {id} Q, (f x , f c), {id} ¬Q, (f x , f c), {id} P, f c, {id} 5
{ ¬P, f c, ∅ , Q, (f δ, γ * ), {[(δ, γ * )\(c, c)], [(β, γ)\(c, f f x )]} , ¬Q, (f δ, γ * ), ∅ }, { ¬P, f c, ∅ , Q, (f x , f c), ∅ , ¬Q, (f x , f c), ∅ }, and
{ ¬P, f c, ∅ , P, f c, ∅ }.
All of them are closed and so the tableau is closed. Observe that the inferences closing the branches corresponding to the literals Q(f (c), c) and Q(f (z), f (c)) in {l 1 , l 4 } are shared in the constructed tableau (both branches are closed by introduced suitable instances of l 3 ), whereas the literal Q(z, f (c)) is handled separately (by instantiating z by f (x ) and using yet another instance of l 3 ).

Proposition 2. Let T be a tableau. If ν 1 and ν 2 are distinct nodes in T , labelled by the M -literals L 1 , t1 , S 1 and L 2 , t2 , S 2 respectively, then S 1 and S 2 have disjoint domains.

Proposition 3. Let T be a tableau for a set of M -clauses C. For every non-leaf node ν in T , the formula associated with ν (as defined in Definition 5) is an instance of a formula formula(C), where C is a renaming of an M -clause in C.

Proof. It suffices to show that all the construction rules preserve the desired property.

-Expansion. The property immediately holds for the nodes on which the rule is applied, by definition of the rule. The other nodes are not affected. -Instantiation. By definition, the formula associated with a node ν in the final tableau is an instance of the formula associated with ν in the initial one. Thus the property holds. -Separation. The nodes occurring outside of the subtree of root µ are not affected. By definition, the formula associated with the descendants of µ in the new tableau are instances of formulas associated with nodes of the initial tableau. Thus it only remains to consider the node ν. The formula associated with ν in the final tableau is obtained from that of the initial one by removing the formula corresponding to an M -literal l = L, t, S and replacing it by formula(l ) ∨ formula( L, t, S 2 ). Since l = L, r, {σ | σ ∈ S 1 } , we have formula(l ) = σ∈S1 L(rσ ) = σ∈S1 L( tσ) (since tσ = rσ by definition of the Separation rule). Thus formula(l ) ∨ formula( L, t, S 2 ) = formula( L, t, S ) and the proof is completed.

Proposition 4. Let T be a tableau for C. Let α ∈ V a be a variable introduced in a node ν and assume that α occurs in an M -literal labelling a node µ. Then µ is a descendant of ν.

Lemma 2. Let T be a closed tableau for C and let T be the tableau after applying once the Separation rule to a node ν of T with a child µ labelled with l. Then there is at most one branch B in T that is not closed. Moreover, this branch necessarily contains the node labelled by L, t, S 2 (see Figure 3). In particular, if S 2 is empty then L, t, S 2 is false and T is closed.

Theorem 1 (Soundness). If a set of M -clauses C admits a closed tableau T then C is unsatisfiable.

Proof. We prove soundness by transforming T into a closed tableau that contains only M -literals where the substitution set is {id } or ∅. Due to Proposition 3, the resulting tableau then corresponds to an ordinary tableau. The soundness of ordinary tableau then implies the statement.

We transform the tableau T by an iterative procedure. We always take an arbitrary topmost node ν labelled with an M -literal l = L, t, S where S = {id } and S = ∅. Then we consider a substitution θ ∈ S and we apply the Separation rule with the tuple tθ. We have tθ = tθid and if σ ∈ S \ {θ}, then tσ = tθ, hence there is no substitution σ with tσσ = tθ, such that dom(σ ) only contains fresh variables. Consequently, the rule splits S into a singleton S 1 = {θ} and S 2 = S 1 \{θ}. The literal l gets replaced by l = L, tθ, {id } and we add the node µ labelled with L, t, S 2 . By Lemma 2, there is at most one non-closed branch, i.e. the branch ending with the node µ is the only open branch. We consider a copy T ν of the subtree of root ν in T , renaming all variables introduced in T ν by fresh variables. We replace the root node of T ν by L, t, S 2 and replace the subtree of root µ in the tableau by T ν . It is easy to check that the obtained tableau is a closed tableau for C. Furthermore, the length of the branches does not increase, the number of non-empty substitutions occurring in the M -literals does not increase, and it decreases strictly in l and L, t, S 2 . This implies that the multiset of multisets {|{σ ∈ S 1 | σ = id }|, . . . , |{σ ∈ S n | σ = id }|} of natural numbers, where { L i , ti , S i | i ∈ [1, n]} is a branch in T is strictly decreasing according to the multiset extension of the usual ordering. Since this ordering is well-founded, the process eventually terminates, and after a finite number of applications of this procedure we get a tableau only containing nodes labelled with M -literals whose substitution set is equal to {id } or ∅.

Remark 3. As a by-product of the proof, we get that the size of the minimal ordinary tableau for a clause set formula(C) is bounded exponentially by the size of any closed tableau for C. Indeed, we constructed an ordinary tableau from an M -tableau T in which every branch (l 1 , . . . , l n ) in T is replaced by (at most) k n branches, where k is the maximal number of substitutions in l i . In Section 7, we shall prove that this bound is precise, i.e. that our tableau calculus allows exponential reduction of proof size w.r.t. ordinary (cut-free) tableaux.

Completeness

Proving completeness of M -tableau is actually a trivial task, since one could always apply the Separation rule in a systematic way on all M -literals to trans-form them into ordinary literals (as it is done in the proof of Theorem 1), and then get the desired result by completeness of ordinary tableau. However, this strategy would not be of practical use. Instead, we shall devise a strategy that keeps the M -tableau as compact as possible and at the same time allows one to "simulate" any application of the ordinary expansion rules. In this strategy, the Separation rule is applied on demand, i.e. only when it is necessary to close a branch. No hypothesis is assumed on the application of the ordinary expansion rules, therefore the proposed strategy is "orthogonal" to the usual refinements of ordinary tableaux, for instance connection tableaux7 [START_REF] Letz | Model elimination and connection tableau procedures[END_REF] or hyper-tableaux8 [START_REF] Baumgartner | Hyper Tableaux -The Next Generation[END_REF]. Thus our approach can be combined with any refutationally complete tableau procedure [START_REF] Hähnle | Tableaux and Related Methods[END_REF].

The main idea denoted by simulate a strategy is to do the same steps as in ordinary tableau, while keeping M -clauses as compressed as possible. If ordinary tableau expands the tableau by a clause, we expand the tableau with the corresponding M -clause, and if a branch is closed in the ordinary tableau, then the corresponding branch is closed in the M -tableau. This last step is not trivial: Given two ordinary literals P ( t) and ¬P (r) the ordinary tableau might compute the most general unifier (mgu) of t and r. But in the presented formalism, the two literals might not appear as such, i.e. there are no literals m = P, t, {id } and k = ¬P, r, {id } . In general, there are only M -literals m = P, t , S 1 and k = ¬P, r , S 2 such that t θ = t and r ϑ = r, where θ and ϑ denote the compositions of the substitutions occurring in the M -literals in the considered branch. Note also that, although t and r are unifiable, the Instantiation rule cannot always be applied to unify them and close the branch. Indeed, the domain of the mgu may contain abstraction variables, whereas the Instantiation rule only handles universal variables. For showing completeness, it would suffice to apply the Separation rule on each ancestor of k and m involved in the definition of θ or ϑ, to create a branch where the literals m and k appear explicitly. Thereby, we would lose a lot of the formalisms benefit. Instead, we shall introduce a strategy that uses the Separation rule only if this is necessary for making the unification of t and r feasible (by mean of the Instantiation rule). Such applications of the Separation rule may be seen as preliminary steps for the Instantiation rule. This follows the maxim to stay as general as possible because a more general proof might be more compact.

In the formalisation of the Instantiation rule we ensured soundness by allowing abstraction variables only to occur in descendants of the literal that introduced the variable. This has a drawback to our strategy: The unification process that we try to simulate can ask for an application of the Instantiation rule which would cause a violation of this condition for abstraction variables if we follow the procedure in the former paragraph. We thus have to add further applications of the Separation rule to ensure that this condition is fulfilled. Definition 9. Let B = (ν 0 , ν 1 , . . . , ν n ) be a path in a tableau T where ν 0 is the initial node of T and each node ν i (with i > 0) is labelled by L i , ti , S i .

An abstraction substitution for B is a substitution η n . . . η 1 with η i ∈ S i , for i = 1, . . . , n.

A conflict in a branch B is a pair ( ti , tj ) with i, j ∈ [1, n], L i and L j are dual and ti and tj are unifiable. A conflict is η-realizable if η is an abstraction substitution for B such that ti η and tj η are unifiable.

In practice, we do not have to check that a conflict is realizable (this would be costly since we have to consider exponentially many substitutions).

If ( t, t ) is a conflict then t and t are necessarily unifiable, with some mgu θ. As mentioned before, this does not mean that a branch with conflict can be closed. Moreover, according to the restriction on the Instantiation rule, a variable x cannot be instantiated by a term containing an abstraction variable α, if x occurs in some ancestor of the literal introducing α in the tableau. This motivates the following: Definition 10. A variable α ∈ V a is blocking for a conflict ( t, t ), where θ = mgu( t, t ) if α ∈ dom(θ) or α occurs in a term xθ, where x ∈ V o and x occurs in a literal labelling an ancestor of the node introducing α.

Finally, we introduce a specific application of the Separation rule which allows one either to "isolate" some literals in order to ensure that they have a specific "shape" (as specified by a substitution), or to eliminate abstraction variables completely if needed. Definition 11. If σ is a substitution, we denote by dom a (σ) the set of variables α ∈ V a such that ασ ∈ V a .

A tableau is compact if it is constructed by a sequence of applications of the tableau rule in which:

-The Instantiation rule is applied only if the tableau contains a branch with a conflict ( t, t ), with no blocking variable. Each variable x ∈ dom(σ) is replaced by a term tσ, where σ = mgu( t, t ) (since there is no blocking variable it is easy to check that the conditions on the Instantiation rule are satisfied). Afterwards, it is clear that the branch is closed. -The Separation rule is applied on a node labelled by L, t, S , using a substitution θ only if there exists a conflict ( t, t ) with σ = mgu( t, t ) such that one of the following conditions holds: 1. dom(S) contains a blocking variable in dom a (σ) and θ is defined as follows: dom(θ) = dom(S)∩dom a (σ), xθ = xσ if xσ is a variable, otherwise xθ is obtained from xσ by replacing all variables by pairwise distinct fresh abstraction variables. 2. Or dom(S) contains a blocking variable not occurring in dom a (σ), and θ ∈ S.

The applications of the Separation rule in Definition 11 are targeted at making the closure of the branch possible by getting rid of blocking variables, while keeping the tableau as compact as possible (thus useless separations are avoided).

Example 9. For instance, assume that we want to close a branch containing two literals l = L, (α), {[α\f (a)], [α\f (b)], [α\a]} and l = ¬L, f (x), {id } . To this aim, we need to ensure that α is unifiable with f (x). This is done by applying the separation rule (Case 1 of Definition 11) with the substitution [α\f (β)], so that α has the desired shape. This yields: L, (f (β)), {[β\a], [β\b]} Afterwards, if x does not occur before l in the branch then the branch is closed by unifying x with β. If x occurs before l, then this is not feasible since this would the condition on the Instantiation rule, and we have to apply the Separation rule again (Case 2) to eliminate β, yielding (for instance) L, (f (a)), {id } . The direct application of the Separation rule with, e.g., θ = [α\f (a)] is forbidden in the strategy.

Theorem 2 (Completeness). Let C be a clause set and C be an M -clause set with formula(C) C. If C is unsatisfiable, then there is a closed compact tableau for C.

Proof. For an M -clause C i ∈ C, we denote by C i the ordinary clause in C with formula(C i ) formula(C i ). W.l.o.g. we can assume that clauses do not appear twice, neither in C nor in C. Now, we can perform a proof search based on ordinary tableau starting with C (using any complete strategy) yielding a closed tableau, built by applying the usual Expansion and Closure rules. In the following, T will denote an already constructed ordinary tableau for C and T will represent the corresponding M -tableau for C. More precisely, the tableau T is constructed in such a way that there exists an injective mapping h from the nodes in T to those in T, a function ν → η ν mapping each node ν in T labelled by some literal L, t, S to an abstraction substitution η and a substitution ϑ (with dom(ϑ) ⊆ V o ) such that the following property holds (denoted by ( )):

1. The root of T is mapped to the root of T. 2. If ν is a child of ν then h(ν) is a child of h(ν ). 3. For any path (ν 0 , . . . , ν n ), if ν n is labelled by an M -literal L, t, S , then h(ν n ) is labelled by a literal L( t)η νn . . . η ν1 ϑ.

If a branch of the form (h(ν

0 ), . . . , h(ν n )) is closed in T, then (ν 0 , . . . , ν n ) is closed in T .
Note that the mapping is not surjective in general (T may be bigger than T ). By ( ), if T is closed then T is also closed, which gives us the desired result.

It is easy to check that applying the Separation rule on a node ν i in a branch (ν 0 , . . . , ν n ) in T preserves ( ), provided it is applied using a substitution θ (as defined in the Separation rule) that is more general than

η νn • • • • • η ν1 .
The tableau T is constructed inductively as follows. For the base case, we may take T = T = true and ( ) trivially holds.

Expansion: The Expansion rule of ordinary tableaux allows one to expand the tableau by an arbitrary clause C i of C. We define the corresponding tableau for C as the tableau expanded by C i . The mappings h and η ν may be extended in a straightforward way so that ( ) is preserved (the unique new node ν in T may be mapped to an arbitrary chosen new node in T).

Closure: Assume that a branch in T is closed by applying some substitution σ, using two literals L( t) and ¬L(r), where σ = mgu( t, r). If one of these literals do not occur in the image of a branch of T then it is clear that the operation preserves ( ) (except that the substitution ϑ is replaced by ϑσ), hence no further transformation is required on T . Otherwise, by ( ), there is a branch B = (ν 0 , . . . , ν n ) in T where for every i ∈ [1, n], ν i is labelled by l i = L i , t i , S i , two numbers j, k ∈ N such that L j = L, L k = ¬L, t j ηϑ = t and t k ηϑ = r, with η = η νn . . . η ν1 .

By definition, ( t j , t k ) is an η-realizable conflict. Let σ be the mgu of t j and t k . If there is no blocking variable for ( t j , t k ), then the Instantiation rule applies, replacing every variable x ∈ dom(σ ) by xσ , and the branch may be closed. By definition ηϑσ is a unifier of t and r, hence ηϑσ = σ θ , for some substitution θ . By definition, the co-domain of η contains no abstraction variables, thus θ = ηϑ , with dom(ϑ ) ⊆ V o , and ϑσ = σ ϑ . The application of the rule preserves ( ), where ϑ is replaced by the substitution ϑ . Indeed, consider a node ν in T , initially labelled by a literal L, t, S , where h(ν) is labelled by L( t)η νn . . . η ν1 ϑ. After the rule application, ν is labelled by L, tσ , Sσ , h(ν) is labelled by L( t)η νn . . . η ν1 ϑσ, and the substitutions η νi are replaced by η νi σ . Since dom(σ ) ∩ V a = ∅, it is clear that σ η νn . . . η ν1 σ ϑ = η νn . . . η ν1 σ ϑ = η νn . . . η ν1 ϑσ.

Otherwise, the set of blocking variables is not empty, and since all abstraction variables occurring in the tableau must be introduced in some node, there exists l ∈ [1, n] such that dom(S l ) contains a blocking variable. According to Definition 11, the Separation rule may be applied on ν l (it is easy to check that all the application conditions of the rule are satisfied). In Case 1 (of Definition 11), θ is more general than σ by definition, and since η νn • • • • • η ν1 ϑσ is a unifier of t j and t k , the mgu σ must be more general than η νn • • • • • η ν1 . In Case 2, we can take θ = η ν l , which is more general than η νn • • • • • η ν1 (since the substitutions η ν have disjoint domains). Thus the property ( ) is preserved.

This operation is repeated until the set of blocking variables is empty, which allows us to apply the Instantiation rule as explained before. The process necessarily terminates since each application of the Separation rule either increases the size of the tableau (either by adding new nodes, or by instantiating a variable by a non variable term), or does not increase the size of the tableau but strictly reduces the number of abstraction variables. Furthermore, by ( ), the size of T is smaller than that of T.

An Exponentially Compressed Tableau

In this section, we will show that the presented method is able to compress tableaux by an exponential factor. This corresponds to an introduction of a to other logics, and even to other calculi, including saturation-based procedures. It would also be interesting to combine this approach with other techniques for reducing proof size, for instance variable splitting [START_REF] Hansen | Incremental variable splitting[END_REF], or with techniques for the incremental construction of closures [START_REF] Giese | Incremental Closure of Free Variable Tableaux[END_REF].

A current restriction of the calculus is that no abstraction variables may occur above their introduction (see the condition on the Instantiation rule in Section 4). This restriction is essential for soundness: without it, one could for instance construct a closed tableau for the (satisfiable) set of M -clauses {{l}, {l }}, with l = L, (x, α), {[α\a, α\b]} and l = L, (β, y), {[β\a, β\b]} , by replacing x by α and y by β. We think that this condition can be relaxed by defining an order over the abstraction variables. This would yield a more flexible calculus, thus further reducing proof size. It would be interesting to know whether the exponential bound of Remark 3 still holds for the relaxed calculus. An ambitious long-term goal is to devise extensions of M -tableaux with the same deductive power of cuts, i.e. enabling a non-elementary reduction of proof size.

Example 2 .Proposition 1 .

 21 Let l = P, (α, x), {[α\x], [α\y]} and σ = [x\a]. Then: lσ = P, (α, a), {[α\a], [α\y]} Let l = Q, (α), {[α\a], [α\b]} and θ = [α\a]. Then l θ = l . Let l = L, t, S be an M -literal. If dom(S) = ∅, then one of the following conditions hold:

Lemma 1 .Example 5 .

 15 Let F be a formula in conjunctive normal form. Then there is an M -clause set C in BNF such that formula(C) F. Consider the clause {l 3 , l 4 } of Example 3. It can be written in BNF as Q, (β, γ), S , where S denotes the following set of substitutions:

Example 7 .

 7 Letl 1 := P, α, {[α\f c]} , l 2 := ¬P, α , {[α \f c]} , l 3 := ¬Q, (β , γ ), {[(β , γ )\(f x, y)]} , and

Fig. 1 .

 1 Fig. 1. The initial subtree in the Separation rule.

1 where

 1 m is the label of node ν and T1, T2, and T3 are possibly empty subtrees. Now, we apply two times the Separation rule. First we choose m of Figure 1 to be true and l to be ¬P, α , {[α \f c]} , where the substitution θ is [α \f c] (hence we get S 1 = {id }). Afterwards, we choose analogously ¬P, f c, {id } (which is the result of the first application) and P, α, {[α\f c]} , with the substitution [α\f c]. Both times, the tuple r of the Separation rule is f c (with S 2 = ∅ in both cases). This leads to the tableau: true ¬P, f c, {id} Q, (β, γ), {[(β, γ)\(f c, c)], [(β, γ)\(z, f c)], [(β, γ)\(f z, f c)]} ¬Q, (β , γ ), {[(β , γ )\(f x, y)]} P, f c, {id} Afterwards, we again apply the Separation rule, to modify the node labelled with l 4 where r = (f δ, γ * ) and S 2 = {[(β, γ)\(z, f c)]}.

Soundness Definition 8 .Example 8 .

 88 Let T be a pre-tableau or a tableau. A branch B of T is closed if it contains false or two nodes labelled by literals L 1 , t1 , S 1 , L 2 , t2 , S 2 such that t1 = t2 , L 1 = P , L 2 = ¬P for some predicate symbol P . The (pre)-tableau T is closed iff all branches of T are closed. The final tableau of Example 7 contains three branches, i.e.

Due to the limited number of pages, we omit proofs that are not necessary for the understanding of the method. A full version can be found in[START_REF] Lettmann | A Tableaux Calculus for Reducing Proof Size[END_REF].

Note that both ordinary and abstraction variables are renamed.

Actually, due to the above conditions, the variables in dom(θ) only occur in the subtree of root µ, hence θ only affects this subtree.

Connection tableaux can be seen as ordinary tableaux in which any application of the Expansion rule must be followed by the closure of a branch, using one of the newly added literals and the previous literal in the branch.

Hyper-tableaux may be viewed in our framework as ordinary tableaux in which the Expansion rule must be followed by the closure of all the newly added branches containing negative literals.

In a Π2-cut, the cut formula is of the form ∀x∃yA where A is a quantifier-free formula.

single Π 2 -cut 9 (see [START_REF] Leitsch | The problem of Π 2 -cut-introduction[END_REF]). As a simplified measurement of the size of a tableau we consider the number of nodes. Let us consider the schema of M -clause sets

where ᾱ = (α 1 , α 2 ), β = (β 1 , β 2 ), γ = (γ 1 , γ 2 ), and δ = (δ 1 , δ 2 ) for n ∈ N. Then we can construct a closed tableau for C n whose size is linear w.r.t. n:

The clause set schema C n is a simplified variant of the example in [9, Section 3 and 9] and one can easily verify that an ordinary tableau method is of exponential size of n. Just consider the term instantiations which are necessary for an ordinary tableau:

Obviously, x n in l n 4 is substituted with n n-1 terms. These correspond to the instantiations defined in [9, Theorem 13].

Future Work

From a practical point of view, algorithms and data-structures have to be devised to apply the above rules efficiently, especially to identify conflicts and blocking substitutions in an incremental way. In the wake of this, experimental evaluations based on an implementation are reasonable. While the procedure is described for first-order logic, we believe that the same ideas could be profitably applied