Christophe Morvan
email: christophe.morvan@irisa.fr

On rational graphs

Using rationality, like in language theory, we define a family of infinite graphs. This family is a strict extension of the context-free graphs of Muller and Schupp, the equational graphs of Courcelle and the prefix recognizable graphs of Caucal. We give basic properties, as well as an internal and an external characterization of these graphs. We also show that their traces form an AFL of recursive languages, containing the context-free languages.

Introduction

When dealing with computers, infinite graphs are natural objects. They emerge naturally in recursive program schemes or communicating automata, for example. Studying them as families of objects is comparatively recent: Muller and Schupp (in [MS 85]) first captured the structure of the graphs of pushdown automata, then Courcelle (in [Co 90]) defined the set of regular (equational) graphs. More recently Caucal introduced (in [Ca 96]) a characterization of graphs in terms of inverse (rational) substitution from the complete binary tree. Step by step, like Chomsky's languages family, a hierarchy of graph families is built: the graphs of pushdown automata, regular graphs and prefix-recognizable graphs.

To define infinite objects conveniently, we have to use finite systems. For infinite graphs, two kinds of finite systems are employed: internal systems or external systems. Roughly speaking an internal characterization is a machine producing the arcs of the graph. An external characterization yields the structure of the graph (usually "up to isomorphism"). There is, of course a relationship between internal and external characterization: for example the pushdown automata are an internal characterization of the connected regular graphs of finite degree whereas the deterministic graph grammars are an external system for the family of regular graphs.

The purpose of this article is to give both internal and external characterization of a wider family of graphs. Using words for vertices, rationality (like in language theory) will provide an internal characterization; it will also give basic results for this family: for example rational graphs will be recognized by transducers; a rational graph is a recursive set; determinism for rational graphs will be decidable. Then inverse substitution from the complete binary tree (like in [Ca 96]) will be an external characterization of this family. Strangely this extension will prove to be a slight extension of the prefix-recognizable graphs: instead of taking the inverse image of the complete binary tree by a rational substitution we will consider the inverse image of the complete binary tree by a linear substitution (i.e., a substitution where the image of each letter is a linear language). Finally properties of the traces of these graphs will be investigated: we will show that the traces of these graphs form an abstract family of (recursive) languages containing the context-free languages.

Rational graphs

In this section we will define a new family of infinite graphs, namely the set of rational graphs. We will state some results for this family and give examples of rational graphs.

Partial semigroups

This paragraph introduces rationality for partial semigroups and uses this notion to give a natural introduction for rational graphs. We start by recalling some standards notations: for any set E, its cardinal is denoted by |E|; its powerset is denoted by 2 E . Let the set of nonnegative integers be denoted by N. A semigroup S is a set equipped with an operation • : S × S → S such that: for all u, v in S there exists w in S such that

•(u, v) = w denoted by u • v = w and this operation is associative (i.e., ∀u, v, w ∈ S, (u • v) • w = u • (v • w).
Finally, a monoid M is a semigroup with a (unique) neutral element (denoted ε along these lines) i.e., an element ε ∈ M such that for all element u in M u • ε = ε • u = u. Now, a partial semigroup is a set S equipped with • : S × S → S, a partial operation, with D ⊆ S × S the domain of •; set D need not be S × S. Moreover we impose this operation to be associative as follows:

[(u, v) ∈ D ∧ ((u • v), w) ∈ D] ⇔ [(v, w) ∈ D ∧ (u, (v • w)) ∈ D] and in that case, u • (v • w) = (u • v) • w.
Meaning that if multiplication is defined on the one side, then it is defined on the other side and both agree. Notice that a partial semigroup S such that D is S × S is a semigroup.

Example 2.1. Given two semigroups (S 1 , • 1 ) and (S 2 , • 2 ) such that S 1 ∩ S 2 is empty. The union S = S 1 ∪ S 2 , with the partial operation • defined as • 1 over the elements of S 1 and • 2 over the element of S 2 , is a partial semigroup.

Taking a new element ⊥ we complete any partial semigroup S into a semigroup S ∪ {⊥} by extending its operation • as follows:

a • b = ⊥ for all a, b ∈ S ∪ {⊥} such that (a, b) ∈ D. Also the product S ×S ′ of two partial semigroups S and S ′ is a partial semigroup for operation • defined componentwise: (a, a ′ ) • (b, b ′ ) = (a • b, a ′ • b ′ ) for all (a, b) ∈ D and (a ′ , b ′ ) ∈ D ′ .
In order to define the rational subsets of a partial semigroup, we have to extend its operation to its subsets:

A • B := {a • b | a ∈ A ∧ b ∈ B } for every A, B ⊆ S
The powerset 2 S of S, is a semigroup for • so defined. Now, a subset P of a partial semigroup S is a partial subsemigroup of S, if P is a partial semigroup for • of S i.e., P • P is a subset of P . For any subset P of a partial semigroup S, following subset P + = n 1 P n (with P 1 = P and P n+1 = P n • P for every n 1) is the smallest (for inclusion) partial subsemigroup of S containing P . Set P + is called the partial semigroup generated by P . In particular (P + ) + = P + . Also, S is finitely generated if S = P + for some finite P . A set P ⊆ S is a code if there is no two factorization in P + of the same element:

u 1 • • • u m = v 1 • • • v n ∧ u 1 , . . . , u m , v 1 , . . . , v n ∈ P ⇒ m = n ∧ ∀ i ∈ [1 • • • n], u i = v i A partial semigroup S is free if there is code P such that P + = S.
For every W ⊆ 2 S , we denote by W = {a | ∃P ∈ W, a ∈ P }. Operator + commutes with operator , i.e., (W + ) = ( W ) + for every W ⊆ 2 S . The (left) residual u -1 P of P ⊆ S by u ∈ S is following subset:

u -1 P := {v ∈ S | u • v ∈ P } and satisfies following basic equality:

(u • v) -1 P = v -1 (u -1 P ) for all u, v ∈ S and P ⊆ S.

Definition 2.2. Let (S, •) be a partial semigroup. The family Rat(S) of rational subsets of S is the least family R of subsets of S satisfying the following conditions:

(i) ∅ ∈ R; {m} ∈ R for all m in S; (ii) if A, B ∈ R then A ∪ B, A • B and A + ∈ R.
In order to generalize well known results for monoids in the case of partial semigroups, and as our purpose is to deal with graphs, we will set some notations and definitions for graphs and automata.

Let P be a subset of S. A (simple oriented labelled) P -graph G over V with arcs labelled in P is a subset of V × P × V . An element (s, a, t) in G is an arc of source s, goal t and label a (s and t are vertices of G). We denote by Dom(G), Im(G) and V G the sets respectively of sources, goals and vertices of G. Each (s, a, t) of G is identified with labelled transition

s a -→ G t or simply s a -→ t if G is understood. A graph G is deterministic if distinct arcs with same source have distinct label: r a -→ s ∧ r a -→ t ⇒ s = t.
A graph is (source) complete if, for every label a, every vertex is source of an arc labelled a: ∀a ∈ P, ∀s ∈ V G , ∃t s a -→ t. Set 2 V ×P + ×V of P + -graphs with vertices in V is a semigroup for composition relation:

G • H := {r a•b -→ t | ∃s, r a -→ G s ∧ s b -→ H t} for any G, H ⊆ V × P + × V . Relation u -→ G + denoted by u =⇒ G or simply u =⇒ if G is understood, is the existence of a path in G labelled u in P + . For any L in S, we denote by s L =⇒ t that there exists u in L such that s u =⇒ t.
The trace (or set of path labels) L(G, E, F ) of G from a set E to a set F is the following subset of P + :

L(G, E, F ) := {u ∈ S | ∃ s ∈ E, ∃ t ∈ F, s u =⇒ G t }
Given P ⊆ S, a P -automaton A is a P -graph G whose vertices are called states, with an initial state i and a subset F of final states; the automaton recognizes subset L(A) of P + : L(A) := L(G, {i}, F ). An automaton is finite (resp. deterministic, complete) if its graph is finite (resp. deterministic, complete). This allows to state a standard result for rational subsets.

Proposition 2.3. Given a subset P of a partial semigroup S, Rat(P + ) is (i) the smallest subset of 2 S containing ∅ and {a} for each a ∈ P , and closed for ∪, •, + (ii) the set of subsets recognized by finite P -automata, (iii) the set of subsets recognized by finite and deterministic P -automata.

We simply translated the standards definitions of rational subsets of monoids given for example in [Be 79]. An interesting example of a partial semigroup is the subject of these lines: the set of arcs (labelled with an element of a finite set) between elements of a free monoid is a partial semigroup; its rational subsets are the rational graphs.

Partial semigroups and graphs

In this section, we will consider an important example of partial semigroup: the set of rational graphs. So consider an arbitrary finite set X and denote X * its associated free monoid. We will consider graphs as subsets of X * ×A×X * (the set of graphs over X * with arcs labelled in A). For convenience, set 2

X * ×A×X * is denoted G A (X * ). Now, with (u, a i , v) • i (u ′ , a i , v ′ ) = (u • u ′ , a i , v • v ′ ), set X * × {a i } × X * (a i in A) is a monoid.
As stated in Example 2.1 the union of these monoids (namely X * ×A×X * ) is a partial semigroup. We denote by • the operation in X * ×A×X * (which is • i for each X * × {a i } × X * ). Remark: this • operation for graphs is indeed, similar to the synchronization product for transition systems defined by Nivat and Arnold in [AN 88].

We are now able to define the set of rational graphs.

Definition 2.4. The set of rational graphs, denoted Rat(X * × A × X * ) is the family of rational subsets of X * ×A×X * .

Let us now recall that a transducer is a finite automaton over pairs (see for example [Au 88] [Be 79]). A rational relation (i.e., a rational subset of X * × X * ) is recognized by a rational transducer. There is a strong relationship between rational graphs and rational relations and to characterize the family of rational graphs in a more practical way we will use labelled transducers.

Definition 2.5. A labelled transducer T = Q, I, F, E, L over X, is composed of a finite set of states Q, a set of initial states I ⊆ Q, a set of final states F ⊆ Q, a finite set of transitions (or edges) E ⊆ Q × X * × X * × Q and an application L from F into 2 A .
Like for P -graphs, transition (p, u, v, q) of transducer T will be denoted by p

u/v -→ T q or simply p u/v -→ q if T is understood. Now similarly an element (u, d, v) ∈ X * × A×X * is recognized by transducer T if there is a path p 0 u1/v1 -→ T p 1 • • • p n-1 un/vn -→ T p n and p 0 ∈ I, p n ∈ F , u = u 1 • • • u n , v = v 1 • • • v n and d ∈ L(p n ).
Remark: an illustration of transducer execution will be given in Example 2.7.

Proposition 2.6. A graph G in G A (X * ) is rational if
G = d∈A R d , for R d ∈ Rat(X * × {d} × X * ); (iii) G is recognized by labelled rational transducer.
This Proposition states that for any graph G in Rat(X * ×A×X * ), the relation: ) (and similarly for subsets of X). Also for a rational graph G there are possibly many transducers generating it, thus we will denote by Θ(G) the set of transducers generating G.

d -→ G := {(u, v) | u d -→ G v} is rational for each d in A.
We will now give some examples of rational graphs.

Example 2.7. This graph :

a a a a b b b a a b b b A A 2 B AB A 2 B B 2 A 2 B 2 ε AB 2
is a rational graph generated by this transducer :

p q 1 a A/A q 2 b B/B A/A ε/A ε/B
Notice that its second order monadic theory is undecidable and therefore rational graphs have an undecidable second order monadic theory. Why does the arc (AB, b, AB 2 ) belong to the graph? Simply because the following path is in the transducer:

p A/A -→ p ε/B -→ q 2 B/B -→ q 2
and that b is associated to the final state q 2 .

Example 2.8. This graph : is rational, generated by this transducer :

1/1 0/0 r 1 r 2 r 3 a b c p 1/1 ε/0 0/1 0/0 0/1 0/0 1/ε 1/⊥ 1/1 q 2 q 1
We finish with a last example showing that the transition graphs of Petri nets are rational graphs.

Example 2.9. For more detail on Petri nets the reader may refer to [Re 85]. A Petri net can be seen as a finite set of transitions of this form:

A n1 1 A n2 2 • • • A nm m d -→ A l1 1 A l2 2 • • • A lm m
, with A x i representing there are x coins in place A i (d represents the label (if any) of the transition). Following transducer generates the transition graph associated to the above transition:

A 2 /A 2 A n 2 2 /A l 2 2 d q p 1 p 2 A n 1 1 /A l 1 1 A 1 /A 1 A nm m /A lm m
Each vertex of the generated graph correspond to a marking of the Petri net. Each arc of the graph represents that a transition has been fired.

Some results for rational graphs

This section will introduce results for this family of graphs. Some of these results are just a reformulation of known results over rational relations. Others are simple facts on these graphs and their boundary. The first fact is that this family is an extension of previous families. Simply recall that every prefix-recognizable graph (defined in [Ca 96]) is a finite union of graphs of the following form :

( U a -→ V ) • W := { uw a -→ vw | u ∈ U ∧ v ∈ V ∧ w ∈ W }
with U, V, W rational sets. This characterization ensures that prefix-recognizable graphs are rational graphs. As the regular graphs (defined in [Co 90]) are prefix-recognizable graphs, they are rational too. Furthermore, the graphs in Examples 2.7 and 2.8 are not prefixrecognizable graphs thus the inclusion is strict. Let us now translate some wellknown results for rational relations, to rational graphs (the proofs will be omitted they are mostly direct consequences of results found in [Au 88] and [Be 79]).

Proposition 2.10. A rational graph G is of finite out-degree if and only if there exists a transducer T ∈ Θ(G) such that there exists no cycle in T labelled on the left with the empty word which is not labelled on the right with the empty word. In other words the only cycles labelled on the left ε, are labelled on the right ε.

Remark: naturally this proposition can be translated to characterize the graphs of finite in-degree, by simply replacing right by left and vice-versa.

Proposition 2.11. Every rational graph is recursive: it is decidable whether an arc (u, d, v) belongs to a rational graph.

Theorem 2.12. It is decidable whether a rational graph is deterministic (from its transducer).

Proposition 2.13. The inclusion and equality of deterministic rational graphs is decidable.

Remark: unfortunately this result ceases to be true for general rational graphs ([Be 79] Theorem 8.4, page 90). We have already seen that the second order monadic theory of these graphs is undecidable in general. We will now see that it is also the case for the first order theory.

Proposition 2.14. The first order theory of rational graphs is undecidable.

Proof. We will prove this proposition by reducing Post's correspondence problem (P.C.P.) to this problem. Let us recall the P.C.P.: given an alphabet X and (u 0 , v 0 ), (u 1 , v 1 ),..., (u n , v n ) elements of X * × X * . Does there exist a sequence 0 i 1 , i 2 , . . . , i m n, such that

u 0 u i1 • • • u im = v 0 v i1 • • • v im ?
To an instance of P.C.P. (i.e. a family (u i , v i )) we associate following transducer:

p u 0 /v 0 q a u i /v i (for i ∈ [1 • • • n])
The resolution of P.C.P. becomes finding a vertex s such that s a -→ s is an arc of the graph generated by the transducer. It is a first order instance, therefore,as P.C.P. is undecidable, the first order theory of rational graphs is not decidable in general.

⊓ ⊔

Before giving another negative decision result, let us denote by ũ the mirror of word u (defined by induction on the length of u: ε = ε and au = ũa (for any u with |u| 0). Proposition 2.15. Accessibility is not decidable for rational graphs in general.

Proof. Once again, we use P.C.P. Using the same notations as earlier define a (word) rewriting system G, using two new symbols # and $, in the following way:

G    $ -→ u i $ v i ∀i ∈ {0, • • •, n} $ -→ # A#A -→ # ∀A ∈ X
Now "P.C.P. has a solution" is equivalent to the existence of a derivation from u 0 $ v 0 to #. But, considering the following transducer:

q a A/A(for A ∈ X) p A/A(for A ∈ X) $/u i $ṽ i (for i ∈ {0, • • •, n}) $/# A#A/#(for A ∈ X)
the question becomes: is there a path leading from u 0 $ v 0 to the vertex # ? Answering the last question would allow P.C.P. to be solved in the general case which is a contradiction. Therefore accessibility is undecidable for the rational graphs in general.

⊓ ⊔

Remark: the transitive closure of a rational graph is, at least, uneffective. If this construction were effective and rational, then accessibility for rational graph would be decidable. Now we will see a case where accessibility is decidable for rational graphs. A transducer T is increasing if every pair (u, v) recognized by T is such that the length of v (denoted by |v|) is greater or equal to the length of u : |v| |u|.

Proposition 2.16. The accessibility is decidable for any rational graph with an increasing transducer.

Proof. Let us denote by T n (u) following set: T n (u) := n i=0 T i (u). For all n ∈ N this set is rational. Now, let G be a rational graph generated by an increasing transducer T and let u and v be two vertices of G. Let us put n

0 = |{w ∈ X * | |u| |w| |v|}| = |X| |u| + • • • + |X| |v| .
Vertex v is accessible from u if and only if v belongs to T n0 (u). Thus accessibility is decidable for rational graphs with an increasing transducer.

⊓ ⊔

We now give a technical Lemma that allows the construction of a graph that is not structurally rational.

Lemma 2.17. Let G be a rational graph of finite out-degree. There exists two integers p and q such that for every (s, a, t) ∈ G we have |t| p.|s| + q Example 2.18. Consider an infinite tree in X * ×A×X * such that every vertex of depth n has 2 2 2 n sons. This tree is not strucurally rational, in other words whatever name are given to its vertices this graph is never a rational graph. This is a direct consequence of previous lemma: say n is the length of the root, there are at most |X| (np l +p l-1 q+•••+q) vertices of depth l.

Despite these results the transducers are not able to capture the structure of rational graphs. For example, this transducer:

p ε/AB q a A/A B/B
generates this graph:

a a a a a a a a a A 2 B 2 A 3 B 3 B A AB A 2 B A 3 B 2 A 4 B 3 A 3 B 4 A 2 B 3 AB 2 ε
The connected component of the empty word, ε, is a straight-line. It is "up to isomorphism" obviously rational, but as a sub-graph of this graph, it is not rational (its vertices form a context-free language). Therefore we need an external ("up to isomorphism") characterization of these graphs. This is the subject of the next section.

An external characterization

In this section, we will characterize rational graphs using inverse linear substitutions. Labelled transducers are an internal representation of rational graphs, it clearly depends on the name of the vertices. But often in graph theory, the name of the vertices is not relevant, it carries no information. An external characterization, like the graph grammars for equational graphs, produces graphs without giving names for vertices. It only gives the structure of the graph. Inverse linear substitution is an external characterization of rational graphs.

Graph isomorphism

An external characterization of rational graphs is given "up to isomorphism". Two graphs G 1 and G 2 in G A (X * ) are isomorphic, if there is a bijection ψ :

V (G 1 ) → V (G 2 ) such that: s 1 d -→ G1 s 2 (i.e., (s 1 , d, s 2 ) ∈ G 1 ) if and only if ψ(s 1 ) d -→ G2 ψ(s 2 ).
Two isomorphic graphs have the same structure: they are the same up to a renaming of the vertices. Now let us consider the equivalence (≡) generated by graph isomorphism: we say that G 1 is equivalent to G 2 (denoted G 1 ≡ G 2 ) if G 1 and G 2 are isomorphic. This equivalence relation provides us with a partition of G A (X * ) denoted Graph A := G A (X * )/ ≡. This allows the introduction of the set of structural rational graphs:

GRat A := {[G] ≡ ∈ Graph A | G ∈ Rat(X * ×A×X * )}
This set is the set of graphs that are isomorphic to some rational graph. Set Graph A (and GRat A ) does not depend on the choice of set X, therefore we can choose X to be any two letters alphabet with no loss of generality.

Lemma 3.1. For all subset X ′ (with at least two elements) of X and all class

[G] ≡ of Graph A (= G A (X * )/ ≡) there exists G 0 in G A (X ′ * ) such that G 0 ∈ [G] ≡ .
We now have to characterize the structure of GRat A . This is the goal of the next section.

Substitution

Recall the definition of the prefix-recognizable graphs (family REC Rat ). This family has been defined as the set of graphs obtained from the complete binary tree by inverse rational substitution, followed by rational restriction. We will use the same process (actually a linear context-free substitution) to obtain the family of rational graphs. A substitution over a free monoid X * is a morphism ϕ : A * → 2 X * , which associates to each letter in A a language in X * . Our purpose is to study graphs, starting from the complete binary tree (Λ) labelled X = {A, B}. To move by inverse arcs, we use a new alphabet : X = {A, B} and we say that x A -→ y if y A -→ x. Given a language L and two vertices x and y, recall that x

L =⇒ Λ y ⇔ ∃u ∈ L, x u =⇒ Λ
y. Now, given a substitution ϕ : A * → 2 (X∪X) * , we can define the graph ϕ -1 (Λ) in the following way:

ϕ -1 (Λ) = {x d -→ y | d ∈ A ∧ x ϕ(d) =⇒ Λ y} Given a language L, we define now L Λ = {s | r L =⇒ Λ s}.
It allows us to consider the graph ϕ -1 (Λ) |LΛ : it is the image of the complete binary tree by an inverse substitution followed by a restriction; if L is rational, we say a rational restriction. Now, it is well know that there is a close relationship between linear languages and rational relations (a linear language is a context-free language generated by a grammar with only, at most, one non-terminal on the right hand side of each rule). And indeed, if we denote the set of linear languages over the alphabet X ∪ X by Lin(X ∪ X), we have the following proposition.

Proposition 3.3. The set GRat A is a subset of the family of the graphs obtained from the complete binary tree (Λ) by an inverse linear substitution, followed by a rational restriction:

GRat A ⊆ {[ϕ -1 (Λ) |LΛ ] ≡ | ∀d ∈ A, ϕ(d) ∈ Lin(X ∪ X) ∧ L ∈ Rat(X)}
Proof (Sketch). We first transform the transducer generating the graph (G) so that each vertex begins with the same prefix. Then we produce linear languages (L d ) such that (u, d, v) ∈ X * ×A×X * is an arc of G if and only if uv ∈ L d . We then define ϕ(d) to be L d . It only remains to define L (the rational restriction) to be

L := Dom(G) ∪ Im(G) ⊓ ⊔
The converse of this result would help us to grab the structure of rational graphs. Unfortunately it is not obvious. Actually the following example illustrate the difficulty of the naive converse of Proposition 3.3.

Example 3.4. Consider ϕ(a) = {BBA n B n | n ∈ N}, it is a linear substitution. Consider L = BA * B * and the graph G = ϕ -1 (Λ) |LΛ .
Structurally, graph G is rational (it is the star). But the graph naturally associated to G (according to ϕ(a) and L) is

G ′ = {(B, a, BA n B n )| n ∈ N}, which is not rational.
So there is a deep isomorphism problem to get the converse. Actually, we will try to inject rationality in the "linear language" to achieve a complete characterization of rational graphs.

A natural way to introduce rationality into Lin(X ∪ X) would be to impose the projections over barred and non-barred letters to be rational. The next example shows that again, things are not so nice. Structurally, graph G is rational (it is two stars). But the graph naturally associated to G (according to ϕ(a) and L) is G ′ = {(BA, a, BA n B m )| n m} ∪ {(B, a, BA n B m )| m > n}, which is not rational (its intersection with the recognizable set {BA} × {a} × BA * B * is {(BA, a, BA n B m )| n m} which is not rational). Now consider the set Ratlin(X ∪ X) of linear languages (called rationallinear) over (X ∪X) * such that the production of their grammars are of following form: p → uqv (with u ∈ X * and v ∈ X * ) or p → ε.

Theorem 3.6. Set GRat A is precisely the set of graphs obtained from the complete binary tree (Λ) by a rational-linear substitution, followed by a rational restriction :

GRat A = {[ϕ -1 (Λ) |LΛ ] ≡ | ∀d ∈ A, ϕ(d) ∈ Ratlin(X ∪ X) ∧ L ∈ Rat(X)}
Proof (Sketch). The first inclusion is treated in Proposition 3.3. For the reverse inclusion we first take a graph G image of a rational-linear substitution, followed by a rational restriction then we need to check that it is possible to produce a transducer from the grammars of ϕ(d) for each d. Then we show that this graph contains G, finally, using rational intersection we obtain precisely G.

⊓ ⊔

Now that an external characterization of the rational graphs has been given, the next section will consider the properties of the traces of rational graphs.

The traces of rational graphs

We have already seen that there is a strong connection between language theory and rational graphs. In this section we will see another connection between graphs and languages, in terms of traces. We first recall that the trace of a graph G leading from a vertex set I (of initial states) to a vertex set F (of final states) is the set of all the path labels in the graph, leading from a vertex in the set of initial states to a vertex in the set of final states:

L(G, I, F ) := {u | ∃s ∈ I ∃t ∈ F, s u =⇒ G t}
In other words the trace of a graph is "the language of its labels". For example the traces of the finite graphs are all rational languages and the traces of prefixrecognizable graphs are all context-free languages. Notice by the way that the traces of rational graphs contain therefore every context free language.

Proposition 4.1. The traces of rational graph leading from a rational vertex set to a context free vertex set (or vice-versa) is recursive Proof. In order to check whether a word u is in the trace of graph G (from a set I to a set F ), it is just to check if the set S =

u(|u|) -→ G ( u(|u|-1) -→ G (• • • u(1) -→ G (I) • • • ))
intersects set F . If set I is rational (resp. context-free) its image by a rational transduction is rational (resp. context-free), hence by a simple induction, set S is rational (resp. context-free). Therefore it is decidable whether S ∩ F is empty.

⊓ ⊔

Let us denote by TR the family of the traces of rational graphs leading from a rational vertex set to a rational vertex set: TR = {L(G, I, F )| G ∈ Rat(X * × A×X * ) ∧ I, F ∈ Rat(X * )} (notice that we could as well restrict ourselves to a unique initial state and a unique final state). Now we will show that set TR form an Abstract Family of Languages (AFL), that is, it satisfies following properties:

closure for intersection with a rational (regular) language, -closure under non-erasing (monoid)morphism, and inverse morphism,

-for each L, L ′ ∈ TR we have L • L ′ , L ∩ L ′ , L + , L * ∈ TR.
Proposition 4.2. The intersection of two elements of TR is an element of TR.

Proof. Consider two elements L and L ′ of TR. Say L = L(G, I, F ) and

L ′ = L(G ′ , I, F ). The language L ∩ L ′ is actually the trace of G • ({$} × A × {$}) • G ′ (with $ a new symbol) between I G • {$} • I G ′ and F G • {$} • F G ′ . Hence L ∩ L ′ in an element of TR. ⊓ ⊔
As rational languages are traces of rational graphs (finite graphs are rational graphs), family TR is closed under intersection with rational languages. Now let us recall that a finite (resp. rational) substitution σ :

A * → 2 A * is a morphism such that for each letter d in A σ(d) is a finite (resp. rational) subset of A * . A substitution is non-erasing if ε ∈ σ(d) for all d ∈ A.
Proposition 4.3. Family TR is closed under non-erasing finite substitution.

Proof (Sketch). Consider σ a non-erasing finite substitution, and L a language in TR. We take a graph G such that L = L(G, I, F ), and T a transducer generating G. We, then, construct a new transducer such that each production d in T is replaced by a path u (in the corresponding graph), for each u ∈ σ(d). The trace of the graph generated by this transducer is σ(L) ⊓ ⊔

Following corollary is a direct consequence of this proposition.

Corollary 4.4. Family TR is closed under non-erasing morphism.

Notice that the condition "non-erasing" is essential for our proof. A interesting question is whether this condition is necessary. Proposition 4.5. Assume that L is an element of TR and that σ is a finite substitution over A * then σ -1 (L) is a language of TR.

Proof (Sketch). This proposition is a consequence of Elgot and Mezei's theorem, which states that the composition of two rational relations is a rational relation (see for example [Be 79], Theorem 4.4 p 68). Using this we can produce a rational graph in which a finite number of finite path are replaced by arcs. Which proves the Proposition.

⊓ ⊔

Remark: Note that it is not as straightforward for inverse rational substitution.

Actually it seems that it is not true for inverse rational substitution: consider any rational graph with one label (a) and the inverse rational substitution σ(a) = a * . The graph image with the same approach would be the transitive closure of the original graph, which is not effectively rational (and might not even be structurally rational) as stated in the remark after Proposition 2.15. Following corollary is an obvious consequence of proposition 4.5.

Corollary 4.6. Family TR is closed under inverse morphism.

Proposition 4.7. Family TR is closed under concatenation, Kleene plus and star.

Proof (Sketch). The argument is more or less the same as for finite automata. We use operation over rational relations to get the results.

⊓ ⊔

As stated earlier, we only have now to summary these results.

Theorem 4.8. The traces of rational graphs, leading from a rational vertex set to a rational vertex set, form an AFL ( Abstract Family of Languages).

Proof. This result is simply a brief summary of corollaries 4.4, 4.6 and propositions 4.2 and 4.7.

⊓ ⊔

Now we have an abstract family of languages that contains the context free languages. This AFL is a subset of the recursive languages. It seems that this family is composed of the context sensitive languages.

Conjecture 4.9. The traces of the rational graphs are precisely the context sensitives languages.

Notice also that recently graphs of linear bounded machines (which characterize context sensitive languages) have been studied in [KP 99].

Conclusion

In this paper, a general family of graphs has been introduced. Rational graphs are a strict extension of previously studied families. It is a well grounded family, related to well known structures of language theory. We have given both an internal and an external characterization, as well as some basic properties.

Unfortunately, or fortunately depending on the point of view, it is a very expressive family. Therefore many decision results are lost. An interesting question is to study restrictions of this family that will retain decision results from former families.

Traces of rational graphs are another aspect of this family. We have shown that it forms an abstract family of recursive languages. An interesting question is to know if these traces are precisely the context sensitive languages.

Rational trees also seem to be an interesting field of research, but this has not been done yet.

  also a rational relation. Naturally we denote by d -→ G (u) (resp. -→ G (u)) the image of word u by relation d -→ G (resp. -→ G

Example 3. 2 .

 2 Example 2.7 states that the grid is a rational graph. Following substitution:h(a) = {B m AB m | m 0}, h(b)= {B} over the complete binary tree on {A, B}, followed with the restriction to L = A * B * produces a graph isomorphic to the grid:

Example 3. 5 .

 5 Consider ϕ(a) = {A BBA n B m | n m} ∪ {BBA n B m | m > n} ϕ is a linear substitution. Moreover it has rational projections over barred and non-barred letters. Consider L = BA * B * and the graph G = ϕ -1 (Λ) |LΛ .

  and only if it satisfies one of the following equivalent properties:(i) G belongs to the smallest subset of G A (X

* ) containing: ∅,{ε d -→ ε},{x d -→ ε} and {ε d -→ x}, for all x ∈ X, all d ∈ A, and closed under ∪, • and +;

(ii) G is a finite union of rational relations over each letter:

Acknowledgements

The author would like to express his gratitude to Didier Caucal for his help along the preparation of this paper.


Flavio Pressacco

Giacomo Plazzotta

Laura Ziani

K-Fibonacci sequences and minimal winning quota in Parsimonious game

Keywords: Homogeneous weighted majority games, parsimonious games, minimal winning quota, k-Fibonacci sequence, Fibonacci polynomials

Introduction

In this paper we treat the problem of finding a closed formula for the minimal winning quota of parsimonious games (henceforth P games) as a function of the free type representation of the game.

P games have been introduced in a vintage paper by Isbell ([6], 1956) as the subset of constant sum homogeneous weighted majority games characterized by the parsimony property to have, for any given number n of non dummy players in the game, the smallest number, i.e. exactly n, of minimal winning coalitions.

It turns out that, in any n person P game, there are h (2 ≤ h ≤ n-2) types of players; in the minimal homogeneous representation of the game, type t players share the same type weight w t . Conversely a P game is fully and unequivocally described by its type representation, the ordered (according to an increasing weight convention) h dimension vector x = (x 1 , . . . , x t , . . . , x h ), whose component x t is the (obviously positive integer) number of type t players in the game. Besides lower bounds on x 1 and x h-1 , this vector should satisfy the binding constraint x h = 1. Then, what really matters is the free type version f x = (x 1 , . . . , x t , . . . , x h-1 ) of the representation, which is obtained by deleting the last component x h of x. In particular, we shall see that an important role in what follows is played by the subset of k-uniform P games (henceforth k -U P games), those with uniform free type representation at the level x t = k = (n -1)/(h -1).

Elsewhere ( [START_REF] Pressacco | Bilateral symmetry and modified Pascal triangles in Parsimonious games[END_REF], sect. 2, formula 2.1) we put in evidence that starting from the standard initial conditions on the weight of the groups labelled 0 (dummy players) and 1 (non dummy with smallest weight), a simple rule gives, for any P game, the sequence of type weights for all but the top player as the recursive solution of a second order linear homogeneous finite difference equation, with nonconstant coefficients except for the subset of k -U P games.

Moreover, keeping account of the rule governing the weight of the top player and of the fact that in any P game the coalition made by the top player and one of the last but top is minimal winning, we show here that also the minimal winning quota q is, for any h, the solution of a finite difference equation with exactly the same structure and the same initial conditions of the weight equation and hence with non constant coefficients except for the k -U P games. In particular, for the subset of k -U P games the corresponding finite difference equations have constant coefficient k.

Looking at the wide literature (see citations in [START_REF] Zhang | Some Identities Involving the Fibonacci Numbers[END_REF] and in [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF]) on properties and solutions of second order linear recurrence equations you can check that special attention has been devoted for k positive integer to k-Fibonacci equations, i.e. equations of the form F n (k) = k • F n-1 (k) + F n-2 (k) with initial conditions F 0 (k) = 0 and F 1 (k) = 1, whose solution is known as the k-Fibonacci sequence.

It was a lucky surprise to realize that both the structure and the initial conditions of the k-Fibonacci equations coincide with those of the weight problem and of the minimal winning quota problem of k -U P games.

This makes clear that the problem of finding the sequence of weights (or respectively the sequence of minimal winning quotas) of k -U P games is isomorphic to the one of solving the corresponding constant coefficients k-Fibonacci equation.

We recall that closed form of this solution may be expressed either by the Binet's formula (see [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF] and [START_REF] Stakhov | Theory of Binet formulas for Fibonacci and Lucas p-numbers[END_REF]) or by a polynomial expansion in k, whose coefficients may be linked to Pascal triangles (precisely, to the coefficients of the so called 2-Pascal triangles, see [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF] and [START_REF] Falcóna | On k-Fibonacci sequences and polynomials and their derivatives[END_REF] or of the "shallow diagonals" of the classic Pascal triangle, see for example [START_REF] Andersen | Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields[END_REF]). We found useful to introduce here the alternative but perfectly equivalent polynomial representation, q h (k) = s=0,...,h-1 C ′ (h, s) • k s whose coefficients are given by the elements C ′ (h, s) of a conveniently modified Pascal triangle. Going back now to the minimal winning quota of the general case of P game non U , it is clear that this problem too is isomorphic to the one of solving the corresponding nonconstant coefficients finite difference equation.

This suggested to us that the solution could be expressed by the generalized version (in terms of the free type representation f x) of the polynomial expansion in k found for the U P (constant coefficients) case. Indeed, the key connection between the particular and the general case comes from the coefficients C ′ (h, s) of the polynomial expansion, which play the same role in both cases. Precisely it turns out that, for any combination of h types and s factors, the C ′ (h, s) which multiplied k s in the polynomial expansion of q h (k) in the U case, is now the number of different products of s factors chosen (according to proper feasibility rules) from the free type representation vector. After that the minimal winning quota is simply the sum over all s (from 0 to h -1) of such products. Among other things, it implies that the number of addends of the polynomial expansion of the minimal winning quota of any P game with h types is exactly the h-th number of the (classical) Fibonacci sequence.

Summing up the first part of the paper, we may say that the minimal winning quota of any P game with n players and h types may be seen as a generalized version of the h-th number of the k-Fibonacci sequence, with k = (n -1)/(h -1). See examples 2 and 3 in section 9.

In the second part of the paper we will see that the solution of our finite difference equation is a symmetric function of the free type representation of the game. This paves the way for an alternative proof of the result given elsewhere (see [START_REF] Pressacco | Twin relationships in Parsimonious games: some results[END_REF], sect. 4) on the equality of the minimal winning quota of any couple of twin games, i.e. games whose free type representations are each other symmetric.

The plan of the paper is as follows. A short recall of the properties of P games, useful for our treatment, is given in section 2. Section 3 is devoted to derive the difference equation describing the behaviour of the minimal winning quota in not U as well as in U P games. Section 4 recalls some results on k-Fibonacci polynomials and k-Fibonacci sequences. Section 5 gives closed form solutions of the finite difference equation of the minimal winning quota for U P games, along with a discussion of the connection between the polynomial expansion and the coefficients of the modified Pascal triangle resuming such coefficients. Section 6 builds a bridge between the solution of the U and the not U case, and describes the rule behind the generalized version of the polynomial expansion, giving the minimal winning quota for the not U games as a function q h ( f x) of the free type representation of the game. In section 7 we show that q h is a symmetric function of its argument ( f x). Section 8 gives an alternative proof of the equality of the minimal winning quota of twin games based on such a property of symmetry; section 9 offers some examples and conclusions follow in section 10.

A short recall of the main properties of P games

As usual N is the set of players whose number is supposed here greater than three 1 , S is any coalition (subset of players), v(S) is the characteristic function of the game.

Let us recall that constant sum homogeneous weighted majority games 2 are simple (v(S) = 0 or 1), constant sum (v(S) + v( S) = 1) n person games, which admit a minimal homogeneous representation (q, w) in which q = 1+w(N ) 2 is the minimal winning quota (v(S) = 1 ⇔ w(S) = j∈S w j ≥ q), and w is an ordered vector of individual weights (w j ≤ w j+1 ) such that all weights are integer, there are players with weight 1 and for any coalition S minimal winning 3 , w(S) = q, which implies for such coalitions w(S) -w( S) = 1.

The number of minimal winning coalitions of a n (non dummy and greater than 3) person constant sum homogeneous weighted majority game may be either greater or equal, but not lower than n (see [START_REF] Isbell | A class of majority games[END_REF], p. 185). Parsimonious games are the subset of constant sum homogeneous weighted majority games with exactly n minimal winning coalitions.

Players of a P game may be divided in h (2 ≤ h ≤ n -2) subsets, grouping players with the same individual weight.

An alternative, very important in our treatment, representation of a P game is the ordered vector x = (x 1 , . . . , x t , . . . , x h ), whose component x t is the number of players of type t (i.e. with common individual weight w j = w t for any player j of type t) in the game. The group labelling is coherent with the increasing weight convention that w t-1 < w t . The following lower bounds and constraints ( [START_REF] Isbell | A class of majority games[END_REF], p. 185) hold on x:

x 1 and x h-1 > 1, x h = 1.
We suggest to call type representation of a P game the vector x, and free type representation the vector f x = (x 1 , . . . , x t , . . . , x h-1 ) obtained by deleting the last component of x.

Moreover, we define k-uniform P (henceforth k -U P ) games, the subset of P games, whose free type representation is uniform at level k, i.e.:

x t = k = n -1 h -1 for any t = 1, . . . , h -1 (2.1)
A simple recursion rule (see [START_REF] Pressacco | Bilateral symmetry and modified Pascal triangles in Parsimonious games[END_REF], sect. 2, formula 2.1) gives the type weights of a P game starting from the initial conditions w 0 = 0 and w 1 = 1:

w 0 = 0 (2.2a) w 1 = 1 (2.2b) w t = x t-1 • w t-1 + w t-2 , ∀1 < t < h (2.

2c

)

w h = (x h-1 -1) • w h-1 + w h-2 (2.2d)
Remark 2.1. We underline that (2.2c) jointly with the initial conditions (2.2a) and (2.2b) describe a second order linear homogeneous finite difference equation, whose recursive solution gives the type weights w t of all, but the top, players. Clearly, the equation does not have constant coefficients, except in the k -U P case in which (initial conditions unchanged):

w 0 = 0 (2.3a) w 1 = 1 (2.3b) w t = k • w t-1 + w t-2 , ∀1 < t < h (2.3c) w h = (k -1) • w h-1 + w h-2 (2.3d)
3 The minimal winning quota in P games

Let us consider for any h ≥ 2 the two sequences q h and w h defined respectively as the minimal winning quota of a P game with exactly h types of players and the type weight of type h players in a P game with more than h types.

Remark 3.1. Hereafter it is convenient to distinguish the expressions of w h coming from the previous definition, from the ones, denoted by w * h , representing the weight of the top player in a P game with exactly h types.

Coherently with such definitions, for any h we have by (2.2c):

w h = x h-1 • w h-1 + w h-2 (3.1)
while by (2.2d) we know that:

w * h = (x h-1 -1) • w h-1 + w h-2 (3.2)
Moreover, keeping account that in any P game the coalition made by the top player and one of the last but top (see [START_REF] Pressacco | Twin relationships in Parsimonious games: some results[END_REF], prop. 3.1) is minimal winning, it is: for any h ≥ 2:

q h = w * h + w h-1 = x h-1 • w h-1 + w h-2 (3.3)
If we could choose the following initial conditions on the function q h : q 0 = w 0 = 0 (3.4)

q 1 = w 1 = 1 (3.5)
this choice, jointly with (3.1) and (3.3), would imply by immediate induction on h:

q h = w h ∀h (3.6)
and by substitution in (3.3):

q h = x h-1 • q h-1 + q h-2 (3.7)
and keeping account of the initial conditions on q h the following result would hold:

Theorem 3.1. The minimal winning quota q h of any P game with h ≥ 2 types of players satisfies the second order, linear, homogeneous, nonconstant coefficients, finite difference equation (3.7) with initial conditions (3.4), (3.5).

It remains to justify the initial conditions, which per se are meaningless, as there are no P games with less than two types (see footnote 2, p. 3); yet this choice is the unique coherent with the true expressions of the really substantial initial conditions:

q 2 = x 1 (3.8) q 3 = 1 + x 1 x 2 (3.9)
easily derived by direct reasoning as follows.

In a P game with h = 2 there are x 1 ≥ 3 players of type 1, with weight 1, and one top player of type 2 with weight x 1 -1; one of the minimal winning coalitions is made by one player of type 1 and the top player, hence by (2.2) q 2 = x 1 is the expression of the minimal winning quota of a P game with h = 2 types.

In P games with h = 3 there are x 1 players of type 1 (type weight w 1 = 1), x 2 players of type 2 (type weight w 2 = x 1 ) and the type 3, top player, with weight (x 2 -1)

• w 2 + w 1 = 1 -x 1 + x 1 x 2 .
One of the minimal winning coalitions is made by one player of type 2 and the top player, hence the minimal winning quota of P games with h = 3 types is

q 3 = x 1 + 1 -x 1 + x 1 x 2 = 1 + x 1 x 2 .
After that, elementary algebra gives (3.4) and (3.5) as the unique solution of the system of (3.7), (3.8), (3.9), and Theorem 3.1 has been proved. Remark 3.2. In the case of k -U P , formula (3.7) becomes:

q h = k • q h-1 + q h-2 (3.10)
4 Fibonacci polynomials and k-Fibonacci sequences Definition 4.1. The sequence of polynomials in the real variable x defined by the recursive relation:

P n (x) = x • P n-1 (x) + P n-2 (x) (4.1)
with initial conditions P 0 (x) = 0 and P 1 (x) = 1 for any x is known as the sequence of Fibonacci polynomials (see [START_REF] Hoggatt | Generalized Fibonacci polynomials[END_REF].

Remark 4.1. It is immediate to check that the evaluation of the values P n (1) of the sequence at x = 1 gives the sequence of Fibonacci numbers P n (1) = F n .

The following generalization of this result has been given: Definition 4.2. For any given positive integer k, the sequence P n (k) is defined as the sequence of k-Fibonacci numbers or shortly k-Fibonacci sequence (see [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF]). The notation P n (k) = F n (k) may be used.

Remark 4.2. P n (k) is the solution of the second order finite difference equation with constant coefficients:

P n (k) = k • P n-1 (k) + P n-2 (k) (4.2)
with initial conditions P 0 (k) = 0 and P 1 (k) = 1.

In particular, the 1-Fibonacci sequence is just the classic one, the 2-Fibonacci sequence (0, 1, 2, 5, 12, 29, 70,...) is known as the Pell sequence, the 3-Fibonacci sequence is (0, 1, 3, 10, 33, 109, . . .) and so on.

5 k-Fibonacci sequences and the minimal winning quota in k -U P games Remarks 2.1, 3.2 as well as 4.2 make clear that the problem of finding the sequence of weights (or respectively the sequence of minimal winning quotas) of k -U P games is isomorphic to the one of solving the corresponding constant coefficients k-Fibonacci equation. Then the following results hold: Theorem 5.1. The sequence of all but the top type weights of a k -U P game G with h types is the sequence of the first h -1 k-Fibonacci numbers; formally:

w t (k) = F t (k) for t = 1, . . . , h -1
Proof. Immediate, by remark 4.2 the solution of (2.3c) with initial conditions (2.3a) and (2.3b) is

w t (k) = F t (k). Theorem 5.2. The minimal winning quota of a k -U P game G with h types is q h (k) = F h (k).
The proof mimics the one given for theorem 5.1 keeping account of formula (3.10) and the initial conditions q 0 (k) = 0 and q 1 (k) = 1.

Besides the recursive relation (4.2), closed form formulae of the k-Fibonacci sequences have been given.

Result 5.1. The Binet's formula (see [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF], p. 39):

F n (k) = [α(k)] n -[β(k)] n α(k) -β(k) (5.1) with α(k) = (k + (k 2 + 4) 1/2 )/2 and β(k) = (k -(k 2 + 4) 1/2
)/2 the two solutions of the characteristic equation x 2 -kx -1 = 0.

Result 5.2.

F n (k) =) = ⌊(n-1)/2⌋ j=0 C(n -1 -j, j) • k n-1-2j (5.2)
with ⌊(n -1)/2⌋ the greatest integer contained in (n -1)/2, and C binomial coefficients.

Hence it is:

F 1 (k) = 1 F 2 (k) = k F 3 (k) = k 2 + 1 F 4 (k) = k 3 + 2k F 5 (k) = k 4 + 3k 2 + 1 F 6 (k) = k 5 + 4k 3 + 3k ..... (5.3)
Result 5.2 gives a polynomial expansion of any number F n (k) of the k-Fibonacci sequence. On the basis of this result, it has been observed (see [START_REF] Falcóna | On k-Fibonacci sequences and polynomials and their derivatives[END_REF], sect. 2.1, table 3) that the sequence of the binomial coefficients of any F n (k) polynomial representation may be described by a modified Pascal triangle (named 2 Pascal triangle).

We suggest here the alternative equivalent polynomial expansion of F n (k):

Result 5.3.

F n (k) = n-1 s=0 C ′ (n, s) • k s (5.4)
with C ′ (n, s) integer coefficients satisfying:

for n odd (even):

C ′ (n, 0) = 1 (=0) (5.5a)
for n positive integer: C ′ (n, n -1) = 1 (5.5b)

for n positive integer > 1: C ′ (n, n -2) = 0 (5.5c)
for n positive integer and 0 < s < n -2:

C ′ (n, s) = C ′ (n -2, s) + C ′ (n -1, s -1) (5.
F n (k) = n-1 s=0 C ′ (n, s) • k s .
The rule governing the triangle is very simple: the first column alternates 1 and 0, the main (external) diagonal has all elements equal to 1; the diagonal under the main has all elements equal to 0, all the other internal coefficients follow the recursive rule (5.5d).

Remark 5.2. As revealed by the notation, the coefficients C ′ (n, s) do not depend on k, i.e. are the same for any k.

Remark 5.3. The sum of the binomial coefficients of the row n (as said before independent from k) is equal to the n-th Fibonacci number; formally: s=0,...,n-1 C ′ (n, s) = F n .

We will see in section 6, that this modified Pascal triangle plays a key role in finding a polynomial expansion of the minimal winning quota for non U P games.

6 Fibonacci polynomials and the minimal winning quota of non U P games In this section we will argue that the minimal winning quota of a P game not U with h types may be thought as a generalized version of F h (k). A key role in this reasoning is played by the modified Pascal triangle MPT1.

We have been inspired by the following intuition: Proposition 6.1. In any P game not U with n players and h types, the minimal winning quota q h (x 1 , x 2 , . . . , x h-1 ) should be given by a polynomial expansion isomorphic to the one found in the corresponding k -U P game (k = (n -1)/(h -1)) with the same number of players and types.

More precisely, in such an expansion the number of addends, obtained as feasible products of exactly s factors chosen from the free type representation vector, should be given (for any s) by the same coefficient C

′ (h, s) which multiplies k s (in formula (5.4)) in the polynomial expansion of the k -U case.

This way each one of the feasible products of exactly s factors in a P game not U may be thought as the counterpart of one of the products k s in a U P game.

Let us comment here a simple example. Consider a U P game G with n players and h = 5 types with level k = (n -1)/(h -1). For such a game it is (coherently with the coefficients of row n = 5 of MPT1 in Table 1):

q 5 (k) = F 5 (k) = 1 • k 0 + 3 • k 2 + 1 • k 4 = 1 + kk + kk + kk + kkkk (6.1)
For a general P game G ′ not U with the same number of players as well as of types of G, so that

h-1 t=1 x t = n -1
it is (as proved in the next section):

q 5 (x 1 , x 2 , x 3 , x 4 ) = 1 + x 1 • x 2 + x 1 • x 4 + x 3 • x 4 + x 1 • x 2 • x 3 • x 4 (6.2)
A comparison between (6.1) and (6.2) reveals that the three addends (C ′ (5, 2) = 3) kk in (6.1) have been substituted in (6.2) by the three feasible addends which are the product of exactly two different factors (chosen among the x 1 , x 2 , x 3 , x 4 coherently with the rules in theorem 6.1), while the unique addend (C ′ (5, 4) = 1) kkkk has been replaced by the unique feasible product of four factors; moreover there is also one addend (C ′ (5, 0) = 1), counterpart of k 0 , which requires to think that the fictitious product of zero factors is just equal to one.

Hence the conclusion that q 5 (x 1 , x 2 , x 3 , x 4 ) may be considered a generalized version of q 5 (k) = F 5 (k) as well as

q h (x 1 , x 2 , . . . , x h-1 ) is a generalized version of q h (k) = F h (k).
It remains to precise the rule governing the choice of the factors for any feasible combination of (h, s), i.e for which C ′ (h, s) is positive, and to show that the expansion provided by this rule gives exactly the minimal winning quota.

The answer to this couple of problems is given by the following result which provides the required expansion: Theorem 6.1.

for h even: q h ( f x) = s=1 mod 2,s<h Π j=1,...,s x i j (6.3a)

for h odd: q h ( f x) = 1 + s=0 mod 2,s<h
Π j=1,...,s x i j (6.3b) sub (in both cases) to the set of constraints on i j :

i 1 = 1 mod 2 (6.4a) i j < i j+1 for j = 1, . . . , s -1 (6.4b) i j + i j+1 = 1 mod 2 for j = 1, . . . , s -1 (6.4c) i s < h (6.4d) Remark 6.1. In (6.3a) and (6.3b) all sequences respecting the constraints are feasible and appear just once (no repetition of sequences) in the expressions of q h ( f x). Remark 6.2. For h even (odd) (6.3) and (6.4) imply that i 1 • i s = 1 mod 2, i.e. i s is odd (i 1 • i s = 0 mod 2, i.e. i s is even).

Remark 6.3. Denoting by F h the h-th Fibonacci number and by n h the number of addends of q h , it turns out that n 2 = 1 = F 2 (by (6.5a)) and n 3 = 2 = F 3 (by (6.5b)); moreover the structure of the recursive relation (3.7) makes clear that for any h > 3, n h = n h-1 + n h-2 so that (by induction on h) for any h, n h = F h and the following proposition holds: Proposition 6.2. In any P game with h types the number of addends of the polynomial expansion of q h is the h-th Fibonacci number.

Hence Theorem 6.1 says that q h is given by a sum of F h addends. For h even each of these addends is the product of an odd number s, smaller than h, of components of the free type representation f x whose sequence of indices i 1 , i 2 , . . . , i j , . . . , i s satisfy constraints of first index odd (6.4a), strict monotony (6.4b), for s > 1 alternation of parity (6.4c) and last index obviously lower than h (6.4d). For h odd, s is even and the constant 1 appears as one of the F h addends, while the constraints do not change.

We list here the first polynomial expansion of q h analogous to (5.3).

q 2 = x 1 (6.5a)

q 3 = 1 + x 1 x 2 (6.5b) q 4 = x 1 + x 3 + x 1 x 2 x 3 (6.5c) q 5 = 1 + x 1 x 2 + x 1 x 4 + x 3 x 4 + x 1 x 2 x 3 x 4 (6.5d) q 6 = x 1 + x 3 + x 5 + x 1 x 2 x 3 + x 1 x 2 x 5 + x 1 x 4 x 5 + x 3 x 4 x 5 + x 1 x 2 x 3 x 4 x 5 (6.5e)
Now we are going to give the proof of Theorem 6.1, but with a preliminary warning. In the proof we will denote by s.c. the (standard) constraints (6.4a), (6.4b) and (6.4c) which survive unchanged in all formulas, while on the contrary writing explicitly the updated version of (6.4d) regarding the constraint on the last index.

Proof. The theorem clearly holds for h = 2 as the only feasible s odd, lower than 2, is 1 (and hence q 2 = x 1 ), and for h = 3, for which the only feasible s even is 2 and hence q 3 = 1 + x 1 x 2 . Then, we proceed by induction: suppose that the theorem holds for some values h -2 and h -1, check that it is satisfied also for h, hence it holds for any positive integer.

Case h even. Let us write

q h = q h,1 + q h,2 (6.6)
with: q h,1 = s=1 mod 2,s<h Π j=1,...,s x i j (6.7) sub to s.c. (6.8a)

i s = h -1 (6.8b)
and:

q h,2 = s=1 mod 2,s<h-2
Π j=1,...,s x i j (6.9) sub to s.c. (6.10a)

i s < h -2 (6.10b)
Thus in (6.6) we split the addends of q h in two subsets; the first (whose sum is q h,1 ) contains all addends with last index exactly h-1, the second one (whose sum is q h,2 ) contains all the other addends with last index at most h -3. The following equalities hold:

q h,1 = x h-1 • q h-1 (6.11)
q h,2 = q h-2 (6.12)

The (6.12) follows by definition, the (6.11) by:

s=1 mod 2,s<h Π j=1,...,s x i j = x h-1 • 1 + s=0 mod 2,s<h
Π j=1,...,s x i j (6.13) sub to s.c sub to s.c

i s = h -1 i s < h -1
The left hand side of (6.13) has already been explained as the sum of products made by any feasible odd number of components of the free type representation with last component exactly x h-1 (h -1 odd). The right hand side suggests that all the addends are obtained multiplying by x h-1 all the addends of q h-1 , i.e. the constant 1 plus the sum of products made by any feasible even number of components of the representation with last index (even) lower than h -1. This way all constraints of alternation of parity, last index exactly h -1 and hence monotony and first index odd (either unchanged or h -1 for s = 1) are satisfied. After that the Theorem (in the even version of the induction) comes trivially from the following chain:

q h ( f x) = q h,1 + q h,2 = x h-1 • q h-1 + q h-2 = q h (6.14)
which fills the gap between the recursive solution and the polynomial expansion of the minimal winning quota problem.

Case h odd. We still put

q h = q h,1 + q h,2 (6.15)
with: q h,1 = s=0 mod 2,s<h Π j=1,...,s x i j (6.16) sub to s.c. (6.17a)

i s = h -1 (6.17b) and:
q h,2 = s=0 mod 2,s<h-2 Π j=1,...,s x i j (6.18) sub to s.c. (6.19a)

i s < h -2 (6.19b)
As before still (6.11) and (6.12) hold; in particular (6.11) comes from:

s=0 mod 2,s<h Π j=1,...,s x i j = x h-1 • s=1 mod 2,s<h-1 Π j=1,...,s x i j (6.20)
sub to s.c sub to s.c

i s = h -1 i s < h -1
The explanation of (6.20) is (mutatis mutandis) analogous to the one given for (6.13). Hence the chain (6.14) still holds which completes the proof.

It would be useful for the future to denote by ϕ h,m the m-th 4 of the F h addends of q h in (6.3) so that formally:

q h = m=1,...,F h ϕ h,m (6.21)
With these notation Theorems 3.1 and 6.1 may be synthesized by:

q h+2 = m=1,...,F h ϕ h,m + x h+1 • m=1,...,F h+1 ϕ h+1,m (6.22)
7 The symmetry of the function q h ( f x)

With reference to h -1 dimensional vectors, let us introduce the following definitions.

Definition 7.1. A couple of vectors x = (x 1 , x 2 , . . . , x h-1 ) and y = (y 1 , y 2 , . . . , y h-1 ) are each other symmetric if and only if, for any t = 1, . . . , h -1, x t = y h-t .

Definition 7.2. A vector function Φ is symmetric if and only if, for any couple x, y of (each other) symmetric vectors, it is: Φ(x) = Φ(y). Now, let Φ 1 , Φ 2 , . . . , Φ m , . . . , Φ n be a set of n(≥ 2) symmetric vector functions, then:

Proposition 7.1. Ψ n = m=1,...,n Φ m is a symmetric function. 4 According to whichever order you freely choose; in the examples of section 6 we will use an order induced at first by s (in increasing order) and inside a given s, by the lexicographic order dictated by the sequence of indices (still in increasing order); for h odd the constant 1 comes first in the ordering.

Proof. For n = 2 and x, y symmetric vectors it is:

Ψ 2 (x) = Φ 1 (x) + Φ 2 (x) = Φ 1 (y) + Φ 2 (y) = Ψ 2 (y)
An induction argument is then applied proving that, if the Prop. 7.1 holds for some m(≥ 2), then it holds also for m + 1 (and hence for any n):

Ψ m+1 (x) = Ψ m (x) + Φ m+1 (x) = Ψ m (y) + Φ m+1 (y) = Ψ m+1 (y)
Remark 7.1. Note that the symmetry of the Φ m functions is a sufficient but not a necessary condition for the symmetry of their sum Ψ.

Hereafter we will apply these ideas to the function q h ( f x) defined in (6.3). Let us start with the following Proposition 7.2. Suppose addend ϕ h,m of q h ( f x) is not symmetric, then among the other addends there is a non symmetric one, denoted hereafter by ϕ h,m such that Φ h,m = ϕ h,m + ϕ h,m is a symmetric function. Recalling that ϕ h,m = Π j=1,...,s x i j , this happens when ϕ h,m = Π j=s,...,1 x h-i j .

Proof. First of all we must check that the factors of ϕ h,m satisfy the feasibility conditions (monotony, alternate parity, first odd and last lower than h) of Theorem 6.1.

Monotony and alternate parity of the sequence of ϕ h,m indices are a straightforward consequence of monotony and alternate parity of the sequence of ϕ h,m indices; for h even i s is odd, which implies that the first index h -i s of ϕ h,m is odd too; on the contrary, for h odd i s is even and h -i s is odd too and the "first odd" condition is satisfied; finally i j positive and lower than h for any j in ϕ h,m imply the same property in ϕ h,m .

After that, let us consider any couple x, y of symmetric vectors according to definition 7.1; for such vectors it is immediately seen that:

ϕ h,m (x) = ϕ h,m (y)
and

ϕ h,m (x) = ϕ h,m (y) then Φ h,m (x) = ϕ h,m (x) + ϕ h,m (x) = ϕ h,m (y) + ϕ h,m (y) = Φ h,m (y)
It is now easy to show that:

Theorem 7.1. For any P game with h types, q h ( f x) is a symmetric function of the free type representation of the game.

Proof. At first, keep account of the fact that for a given h only some of the ϕ h,m are symmetric functions, while some other are not symmetric. Symmetry holds if ϕ h,m = 1 or if, for any t = 1, . . . , h -1, both or none of the components x t and x h-t are factors of ϕ h,m . On the other side for the ϕ h,m which are not symmetric functions, Prop. 7.2 holds and this grants that q h ( f x) may be written as a sum of symmetric functions (the ϕ h,m already symmetric and the Φ h,m symmetric by Prop. 7.2); hence, by Prop. 7.1, it is a symmetric function.

The equality of the winning quota in symmetric games

Let us give the following definition: Definition 8.1. Two P games G and G whose free type representations f x and f x are (each other) symmetric and not identical are twin games (twins).

Remark 8.1. For twins h = h: twins have the same number of types and of course of players.

The following theorem concerning twins turns out to be a straightforward corollary of the results given in section 4: Theorem 8.1. Let G and G be twins with minimal winning quota q and respectively q bar; then it is q = q.

Proof. The symmetry of the function q h ( f x) on one side and of the vectors f x and f x on the other imply q h ( f x) = q h ( f x)

Hence any couple of twin P games has the same minimal winning quota.

Remark 8.2. Elsewhere (see [START_REF] Pressacco | Twin relationships in Parsimonious games: some results[END_REF], sect. 4) we give an alternative proof of Theorem 8.1 based on the transposition properties of the incidence matrices of any couple of twin P games. While probably less elegant from a purely mathematical point of view, the proof given in this paper has the advantage to give an enlightening analytic explanation of the true reasons behind the equality of the minimal winning quotas of twin games.

Examples

Ex. 1 Let us consider the nine person P game G with free type representation f x = (3, 1, 2, 2) and minimal homogeneous representation (26; 1, 1, 1, [START_REF] Falcóna | The k-Fibonacci sequence and the Pascal 2-triangle[END_REF][START_REF] Falcóna | On k-Fibonacci sequences and polynomials and their derivatives[END_REF][START_REF] Falcóna | On k-Fibonacci sequences and polynomials and their derivatives[END_REF][START_REF] Pressacco | Symmetry and twin relationships in Parsimoniuos games[END_REF][START_REF] Pressacco | Symmetry and twin relationships in Parsimoniuos games[END_REF][START_REF] Stakhov | Theory of Binet formulas for Fibonacci and Lucas p-numbers[END_REF]. There are 5 types in G (h -1 = 4) and thus F 5 = 5 addends in the polynomial expansion q 5 ( f x):

q 5 ( f x) = 1 + x 1 x 2 + x 1 x 4 + x 3 x 4 + x 1 x 2 x 3 x 4 = 1 + 3 + 6 + 4 + 12 = 26
Three of the addends: 1, x 1 x 4 and x 1 x 2 x 3 x 4 are symmetric functions of a four dimension vector; the sum x 1 x 2 + x 3 x 4 of the remaining (non symmetric) two is symmetric too.

The twin G has free type representation f x = (2, 2, 1, 3) and minimal homogeneous representation (26; 1, 1, 2, 2, 5, 7, 7, 7, 19). Now:

q 5 ( f x) = 1 + x 1 x 2 + x 1 x 4 + x 3 x 4 + x 1 x 2 x 3 x 4 = 1 + 4 + 6 + 3 + 12 = 26
Note that the first, third and fifth addend are the same found in the expansion of q 5 ( f x), while the second and the fourth have been inverted (so that their sum 7 did not change).

Ex. 2 Let us consider the set of k -U P games G with six types and free type representation f x = (k, k, k, k, k). Coherently with row corresponding to n = 6 of the triangle in Table 1 (here h = 6), the minimal winning quota is expressed in the k-Fibonacci polynomial version by q 6 (k) = 3k + 4k 3 + k 5 , which is the sixth (positive) number of the k-Fibonacci sequence. Note that the sum of the coefficients is 8, i.e. the sixth Fibonacci number. In particular for k = 2 the minimal homogeneous representation of the 2-U P game is (70;1,1,2,2,5,5,12,12,29,29,41). Then, the minimal winning quota q 6 (2) = 3 • 2 + 4 • 2 3 + 2 5 = 70, is just the sixth positive number of the Pell sequence [START_REF] Andersen | Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields[END_REF][START_REF] Bolat | On the Properties of k-Fibonacci Numbers[END_REF][START_REF] Hoggatt | Generalized Fibonacci polynomials[END_REF][START_REF] Pressacco | Bilateral symmetry and modified Pascal triangles in Parsimonious games[END_REF]29,70). Hence the amazing equality between the type weights and the Pell sequence and, more generally, between the type weights and the k-Fibonacci sequences in k -U P games.

Ex. 3 Let us consider the twelve person P game G with free type representation f x = (2, 1, 3, 2, 2) and minimal homogeneous representation (61; 1, 1, 2, 3, 3, 3, 11, 11, 25, 25, 36). There are 6 types in G (h -1 = 5) and thus F 6 = 8 addends in the polynomial expansion q 6 ( f x):

q 6 ( f x) = x 1 + x 3 + x 5 + x 1 x 2 x 3 + x 1 x 2 x 5 + x 1 x 4 x 5 + x 3 x 4 x 5 + +x 1 x 2 x 3 x 4 x 5 = 2 + 3 + 2 + 6 + 4 + 8 + 12 + 24 = 61
Among the addends, only the second x 3 (3) and the last one x 1 x 2 x 3 x 4 x 5 (24) are symmetric functions of a five dimension vector, the other six may be coupled in three pairs, the first and the third, the fourth and the last but one, the fifth and the sixth, so as each pair has symmetric sum (x 1 + x 5 = 2 + 2 = 4), (x 1 x 2 x 3 + x 3 x 4 x 5 = 6 + 12 = 18), (x 1 x 2 x 5 + x 1 x 4 x 5 = 4 + 8 = 12).

The twin G has free type representation f x = (2, 2, 3, 1, 2) and minimal homogeneous representation (61; 1, 1, 2, 2, 5, 5, 5, 17, 22, 22, 39). q 6 ( f x) = x 1 + x 3 + x 5 + x 1 x 2 x 3 + x 1 x 2 x 5 + x 1 x 4 x 5 + x 3 x 4 x 5 + +x 1 x 2 x 3 x 4 x 5 = 2 + 3 + 2 + 12 + 8 + 4 + 6 + 24 = 61

The second and the last one addend are the same found in the expansion of q 6 ( f x), the other pairs have been interchanged according to the rule of symmetry of the sum.

We underline that the two games G and G of Ex. 3 are two of the many non U P games with 11 players and 6 types, which may be thought as counterpart of the 2 -U P game of Ex. 2 (with 11 players and 6 types too); on the other side, the minimal winning quota polynomial expansions of G and respectively G may be considered as two generalized versions of the polynomial expansion of the sixth number of the Pell sequence.

Conclusions

In the first part of the paper we give a closed form solution in terms of a polynomial expansion to the minimal winning quota of parsimonious games. Preliminarily, we underline that a parsimonious game is unequivocally described by its free type representation vector and introduce the class of k-uniform parsimonious games, i.e. games whose free type representation is uniform at the level k. We show that the minimal winning quota of parsimonious games satisfies a second order linear, homogeneous, finite difference equation, with nonconstant coefficients, except for the uniform case, and index h, the number of players types. We check that, keeping account of the initial conditions, the solution of the equation for the k uniform case is just the k-Fibonacci sequence. Then we recall that any element of the k-Fibonacci sequence may be expressed through a polynomial expansion in k, whose coefficients are linked to the binomial coefficients of the Pascal triangle. In order to build a bridge towards the solution of the equation in the nonconstant coefficients case, we introduce an alternative, perfectly equivalent, polynomial expansion, whose coefficients are given by a conveniently modified Pascal triangle. After that we show that the minimal winning quota in non uniform games (nonconstant coefficient case) is given by a polynomial expansion of the free type representation vector, which may be considered as the generalized version of the polynomial expansion of the k-Fibonacci sequence for the corresponding k-uniform games (constant coefficient case). In the second part of the paper we demonstrate that the minimal winning quota is a symmetric function of its argument (the free type representation vector). Exploiting this property it is immediate to prove that twin parsimonious games, i.e. couple of games whose type representations are each other symmetric, share the same minimal winning quota. Finally we underline that this offers an alternative, enlightening proof of a result which has been obtained elsewhere, exploiting properties of the determinants of the incidence matrices of twin games.

5d) Remark 5 . 1 .

 51 On the basis of such rules the coefficients C ′ are resumed by the following modified Pascal triangle, with index n = 1, 2, . . . on the rows and s = 0, 1, 2, . . . on columns. ... ... ... ... ... ... ... ...

Table 1 :

 1 Modified Pascal Triangle (MPT1) of the coefficients C ′ (n, s) of the polynomial representation

Acknowledgements

We acknowledge financial support of MedioCredito Friuli Venezia Friuli through the "Bonaldo Stringher" Laboratory of Finance, Department of Finance, University of Udine.