Pierre Fraigniaud
email: pierre@lri.fr.

Cyril Gavoille
email: gavoille@labri.fr.

David Ilcinkas
email: ilcinkas@lri.fr.

Andrzej Pelc
email: pelc@uqo.ca

Distributed Computing with Advice: Information Sensitivity of Graph Coloring

Keywords: network algorithm, graph coloring, distributed computing

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution.

In this paper, we study the information sensitivity of distributed graph coloring. We use the classical LOCAL model in which arbitrary messages can be exchanged between neighbors in one round. Originally, each node knows only its own ID. All additional information about the graph may be given to nodes as advice from an oracle knowing the entire graph. Linial (1992) proved that the minimum time of 3-coloring (without advice) is Θ(log * n) for n-node cycles and Θ(D) for the class of trees of diameter D. We show that Ω(n/ log (k) n) bits of advice are needed, for any constant k, in order to beat the Θ(log * n) time of 3-coloring a cycle. Hence, 3-coloring a cycle is information insensitive. Similarly, we show that the same number of bits is needed in order to 3-color all n-node trees in time Θ(log * n). We also show that Ω(n) bits of advice are needed for 3-coloring in constant time, both for cycles and trees. Thus fast coloring of cycles and trees requires essentially as much information as if colors were explicitly assigned to nodes. In fact, our lower bounds hold not only for the total number of bits of advice given to nodes but also for the number of nodes that must be informed (i.e., the number of nodes that are given at least one bit of advice).

Introduction

This work is a part of a recent project aiming at studying the quantitative impact of knowledge on the efficiency when computing with distributed entities (nodes of a distributed system, mobile users in ad hoc networks, etc.). Indeed, as observed by Linial [START_REF]Locality in distributed graph algorithms[END_REF], "within the various computational models for parallel computers, the limitations that follow from the local nature of the computation are specific to the distributed context". Two frameworks have been considered for analyzing the limitations incurring because of the local nature of the distributed computation. One aims at identifying which tasks can or cannot be computed locally, i.e., when every node can acquire knowledge only about the nodes that are at constant distance from it. Surprisingly, non trivial tasks can be achieved locally [START_REF] Naor | What can be computed locally?[END_REF]. This is for instance the case of weak-coloring, a basis for a solution to some resource allocation problems. However, many important problems in distributed computing do not have a local solution [START_REF] Kuhn | What cannot be computed Locally! In 23th[END_REF]. This is the case of computing an approximate minimum vertex cover or an approximate minimum dominating set.

The other framework that has been considered is distributed computing with advice. In this framework, the computing entities can be given information about the instance of the considered problem. The traditional approach is actually qualitative in the sense that algorithms are designed or impossibility results are proved under the assumption that the nodes are aware of specific parameters, e.g., the size of the network. It was proved that the impact of knowledge concerning the environment is significant in many areas of distributed computing, as witnessed by [START_REF] Fich | Hundreds of impossibility results for distributed computing[END_REF][START_REF] Lynch | A hundred impossibility proofs for distributed computing[END_REF] where a lot of impossibility results and lower bounds are surveyed, many of them depending on whether or not the nodes are provided with partial knowledge of the topology of the network. A quantitative approach was recently introduced in [START_REF] Fraigniaud | Oracle size: a new measure of difficulty for communication tasks[END_REF], in which limitations of local computation can be estimated by establishing tradeoffs between the efficiency of the computation (number of steps, number of messages, etc.) and the amount of information provided to the nodes about their environment, independently of what kind of information they receive.

More precisely, we consider network computing with advice in the following context. A network is modeled as an undirected graph, where links represent communication channels between nodes. Nodes of n-node networks have distinct IDs from {1, . . . , n}, and communication ports at a node of degree d are labeled by distinct integers from {1, . . . , d}. A priori, every node knows only its own ID, and the labels of its ports. All additional knowledge available to the nodes of the graph (in particular knowledge concerning the topology and the labels of the rest of the graph), is modeled by an oracle providing advice. An oracle is a function O whose arguments are networks, and the value O(G), for a network G = (V, E), called the advice provided by the oracle to this graph, is in turn a function f : V → {0, 1} * assigning a finite binary string to every node v of the graph. Intuitively, the oracle looks at the entire labeled graph with IDs, and assigns to every node some information, coded as a string of bits. A node v is informed by the oracle if the string f (v) is non-empty. The size of the advice given by the oracle to a given graph G is the sum of the lengths of all strings it assigns to nodes. Hence this size is a measure of the amount of information about the graph, available to its nodes. Clearly, the size of advice is not smaller than the number of informed nodes. The objective is to establish tradeoffs between the size of the advice and the computational efficiency of the network.

Specifically, we focus on the distributed graph coloring problem, one of the most challenging problems in network computing for its practical applications, e.g., in radio networks [START_REF] Moscibroda | Coloring unstructured radio networks[END_REF], and for its relation with many other problems such as maximal independent set (MIS) [START_REF] Kuhn | What cannot be computed Locally! In 23th[END_REF][START_REF] Panconesi | Improved distributed algorithms for coloring and network decomposition problems[END_REF] and symmetry breaking [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF]. Initially, each node knows its ID from {1, . . . , n}. The c-coloring problem requires each node to compute a color in {1, . . . , c}, under the constraint that any two adjacent nodes have different colors. Computation proceeds in rounds following Linial's model defined in [START_REF]Locality in distributed graph algorithms[END_REF] (a.k.a., LOCAL model [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]). At each round, a node sends a message to each of its neighbors, receives messages from each of its neighbors, and performs some local computations. The LOCAL model does not put any limit on the message size and any restrictions on local computations because it is designed to estimate limitations of local computing. The complexity of c-coloring a graph G is measured by the number of rounds required to compute a proper c-coloring. There is an obvious relation between the complexity of c-coloring and the maximum distance between two nodes that exchange information during the computation.

Coloring graphs using advice provided by oracle O consists in designing an algorithm that is unaware of the graph G at hand but colors it distributively, as long as every node v of the graph G is provided with the string of bits f (v), where f = O(G). Trivially, an advice of size O(n log c) bits that provides the appropriate color to each node yields a coloring algorithm working in 0 rounds. On the other hand, an advice of size 0, i.e., providing no information, yields an algorithm running in t(n, c) rounds where t(n, c) is the complexity of the coloring problem in the usual distributed setting (i.e., with no advice).

The theory of network computing with advice allows us to establish tradeoffs between these two extreme cases. Different forms of tradeoffs are illustrated in Figure 1. This figure plots the execution time as a function of the size of advice (i.e., the amount of information given to the nodes). The execution time decreases as the size of advice increases, for instance such as illustrated by the dashed curve. Depending on how quickly the time decreases enables to roughly classify problems as "sensitive" or "insensitive" to information. A problem is information sensitive if few bits of information given to the nodes enable to decrease drastically the execution time. Conversely, a problem is information insensitive if the oracle must give a lot of information to the nodes for the execution time to decrease significantly. In this paper, we study the information sensitivity of graph coloring.

Our results

To study the information sensitivity of graph coloring, we focus on lower bounds on the size of advice necessary for fast distributed coloring of cycles and trees, two important cases analyzed in depth by Linial in his seminal paper [START_REF]Locality in distributed graph algorithms[END_REF] (cf. also [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF]).

We show that coloring a cycle is information insensitive. Precisely, we show that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to beat the Θ(log * n) time of 3coloring a cycle, where log (k) n denotes k iterations of log n. This shows a huge gap between 3-coloring in time Θ(log * n) and 3-coloring below this time: while the first can be done without any advice [START_REF] Cole | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms[END_REF], the second requires almost as much information as if colors were explicitly assigned to nodes (which would take O(n) bits).

The result for cycles easily extends to oriented trees (i.e., rooted trees in which every node in the tree knows its parent in the tree), proving that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to beat the O(log * n) time of 3-coloring an oriented tree [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF]. Coloring an oriented tree is thus also information insensitive.

The power of orienting a tree (i.e., giving an orientation of its edges toward a root), from the point of view of distributed coloring, was known since Linial [START_REF]Locality in distributed graph algorithms[END_REF] proved that no algorithm can color the d-regular unoriented tree of radius r in time at most 2 3 r by fewer that 1 2 √ d colors. Hence 3-coloring unoriented trees essentially requires Θ(D) rounds, where D is the diameter of the tree. Therefore, informing every node of the port leading to its parent in the tree results in decreasing the time of 3-coloring from Ω(D) to O(log * n). We revisit this result using our quantitative approach. Precisely, we aim at computing the amount of advice required to reach the O(log * n) time bound. It is known that O(n log log n) bits of advice enable to orient a tree (i.e., to select a root, and to give to every node the port number of the edge leading to its parent) with an algorithm working in 0 rounds [START_REF] Cohen | Labeling Schemes for Tree Representation[END_REF], and O(n) bits of advice enable to orient a tree with an algorithm working in 1 round [START_REF] Cohen | Label-Guided Graph Exploration by a Finite Automaton[END_REF]. However, 3-coloring a tree in time Θ(log * n) does not necessarily require to orient the tree. Nevertheless, we show that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to 3-color all n-node unoriented trees in time Θ(log * n). Thus, while for oriented trees 3-coloring in time O(log * n) can be done without any additional information [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF], achieving the same efficiency for arbitrary trees requires almost as much information as if colors were explicitly assigned to nodes.

Finally, both for cycles and trees, even if oriented, we also show that Ω(n) bits of advice are needed for 3-coloring in constant time (i.e., for 3-coloring to become a locally solvable problem). Thus constant-time coloring requires essentially as much information as if colors were explicitly assigned to nodes. In fact, our lower bounds hold not only for the total number of bits of advice given to nodes but also for the number of nodes that must be informed (i.e., the number of nodes that are given at least one bit of advice).

Although we formulate our results for the task of 3-coloring, they remain true for coloring with any constant number of colors, by slight technical modification of the proofs.

While our lower bound proofs present different technical challenges in the case of the cycle and that of trees, the underlying idea is similar in both cases. Linial [START_REF]Locality in distributed graph algorithms[END_REF] constructed the neighborhood graph N [G] of a graph G in order to estimate the time of coloring G using the chromatic number of N [G]. Since in our case there is an oracle giving advice to nodes, we have to use a more complex tool in the lower bound argument. We also argue about the chromatic number of a suitably chosen graph H in order to bound coloring time of G. However, in our case, this graph depends on the oracle as well as on the time of coloring, and on the graph G, and hence it is very irregularly structured. We show that, if the number of nodes of G informed by the oracle is not too large, then H has a large chromatic number, and thus forces large coloring time of G. (Equivalently, if G can be colored fast then the advice must be large.) The main difficulty in our argument is to show the existence of a regularly structured subgraph (whose chromatic number can be bounded from below) in the highly irregularly structured graph H.

Related work

Because of the intrinsic difficulty of computing the chromatic number of a graph in the sequential setting [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF], or even to approximate it [START_REF] Bellare | Free Bits, PCPs, and Nonapproximability -Towards Tight Results[END_REF][START_REF] Feige | Zero Knowledge and the Chromatic Number[END_REF], the distributed computing literature dealing with graph coloring mostly focuses on the (∆ + 1)-coloring problem, where ∆ denotes the maximum degree of the graph. In fact, the interest expressed for the (∆ + 1)-coloring problem is also due to its intriguing relation with the maximal independent set (MIS) problem, already underlined by Linial in [START_REF]Locality in distributed graph algorithms[END_REF]. In particular, combining the best known algorithms for MIS [START_REF] Alon | A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem[END_REF][START_REF] Luby | A Simple Parallel Algorithm for the Maximal Independent Set Problem[END_REF] with the reduction from (∆+1)-coloring to MIS by Linial yields a randomized (∆+1)-coloring algorithm working in expected time O(log n). Using techniques described in [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF] and [START_REF] Panconesi | On the complexity of distributed network decomposition[END_REF], one can compute a (∆ + 1)-coloring (as well as a MIS) of arbitrary graphs in deterministic time O(n 1/ √ log n ). For graphs of maximum degree bounded by ∆, (∆ + 1)-coloring can be achieved in time O(∆ log n) (see [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF]). [START_REF] Cole | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms[END_REF] described a PRAM algorithm that can be easily transformed into an algorithm working in the LOCAL model, computing a 3-coloring of oriented cycles in O(log * n) rounds. This bound is tight as proved by Linial [START_REF]Locality in distributed graph algorithms[END_REF]. Similarly, [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF] described a 3-coloring of oriented trees working in O(log * n) rounds. The O(∆ 2 )-coloring algorithm in [START_REF]Locality in distributed graph algorithms[END_REF], working in O(log * n) rounds, can be easily converted into a (∆ + 1)-coloring algorithm working in O(∆ 2 + log * n) rounds, reaching the same complexity as the algorithm in [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF]. [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] analyses what can be achieved in one round, and proves that no algorithm based on iterations of the application of a 1-round algorithm can achieve O(∆)-coloring in less than Ω(∆/ log 2 ∆ + log * n) rounds. On the other hand, [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] presents a (∆ + 1)-coloring algorithm working in O(∆ log ∆ + log * n) rounds, thus improving [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF][START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF][START_REF]Locality in distributed graph algorithms[END_REF]. Recently, the power of orienting the network was also demonstrated in terms of bit complexity in [START_REF] Kothapalli | Distributed coloring in O( √ log n) bit rounds[END_REF].

Coloring cycles with advice

In order to prove the lower bounds listed in Section 1.1 on the size of advice needed for fast 3-coloring of all cycles, we prove the following result.

Theorem 2.1 Suppose that an oracle O informs at most q nodes in any n-node cycle. Then the time of 3-coloring of n-node cycles using oracle O is Ω(log * (n/q)). This result holds even if the cycle is oriented, i.e., even if the nodes have a consistent notion of clockwise and counterclockwise directions.

Proof. Recall the definition of the directed graph B t,n from [START_REF]Locality in distributed graph algorithms[END_REF]. Let s = 2t + 1 < n -1. The nodes of the graph are sequences of length s of distinct integers from {1, . . . , n}. Intuitively, node (x 1 , x 2 , . . . , x s ) of the graph B t,n represents the information acquired in time t by node x t+1 of a labeled directed cycle containing a segment (x 1 , x 2 , . . . , x s ). Out-neighbors of node (x 1 , x 2 , . . . , x s ) are all nodes (x 2 , x 3 , . . . , x s , y), where y = x 1 . Note that the chromatic number χ(B t,n ) is a lower bound on the number of colors with which an n-node cycle may be colored distributively in time t. Thus, by restricting attention to 3-coloring algorithms, this yields a lower bound on the time of 3-coloring.

It was proved in [START_REF]Locality in distributed graph algorithms[END_REF] that χ(B t,n ) ≥ log (2t) n. For any set X ⊆ {1, . . . , n} of size > s + 1, define B t,n (X) to be the subgraph of B t,n induced by all nodes (x 1 , x 2 , . . . , x s ) with x i ∈ X, for all 1 ≤ i ≤ s. It is easy to see that the graph B t,n (X) is isomorphic to B t,|X| .

Fix an oracle O giving advice to all cycles of length n. Let q be the maximum number of nodes informed by oracle O in any of these cycles. Without loss of generality we may assume that the number of bits given to any node is not more than needed to code all directed labeled cycles of length n, i.e., ⌈log(n -1)!⌉. Consider a 3-coloring algorithm for cycles of length n using oracle O and running in time t. If t ≥ n/(2q) -1, we are done. Hence suppose that t < n/(2q) -1 which implies s < n/q. We define the directed graph B t,n,O that will be crucial in our argument. The nodes of the graph are sequences ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )), where x i are distinct integers from {1, . . . , n} and α i are binary strings of length at most ⌈log(n -1)!⌉. Intuitively, node ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) represents the total information acquired in time t by node x t+1 of a labeled directed cycle containing a segment (x 1 , x 2 , . . . , x s ), including labels of nodes at distance at most t and advice given to them by the oracle. There exists a (directed) edge from node v = ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) to a node w, if w = ((x 2 , α 2 ), . . . , (x s , α s ), (y, β)) and if there exists a labeled directed cycle of length n containing the segment (x 1 , x 2 , . . . , x s , y), such that oracle O applied to this cycle gives advice α 1 , α 2 , . . . , α s , β to nodes x 1 , x 2 , . . . , x s , y, respectively. We will say that the segment (x 1 , x 2 , . . . , x s , y) of such a cycle induces this directed edge. Similarly as above, the chromatic number χ(B t,n,O ) is a lower bound on the number of colors with which the cycle may be colored distributively in time t, using oracle O. Note that a coloring algorithm using oracle O does not need to assign a color to all nodes ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) of B t,n,O . Indeed, it is possible that there is no cycle containing the segment (x 1 , x 2 , . . . , x s ), such that oracle O applied to this cycle gives advice α 1 , α 2 , . . . , α s to nodes x 1 , x 2 , . . . x s , respectively. However, by definition, such "non-legitimate" nodes are isolated in the graph B t,n,O and hence they do not affect its chromatic number.

We will establish a lower bound on the chromatic number of B t,n,O , and then show how to deduce from it a lower bound on the time of 3-coloring with oracle O. To this end it is sufficient to focus on the subgraph Bt,n,O of B t,n,O induced by the nodes ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )), with all α i being empty strings. By definition, the graph Bt,n,O is isomorphic to a subgraph of B t,n and has the same number of nodes as B t,n . By a slight abuse of notation we will identify Bt,n,O with this subgraph of B t,n .

Claim 2.1 For n/q sufficiently large, there exists a set X of size k = n q(s+1)

1/(s+1) such that B t,n (X) is a subgraph of Bt,n,O .
We will establish an upper bound on the number of edges from the graph B t,n missing in Bt,n,O . This upper bound will allow us to prove that Bt,n,O contains a subgraph B t,n (X), for some set X of size k. Fix a directed labeled cycle of length n. When the oracle O informs a node of this cycle, exactly s + 1 of its segments (those containing the node) induce s + 1 edges in B t,n,O that are different than in B t,n,O ′ , where oracle O ′ differs from O by not informing this node. Moreover, these s + 1 edges in B t,n,O are outside Bt,n,O . For a given cycle, at most q(s + 1) of the edges induced by all the n possible segments of the cycle are outside Bt,n,O . There are (n -1)! directed labeled cycles of length n. In order that a given edge of B t,n do not appear in Bt,n,O , the (n -s -1)! cycles that could potentially induce it, should not do it. Let µ be the number of edges in B t,n that do not appear in Bt,n,O . Then

µ ≤ q(s + 1) • (n -1)! (n -s -1)! ≤ q • (s + 1) • n s .
Consider all graphs B t,n (X), for X of size k > s+1. Every edge ((x 1 , x 2 , . . . , x s ), (x 2 , . . . , x s , x s+1 )) of B t,n belongs to at most n-s-1 k-s-1 such graphs B t,n (X), where all x i are in X. Thus there exist at most q • (s + 1) • n s • n-s-1 k-s-1 graphs B t,n (X), for X of size k, such that at least one of their edges does not appear in Bt,n,O . We will now prove that this number of graphs is strictly smaller than the total number n k of graphs B t,n (X), for X of a suitably chosen size k. Indeed,

n k n-s-1 k-s-1 = n(n -1) • • • (n -s) k(k -1) • • • (k -s) > n k s+1 . Let k = n q(s + 1) 1/(s+1)
.

Note that we have k > s + 1, for n/q sufficiently large. Hence n k s+1 ≥ q • (s + 1) • n s . Hence there exists a graph B t,n (X) all of whose edges appear in Bt,n,O . This proves Claim 2.1.

In view of Claim 2.1, the chromatic number of B t,n,O can be bounded as follows (for n/q sufficiently large):

χ(B t,n,O ) ≥ log (s-1) k = log (s-1) n q(s + 1) 1/(s+1)
. Since t is the running time of a 3-coloring algorithm for cycles of length n using oracle O, we have χ(B t,n,O ) ≤ 3, which implies log (s-1) n q(s+1) 1/(s+1) ≤ 3. In order to finish the argument, it is enough to prove that s ≥ 1 5 log * (n/q). Suppose not. Thus n/q ≥ 2 2 16 . For such large n/q we have log n q(s + 1)

> log n q -log log * n q ≥ 1 2 log n q . Hence 1 s + 1 log n q(s + 1) > 1 2(s + 1) log n q ≥ 1 2 log * n q log n q ≥ log log n q .
This implies n q(s + 1)

1/(s+1) > log n q ,
and 3 ≥ log (s-1) n q(s + 1)

1/(s+1) > log (s) n q .
Thus s ≥ log * n q -2, which contradicts the assumption s < 1 5 log * (n/q). Theorem 2.1 has several interesting consequences. The following corollary proves that transforming the 3-coloring problem into a locally solvable problem (in the sense of [START_REF] Naor | What can be computed locally?[END_REF]) essentially requires to give the solution to the nodes.

Corollary 2.1 Any distributed algorithm that produces a 3-coloring of all cycles of length n in constant time requires advice for Ω(n) nodes.

The next corollary proves that 3-coloring of cycles is information insensitive. Corollary 2.2 Any distributed algorithm that produces a 3-coloring of all cycles of length n in time o(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

Coloring trees with advice

Theorem 2.1 concerning cycles has an interesting consequence concerning trees, that proves that 3-coloring is information insensitive in oriented trees. Recall that a tree is oriented if it is rooted, and every node is aware of which of its incident edges leads to its parent in the tree. If there exists an oracle O informing at most q nodes in any n-node oriented tree, and a 3-coloring algorithm A using O and working in t(n) rounds, then there exists an oracle O ′ informing at most q + 2 nodes in any n-node oriented cycle, and a 3-coloring algorithm A ′ using O ′ and working in t(n) + 1 rounds. O ′ picks arbitrarily two neighboring nodes x and y in the cycle. Assume that y is the neighbor of x in the counterclockwise direction. O ′ gives the advice (tail) to x, and the advice (t(n), root) to y. The ith node v in the cycle, counting counterclockwise from x, receives from O ′ the advice f (v i ) given by O to the node v i at distance i from the root of the oriented path P rooted at one of its two extremities, where f = O(P ). A ′ proceeds in t(n) + 1 rounds. During rounds 1 to t(n), A ′ simply executes A, for which nodes x and y just act as if they would be respectively the tail and the root of a directed path from x to y. At round t(n) + 1 of A ′ , the root node y checks if its color is different from x. If not, it takes a color distinct from the colors if its two neighbors. This simple reduction enables to establish the following corollary of Theorem 2.1 proving that 3-coloring oriented trees is information insensitive.

Corollary 3.1 Suppose that an oracle O informs at most q nodes in any n-node oriented tree. Then the time of 3-coloring of n-node oriented trees using oracle O is Ω(log * (n/q)). Thus in particular any distributed algorithm that produces a 3-coloring of all n-node oriented trees in time o(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

The main result of this section is a lower bound on the size of advice necessary for fast coloring of all n-node unoriented trees. In fact we will show that this bound holds already for the class of all unoriented complete d-regular trees. These are trees T d,r such that each leaf is at distance r from the root, and each internal node has degree d. It should be stressed that the notion of root and children is brought up only to facilitate the definition. From the point of view of nodes, the tree is not rooted (a node does not have information which neighbor is its parent). Proof. Fix d ≥ 37, t > 0, and r > 2t + 3. Consider any node v of the tree T d,r at distance at least t + 1 from all leaves. The number of nodes at distance at most t from v will be denoted by α(t). We have

α(t) = d • t-1 1=0 (d -1) i ≤ 2(d -1) t -1.
Consider an edge e of the tree T d,r whose both extremities are at distance at least t + 1 from all leaves. The subtree induced by the set of nodes at distance at most t from one of these extremities will be be called the bow-tie of T d,r based on edge e. The number of nodes in this bow-tie will be denoted by β(t). We have

β(t) = α(t) + 1 + (d -1) t ≤ 3(d -1) t .
Consider the tree T d,r with a labeling Φ of nodes and ports. Φ labels all nodes by distinct integers from {1, . . . , n}, where n = 1 + α(r), and labels all ports at internal nodes by integers from {1, . . . , d}. For any such labeled tree, consider its subtrees of the form N (v, t, Φ), where t is a positive integer and v is a node of T d,r at distance at least t + 1 from any leaf of T d,r . N (v, t, Φ) is defined as the labeled subtree of T d,r induced by all nodes at distance at most t from v. Note that if restrictions of labelings Φ and Φ ′ to the subtree of T d,r induced by all nodes at distance at most t from v are identical, then N (v, t, Φ) = N (v, t, Φ ′ ). Consider the following graph G t (T d,r ). The nodes of the graph are all subtrees N (v, t, Φ) of T d,r for all possible nodes v and labelings Φ of nodes and ports of T d,r . Two nodes of G t (T d,r ) are adjacent, if and only if, they are of the form N (v, t, Φ) and N (v ′ , t, Φ), for some labeling Φ, with v and v ′ adjacent in T d,r . Note that the graph G t (T d,r ) is a subgraph of the t-neighborhood graph of T d,r , defined in [START_REF]Locality in distributed graph algorithms[END_REF]. Moreover, it follows from [START_REF]Locality in distributed graph algorithms[END_REF] that the chromatic number χ(G t (T d,r )) is a lower bound on the number of colors with which the tree T d,r may be colored distributively in time t, and that χ(G t (T d,r )) ≥ 1 2 √ d, if t < 2r/3. Also, for any set X ⊆ {1, . . . , n}, we define the graph G(X) as the subgraph of G t (T d,r ) induced by nodes with labels from the set X. Note that, for |X| = 1 + α(s), for some positive integer s ≤ r, the graph G(X) is isomorphic to G t (T d,s ).

Fix an oracle O giving advice to all n-node labeled trees T d,r . Let q be the maximum number of nodes informed by oracle O in any of these trees. Without loss of generality we may assume that the number of bits given to any node is not more than needed to code all n-node labeled trees T d,r . There are d α(r-1) port labelings of T d,r , and for each such labeling there are n! ways to label nodes. Hence the number of bits needed to code these trees is at most ⌈log(d α(r-1) n!)⌉. Consider a 3-coloring algorithm for n-node labeled trees T d,r using oracle O and running in time t. We define the following graph G t,O (T d,r ). Nodes of this graph are couples of the form (N (v, t, Φ), f ), where N (v, t, Φ) is the tree defined above and f is a function from nodes of this tree into the set of binary strings of length at most ⌈log(d α(r-1) n!)⌉. Intuitively, the value f (w) is the advice given to node w of N (v, t, Φ) by the oracle, and the entire couple (N (v, t, Φ), f ) represents the total information acquired in time t by node v, including advice given to nodes of N (v, t, Φ) by the oracle. Edges of the graph G t,O (T d,r ) are defined as follows. There is an (undirected) edge between two nodes of G t,O (T d,r ) if these nodes are of the form (N (v, t, Φ), f ) and N (v ′ , t, Φ), f ′ ), for some labeling Φ, where v and v ′ are adjacent in T d,r and for all nodes w of N (v, t, Φ) and w ′ of N (v ′ , t, Φ), the values f (w) and f ′ (w ′ ) are advice strings given to nodes w and w ′ , respectively, by oracle O for the tree T d,r labeled by Φ. We will say that this edge of G t,O (T d,r ) is induced by the bow-tie based on edge {v, v ′ } of the tree T d,r labeled by Φ.

The chromatic number χ(G t,O (T d,r )) is a lower bound on the number of colors with which the tree T d,r may be colored distributively in time t, using oracle O. Similarly as in the case of the cycle, there may be "non-legitimate" nodes in G t,O (T d,r ) but they are isolated and thus do not affect the chromatic number.

In order to establish a lower bound on the chromatic number of G t,O (T d,r ), it is sufficient to focus on the subgraph Gt,O (T d,r ) induced by the nodes (N (v, t, Φ), f ) with f being a function giving the empty string to all nodes. By definition, the graph Gt,O (T d,r ) is isomorphic to a subgraph of G t (T d,r ) and has the same number of nodes as G t (T d,r ). Similarly as before we will identify Gt,O (T d,r ) with this subgraph of G t (T d,r ). Claim 3.1 Let ν(k) be the number of sets X of size k, such that the graph G(X) is not a subgraph of Gt,O (T d,r ). Then

ν(k) ≤ 2 • q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t) .
In order to prove Claim 3.1, consider an edge of G t,O (T d,r ). Let λ be the number of labeled trees T d,r that contain a bow-tie B inducing this edge. Let b be the node of B closest to the root of T d,r . Consider two cases.

Case 1. b is the root of T d,r .

There are β(t) ways of choosing node b in the bow-tie. For each such choice there are d α(r-1)-(β(t)-1) ways of fixing port numbers in T d,r because for every internal node other than the root the port leading to its parent has to be chosen and this has already been done for these nodes that appear in the bow-tie B. Finally for each such choice there are n -β(t) ! ways of labeling all nodes outside B. Hence in Case 1, there are

β(t) • d α(r-1)-β(t)+1 • n -β(t) ! labeled trees T d,r that contain B. Case 2. b is not the root of T d,r .
In this case b must be a leaf of B. The number of leaves of B is 2(d -1) t . For any choice of b there are d α(r-1)-β(t) ways of fixing the port number leading to the parent, for all internal nodes in T d,r other than the root and outside B. For any such choice there are d • r-(2t+3) i=0 (d -1) i ways of choosing the port numbers on the (unique) path from the root to b (index i corresponds to the distance between the root and node b). Finally, we have to consider again the n -β(t) ! ways of labeling all nodes outside B. Hence in Case 2, there are

2(d -1) t • d • r-(2t+3) i=0 (d -1) i • d α(r-1)-β(t) • n -β(t) ! labeled trees T d,r that contain B. Consequently we have λ =   β(t) • d α(r-1)-β(t)+1 + 2(d -1) t • d • r-(2t+3) i=0 (d -1) i • d α(r-1)-β(t)   • n -β(t) ! =   β(t) + 2(d -1) t • r-(2t+3) i=0 (d -1) i   d α(r-1)-β(t)+1 • n -β(t) ! ≥ 2(d -1) t • (d -1) r-(2t+3) • d α(r-1)-β(t) • n -β(t) ! .
Fix an n-node labeled tree T d,r . When the oracle O informs a node of this tree, exactly α(t+1) bow-ties (those containing the node) induce α(t+1) edges in G t,O (T d,r ) that are different than in G t,O ′ (T d,r ), where oracle O ′ differs from O by not informing this node. Moreover, these α(t + 1) edges in G t,O (T d,r ) are outside Gt,O (T d,r ). For a given tree, at most q • (α(t + 1) of the edges induced by all possible bow-ties are outside Gt,O (T d,r ). There are d α(r-1) • n! n-node labeled trees. In order that a given edge of G t (T d,r ) do not appear in Gt,O (T d,r ), the λ trees that could potentially induce it, should not do it. Let µ be the number of edges in G t (T d,r ) that do not appear in Gt,O (T d,r ). Then

µ ≤ q • α(t + 1) • d α(r-1) • n! 2(d -1) t • (d -1) r-(2t+3) • d α(r-1)-β(t) • n -β(t) ! ≤ q • n! • d β(t) (d -1) r-(2t+3) • n -β(t) ! ≤ 2 • q • n! • d 4d t n • n -β(t) ! .
The last inequality follows from n ≤ (d -1) r and d β(t)+(2t+3) ≤ d 4d t . Consider all graphs G(X), for X of size k = α(⌊ 3 2 t + 1⌋). Every edge of G t (T d,r ) belongs to at most n-β(t) k-β(t) such graphs G(X). Thus there exist

ν(k) ≤ 2 • q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t)
sets X of size k, such that the graph G(X) is not a subgraph of Gt,O (T d,r ). This proves Claim 3.1. Suppose that ν(k) < n k . Then there exists a set X of size k for which G(X) is a subgraph of Gt,O (T d,r ). Since k = α(s) for s > 3t/2, it follows from [START_REF]Locality in distributed graph algorithms[END_REF] that the chromatic number of the graph G(X) (and thus also of the graph G t,O (T d,r )) is at least 1 2 √ d, which is larger than 3 for d ≥ 37. This contradicts the fact that we consider a 3-coloring algorithm running in time t. Hence we may assume ν(k) ≥ n k . From Claim 3.1, this implies

2 • q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t) ≥ n k
and hence the number q of informed nodes satisfies

q ≥ n • k -β(t) ! 2 • d 4d t • k! ≥ n 2 • d 4d t • k β(t) .
Since k = α(⌊ Remark. By considering trees of a sufficiently large constant degree (instead of just degree d ≥ 37) we can generalize the above result to the case of c-coloring, for any constant c. Theorem 3.1 has several interesting consequences. The following corollary proves that lack of cycles does not help in coloring a network since transforming the 3-coloring problem in trees into a locally solvable problem essentially requires, as for cycles, to give the solution to the nodes.

Corollary 3.2 Any distributed algorithm that produces a 3-coloring of all n-node trees in constant time requires advice for Ω(n) nodes.

The next corollary proves that reaching the O(log * n) bound in unoriented trees requires lot of advice. This should be contrasted with the fact that O(log * n) is the complexity of 3-coloring of oriented trees, without advice. Corollary 3.3 Any distributed algorithm that produces a 3-coloring of all n-node unoriented trees in time O(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

Conclusion

We presented lower bounds on the amount of advice that has to be given to nodes of cycles and of trees in order to produce distributively a fast 3-coloring of these networks. Although our lower bounds are very close to the obvious upper bound O(n), some interesting detailed questions concerning the trade-offs between the size of advice and the time of coloring remain open, even for cycles and trees. In particular, what is the minimum number of bits of advice to produce a 3-coloring of every n-node cycle or tree in a given time t = o(log * n)? More generally, what is the information sensitivity of coloring arbitrary graphs? For arbitrary graphs, it is natural to consider the maximum degree ∆ as a parameter, and seek distributed (∆ + 1)-coloring. It was proved in [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] that a (∆ + 1)-coloring can be produced in time O∆ log ∆ + log * n). What is the minimum number of bits of advice to produce a (∆ + 1)-coloring in time O(log * n)? And in constant time? We conjecture that for the former task O(n) bits of advice are sufficient, and for the latter Ω(n log ∆) bits of advice are needed.

Figure 1 :

 1 Figure 1: Tradeoff between the execution time and the size of advice.

Theorem 3 . 1

 31 Fix d ≥ 37. Any 3-coloring algorithm working in time t for the class of n-node unoriented complete d-regular trees requires advice for at least n d d 2t nodes.

  3 2 t + 1⌋) ≤ d 7 2 t and β(t) ≤ 3(d -1) t , we have

	q ≥	n 2 • d 4d t • d 7 2 t•3(d-1) t ≥	n d d 2t .

Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. A part of this work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais, as a postdoctoral fellow.


The submorphemic conjecture in

come

Introduction

The question of lexical submorphemics has long been controversial in English lexical studies and in general [START_REF] Genette | Mimologiques[END_REF][START_REF] Jakobson | La charpente phonique du langage[END_REF][START_REF] Toussaint | Contre l'arbitraire du signe[END_REF]. The linguistic sign is traditionally considered as "arbitrary": the phonological form is not iconic and does not reflect the physical properties of the object or event to which the word refers; for lack of motivation there are as many words as languages for one given item (snow, neige in French, elur in Basque, erc'h in Breton) and no human community produces "ideal" signs as is done by Adam in the Genesis or by the logothete according to Cratyle. On the other hand, a minority of authors is convinced that some areas of the English lexicon are organized by a paradigm of submorphemic markers: clusters of more than one phoneme, and occasionally isolated phonemes, which appear to attach the lexical notion to a specific semantic field.

Between these two positions there is hardly any room for scientific debate. Submorphologists usually accumulate impressive bodies of data (Nemo for French, Bohas for Arabic and other Semitic languages) which are interpreted in the light of elaborate theoretical models such as Bohas's Matrices, Etymons and Racines and Philps's sublexical markers which are described in their synchronic, diachronic and panchronic dimension; but the sceptical opponents consider that the undertaking is illegitimate and ill-targeted in the first place so that the accumulated data and analyses, far from supporting the cause of submorphologists, is at best ignored and occasionally taken to illustrate the extent to which one can err. The gap separating the two sides could hardly be wider; for a productive scientific debate to be inaugurated, what is urgently needed is to reconcile antagonistic views over at least one issue: the real nature of the problem.

1.

Establishing the issues: towards an embodied and distributed conception of speech and the word At the root of the misunderstanding lies the fact that the questions for which those positions are supposed to provide an answer have not really been raised in the first place. What is, after all, a word? Basically, a segment of vocal action undertaken by a human subject in the presence of fellows of his kin. In a series of recent studies the author of these lines has proposed a model of the speaking activity that can be summarized as follows (Bottineau 2008).

Vocal speech takes place when a human subject starts altering the acoustic properties of the atmospheric environment. This perturbation is perceivable by all embodied consciences present, including the emitter's own. Utterances, whether they take the form of full-fledged standardized sentences or of partial and improvised sequences, will have a distributed cognitive impact on all brains involved: interpretation. To interpret is (i) to realize a semantic construction on the basis of the sequence of vocal keys received and (ii) to map the semantic responses against the pre-existing psychological context characterizing each individual subject (personal generic background and specific knowledge, moods and emotions, intentions, social relations and so on). Because interpretive dynamics is based on the perceptions of the same signal the outcomes will tend to converge, and because the psychological contexts enacting them are different interpretive dynamics is inevitably divergent. Verbal constructivism is about the emergence of concerted semantic and pragmatic projects out of psychological diversity and idiosyncracies.

Speech should not be reduced to communication: speech is also used in the process of forming one's own conscious ideas like Why is that silly dog barking? Or I must be dreaming. The same vocal ritual is used for both transitive vocal speech and reflexive inhibited speech: a speaker will orient vocally (in Maturana's sense) a hearer's interpretive mind map in the same way as a thinker will orient silently his own sense-making itinerary; to think is to anticipate what the auditory and tactile proprioception of one's own voicing would sound and feel like if it were actually carried out motorically, and internal discourse does indeed provide evidence of some of the prosodic features of actually vocalized speech (rhythm, word and sentence stress, tone units, melody, etc.). The same orienting process is used to direct either an external conscience's activity (communication, with intended meaning), or the private activity of one's own internal conscience (meditation, generating unintended semantic emergence). We are therefore rejecting encodingism: even if language is commonly used to express ideas (or so we believe -and how could we ever talk without this necessary faith?), the chain of vocal action's effect is not to organize and give acoustic substance to the externalization of internally formed representations, but to conduct by vocal motricity the distributed procedure of semantic networking1 . In this perspective, the linguist's empirical objects of investigation (the lexicon, morphology, syntax and prosody) are to be re-defined in terms of vocal subactions, each of them yielding a specific cognitive contribution to the general orchestration of the sense-making process.

Syntax: Word order cannot be explained in terms of information packaging (Chafe 1976). Syntax, or the distinction and ordering of the successive steps of the sense-making process (both transitive and reflexive), is about the prototypical mind-map characterizing ideation in a given language; to this day, three different cognitive types have been proposed, but they cannot be recalled here.

The lexicon: words are ritual vocal actions whose perceptual-motoric coupling is imposed by the surrounding speaking community of local experts (parents, relatives, teachers, friends) to developing and language-forming children in the presence of heterogenous but consistent and regular sets of situations and in the context of stereotypical discourse [START_REF] Putnam | The meaning of " meaning[END_REF], Anscombre 2001). For one given individual subject, the meaning of the word is a network of synchronized and correlated heterogenous memories of impressions, both non-linguistic (Culioli's notion with all its pragmatic and cultural dimensions) and verbal (the sequences of discourse in which a word is regularly encountered, both formally and thematically: Anscombre's stereotypes)dog is a word I and others use in a whole range of contexts (including in the absence of the dog) and each reiterated occurrence of the word will map the recorded hierarchized network of previously experienced impressions against the other structurally similar networks reactivated by other lexical units, to form a consistent hypernetwork: a mental scene. Abstraction is not a problem: there does not have to be an empirical common denominator for a given word (take abstraction, for example) apart from the type of social situations and discourse contexts in which it is ordinarily used. "A word is a powerful madeleine" (Stéphane Robert 2003): a constant and reiterated piece of vocal action linking heterogenous sections of experience with converging and diverging properties; the role of this socially controlled motoric token is to map, when needed, a given experiencial occurrence against the knowledge and pragmatic knowhow acquired in the course of all previous occurrences of the word / real life coupling: the word maps singularize currently experienced occurrences of categories against a recorded background of features retrieved from multiple previous occurrences; literally, language amplifies intelligence (in the etymological sense): vocal action catalyzes the retrieval of previously stored knowledge, a retrieval which could not be executed so efficiently and extensively without the socially-nurtured tokens. This vocal intelligence agency is used as a guideline to form predictions and make decisions, that is, promote action. As the lexicon is imposed by the speaking kins to the child, as speech shapes dynamically the acoustic environment in which the infant grows and to which its development adapts, words act as the social and cultural profilers of the category-making processes: thanks to these social agents of vocal intelligence, personal memories and experience is framed by externally imposed labels and contrastive networks (dogs as opposed to cats in a given cultural-linguistic collective way of life).

Morphology: just as notional words are vocal sub-actions that activate recorded networks of impressions, functional morphemes are vocal sub-actions of a different kind: they activate recorded patterns of connections whose effect is to relate notions to one another and to the currently experienced situation in terms of time, space, determination and so on; the outcome is the formation of the hyper-network required to achieve a "mental scene" that is correlated with the ongoing experience, both material and psychological, both verbal and non-verbal.

Prosody: melody and rhythm in English are mainly used to plan and fine-tune the reception of the ongoing orienting process in the intersubjective interplay but it will be affected in real time by the emotional effect of the visual perception of the addressee's and witnesses' reactions.

To summarize, speech is to be understood as an individual vocal process whose effect is to coordinate the cognitive activities of all receptors involved by focussing them all on the same sense-making procedure, to be mapped against contrasted psychological contexts and backgrounds. The coordinative span is restricted to the individual self when the vocal emission of the acoustic signal is inhibited, and extended to all the attainable kins otherwise (including the use of technological artefacts to lengthen the perceptual reach of the signal and record or stabilize it: Bruner's amplifiers). The vocal speaker is the individual director of the cognitive coordination, and dialogue consists in "voicing over" the subjective vocal leadership of the coordinative process in a constructivistic way. In the debate opposing internalism and externalism, this account is a moderate compromise: the biological loci of the verbally generated mental scenes are the brains' nervous systems confined in the cortices, but the neural dynamics through which the semantic constructions are carried out involves the motoric activity of the whole body's muscles and its perception by the nervous system. Linguistic cognition is not confined in neural systems, but distributed; the whole metabolism is part and parcel of cognitive dynamics, which are embodied, and not in metaphorical and representational terms (which implies a rejection of some of the major tenets of the cognitivist paradigm). And as this motoric activity affects the atmospheric mediating environment in a perceivable way for all bodies present, linguistic cognition cannot be individual except when its muscular motricity is inhibited (internal meditative thinking): at this second level, cognitive processes are distributed over bodies, brains and the environment.

The coordinative dynamics involves a plurality of agents in a given medium and will form a fluctuating collective and concerted mind. The anthropological effects are well known: the human species is the only one to have developed an aptitude for subjectively-led collective autodetermination (to be opposed to bees' and ants' functionally rigid systems of pragmatic coordination). As a result, it is also the only species to have self-determined and concerted its relation to the other species, taking over the whole environment and turning it into its own private ecological niche -a process that started with sedentarization and agriculture and is now reaching a climax with rampant demography, the globalization of exchanges in all their forms, the fall of biodiversity, and climate change.

In a nutshell, languageing is about the reciprocal effects of neural and muscular ritual motoric actions learned by the developing subject in the social and cultural environment. This conception paves the way for a more technical formulation of the submorphemic conjecture. Paradoxically, there is no difference in nature between the signifier and the signified: the lexical signifier is a vocal sub-action, a multimodal motoric-perceptual coupling and programme to be inserted in a hyperordinate sequence of analogous sub-actions; and the lexical signified is a network of recorded impressions experienced in the course of real life, that is, another network of multimodal motoric-perceptual couplings, both verbal and nonverbal. The difference is that the signifier is a relatively stable and consensual programme of vocal action, while the galaxy of experiences out of which the collected impressions forming the features to be organized into notional networks emerge is largely chaotic despite the streamlining effect of parenting, schooling and socializing in general. A theory of the lexicon is a model of the linking of those two types of perceptual-motoric couplings: the vocal token, the signifier; and the varying collection of impressions attached to it, the signified. A theory of phonetic change is a model of how inevitable idiosyncratic "errors of phonatory copy" in the analogical reproduction of sounds are made to converge and form strains of phonetic evolutions to which specific sub-groups may identify (or emerge) and compete with other communities. And a theory of semantic change is a model of how the random differences in the idiosyncratic collections of impressive items forming notional networks are made to converge and form emerging strains of interpretation.

The submorphemic conjecture consists in hypothesizing that in English the word is not always the smallest relevant vocal sub-action to be singled out in the monitoring of the distributed sense-making process; that submorphemic markers constitute, as it were, hypo-sub-actions whose specific orienting effect can be modelled. To explore this hypothesis, the following sections are devoted to -a review of some of the arguments against the establishment of submorphemic markers as a relevant object worthy of scientific scrutiny;

-the presentation of the nature of the semantics of submorphemic markers: their orienting effect;

-the exploration of the ways in which vocal "hypo-sub-acting" may be acquired by developing infants and of the traces their popular intuitive awareness leaves in some adult language practices.

Establishing the object

A. Submorphemes are best described by the following objective properties:

(i) a [submorpheme] is an identifiable segment in a {lexical unit}: {[st]and}, {sh[amble]}, {[st][ump]}.
(ii) to the consenting linguist, this segment appears as a submorphological common denominator shared by a list of lexical units belonging to the same semantic field: in the semantic field of 'stativity' (in space or time) and rigidity (of an object) we find still stall stand stay stare along with many others. The following table presents some of the most often studied initial consonantal clusters: (iii) concerning their structure, submorphemes are formatted by the morphophonological constraint. According to [START_REF] Tournier | Introduction descriptive à la lexicogénétique de l'anglais contemporain[END_REF] they may cover either the onset of the syllable (stand), or the rhyme, which must possess a coda (shamble).

In the onset, submorphemes are usually bi-or tri-consonantal clusters ([st]and, [str]etch) but analyses will vary. Among the 29 initial submorphemes he postulates, Tournier admits a limited number of uniconsonantal submorphemes: w for instability, oscillation as in wag, waddle, wobble; v for violence as in violent, vicious, vituperate, virulent. As regards bi-and tri-consonantal clusters, [START_REF] Bottineau | Les cognèmes de l'anglais : principes théoriques[END_REF]Bottineau ( , 2003a) ) has suggested that three tri-consonantal submorphemes, spr, str and scr, are actually variants of sp, st and sk complemented by an additional r related to the notion of dynamic movement and agentivity. It should be added that aprt from scl-(sclerosis, skeleton) no other format for tri-consonantal clusters is available in the range of possibilities offered by the morpho-phonologic constraint in English (*stl, *swr etc.): it is usually considered that English, unlike Semitic languages, compresses its submorphemes in the form of clusters located in one of the pre-or post-vocal locations in the syllable: the onset, the coda. However the question whether a distributed approach of submorphology should not be preferred sometimes emerges: should discontinuous matrices be admitted? This might be the case for sit, sat and set in the case of s-t, and other instances of discontinuous matrices have long been identified: loop, lap, lip, and maybe leap; full and fill.

If it were so, tri-consonantal matrices are potential candidates for submorphology: spin, span, spoon, spank, spend. It is worth noticing that this questions echos a current debate among specialists of the Semitic languages: for the tradition, matrices are tri-consonantal; for a contemporary trend, bi-consonantal matrices to which one consonant is added (with a special mention to Bohas more elaborate model); and Zev bar-Lev ( 2008), in a marginal uniconsonantal model, postulates the existence of Arabic key consonants in initial position. The lexicon of English, however, is primarily based on one-syllable units, leaving little systematic space for tri-consonantal matrices.

For the rhyme and the coda, Tournier itemizes 9 submorphemes (this does include some cases of vowel alternations), once again uni-, bi-and tri-consonantal (VC 1>3 ). Some submorphemic markers may appear either in the onset or in the coda if the morphophonological constraint will allow it in terms of the number and location of mores: spend, wisp; skin, mask; stick, mast. In some cases both the onset and the coda host submorphemic consonant clusters: flask, clasp. Initial submorphemes are semantically more salient than final ones: the former select a primary classifying property while the latter provide a secondary, complementary feature. To substantiate this with arguments other than subjective semantic intuition (or aspiration) a dynamic theory of the syllable is required. In Diver's Columbia School of Phonology (Phonology as Human Behaviour, Tobin 1997) the vowel and the consonant are not sets of static features but dynamic actions: vowels are obtained in the process of lowering the lower jaw (increasing the aperture) from a minimum (closed /i/) to a maximum (open /a/) while consonants are obtained in the process of raising the same organ (reducing the aperture) from a minimum (approximate) to a maximum (stops, with total stricture) through fricatives (obstruents). Combining this proposal with the CVC syllabic format of the morphophonological constraint entails that the syllable is a unit of expiratory action during which up to three mandibular shifts may occur (closing, opening and closing), forming the syllable's kinetic cyclical programme (MacNeilage's Frame / Content Theory, 1978); recent studies suggest that the syllable has emerged from recombining kinetic actions that preexisted separately: shouting (an alteration of expiring by the vocal chords) and, for the mandibular oscillation, eating in all its forms (breastfeeding, licking and so on). In this view, the CVC template is the integration and coordination of a mandibular oscillation borrowed from a specific family of motoric programmes with an expiratory sequence, belonging to another family of programmes. The shift from a symbolic approach to an embodied one requires that these elements be taken into account.

B. Arguments against submorphemics

Submorphemes are usually considered as non-existing objects for a number of reasons including the following:

submorphemes are unnecessary and therefore sporadic: birds of a feather flock together -in this proverb the verb flock can be related with one submarker, fl-, but the noun bird does not appear to contain any such element and is quite successful in relating with the avian notion in the absence of any classifying submorpheme.

submorphemes are not unified and continuous linguistic objects: what may appear as objects in present-day English cannot always be traced as continuous objects in the history of the language. Philps (2003b) extensively discussed the role of Indo-European *s-mobile in the formation of bi-consonantal initial clusters. The inclusion of one given lexical item depends on the semantic definition of the submorpheme in the first place: if sp is defined as "pointed" as is done by Tournier, spend is to be excluded from the series; but Bottineau proposes "a rapid centrifugal movement", which includes pointed objects that can be cast by means of a similar movement (spear, spike). In this definition spend is included (cf. to go on a spending spree), but this in turn raises the question of the continuity of the submorpheme sp in lexical diachrony: the present-day paradigm, which includes spear and spend, is made to incorporate words bearing an original sp-cluster along with words historically starting with a latin exprefix; for this reason, submorphology is frequently rejected as folk etymology.

Discussion: this argument mixes two dimensions, synchrony and diachrony. Synchrony is about how a subject is able to construct a systematic knowhow out of reiterated experiences, both passive (interpretation of others' statements) and active (personal production). One does not see how this knowhow should take into account the academic knowledge of the word's history as no popular access to it is can be observed. Instead, analogy may be instrumental in fostering morpho-semantic connections: random resemblances between semantically similar words are taken as memo-technical cues and become submorphologically meaningful; thus a word which evolves phonologically by reducing a prefix to an s-incidentally becomes a competent candidate for incorporation into the "club" of sp-class nouns, and, if the connection turns out to appear relevant, even metaphorically, the inclusion is implemented.

submorphemes have too many exceptions. This in fact depends on two factors: (i) the semantic categorization of the lexical class; see above the discrepancy between Tournier and Bottineau about sp: the latter's formulation makes sp's inclusive power much more farreaching. And (ii) the formal properties of the submorpheme considered, and more generally the boundaries of the morphological format accepted for submorphemes. As a rule, initial biand tri-consonantal clusters are those with the lowest proportion of exceptions, as low as 10% for sp, although quantifying is problematic on account of derivation and frequency. If one considers Tournier's uni-consonantal clusters, more exceptions than matches are likely to be found. As regards final submorphemes, they are more limited in number and should probably be treated as a particular case. And more generally, scores of ordinary words like car, chair, eat are devoid of submorphological semantic classifiers: obviously the system is not intrinsically needed; not all words bear the morphological signature of the semantic field they belong to. In other words, up to a certain point, the submorphology of the English lexicon bears some resemblance with the semantic classifiers of Bantu and West-Atlantic languages, but without their formal systematicity.

submorphemes are phonosymbolic. Clarifications are required here. (i) literally, any morpheme is phonosymbolic by definition: a piece of vocal action like chair is supposed to be reminiscent of the prototypical object in the presence of which the word was repeatedly heard by the infant in the presence of adults. Literally, any meaningful piece of vocal action is an ideophone. (ii) submorphemes are sensomimetic: on the semantic side, consonant clusters underline some piece of sensori-motor experience through which an object is apprehended: st points to a notable lack of movement, sp to a centrifugal movement (according to Bottineau), scr to a friction, gl to luminosity, and so on. The difficulty is that on the phonic side, consonant clusters are also pieces of sensori-motor experience: vocal hypo-sub-actions involving the interaction of active articulators (the vocal cords, the blade, the apex, the teeth, the lips) and passive articulators (the hard and soft palate, the alveolar ridge, the teeth 2 ) whose tactile proprioception is systematically carried out by sensors located in all the relevant organs; vocal actions whose perturbing effect in the surrounding atmospheric environment is immediately perceived by auditory means; and finally, vocal actions whose muscular counterparts are at least partially visible on any speaker's face from the hearer's position 3 . Any word can be defined in the terms of selected sensori-motor couplings on the side of the signifier, but on that of the signified, words refer to "objects" and "events" whose experience implies a whole range of highly heterogenous sensations: a church is a place with a given visible structure, but also a place in which one will stand, sit and occasionally kneel and walk, have contact with stone and wooden elements, hear songs, psalms, readings and homilies, smell incense. In this example, none of those competing sensations is selected: the word church does not display any submorpheme. In the word spire, one selected visual impression attached to the object, pointedness, is selected by one submorpheme, sp, itself a sensori-motor complex in terms of vocal action.

Because of this mapping it is tempting to look for analogical matches between the linguistic and non-linguistic experiences. This is the choice implicitly made by most submorphologists: Tournier, for instance, explicitely states that the ideophonic element is motivated by an unidentified synesthaesia (as opposed to onomatopeia, in which a linguisic sound mimicks a natural sound without requiring any perceptual shift: cock-a-doodle-doo). Tournier does not suggest that submorphemes might well be just as unmotivated or de-motivated as full-fledged words, and the effect of this bias is manifest in his presentation of English ideophonic elements: the table indicates (i) the marker, sp, (ii) the purported meaning, "pointed", but nothing is said about (iii) the iconic connection, that is, what kind of senso-mimetic connection there should between the two clusters of impression, the vocal action sp on the one side and the experience of a spire on the other -where does one feel, see or hear sp to involve pointedness? One might even add that st sounds and feels more adequate than sp for this kind of impression. In the same way, the connection between gl-and luminosity is widely acknowledged (Bolinger 1940(Bolinger , 1950(Bolinger , 1953(Bolinger , reprinted in the volume of 1965)), in English as well as in Semitic languages, but in present-day English what kind of synesthesia might link the impression left by the vocalization with that left by the object is a mystery. So a reasonable attitude might consist in (a) investigating the existence of submorphemes as lexical-semantic classifiers in English and (b) cautiously hypothesizing remote diachronic motivations involving onomatopeia and then synesthesia. However, these connections might be far too distant to be traceable, and they do not explain why submorphology remains active in the current lexicon. Thus, leaving aside the question of motivation, ideophonic elements should be understood as sensophonic classifiers.

the impressive value of submorphemes is objectively difficult to determine and therefore highly exposed to the danger of subjectivism and unfalsifiability. In some cases there emerges a "natural consensus" over semantic values: gl-is consistently associated with luminosity by authors, st-with fixity, sw-for pendulation (swing, sweep, swap, swim, swoon), so that there is no real space for controversy. In some cases, the consensus is motivated by a relatively obvious onomatopaeic background: /skr/ as in screech, scratch, scrub) for a sound-generating disordinate movement applied to a surface. In other cases, the consensus seems to be caused by analogous non-auditory sensations which should not be treated in terms of synesthesia either: wr-is said to underline the notion of torsion in wring, writhe, wriggle, write and many other words; in this series the possible analogy lies between the tactile experience of twisting a body or an object and the tactile proprioception of the movement of the tongue required for producing an apical /r/. But in most cases, the semantic unity is not so clear and the sensorimotor connections either, so that varying semantic classes may be proposed: This mismatch is motivated by three methodological protocols underlain by three different projects:

-Tournier's goal is to arrive at the heuristic proposal of a semantic classification on the basis of intuition. Introspection is the rule, and subjectivity is compensated by empirical investigation into English-speaking subjects's own intuitions: according to Tournier, a majority of interrogated subjects will agree on the values ascribed to ideophonic elements, either immediately, or after some reflection. In Tournier's approach, some words are implicitely regarded as central, prototypical representatives of the class: spear, spike and spindle for sp and pointedness. As a result, an ideophonic element's value can usually be glossed by a term containing the very submorpheme in question, and this is illustrated by unilingual dictionaries' tendency to define words using terms containing the same cluster.

-Bottineau's project is to account for the embodied nature of both the semantic experience of the signified and the articulatory experience of the signifier -in short, bridge the gap between the two domain and reduce a binaristic, symbolic conception in favour of a functionally unified one.

The experience-based semantics of submorphemic markers

As a general principle, submorphemic elements do not underline homogenous collections of actions and objects. Rather, they emphasize one salient, and therefore relevant, piece of multimodal sensori-motor experience through which the object can be apprehended; submorphemes relate concepts with keynote experiences through which they are captured:

-/sp/: centrifugation, rapid rotation, ejection. This submarker is found for actions and objects which are seen as rotating things (spindle) or events (spin); it also appears in objects whose ordinary use imply a rotating movement on the part of the human agent: spoon, spear, spade. A spoon is "rotated" for the purpose of collecting food or throwing a stone (roman catapults); a spear is "rotated" when thrown away; a spade is "rotated" when manipulated.

-/st/: stability, fixity. This submarker is found (i) in verbs expressing the absence of movement or change: stand, stay, still; (ii) verbs expressing the terminal access to a state of stability: stop, stoop. This terminal state may concern either a human agent, or the object he manipulates as an instrument: sting, stab, stick.

-/sw/: pendulation. This marker is found in (i) verbs of human attitude or action involving a bodily oscillation (swoon, sway, swim), (ii) transitive verbs implying the use of an instrument or object with the corresponding movement (sweep, swap, switch), (iii) intransitive verbs referring to the alternating movements of non-human external objects (swing, swivel).

As is illustrated by the preceding examples, one ideophone is applicable to the three conceptual domains spanning from the subject to the object: The lexical submarker focusses the interpreter's attention on one dynamic sensori-motor coupling that will ordinarily characterize the human subject's interaction with the object (be it that a thing, an event, an action); whether this interaction is motoric (a spoon) or visual (to spin) is irrelevant; whether it primarily affects the subject (to spew), the object (a sparrow) or both (a spoon) is ignored: perception is a type of action that will involve sensori-motor couplings and the retrieval of multimodal knowledge of the experience of the object / event / action and the way in which both the subject and the object are reciprocally affected in the interaction. In short, the submarker gives substance to the dynamic experience codeterminating the perceiving-acting subject and the object targeted in the environment. In this sense, ideophonic markers can be defined as phenomenological classifiers: they do not describe or symbolize the external, objective reality; instead, they provide the interpreter with a prediction of the way in which an object might behave (a spider), or be used (a spoon), or the sensori-motor way in which an event or action is likely to be experienced (to spew, to spawn). In other words, submarkers pass a subjective comment on the detection of objective "things": they indicate how experience is, in Varelian terms, enacted. In Varela's theory of perception [START_REF] Varela | The Embodied Mind: Cognitive Science and Human Experience[END_REF], enaction is the way in which the perception of the environment by living agents consists in mapping sensation (a bottom-up input or signal) against anticipation (a top-down conteracting output or signal) of what subsequent sensations, happenings and relevant actions might be (for example, the anticipation of edibility, good smell and taste and pleasure on seeing and hearing sizzling bangers or melting chocolate in a TV advertisement).

In the same way, the word sponge is a vocal action (articulating "sponge") and perception (sensing oneself wording sponge through the tactile captors located in the tongue and all the active and passive articulators of the oral tract; hearing oneself or anybody voice the word), that is, a multimodal sensori-motor coupling whose effect is to activate "meaning", a hierarchized network of "features" (as they are defined in the first section). According to the referencialist approach to language, this context is first and foremost "the object to which the word refers", that is, the thing on which the word is supposed to focus the interpreter's attention. As it happens, the word may very well be used in the absence of the corresponding object, if any; it has even been pointed out that newly-borns and infants hear the French word cochon "pig" in comparisons like tu en mets partout comme un cochon "you spill your food all over the place like a pig" long before they ever come across the animal, even in picture books.

In developmental terms, this shows that the recorded meaning of the word is primarily the stereotypical discourse accompanying it in social situations involving protypical actions and agents (in this case, eating and the family): "a pig is something which spills its food as I do"; and secondarily, the stereotypical association may be mapped against recurring non-linguistic impressions -in this case the "pig" itself once encounters with the animal (in books and/or in real life) stabilize the connection and are recorded as a match ("this is a pig"). In one exceptional case, I heard an English mother use the words pig, spill and spread about her child, and she heard herself doing that, so that she eventually came up with the playful portmanteau word spig: "a pig that is likely to spread its food". In so doing, she had embedded a submorphemic element, sp, into the lexical unit pig: she had enacted the "spprediction" for pigs and thus adjusted the label to the current relevance that motivated her applying the term to her own child.

More generally, the submorphemic marker passes the same kind of culturally stabilized pragmatic comment on the notion reactivated by the lexical unit. This explains the randomness of the phenomenon:

(i) an object may well not be marked by the comment it obviously call for: in English a broom is not a sw-word, on account of the synecdoche plant > object. In Spanish, escoba is marked by the /sk/ submorpheme "movement applied to a surface" that is found in English words like scour, scrub etc.: broom might also have been an sk-word, and is one of them indeed in other languages. Book is kniha in Czech, knigu in Russian: an articulated object comprizing two moving parts and a hinge like a knee, a knob, a knife, to knit, a knot etc.; book might have been a kn-word in English, but is not.

(ii) in one given language, the diverse communities which have participated in the introduction of lexical strains may have passed diverging pragmatic comments over the same objects and activities, so that in the present-day language different "visions" will cohabit. For instance, to write "refers" to an activity which is characterized by wr-as a specific movement, the experience of torsion (cf. wring, wrist, wrestle, writhe, wriggle, wrath, wrought, wrap, wreck, wretch, wry…). But in the Latin strain, scribere has left script, inscribe, scribble, scrabble, écrire in French, escribir in Spanish, schreiben in German, all of which involve the scr-submorpheme: a friction applied to a surface by an agent. This marker may have resulted from two merging strains, sk+r (surface + agentivity: scrub, scroll, scratch) and the scronomatopeia (screech, shrill). Clearly, two competing pragmatic outlooks have shed diverging submorphemic lights on the same notion, and the socio-linguistic signature of the comments is engrained in the lexical distribution: wr-is reserved for ordinary experience in daily life (write) while scr-is reserved for abstract applications and technological jargon.

These elements indicate that submorphemic markers should be treated as inbuilt pragmatic cues developed in the course of the linguistic tradition and culture attached to a given speaking community: they do not indicate the way in which an object determines an individual subject's perception or action, but the random way in which a community has constructively focussed on a selected cue at the expense of potentially available alternative ones. The notion of cue raises the question of the cognitive relevance of submorphemes for individual subjects and how a submorphemic competence or sensitiveness may be formed in language acquisition.

4.

Do speakers actually develop a submorphemic knowhow? Submorphemic units represent a serious phenomelogical challenge: the linguist detects semantic consistency which emergences from lists of words that he has created on his own; this semantic response is motivated by the very presentation of the object of analysis, and the risk of circularity has to be circumvented. At least two possibilities can be envisaged:

-either the detection of submorphemic semantic consistency occurs if and only if the interpreting subject is confronted with lexical strings that make the isomorphisms detectable and favour the construction of analogical connections. In this case it has to be shown the ordinary speakers are given the opportunity to experience submorphemic resemblances together and are likely to compare them and derive semantic links.

Otherwise the linguist's phenomenological co-determination of the object and his own self remains idiosyncratic and submorphology is not experienced by the speaking community. Even so one would have to explain why the lexicon tends to self-organize diachronically in a way that is apt to foster this kind of semantic mirage.

-Or the detection of this semantic unity is obtained directly by the speakers, without the help of experiencial stimuli. The theoretical cost of this hypothesis is extremely high as it requires either the phonosymbolical determination of the form / meaning connections, or, even worse in our view, the innate programming of those links in universal grammar, making them independent from experience.

-A middle-of-the-road position consists in proposing that form-meaning associations have to be initiated by the experience of privileged discourse contexts, fostered by linguistic practices and scaffolded by the speaking community before the subject is able to go on incorporating additional lexical units into pre-existing ensembles.

-Submorphemic elements in language acquisition

The detection of ideophones as semantically relevant submorphemes requires at least some of the following features: (i) the number of lexical units whose stressed syllable bears semantically colourful submorphemic clusters has to be sufficiently high in relation to "uncolourful" ones to be detectable and noted. And (ii) the possibility for the subject to detect isomorphisms out of which semantic analogies can be drawn has to be established. It is easy for the linguist to associate sleep with slumber on the basis of the sl-connection in the list he has created, but in the subject's spontaneous experience of language it seems unlikely that the sleep / slumber relation may emerge unless the two words are regularly encountered in a shared environment in which this very connection is emphasized. An empirical survey suggests that this is the case in nursery rhymes and lullabies:

(i) selected words are repeated a number of times, so that making the remembering process facilitated, and the child is given the opportunity to practice the sensori-motor dynamics of articulation: In the dark and out of sight, There's angels to watch over you. This is not to suggest that -ight forms a submorphemic element in its own right, but that this lullaby forms the kind of relevant candidate from which a pattern is potentially derivable: night = "vision is obscured", light = "vision is favoured" and sight = "vision" (unspecific / unmarked); so in this local network -ight = "vision", n-= negative, l-= positive and s-= neutral. For this local network to be extrapolated and stabilized it has to be confirmed by other instances like Then you show your little light, / Twinkle, twinkle, all the night in Twinkle, twinkle little star; and it should not be counterpoised by overwhelming adverse examples. In this respect the case of -ight is dubious as it may be confirmed by bright and white (so long as the spelling is ignored) but not by right and fight; initial n-is regularly connected with negation (and in Slavic languages the d-/n-contrast underlies both the semantic day / night pair and the grammatical yes / no pair: Russian den / not', da / niet). So the kind of environment formed by this poem is not sufficient to determine the systematic and universal construction of submorphemic analogies framing all learners' lexical systems, but it may well participate in the emergence of submorphemic connections in the learner's personal experience encounters other similar networks.

Bees A swarm
(iv) Words bearing the same submorpheme are frequently found together:

Itsy-Bitsy Spider

The The process is repeated ten times with as many different locations on the body.

One should not, of course, exaggerate the power of nursery rhymes and lullabies. What really matters is the extent to which they are intuitively used as linguistic standard-setting models by parenting adults teaching their offspring to recognize words, understand their meaning and practice their articulation. Children are actually taught to rely on submorphemic analogies to form semantic networks and learn associative stereotypes, and the question is whether they do trespass a critical threshold beyond which they become autonomous analogists and start incorporating new isolated lexical items into pre-existing submorphemic files without the stimulus of rhyme, paronomasis and so on.

-The popular awareness of submorphemic dynamics

According to Tournier ideophonic elements are no longer productive in that English-speaking communities do not create new clusters any longer. Tournier does not say that existing clusters are fossiles which have fallen under the surface of intuitive detectability. Indeed, traces of neologisms motivated by submorphology can be evidenced, both in academic and popular literature: in Dicken's A Christmas Carol the protagonist's name is Scrooge, in reference to the notion of scratching the soil for food, making the name suggestive of a rodent's or vulture's. The name of one of the characters in the film Trainspotting is Spud, and, as mentioned earlier, a famous trademark has produced the Swatches. In 1983 Douglas Adams and John Lloyd published a small and humorous dictionary entitled The Meaning of Liff. It consists in a list of place names located in English-speaking countries (most of them in the British Isles); these names are taken to be nouns and given a definition:

BANFF (adj.): Pertaining to, or descriptive of, that kind of facial expression which is impossible to achieve except when having a passport photograph taken.

GLASGOW (n.):

The feeling of infinite sadness engendered when walking through a place filled with happy people fifteen years younger than yourself. SKETTY (n.): Apparently self-propelled little dance a beer glass performs in its own puddle.

Some connections are inspired by direct lexical plays on words: Hastings is "things said on the spur of the moment to explain to someone who comes into a room unexpectedly precisely what it is you are doing". But in many cases submorphemic clusters are instrumental in inspiring a lexical interpretation for the toponym: Blean ("a measure of luminosity"), Glossop, Sneem, Stebbing ("an unconcealable erection"), Skegness, Spofforth, Sproston Green, Swanage, Wrabness, Writtle, etc., hundreds of toponyms are selected for their colourful sonority -and the potential correlations borne by the submorphemic elements they contain, frequently echoed in the definitions. Obviously the authors were receptive to the sense-making effect of the submorphemic hypo-sub-actions and trusted their potential readers to share this semantic experience.

Folk etymology is another domain in which submorphology will strive. Here is an excerpt from an online academic medical dictionary (which borrowed its information from various sources, including the Webster's edition of 1913, accessible online4 : SCALL : a scurf or scabby disease, esp. of the scalp.

SCALD < excaldare: to run off like a scalded cat ; a scald, a boil SCALL < ON skalli "bald head"

A scald is a burn caused by very hot liquid or steam. Variant of skald.

Variant of scall.

A skald is normally a bard while a scald is a burn on the skin. Hundreds of occurrences of this scald / skald confusion can be googled up and it seems quite obvious that we are dealing with competing analogies: scald / scab on the one side, skald / skin on the other. In the same way scall, from old norse skalli "bald head", is mistakenly considered as a "variant of scall", and Skall is the name of a body artist:

Visual artist before anything, Skall considers his body as a raw material to produce art. In his performances, he invites the spectator to assist in a transformation, more specifically, his transformation. The transformation that takes place is not only physical but is also of psychological nature. Some speakers are fully aware that there may exist a mismatch between etymology and the way in which lexical units are reorganized in present-day English. Here are two suggestions for the origin of the word slang:

SLANG

The origin of the word "slang" is unknown, but it may come from the term "thieves" language" where the possessive "s" from thieves" and the "lang" from language are run together to make the word slang.

So now we are all "on the same page," as it were, with regard to our definition of slang, let us at this time turn to the origin of this noun. Etymonline informs us that slang derives in all likelihood from "a Scandinavian source, cf. Norwegian slengenamn "nickname," slengja kjeften "to abuse with words," literally "to sling the jaw," related to Old Norwegian slyngva 'to sling'."

However, both Etymonline and the OED agree that these etymological suppositions are just that, and that "the ultimate source [of the word] is not apparent."

At any rate, it appears that even the word slang itself is colorful. In other words, I sling slang. I slung slang with far-flung, fun-in-the-sun abandon. And so on...

Beyond the contradiction between the two proposals, the second one clearly states that knowing the origin of the word may not be cognitively relevant in the determination of its present-day colour, which is not explicitely defined but is exclusively based on the submorphemic common denominator: colorful is here the intuitive formulation of what we have called the semantic effect of the hypo-sub-action. Here is a discussion about the word snobe, found in a forum5 :

Can somebody answer this stupid riddle for me please?

If all snubes were snobs, and all snobes are snoobs, then why don't the snoobs get along with the snobs if they both think the same way as the snobes? but not all snobs are friends with snoobs because the snobes never liked the snorps, by the way the snorps are not related to the snoobs, nor the snobes, but the snobs liked them. If the snobes don't like the snorps, and the snorps didn't like the snobs, then nobody liked anybody's family, until the snobies came along...the snobies were a special family, and started hanging out with the snorps, who didn't like the snobs, because all they wanted to do was snoop. So the snobies thought they were being sort of snooty, and told them to shut up. But then Sally stepped in, and told the snobies not to talk to the snobs, because the snorps don't like the snobes anymore than the snobs like the snobies. So who is talking to who now?

This of course is an extreme example in which the writer has deliberately played with sounds, but it must be added that submorphemically motivated turns of phrases and idioms do tend to emerge in everyday language, like to go on a spending spree, scant and scarce (scarce < excerptus and scant < ON skammr "short"):

Although it is one of the driest deserts in the world, with scant and scarce rainfall, when it does rain, the wildflowers, like these lupins and colorful yellow flowers, bloom for a short time.

In my corpus it appears that the order of the adjectives is overwhelmingly i) scarce and ii) scant in predicative position and the other way round in attributive function:

Most of the land is arid and desert; rainfall is scarce, vegetation scant, and very little of the land is suitable for agriculture.

Alternative energy sources are scarce and scant. Only one institution reported their use, a pilot photovoltaic installation.

In this combination sk-plays the role of the unvarying common denominator in relation to which an -arce / -ant variable is articulated. In context, scarce takes on a heuristic value: it provides an objective measurement of the quantity; and in relation to it, scant is hermeneutic: it adds an evaluative undertone and passes a modal judgment on the underlying quantification. This sequence can be analyzed as an operation / result sequence (the discovery and the evaluation of the quantity). In attributive constructions this schemata is preconstructed and lexicalized, which is marked by the inversion (cf. to surge up > upsurge, to hunt whales > whale-hunting, be scarce and scant > scant and scarce N). The submorphemic marker fixes a trajectory that can be improvised and run forward or retrieved and run backwards.

Conclusion

Investigation into the cognitive relevance and popular availability of submorphemic markers is incipient. The latter can be defined as the markers of the sensori-motor couplings through which objects and events are culturally assumed to be apprehended: vocal hypo-sub-actions with a characterizable contribution in the distributed sense-making process. Considering the evidence, there is good reason to believe that they cannot be merely explained by the lexicon's apparent tendency to self-organize as an autonomous system disconnected from the intersubjective interplay and subjective experience; and they must be taken into account to describe the subjects' lexical-semantic linguistic knowhow. On the basis of the problematic we have outlined, systematic corpus and field research is required to quantify and formalize the distribution of the submorphemic experience in language acquisition and verbal practices in families and schooling systems, but also in suburban social tribes, with all the social variation this implies. Since the submorphemic competence emerges from specific verbal practices in differentiated social environments, one should not expect there to be a fully unified treatment of the phenomenon. However the possibility of common values between those practices remains open, and the empirical basis of this cognitive dynamic has been outlined.

Bibliography

Anscombre, J.-C., 2001 : « Le rôle du lexique dans la théorie des stéréotypes », Langages, 142, 57-76.

  What this table reveals is that the spatial locus of the property marked by the submorpheme on the subject-object scale is not taken into account. This is confirmed by hybrid cases in which an object is submorphologically labelled in the terms of the action implied for an implicit but necessary agent: a switch is an appliance that is meant to be switched by an agent; a Swatch (a brilliant neologism based on a "mobile s" that is reminiscent of the Indo-European one) is a watch one will catch sight of by making a circular movement of the arm (a rotation of the sp class, indeed), then to come back to the initial position. This reciprocal contamination of the subject's and object's dynamic properties is most visible in the case of conversions (to switch, a switch; to stitch, a stitch) and valency alternations (to stop: (semantically) reflexive, transitive). A combination of the two processes can cause one lexical item to cover the three levels:

		SUBJECT	MEDIUM	OBJECT
	SP	Speak, spit, spew	Spoon, spear, spade	Spindle, spawn
	ST	Stand, stutter, stumble	Stir, start, stop	Stick (the object), star, stub
			(in transitive use)
	SW Swim, sway	Switch, swap	Swing
		SUBJECT		MEDIUM	OBJECT
	stop Reflexive		Transitive	Noun
		To stop (doing something)	To stop someone	A bus stop

  Rhymes consist in emphasizing a final constant and distinguishing an initial variable; to create a rhyme is to cause the orientee to detect an analogical link between two previously unrelated lexical items.

	Is worth a load of hay;
	A swarm of bees in June
	Is worth a silver spoon;
	A swarm of bees in July
	Is not worth a fly.
	(ii) Some lullabies and nursery rimes are densely loaded with ideophonic clusters:
	Twinkle, Twinkle, Little Star
	Twinkle, twinkle, little star,
	How I wonder what you are!
	Up above the world so high,
	Like a diamond in the sky.
	Twinkle, twinkle, little star,
	How I wonder what you are!
	(iii) Humpty Dumpty
	Humpty Dumpty sat on a wall,
	Humpty Dumpty had a great fall;
	All the King's horses, and all the King's men
	Cannot put Humpty Dumpty together again.
	And indeed one of the requirements for a rhyme to be accepted as such is that it should never
	associate two identical suffixes as is done by Vincent Voiture (c.1630), a practice parodied in
	Molière's Tartuffe and denounced in Voltaire's Rhétorique:
	Estampe et crampe vrayment,
	Riment admirablement.
	The following lullaby is remarkable:
	Angels To Watch Over You
	When you go to bed at night
	And you turn off all your lights;
	of bees in May

This metaphorical, somewhat Californian-sounding terminology is only meant to emphasize the collaboration of vocal and mental dynamics, which are not understood as separate processes. The elaboration of an adequate and, hopefully, more elegant terminological apparatus is still under way, but we feel an urgent need to override the reificating effect of conventional and static terminology.

The teeth are used as passive articulators against the the tongue, but as active articulators against the lips in the case of labio-dental fricatives. In English the lips are used as active articulators (bi-labials and labio-dentals) but not as passive ones (there exists no such thing as apico-(bi)labial phonemes).

In Stanley Kubrick's film 2001 : A Space Odyssey, the computer Karl manages to "interpret" the astronauts' conversation out of just seeing the movements of their lips as they talk. This is of course an impossibility as not all articulators are visible, unless one postulates that the action of internal articulators has secondary effects on external ones which can be detected and plotted. However the visual perception of muscular action, along with bodily gestures and eye contact, is instrumental in sense-making processes in non-vocal sign languages.

The ARTFL Project, University of Chicago: http://machaut.uchicago.edu/CGI-BIN/WEBSTER.page.sh?page=1282

http://th.answers.yahoo.com/question/index?qid=20071211192841AAcv1qf