Samy Guezouli

Anas Alhasawi

A new concept for the contact at the interface of steel-concrete composite beams

Keywords: Flying Node Concept, Augmented Lagrangian Method, Contact, F.E.M., Composite beams. -1

This paper deals with the problem of contact at the interface of steel-concrete composite beams. The F.E. model "Pontmixte", able to study continuous composite beams at real scale, was based on a finite element of composite beam which considers only 4 degrees of freedom per node: both longitudinal displacements of the slab and the steel beam and common vertical displacement and rotation of the whole composite cross-section. This assumption did not allow any uplift at the interface between both materials. A "new" finite element is proposed in this work with 6 degrees of freedom per node in the aim to include a contact algorithm in the model. The originality of the method is to use the Augmented Lagrangian Method to solve the contact problem at the steel-concrete interface including a new concept so-called:"Flying Node Concept". This concept solves the problem of "continuous" contact at the interface that could sometimes occur along the beam especially in the case of distributed loads. The influence on the loading capacity of the beam and also the influence on some design variables are highlighted.

INTRODUCTION

In the past few years, several finite element models have been proposed for the analysis of composite steel-concrete beams; most of them are based on one-dimensional beam elements with embedded interlayer slip. "Pontmixte" [START_REF] Guezouli | Pontmixte" a User Friendly Program for Continuous Beams of Composite Bridges[END_REF] is one of the most innovative programs able to study composite continuous beams at real scale making two numerical integrations -the first on the height of the cross-section and the second along the longitudinal axis of the beam -. Nevertheless, the first version of this model assumed that there is no uplift between the concrete slab and the steel beam. The whole composite cross-section had same vertical displacement and same rotation. This assumption prevents the prediction of possible uplift which could occur in particular loading cases for continuous beams and especially on both sides of the intermediate supports.

Huang et al. [START_REF] Huang | Nonlinear Analysis of Reinforced Concrete Slabs Subjected to Fire[END_REF][START_REF] Huang | Modeling Membrane Action of Concrete Slabs in Composite Buildings in Fire[END_REF], proposed a non-linear layered finite element procedure for predicting the structural response of reinforced concrete slabs subjected to fire. The proposed procedure based on Mindlin/Reissner (thick plate) theory includes both geometric and material nonlinearities. In this study a total Lagrangian approach was adopted in which displacements are referred to the original configuration and small strains were assumed. In the case of beams subjected to fire, contact problem needs a special attention. Amilton et al. [START_REF] Amilton | A family of interface elements for the analysis of composite beams with interlayer slip[END_REF], presented a family of zero-thickness interface elements developed for the simulation of composite beams with horizontal deformable connection, or interlayer slip. The proposed elements include formulations to be employed with Euler-Bernoulli as well as with Timoshenko beam theories, combined to displacement-based beam elements sharing the same degrees of freedom. The elements that can be employed for the simulation of steel-concrete composite beams, was computed more recently by Batista et al. [START_REF] Batista | Analytical and numerical analysis of multilayered beams with interlayer slip[END_REF] combining with the plate formulation of Huang. The proposed model used to analyse composite floor that includes interface elements appeared able to give the relative longitudinal and transversal displacements between the slab and the steel beam as-well-as the relative vertical displacements in the transverse plane.

Recently, Qureshi et al. [START_REF] Qureshi | Effect of shear connector spacing and layout on the shear connector capacity in composite beams[END_REF], studied the effect of shear connector spacing and layout on the shear connector capacity in composite beams. A proposed 3D model (Plan dimensions: 1500 mm ×1500 mm), is loaded as a horizontal push test. This model developed with ABAQUS, includes profiled sheeting and the interfaces concerned by the contact algorithm are: (top profile sheeting -bottom of the concrete slab) and (shaft of the headed studs -surrounding concrete). Running time and convergence difficulty lead to consider 3D models inappropriate to study a continuous bridge beam at real scale.

Due to the non-linear nature of contact mechanics, such problems in the past were often approximated by special assumptions within the design process. Due to the rapid improvement of modern computer technology, one can today apply the tools of computational mechanics to simulate applications which include contact mechanisms numerically [START_REF] Kloosterman | Contact methods in finite element Simulations[END_REF].

The model proposed herein takes into account the slip and lengthening-shortening nonlinear behaviours of the connection. Whatever the zone where the contact occurs after uplift, the relative vertical displacements along the longitudinal axis of the beam is obtained without interpenetration between materials.

Different methods exist to solve the contact problem [START_REF] Cavalieri | A finite element formulation for nonlinear 3D contact problems[END_REF]. For example, in penalty method, increasing the penalty factor to infinity would lead to the exact solution, but in computational application it is not possible to use very high penalty factors because of ill-conditioning of the system. The Lagrange multiplier method fulfill the contact constraints exactly by introducing additional variables; for this reason the Lagrange multiplier generate an increment in the system-matrix size. A combination of the penalty method and the Lagrangian multiplier method leads to the so-called Augmented Lagrangian Method (ALM). With this method, the penalty factor does not need to reach a high value to get the convergence of the iterative process. This method will be used in the proposed model to solve the contact problem at the interface between the concrete slab and the steel beam subjected to the inequality constraint corresponding to the non-penetrability between both materials.

For special loading cases, it could happen that the contact at the interface is not only "node-to node" and concerns a part of the finite element length. The "Flying Node Concept (FNC)" is a new method proposed in this work to make the appropriate adjustments to the final solution of the problem.

Practically, the connection design leads to a number of studs which are distributed uniformly along the continuous beam or by portions of it (Eurocode recommendations for studs' design). This uniform distribution is generally validated by models that use a node-based connection. In order to take into account the actual continuous contact by using a node-based connection, the FNC algorithm is proposed. The main objective is to propose a longitudinal stud distribution that could be as realistic as possible by taking into account the continuous contact.

The first mesh of the beam (same as studs' location) begins uniform and at the end of calculation, a new stud location is proposed. If the studs' distribution does not change significantly from the beginning until the end of calculation; this means that the FNC algorithm was not activated significantly and so, no continuous contact zones have been occurred.

THE "NODE-TO-NODE" CONTACT

Uplift tests

Before solving the contact problem at some composite cross-sections along the beam during the loading history, other cross-sections where the uplift could occur or the contact without penetration between both materials is satisfied should be located. With the index (s) for the slab and (g) for the steel beam, the following notation is used: d (s) : Distance between the interface and the centroïd of the slab cross-section, d (g) : Distance between the interface and the centroïd of the steel beam cross-section, γ j : Stud slip at the node j, ( )

( s ) ( s ) ( s ) j j j u v θ
: Horizontal displacement, vertical displacement and rotation of the slab cross-section at the node j, ( )

( g ) ( g ) ( g ) j j j u v θ
: Horizontal displacement, vertical displacement and rotation of the steel beam cross-section at the node j.

The following tests must be activated depending on the sign of the variable

( s ) ( g ) j j j v v α = - :
• Case 1: the contact without penetration is satisfied at the node j the stud is only subjected to a slip (Fig. 1).

• Case 2: the uplift of the concrete slab with the bending of the steel beam the contact does not exist at the node j and the bolt is subjected to both slip and lengthening (Fig. 2).

• Case 3: the uplift of the concrete slab greater (in absolute value) then the uplift of the steel beam the contact does not exist at the node j and the stud is subjected to both slip and lengthening (Fig. 3).

"Node-to-node" contact solution

Equilibrium equations

Augmented Lagrangian Method is used to solve the "node-to-node" contact problem. For elastic deformation in solid mechanics, the kinematically admitted displacements that satisfy a stable equilibrium state are those whom minimize the total potential energy -this is the kinematic approach -. In our problem, the total potential energy is:

t t 1 V .K . .F 2 ∆ ∆ ∆ = - (1)
with:

{ } [ ] { } e e e d , K K and F f ∆ = = = ∑ ∑ ∑
where: { } e d is the finite element displacement vector, [ ] e K is its stiffness matrix and { } e f is its load vector.

The minimization of Eq. (1) corresponds to:

K . F 0 ∆ -= (2)
The problem of partial derivative equations is replaced by a linear system of equations and the minimal value of V in classical finite element approach of unconstrained problem is:

t 1 Min V .F 2 ∆ = - (3
+ + + + ( g ) ( g ) ( g ) j j u d θ θ θ θ + + + + i γ γ γ γ 0 L ) s ( d ) g ( d Interface ( g ) j v ( s ) j v Slab Girder (i) (j)
The constrained problem to solve at each node j can be written as follows:

j Min V sujected to 0 α   ≥  (4)
The problem can be solved as a series of unconstrained minimization problems. It is pointed out that the contact depends on the behaviour of the connectors. Even if the shear failure of a connector (for example) corresponds to 6 mm slip, all along the beam its maximum slip remains around 2 mm (always in elastic range) in serviceability limit state. Similar remark could be done for the tension of a connector. The use of Minimum Potential Energy in this case is then justified.

The penalty method approach gives:

2 j p V 2 After each iteration : updating p Π α  = + ∑     (5)
At iteration (I), penalty method solves this problem, then at iteration (I+1) it re-solves the problem using a largest value of the penalty factor p using the old solution as the initial guess.

The ALM combines the penalty method with the Lagrangian multipliers method. The ALM uses the following constrained objective:

Π α λ α λ λ α  = + - ∑ ∑    -  (6)
The advantage of the ALM is that unlike the penalty method, it is not necessary that p have a very large value in order to solve the original constrained problem. Instead, because of the presence of the Lagrangian multiplier λ j , p can stay much smaller.

According to Eq. ( 6), the modifications that have to be done to the assembled stiffness matrix and to the corresponding loading vector, at each node j, are:

θ θ θ θ j λ λ λ λ ( ( ( ( ) ) ) ) s j u ( ( ( ( ) ) ) ) s j N j * p + + + + j * p - -- - - -- ( ( ( ( ) ) )
)

g j u ( ( ( ( ) ) ) ) g j N j * p - -- - j * p + + + + + + + + 1 1 1 1 ( ( ( ( ) ) ) ) g j v ( ( ( ( )
) ) )

g j j j T p α α α α - -- - ( ( ( ( ) ) ) ) g j θ θ θ θ ( ( ( ( )
) )

)

g j M - -- -1 1 1 1 + + + + 1 1 1 1 j 1 p - -- - j λ λ λ λ j α α α α - -- - (7)
It is easy to verify that the equilibrium is satisfied in Eq. ( 7). The stiffness matrix remains symmetric and there is one line and one column added for each node being in contact.

In practice, it is easier to add the supplementary equations corresponding to the nodes being in contact, at the end of the initial system as shown in Eq. [START_REF] Cavalieri | A finite element formulation for nonlinear 3D contact problems[END_REF]. The system of equations to be solved has finally a "variable" dimension between (n×n) and (2n×2n) maximum depending on the number of nodes being in contact (q 1 , q 2 , q 3 , …). In Eq. ( 8), each value of the Lagrangian multiplier λ qi corresponds to a node q i being in contact. A penalty factor p qi will be adjusted for each node q i ; its initial value is equal to 1 and it increases during iterations (multiplying by 10 at each iteration). During the material nonlinear iterative process, the number of nodes being in contact could change.

( ( ( ( )

) ) )

g n u Initial system dimension ( ( ( ( ) ) )
)

g n v nn K ( ( ( ( )
) ) )

g n θ θ θ θ 1 q λ λ λ λ "Variable" system dimension 2 q λ λ λ λ 3 q λ λ λ λ ⋮ ⋮ ⋮ ⋮ (8)

"Continuous" contact solution

During the loading history, it is possible to have some zones subjected to a contact that concerns a part of the element-length and not only its nodes. This could occur in case of distributed load more than in case of concentrated loads. In order to take into account this actual phenomenon, one proposes an approach so called "Flying Node Concept (FNC)". This method should be included in the iterative process that solves the contact problem at the interface previously described.

The FNC adapts the longitudinal mesh of the beam during the iterative process in order to take into account the "continuous" contact to a "node-to-node" connection. If the initial mesh of the beam appears unchanged at the end-loading history, it means that all the contacts have been "node-to-node"; otherwise, the final mesh will inform about the zones that have been subjected to a "continuous" contact. It is worth to mention out that these zones could sometimes appear and sometime disappear depending on the loading history of the beam. The final solution corresponding to the end-loading and to the real final mesh depends on all intermediate calculation steps. If the FNC leads to major changes to the mesh and thus to the connection in certain zones of the continuous beam, the connection should be correctly distributed in these zones during the steel beam conception.

One considers two consecutive finite elements [(i-1) -i] and [i -j] with respective element lengths 1,I

L and 2 ,I L at iteration I (Fig. 4.a). One supposes that the test concerns the node i of the finite element [i -j] and using appropriate shape functions N i=1,..,4 one calculates the vertical displacements of both the slab and the steel beam as follows:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) s s s s s 1 i 2 i 3 j 4 j g g g g g 1 i 2 i 3 j 4 j v x N x v N x N x v N x v x N x v N x N x v N x θ θ θ θ  = + + +   = + + +   (9)
The difference between both vertical displacements, previously called α, is easily obtained with following equation:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) s g s g s g s g i 1 i i 2 i i 3 j j 4 j j x N x v v N x N x v v N x α θ θ θ θ         = - + - + - + -         (10.a)
or:

( ) ( ) ( ) ( ) ( ) i 1 i 2 i 3 j 4 j x N x v N x N x v N x α ∆ ∆θ ∆ ∆θ = + + + (10.b)
This function depends only on the longitudinal x location of the node i. The objective now is to calculate, if it exists, the distance x ɶ given by ( )

i x 0 α = ɶ .
With:

( )

2 3 1 2 3 2 ,I 2 ,I x x N x 1 3 2 L L   = - +       , ( )
2 3 2 2 2 ,I 2 ,I x x N x x 2 L L   = - +       , ( )
2 3 3 2 3 2 ,I 2 ,I x x N x 3 2 L L   = -      

and

( )

2 3 4 2 2 ,I 2 ,I x x N x L L   = - +      
, Eq. ( 10.b) leads to following equation:

( ) ( ) ( ) ( ) ( ) i j i j i j i j 3 2 i i i 3 2 2 2,I 2 ,I 2,I 2,I v v v v 2 x 2x 3x x v L 2L L 3L ∆ ∆ ∆θ ∆θ ∆ ∆ ∆θ ∆θ α ∆θ ∆     - + - +     = + - + + +         (11)
Finally, the equation ( )

i x 0 α = ɶ
can be easily solved using trigonometric method for example. Only real solutions are considered and if there is more than one solution, the maximum one is restrained while it remains less than actual finite element length. The beam mesh changes at considered node for next iteration (I+1) as follows:

1,I 1 1,I L L x + = + ɶ and 2,I 1 2,I L L x + = -ɶ (12)
Only shape functions on the right side of the node i are employed because the FNC tests all the nodes from the left side to the right side of the beam (x axis sense); the first node being the left support which never moves like the other nodes located at each support of the continuous beam. If the test begins from the second element at the node i, appropriate length changes will concern both elements [(i-1)i] and [ij] and so on... Figure 4 shows how the FNC runs as an adaptive mesh depending on the value of the distance x ɶ obtained from Eq. ( 11). In the case where x ɶ is too close to the finite element length, from Eq. ( 12), one observes that 2,I 1 L + could be very low and then the convergence of the iterative process could be affected. Two methods could be adopted:

-Method1: Limiting x ɶ to an arbitrary value (less than half of the finite element length for example). This method insures to keep constant the number of finite element, it remains easy to compute and it gives enough accurate results. -Method2: If 2,I 1 L + is too low, actual finite element disappears and the number of finite elements changes. In Fig. 4, both finite elements [(i-1), (i)] and [(i), (j)] merge and become only one finite element [(i-1), (j)]. This method is more difficult to compute because it needs a renumbering of the mesh during the iterative process. In addition, the solution could be affected by the final mesh density that is not suitable. In Figure 5, the FNC algorithm is shown with its links to the ALM in order to solve the contact problem. It is worth to mention out that the set of values obtained for the penalty factor p is verified by reconnecting FNC to ALM (at same contact iteration). Generally, these values are still available and the verification is directly satisfied; this is due probably to:

( ) i x 0 α = ɶ
(Eq.10.b).

Figure 5 -Contact algorithm (ALM + FNC).

THE COMPOSITE BEAM F.E.

Nodal variables

The user-friendly software "Pontmixte" has been upgraded to a "new" version based on a new finite element formulation for the composite beam element. Six degrees of freedom are necessary (instead of four in the preceding version), to take into account the contact/uplift at always available the interface. The concrete slab as-well-as the steel beam has 3 degrees of freedom at each node (i) and (j) (Fig. 6). Nodal displacements vector of the composite finite element is:

{ } { } t ) g ( j ) g ( j ) g ( j ) s ( j ) s ( j ) s ( j ) g ( i ) g ( i ) g ( i ) s ( i ) s ( i ) s ( i e v u v u v u v u d θ θ θ θ = (13)
Using corresponding classical shape functions N, the displacement at each fiber of the composite cross-section is then:

{ } [ ]{ } e d( x, y ) N( x, y ) d = (14) [ ] ( ) ( ) ( ) ( )
s g i i s g j j N 0 N 0 0 N 0 N N( x, y )   =       (15)
In Eq. ( 15), N includes (3×3) matrices.

The stud slip and lengthening (or shortening) are calculated considering the translation and the rotation of each material. Concerning the lengthening, the stud will be supposed fixed to the concrete:

Stud-slip: [ ] [ ] ) g ( j ) g ( ) g ( j ) s ( j ) s ( ) s ( j j d u d u θ + - θ + = γ (16) Stud-lengthening: ( s ) ( g ) j j j v v α = - (17)
Figure 6 -Definition of the nodal variables.

Kinematic relationships

The kinematic variables are respectively the longitudinal strain and the curvature of each material cross-section:

( s ) ( g ) ( s ) ( g ) x x 2 ( s ) 2 ( g ) ( s ) ( g ) x x 2 2 u u and x x v v and x x ε ε κ κ  ∂ ∂ = =   ∂ ∂  ∂ ∂  = =  ∂ ∂  (18)
Kinematic relationship and corresponding strain vector are:

{ } [ ]{ } e B d ε = with { } ) g ( x ) g ( x ) s ( x ) s ( x t κ ε κ ε = ε (19)
The kinematic matrix can be written explicitly as follows:

Slab Girder ) s ( i u ) s ( i v ) s ( i θ ) g ( i u ) g ( i v ) g ( i θ ) s ( j u ) s ( j v ) s ( j θ ) g ( j u ) g ( j v ) g ( j θ 0 L ) s ( d ) g ( d Interface [ ] 1 2 3 1 2 3 2 3 2 3 1 2 3 1 2 3 2 3 2 3 2 B B y B y 0 0 0 B B y B y 0 0 0 L 2 0 B B 0 0 0 0 B B 0 0 0 L B 2 0 0 0 B B y B y 0 0 0 B B y B y L 2 0 0 0 0 B B 0 0 0 0 B B L - - - - - - - = - - - - - - -                                               (20)
with:

1 1 B L = , 2 2 3 6 x B 12 L L = - , 3 2 4 x B 6 L L = -

Stiffness matrix of the composite finite element

Paying attention to the kinematic matrix, one observes that it depends on the axial x location of the concerned cross-section and on the depth y of each material-fibre at same cross-section. The composite beam cross-section is then divided into a number of horizontal fibres (m for each steel beam flange, n fibres for the steel beam web and p fibres for the slab). The algorithm undertakes firstly a Gauss-Legendre numerical integration towards the elementdepth with 2 Gauss-points for each fibre (1 st integration along y axis -Fig. 7). By summing different stiffnesses along y axis, the result (that corresponds to the stiffness of the composite cross-section) is affected to one of the Gauss points in order to undertake the 2 nd integration along x axis (Fig. 7) that uses also 2 Gauss points. In order to simplify the presentation, the first numerical integration will not appear explicitly. One begins by the element stiffness matrix of the unconnected [(i), (j)] composite beam that can be easily obtained by:

[ ] [ ][ ]

] ( ) ( ) ( ) ( ) ( s ) ( s ) ( g ) ( g ) EA 0 0 0 0 EI 0 0 D 0 0 EA 0 0 0 0 EI       =           (22)
E: Secant Young's modulus, A: cross-section area and I: quadratic inertia of the cross-section.

A secant algorithm is used to solve nonlinear equations due to nonlinear behaviour of materials.

In order to include a connector at the node (j) of the finite element [(i), (j)] for example, the principle of virtual work is applied to set the global relationship of the stud behaviour under a shear loading as-well-as under a tension.

• The internal work of an infinitesimal slip of the stud at the node (j) and corresponding nodal variables are:

{ } = = -- ss ( s ) ( g ) ss int j j j j W Q Q 1 d 1 d d δ δγ δ (23) { } = t ss ( s ) ( s ) ( g ) ( g ) j j j j j d u u δ δ δθ δ δθ ( 24
)
Q j is the stud shear force and d (s) and d (g) are defined in Fig. 5.

Corresponding nodal forces are:

{ } = t ss ( s ) ( s ) ( g ) ( g ) j j j j j F N M N M (25)
• The internal work of an infinitesimal lengthening of the stud at the node (j) and corresponding nodal variables are:

{ } st st int j j j j W P P 1 1 d δ δα δ = = - ( 26
) { } = t st ( s ) ( g ) j j j d v v δ δ δ (27)
Corresponding nodal forces are:

{ } = t st ( s ) ( g ) j j j F T T ( 28
)
• External works related to the nodal forces given in Eq. ( 22) and Eq. ( 25) are:

{ } { } = t ss ss ss ext j j W d F δ δ (29) { } { } = t st st st ext j j W d F δ δ (30)
• The principle of virtual works leads to:

= ss ss int ext W W δ δ (31) = st st int ext W W δ δ (32)
The stud slip behaviour is defined as the relationship between the force at the stud head and the slip calculated between its base and the force point application. This stud slip has been defined previously in Eq. ( 16) and R ss is the stud slip-resistance:

= ss ss j j Q R γ (33)
From Eq. ( 31), the stud stiffness matrix ss K     related to its slip-resistance can be easily obtained:

{ } { } { } { } t t ss ss ss ( s ) ( g ) ( s ) ( g ) ss int j j j j t ss ss ss ext j j W Q R d 1 d 1 d 1 d 1 d d W d F δ δγ δ δ δ  = = -- --    =  (34) { } { } t ss ss ( s ) ( g ) ( s ) ( g ) ss j j F R 1 d 1 d 1 d 1 d d = -- -- (35)
The stud stiffness matrix related to its slip-resistance is finally:

( ) ( )   - -     - -     =   - -     - -     ( s ) ( g ) 2 ( s ) ( s ) ( s ) ( s ) ( g ) ss ss ( s ) ( g ) 2 ( g ) ( s ) ( g ) ( g ) ( g ) 1 d 1 d d d d d d K R 1 d 1 d d d d d d (36)
Concerning the stud lengthening behaviour, same procedure then the one developed for the stud slip-resistance is carried out. The stud tension resistance is called R st and the stud lengthening has been previously defined in Eq. ( 17):

st st j j P R α = (37) { } { } { } { } t t st st st st int j j j j t st st st ext j j W P R d 1 1 1 1 d W d F δ δα δ δ δ  = = - -    =  (38) { } { } t st st st j j F R 1 1 1 1 d = - - (39)
The stud stiffness matrix related to its lengthening-resistance is finally:

st st 1 1 K R 1 1 -     =     -   (40)
After replacing by the symbol (*) the terms of the stiffness matrix related to an unconnected composite beam element given in Eq. ( 21) concerning an unconnected composite beam, the stiffness matrix of the finite element [(i), (j)] representing a connected composite beam is:

[ ] ss st e e K K K K       = + +       ɶ (41)
Respecting the nodal variables organization given in Eq. ( 13), this matrix can be written explicitly as follows:

[ ] ( )

( ) = + + - - + - + - - + + + +                               ss (
* R * * d R R 0 d R * R * 0 R 0 Symmetry * d R d R 0 d d R * R * * d R * R * * d R         ∫ L 0 dx (42)

NUMERICAL SIMULATION

In order to proof that the use of contact algorithm is relevent to obtain accurate results, first numerical inestigation concerns the comparision between experimental test results and the ones obtained by the "old" model with 4 degrees of freedom per node on one hand and the "new" model with 6 degrees of freedom per node on second hand.

Second numerical simulation will concerns an application for the FNC considering the same twin-beam subjected to a distributed load.

Comparison with an experimental test

The steel-concrete composite twin-beam considered (Fig. 8.a) has been subjected to an experimental test at Structural Laboratory of INSA-Rennes. The beam is loaded in accordance with the following stages:

-Stage 1: The self-weight is taken into account (4.17 kN/m for sagging zones and 4.26 kN/m for hogging ones).

-Stage 2: Concentrated loads "P 1 " and "P 2 " are applied at the mid-spans of the beam until the magnitude of 550 kN for each.

-Stage 3: The load "P 2 " remains constant and the load "P 1 " continue to increase from 550 kN to 850 kN.

In Figure 8.b is plotted the loading history corresponding to the stages 2 and 3, the stage 1 is not represented because it represents a distributed load and it is different on hogging and sagging zones of the continuous beam.

It is assumed that the hogging zone concerns 15% of the span length on each side of the intermediate support. For this zone, the thickness of the bottom flange is equal to 15 mm and for other cross-sections (in sagging zones) only 10 mm is required. The top flange thickness is equal to the bottom one. Related to mechanical behaviour of each material (Fig. 9), the mechanical properties are summarized in Table 1. ( )

( c ) 2 cm k f 1 k 2 σ η η η - = + - with : ( c ) m 0 η ε ε = > and m cm cm k 1.1E f ε = (43) Stud: ( ) 2 1 c c u Q Q 1 e γ - = - (44)
σ σ σ σ (c) ε ε ε ε (c) ε m f ctm f ck = αf cm 0.4f cm ε r (c) Compression f cm Atan(E cm ) σ σ σ σ (a) ε ε ε ε (a) ε e (a) µ 1 (a) ε e (a) µ 2 (a) ε e (a)
Atan(E (a) )

f y (a) f u (a) Tension a -Concrete b -Steel beam σ σ σ σ (s) ε ε ε ε (s) ε e (s) µ 1 (s) ε e (s) µ 2 (s) ε e (s)
Atan(E (s) )

f y (s) f u (s) Tension Q γ γ γ γ γ max Q u c -Rebar d -Stud
Figure 9 -Material mechanical behaviour.

As mentioned previously, with the assumption of 4 degrees of freedom per node, the contact at the interface could not be taken into account as-well-as possible uplifts along the beam. With this assumption, the comparison between numerical and experimental results could not be totally satisfactory. In Fig. 10 obtained from [START_REF] Guezouli | Local buckling influence on the moment redistribution coefficient for composite continuous beams of bridges[END_REF], the comparison of the beam deflexion between numerical and experimental results with the previous "old" model "Pontmixte" shows a significant difference especially over the elastic range. This result was predictable because the penetration as-well-as the uplift at the material interface begin to be significant when the load increases. In this figure, one observes that the deflexion under "P 1 " has been underestimated with this numerical model since "P 1 " continues to increase over 550 kN.

Unfortunately the measurements under the load "P 2 " have not been done, but the conclusion should be similar to "P 1 ".

Figure 10 -Comparison of deflexions -"old" model [START_REF] Guezouli | Local buckling influence on the moment redistribution coefficient for composite continuous beams of bridges[END_REF].

It is clear that the effect of the interface "behaviour" becomes significant for high load level and especially under concentrated loads or at intermediate supports. For this reason, following numerical simulations, using the proposed "new" model (6 degrees of freedom per node), should help to understand how the contact algorithm could give more accurate results.

For the same twin-beam, are compared in Figures 11 some design variables obtained with the "new" finite element model. The left curves correspond to the model without activating the ALM algorithm and the right ones with activating the ALM algorithm. The left curves are plotted in the aim to identify the critical cross-sections along the beam where the ALM algorithm should be activated. In Figure 11.a and Figure 11.b are plotted respectively the comparison of vertical displacements between the slab and the steel beam and the comparison of the rotations for the last-step loading. As it was predicted, the left curves related to the cross-sections located under the concentrated loads show a penetration of the concrete slab in the beam. This penetration is theoretical and not realistic and it will be corrected by activating the ALM algorithm (right curves). It is pointed out that the minimum gap at the interface is fixed to 10 -3 mm for these numerical simulations. This value leads to reasonable time computation for convergence of the contact iterative process. In Figure 11.c, are plotted the stud slip curves and the lengthening-shortening ones. The penetration and the uplift observed in the left curves disappear in the right curves; maximum uplift is observed at each side of the intermediate support. The slip curves become more smoothed with the ALM algorithm especially under the concentrated loads.

One observes that the use of the ALM algorithm makes changes in the magnitude of the design variables and therefore should have a special attention.

In Figure 12 are plotted similar curves as in Figure 10 but for the "new' finite element model activating the ALM algorithm. One observes the incidence on the beam deflexion under the concentrated load "P 1 "; the correlation between numerical and experimental results is more satisfactory in the post-elastic range.

Without ALM algorithm

With ALM algorithm

Influence of the FNC

In order to show how "Pontmixte" solves the problem of the "continuous" contact, precedent twin-beam is now subjected to a distributed load p. The calculation is carried out until reaching elastic hogging bending el Mat intermediate support. Initial mesh of the twin-beam contains 10 finite elements per beam; this mesh is called Mesh-0. The results of two calculations are compared:

-Calculation1: Contact solved with ALM -Calculation2: Contact solved with ALM + FNC In the aim to avoid additional differences between the results due to different numbers of finite elements, Method1 presented in 2.3 will be used in this example. Initial mesh will change several times during the loading history of the beam (Fig. 13). Only the final mesh so called Mesh-n will be highlighted because it corresponds to the last step loading. Mesh-0 and Mesh-n are presented in Figure 14. One observes that the difference between the finite element lengths mostly concerns both sides of the intermediate support and also the zones close to the end-supports. These zones correspond to the ones that are subjected to a "continuous" contact and solved by the FNC. It is pointed out that the symmetry of the problem is retained until convergence. The hogging bending is obtained when the top beam-flange reaches its yield stress (f y (a) = 475 MPa). The stress difference observed on hogging bending between both calculations is due only to the precision and it appears neglectable and same corresponding hogging bending is

S el M M 871 kN/m - - = = -
. Nevertheless, in sagging zone, the stress difference is greater than the one on hogging and should not be neglected. In Calculation2, the sagging bending is greater than in Calculation1; this explains why the elastic hogging bending is reached faster (Table 2). One compares now the stress distribution of both calculations for same load level (p = 264 kN/m). Figure 15.b and Figure 16 show that in Calculation1 the stresses are underestimated and the moments (Table 2) are around 3% less in sagging zone and 6% less on hogging zone. This difference is mostly due to the "continuous" contact that increases the stud slip in Calculation2 and not in Calculation1. In Figure 17 are plotted the stud-slip curves for these both calculations, maximum differences are observed in the zones that are mostly subjected to a "continuous" contact (at each side of intermediate support and near the end-supports -Fig. 14).

CONCLUSION

The finite element model (with 6 degrees of freedom per node) for steel-concrete composite beams presented in this research has been developed in order to solve the problem of contact at the steel-concrete interface using the Augmented Lagrangian Method. The first numerical example is provided to assess the accuracy and robustness of the proposed formulation by comparison to experimental test results to confirm the reliability of the model. A new concept (FNC) has been proposed to take into account the continuous contact that sometimes occurs for special loading cases. The proposed method is easy to compute and to include in the algorithm of the Augmented Lagrangian Method. The second numerical simulation is proposed to show the influence of the FNC on some design variables.

Main conclusions for the present work could be summarized as follows:

The numerical simulation shows that the "old" model of the program "Pontmixte" (with 4 degrees of freedom per node) could not take into account the real behaviour at the steel-concrete interface. Consequently, the comparison with experimental results was not satisfactory especially for high load level and under concentrated loads aswell-as at intermediate support. The separation between the slab and the steel beam degrees of freedom appears necessary, the "new" model with 6 degrees of freedom per node is then proposed.

Contact algorithm based on ALM is well-adapted for composite structures and appears easy to compute and the convergence is relatively fast. The practical organization of the system given in Eq. ( 8) permits to avoid the node-renumbering of the system. The comparison between "without" or "with" ALM algorithm highlights the "critical" zones in the continuous beam where the unrealistic penetration of the concrete slab in the steel beam occurs and then is corrected by the use of ALM algorithm. It is pointed out that the uplift obtained when the calculation does not take into account the ALM algorithm is also unrealistic and is corrected by the use of ALM algorithm.

The proposed model solves the node-to-node contact that is enough accurate in case of concentrated loads. Nevertheless, for distributed loads, the contact becomes more continuous and then the model should include the FNC. The example presented in this work shows that the loading capacity of the beam could be lower than the one predicted by a calculation without FNC (about 6% in this example). This percentage even if it remains relatively low, should be taken into account during the design of the beam because it could be not neglectable for other loading cases (for example asymmetrical distributed load on the beam). Nevertheless, more numerical simulations and experimental tests should be carried out to conclude on practical purposes.

Solving contact problem at the steel-concrete interface has an influence on the design variables especially on the stud slip. It could be interesting to study its influence on the degree of connection in order to optimize the connection design.

Figure 1 -Figure 2 -

 12 Figure 1 -Contact at the node j -Slip only.

Figure 3 -

 3 Figure 3 -Contact at the node j -Slip and (slab uplift + steel beam uplift).

  iteration : updating p and replacing by p

Figure 4 .

 4 Figure 4. Adaptive mesh -FNC.

  Contact iteration loop « I » ALM -test contact at each node Contact at a node is solved penalty factor obtained (p = p I ) Contact at a node is not solved yet penalty factor increases (p I+1 = 10 p I ) Contact on the whole beam is solved: Each node has its own penalty factor re-mesh the continous beam FNC re-locate the connectors  →   Continuous contact is included Load increment: J = J+1 Loading iteration loop « J » Verification if values of p

Figure 7 -

 7 Figure 7 -Two numerical integrations (one along each axis y and x).

  with the behaviour matrix [ ] D in accordance with Eq.18:

[

Figure 8 .

 8 Figure 8.a -Geometrical characteristics of the twin-beam.

Figure 8 .

 8 Figure 8.b -Loading stages 2 and 3.Table 1 -Numerical values of mechanical characteristics. Material Parameters Concrete

Figure 11 .

 11 Figure 11.a -Comparison of the vertical displacement -"new" model.

Figure 12 -

 12 Figure 12 -Comparison of deflexions -with ALM algorithm.

Figure 13 -

 13 Figure 13 -Successive beam meshes.

Figure 14 -

 14 Figure 14 -Comparison between initial and final mesh. For Calculation1 and Calculation2 same stopping criterion is used: reaching elastic hogging bending at intermediate support. For Calculation1, elastic hogging bending is reached for p = 280 kN/m and for Calculation2 p = 264 kN/m. For these both loading levels, the stresses in the composite cross-sections at mid-span and at intermediate support are given in Figure 15.a and Figure 15.b.

Figure 15 .Figure 15

 1515 Figure 15.a -Stress distribution in sagging and hogging cross-sections Calculation1 (ALM) -p = 280 kN/m.

Figure 16 -Table 2 -Figure 17 -

 16217 Figure 16 -Stress distribution in sagging and hogging cross-sections Calculation1 (ALM) -p = 264 kN/m.

  )

						u	( s ) j	+ + + +	( s ) ( s ) j d θ θ θ θ
	(i)	(j)
	Slab					v	( s ) j
		d	(	s	)
	Interface
		d	(	g	)
	Girder					γ γ γ γ	j	v	( g ) j
					u	( g ) j	+ + + +	( g ) ( g ) j d θ θ θ θ
	0	L
						u	( s ) j	( s ) ( s ) j d θ θ θ θ
	2.2.2 Application of ALM to total potential energy


E Koorambas
email: elias.koor@gmail.com

Random numbers generated by orbifold fixed points

Keywords: number(s):11.25.Mj, 03.65.Ta Compactification and four-dimensional models, Random number generators High Energy and Particle Physics

Taking an orbifold with one compact extra dimension as a starting point, we show that random numbers are generated by recurrence modulo 2 over the Galois field of orbifold fixed points.

Our suggestion may open a window for extra dimensions predicted by experiments.

Introduction

Orbifolds, originally introduced as "V -manifolds" by Satake in the 1950s [START_REF] Chirτ Satake | On a generalization of the notion of manifold[END_REF], and named by Thurston in the 1970s [START_REF] Thurston | The Geometry and Topology of Three-Manifolds[END_REF], [START_REF] Thurston | Three-dimensional manifolds, Chelonian groups and hyperbolic geometry[END_REF], are useful generalizations of manifolds: locally they look like the quotient of Euclidean space by the action of a finite group. The concept of orbifolds has gained increasing popularity recently due to its application in many questions of theoretical physics such as [4], [5], [6], [7].

''In various fields of interest, situations often arise in which the mathematical model utilizes a random sequence of numbers, events, or both. In many of these applications it is often advantageous to generate, by some deterministic means, a sequence which appears to be random, even if, upon closer and longer observation, certain regularities become evident.

Monte Carlo experiments, for instance, have benefited greatly from computer programs for generating random numbers [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF].''

This paper describes random numbers generated by recurrence modulo2 over the Galois field of orbifold fixed points. Random numbers are generated by modulo 2 linear recurrence techniques, long used to generate binary codes for communications [8], [7], [START_REF] Golomb | Linear recurring sequences[END_REF], [START_REF] Baumert | Coding theory and its Applications to Communications Systems[END_REF], [START_REF] Titisworth | Modulation by Random and Pseudo-Random Sequences[END_REF]. The idea of using finite fields in quantum theory has been discussed by several authors (see e.g., References [START_REF] Coish | Elementary particles in a finite world geometry[END_REF][START_REF] Shapiro | Weak interactions in the theory of elementary particles with finite space[END_REF][START_REF] Nambu | Field Theory of Galois Fields[END_REF][START_REF] Vourdas | Quantum systems with finite Hilbert space[END_REF][START_REF] Vourdas | Symplectic transformations and quantum tomography in finite quantum systems[END_REF][START_REF] Felix | Lev Introduction to a Quantum Theory over A Galois Field Symmetry[END_REF]).

Random numbers generated by the orbifold fixed points

In the 1 2 / S  orbifold, we compactify one extra dimension on a circle 1 S , and we identify points under a 2  group action generated by : g a a 

(1)

The emerging fundamental domain of the 1 2 / S  orbifold is a 3 space bounded by the orbifold"s fixed points, i.e. the two points that are invariant under the orbifold action:

1 2 0, a a L    ( 2
)
where L is the extra dimension radius. The orbifold 1 2 / S  , depicted in Figure1, is topologically the unit interval [0, 1] with the two fixed points corresponding to the endpoints of the interval. [START_REF] Thurston | Three-dimensional manifolds, Chelonian groups and hyperbolic geometry[END_REF] Furthermore, let 1 S be the manifold with the action of the finite group 2  . The Eulercharacteristic of the quotient space 11 2 / OS  can be computed by the Lefshetz formula [START_REF] Bryan | Fulman Orbiflod Euler-characteristic and Number of Commuting m-tuple in symmetric group Anneal of Combinatories[END_REF]:

2 1 2 1 ( ) ( ) || g g O a      (3)
where 11 2 / OS  the quotient space and g a the fixed point set of g . Here, we define an Euler-characteristic for the finite group 2

Z

acting on the assembly of

O O O a a a Z      , (4)
where ( 11

1 1 2 / O S Z  … 11 2 / nn O S Z 
) the sequence of the quotient space and 12 ( , , ..., )

gg g n a a a
the fixed point n -tuple [1] .

Random numbers can be generated by recurrence modulo two over the Galois field of orbifold fixed points elements. This is achieved in the following steps.

First, starting with the Galois Field of two orbifold fixed points elements GF ( 2) is the smallest finite field. The two orbifold fixed points are 0, 1 being the addition and multiplication identities respectively. The field"s addition operation is given by the Table .1

Table.1 Addition + 0 1 0 0 1 1 1 0
and the multiplication operation by the following Table .2 [1] Note: By following [START_REF]Rotiman Introduction to modern set theory[END_REF] the orbifold fixed point n-tuple is defined as follows: a) Any n-tupe 0 1 ( ,...., )

n xx  orbifold fixed point is a function f with {0,...., 1} dom f n   and () i x f i  b) The Cartesian product of the orbifold 0 1 1 .... n O O O  
is the set of all n-tuples f such that () As a consequence of modular arithmetic which forms the basis of finite fields, these two orbifold fixed points elements and these operations constitute a system with many of important properties of familiar number system: additional and multiplication are commutative and associative, multiplication is distributive over addition, addition has an identity element (0) and an inverse element for every element. Multiplication has an identity element (1) and an inverse for every element but (0).

i f i O  ,for 0 1 in    .

High Energy and

The addition and multiplication operation in GF (2) are also bitwise operators XOR and AND respectively.

Many familiar and powerful tools of mathematics work in GF (2) just as well as integers and real numbers. Since modern computers also represent data in binary code, GF ( 2) is an important tool for studying algorithms on these machines that can be defined by series of bitwise operators.

Next, by following [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF], let {} k aa  be the sequence of 0 and Ls orbifold fixed points generated by the linear recurrence relation

k k k n k n a c a c a c a        (5)
For any given set of integers ( 1, 2, ..., )

i c i n 
, each having the orbifold fixed points values 0 or 1, we require ( , , ...., )

k k k n a a a   
. Each such ntuple of fixed orbifold points, thus, has a unique successor governed by the recursion formula (5). The period p of a is clearly the same as the recurrence period of an n-tuple of fixed orbifold points. The period p of a linear recurring sequence cannot be greater than 21 n  , for the n-tuple (0, 0, ...., 0 ) is always followed by (0, 0, ...., 0 ) . For .

n f x c x c x x      (6)
be primitive over GF (2) [8], [START_REF] Golomb | Linear recurring sequences[END_REF].

As the function () fx is a primitive nth degree polynomial over GF (2), the sequence {} k aa  is a maximallength linearly recurring sequence modulo 2. Such sequences have been studied, and used as a code in communications and theoretical information studies [START_REF] Baumert | Coding theory and its Applications to Communications Systems[END_REF],

High Energy and Particle Physics May 15, 2014 E.Koorambas: Random numbers generated by orbifold fixed points [5] [11]. The following properties of sequence ( 5) are of immediate interest to the scope of this paper [8], [START_REF] Golomb | Linear recurring sequences[END_REF].

[1] 1 1 1 2 2 p n k k p a      (7)
[2]For every distinct set of (0, 1) integers 12 , , ...., n s s s not all zero, there exists a unique integer : (0 1) u u p    such that for every k, 1 1 2 2 , , ...., (m od 2)

k k n k n k u s a s a s a a     
. This is often referred to as the "cycle-and add" property [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF].

[3] For every non-zero (0, 1), a binary n-vector 12 ( , , ...., ) n e e e occurs exactly once per n consecutive binary digits of a .

Note that properties [START_REF] Chirτ Satake | On a generalization of the notion of manifold[END_REF] and [START_REF] Thurston | The Geometry and Topology of Three-Manifolds[END_REF] flow directly from the fact that each possible non-zero binary n-tuple

We see that if k a takes on the fixed orbifold point values 0 and 1, then k a  takes the values +1 and -1, respectively. The properties [START_REF] Chirτ Satake | On a generalization of the notion of manifold[END_REF], [START_REF] Thurston | The Geometry and Topology of Three-Manifolds[END_REF] and [START_REF] Thurston | Three-dimensional manifolds, Chelonian groups and hyperbolic geometry[END_REF], then, take the form: Let () gxbe the 1  -valued Boolean function of (0, 1) fixed orbifold point variables 12 , , ...., n x x

[1"] 1 1 p k k a     (9)
x . For any 12 ( , , ...., )

n s s s s  , 0 i s  or 1, fixed orbifold points define 1 1 2 2 .... /2 ( , ) 2 ( 1) nn s x s x s x n sx        (10)
This 2 n function of x is the Redemacher-Walsh function [5] from an orthonormal basis for extra-dimensional 2 n -space. From this follows that () gx has components () Gsgiven by /2 ( ) 2 ( ) ( , )

n x G s g x x s     (11)
That is, () Gs is the projection of

            (14)
By property [2"], we now have the fourth property basic on [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF]; [4] () 0 (0) ( )

k k u s s G G s a      (15)
where the mapping () us of all binary n-vectors onto  

0,1,..... 1 p  is one-to-one. Let   k aa 
be the (0, 1) orbifold fixed points sequence generated by an nth degree maximallength R linear recurrence modulo 2, as described previously. We define a set of numbers of the form

where r is a randomly chosen integer, 0 That is, k y is the binary expansion of a number whose representation is R consecutive digits. Successive k y are spaced q digits apart [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF]. For reasons essential to the analysis, we restrict qn  and   , 2 1 1 n q  . We can then express k y by

1 2 R t k qk t R t ya      (17)
Such numbers always lie in the interval (0 1) k y  . Because of property [START_REF] Thurston | The Geometry and Topology of Three-Manifolds[END_REF], the randomness of the choice of r is equivalent to the statement that the initial value 0 y is a random choice [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF]. It is convenient to work with a transformed set of numbers k w rather than k y . This transformed set of numbers is defined as follows: Let [7] We see that k y and k w are related by

1 2 2 R k k w y     (19)
there is thus a translation between k w and k y [START_REF]Tausworthe Random Numbers Generated by Linear Recurrence Modulo Two Mathematics of Computation[END_REF].

Conclusion

We conclude that, random numbers can be generated by recurrence modulo 2 over the Galois field of orbifold fixed points GF (2). Since our 3-dimensional space bounded by orbifold"s fixed points, these random numbers can be used to generate binary codes that may correspond to the extra dimensions signature [START_REF] Adelberger | Tests of the Gravitational Inverse-Square Law Ann[END_REF], [START_REF] Hoyle | Sub-millimeter Tests of the Gravitational Inverse-square Law[END_REF], [START_REF] Kapner | Tests of the Gravitational Inverse-Square Law below the Dark-Energy Length Scale[END_REF]. This proposal may open a window for ruled out extra dimensions by experiments.

1 . 2 2.

 12 Introduction...................................................................................................................... Random numbers generated by the orbifold fixed points……………………………..

Figure 1 :

 1 Figure 1: The orbifold 1

  Random numbers generated by orbifold fixed points[4]

1 nc

 1  , and say that the sequence has degree n.For fixed i c , the recursion k a is determined solely by the n

[ 2 "

 2 ]For every distinct set of (0, 1) integers 12 , , ...., With the exception of the all ones vector, every 1  binary n-vector 12 ( , , ...., ) n    occurs exactly once per period as n consecutive element in a .



  and Rn  .

  Random numbers generated by orbifold fixed points

Table . 2

 . Μultiplication

	*	0	1
	0	0	0
	1	0	1

References…………………………………………………………………………………


Anne Dicky
email: dicky|janin@labri.fr

David Janin

Embedding finite and infinite words into overlapping tiles

In this paper, we study languages of finite and infinite birooted words. We show how the embedding of free ω-semigroups of finite and infinite words into the monoid of birooted words can be generalized to the embedding of two-sorted ω-semigroups into (some notion of) onesorted ordered ω-monoids. This leads to an algebraic characterization of regular languages of finite and infinite birooted words that generalizes and unifies the known algebraic characterizations of regular languages of finite and infinite words 1 .

Introduction

Infinite strings naturally arise in Software Engineering as models of (potentially) non-terminating system behaviors. From an abstract point of view, infinite strings are defined as infinite concatenations of non-empty finite strings, with an infinite associativity law ensuring that this infinite product is compatible with the standard concatenation of finite strings. Such an infinite string is depicted Figure 1. The resulting algebraic structures are the (free) ω-semigroups [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF], that is, the free semigroups of finite strings with string concatenation as product extended with the infinite product to produce infinite strings and a related mixed product to concatenate finite strings in front of infinite strings. This leads to the notions of ω-semigroups and morphisms that provide an algebraic characterization of regular languages of infinite words (see [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF]). These results also offer quite a deep insight of the mathematical properties of Büchi's automata on infinite strings [START_REF] Büchi | On a decision method in restricted second order arithmetic[END_REF] and the associated algorithmic tools that have been developed for model-checking and program verification (see e.g. [START_REF] Grädel | Automata, Logics and Infinite Games[END_REF] for an overview).

Programming languages such as Haskell [START_REF] Hudak | A history of Haskell: Being lazy with class[END_REF] allow for effectively defining infinite streams of values by means of lazy evaluation mechanisms. In view of application to temporal media programming, that is, finite and infinite sequences of media type values such as images, sounds or control events, the abstract data type implicitly induced by ω-semigroups is enriched with the parallel product of finite or infinite strings. This leads to effective tools for handling temporal media types [START_REF] Hudak | A sound and complete axiomatization of polymorphic temporal media[END_REF]. The notion of parallel product is depicted Figure 2.

w1 w2

Fig. 2. A parallel product of two words.

It has recently been advocated that there are benefits in embedding finite strings as well as infinite streams into (some notion of) tiled temporal media [START_REF] Hudak | Tiled polymorphic temporal media[END_REF]. Typical temporal media synchronization constructs such as musical pickups (anacrusis) lead to distinguishing the effective starts of temporal media -the first note of a melody, from their logical starts -the first strong beat of that melody [START_REF] Berthaut | Advanced synchronization of audio or symbolic musical patterns: an algebraic approach[END_REF]. Then, the notion of tiled temporal media allows for a fairly simple modeling of these multi-level synchronization constructs. This comes from the fact that they are equipped with a tiled product that is neither a sequential nor a parallel product but both [START_REF] Janin | The T-calculus : towards a structured programming of (musical) time and space[END_REF][START_REF] Hudak | Tiled polymorphic temporal media[END_REF].

More precisely, distinguishing string values from strings synchronization usage can be modeled by enriching the string data type by means of two synchronization marks: the pre synchronization mark or input root, and, respectively, the post synchronization mark or or output root (see Figure 3). These synchro- nization marks tell how such enriched words are to be positioned with respect to the temporal media that comes before, or, respectively, after, the current temporal media. The resulting objects, here called birooted words, are then equipped with a single product, the tiled product, that is neither a sequential product as string concatenation, not a parallel product as string "zip", but both (see Figure 4 and [13] for a fairly simple implementation of these ideas on top of the musical library Euterpea [START_REF] Hudak | The Haskell School of Music : From signals to Symphonies[END_REF] in Haskell).

In the general setting of higher-dimensional strings and tiling semigroups [START_REF] Kellendonk | The local structure of tilings and their integer group of coinvariants[END_REF][START_REF] Kellendonk | Tiling semigroups[END_REF][START_REF] Janin | Towards a higher dimensional string theory for the modeling of computerized systems[END_REF], the tiled temporal media and the related tiled product lay in the mathematical framework of inverse semigroup theory [START_REF] Lawson | Inverse Semigroups : The theory of partial symmetries[END_REF] and semigroups with local units [START_REF] Lawson | Semigroups and ordered categories. I. the reduced case[END_REF][START_REF] Fountain | A Munn type representation for a class of E-semiadequate semigroups[END_REF][START_REF] Fountain | The free ample monoid[END_REF]. Projecting tiled temporal media onto semantical tags, we obtain sorts of tiled words. In the finite case, the induced algebra is the inverse semigroup of McAlister whose elements are birooted words [START_REF] Mcalister | Inverse semigroups which are separated over a subsemigroups[END_REF][START_REF] Lawson | McAlister semigroups[END_REF].

Aiming at providing a robust mathematical framework for handling languages of tagged tiled temporal media, our purpose here is to extend the languagetheoretical tools available for languages of finite birooted words (see [START_REF] Janin | On languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF][START_REF] Dicky | Two-way automata and regular languages of overlapping tiles[END_REF][START_REF] Janin | Overlaping tile automata[END_REF]) to the case of infinite birooted words.

For such a purpose, we show that the obvious embedding of the free ωsemigroups of finite and infinite words into the monoid of birooted words can be generalized to the embedding of two-sorted ω-semigroups into one-sorted ordered ω-monoids.

This leads to an algebraic characterization of regular languages of finite and infinite birooted words that generalizes and unifies the algebraic characterizations of regular languages of finite and infinite words.

For the sake of simplicity, we restrict our presentation to one-sided birooted words. The resulting monoid turned out to be the filter completion (with respect to the natural order [START_REF] Lawson | Inverse Semigroups : The theory of partial symmetries[END_REF]) of the polycyclic monoid of Perrot and Nivat [START_REF] Nivat | Une généralisation du monoïde bicyclique[END_REF]. However, all proposed concepts and constructions can clearly be extended to two-sided birooted words, that is, within the filter completion of the submonoid of McAlister [START_REF] Lawson | Inverse Semigroups : The theory of partial symmetries[END_REF] of positive tiles. It follows that our results also apply to biinfinite words with the resulting ordered ω-monoids equipped with both a left and a right infinite product.

Technically, our results capitalize on the quasi-inverse expansion of semigroups presented in [START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Algebras, automata and logic for languages of labeled birooted trees[END_REF]. However, in the settings of infinite bi-rooted words, a congruence property, that appears in the notion of Ehresmann semigroups [START_REF] Lawson | Semigroups and ordered categories. I. the reduced case[END_REF] is essential and was totally left unnoticed (and unused) in the finite case. The resulting algebraic framework is thus a refinement of the one proposed in [START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Quasi-inverse monoids (and premorphisms)[END_REF].

From finite or infinite words to birooted words

In this section we define the monoid of positive finite or infinite birooted words. From a mathematical point of view, that monoid is a submonoid of the filter completion of the monoid of McAlister [START_REF] Lawson | McAlister semigroups[END_REF]. The language theory of the McAlister monoid has been developed in [START_REF] Janin | On languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Overlaping tile automata[END_REF][START_REF] Dicky | Two-way automata and regular languages of overlapping tiles[END_REF] for finite tiles.

Let A be a finite alphabet. Let (A * , •) be the free monoid of finite strings on the alphabet A, and let (A + , A ω , •, * , π) be the associated free ω-semigroup (see [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF]) with finite product •, mixed product * and infinite product π.

In the sequel, both the finite product u 1 • u 2 when u 1 , u 2 ∈ A * or the mixed product u 1 * u 2 when u 1 ∈ A * and u 2 ∈ A ω may simply be denoted by u 1 u 2 .

The set A ∞ = A * ∪ A ω of finite and infinite strings is ordered by the prefix order ≤ p , defined, for every u and v ∈ A ∞ , by u ≤ p v when either u = v, or u is finite and there is w ∈ A ∞ such that v = uw. Extended with a maximum element denoted by 0, the set A ∞ +0 ordered by the prefix order ≤ p is a complete lattice. The prefix join u ∨ p v of two words u and v ∈ A ∞ is then the least word w ∈ A ∞ , if it exists, such that we have both u ≤ p w and v ≤ p w, or 0 otherwise. Then, for every u ∈ A * and v ∈ A ∞ , the right residual u -1 (v) of v by u, is defined as the word w ∈ A ∞ , unique if it exists, such that v = uw. We take u -1 (v) = 0 otherwise. By definition, u -1 (v) = 0 if and only if u ≤ p v. Definition 1. A positive (right) birooted word u is a pair u = (u 1 , u 2 ) where u 1 ∈ A * and u 2 ∈ A ∞ . The word u 1 u 2 ∈ A ∞ is called the domain of the birooted word u, and the word u 1 , its root path. The birooted word (u 1 , u 2 ) is finite when u 2 is finite. The set of positive birooted words on the alphabet A is denoted by T ∞ (A). The set of finite positive birooted words on A is denoted by T + (A).

The product u•v of two birooted words u = (u 1 , u 2 ) and v = (v 1 , v 2 ) is defined as the birooted word w = (w 1 , w 2 ) with

w 1 = u 1 v 1 and w 2 = v -1 1 (u 2 ) ∨ p v 2 when v -1
1 (u 2 ) ∨ p v 2 = 0. Otherwise, we take u • v = 0 for some new birooted word 0, with 0 • u = u • 0 = 0 for every u ∈ T ∞ (A), and 0 • 0 = 0.

Examples.

The following examples illustrate the definition of the product:

(ab, ab) • (a, bc) = (aba, bc) (ab, (ab) ω ) • (a, bc) = 0 (ab, (ab) ω ) • (a, ba) = (aba, (ba) ω ) (ab, ab) • (a, (ba) ω ) = (aba, (ba) ω ) (ab, ab) • (a, (bc) ω ) = (aba, (bc) ω ) (ab, ac) • (a, (ba

) ω ) = 0 (1, ab) • (1, abc) = (1, abc) (1, ab) • (1, ac) = 0
Let T ∞ 0 (A) (resp. T + 0 (A)) be the set of positive birooted words (resp. finite positive birooted words) extended with 0. Theorem 2. The set T ∞ 0 (A) equipped with the above product is a partially ordered monoid with unit 1 = (1, 1).

Proof. Easily proved by routine arguments. ✷

Let u → u R and, resp., u → u L be the right projection (or reset) and, resp., the left projection (or co-reset) defined on the monoid T ∞ 0 (A) by

0 R = 0 L = 0 , u R = (1, u 1 u 2 ) and u L = (1, u 2 )
for every u = (u 1 , u 2 ) ∈ T ∞ 0 (0). Then the natural order relation (see [START_REF] Lawson | Semigroups and ordered categories. I. the reduced case[END_REF][START_REF] Janin | Quasi-inverse monoids (and premorphisms)[END_REF]) is defined by

u ≤ v when u = u R • v • u L , or, equivalently, u = u R • v
for every u and v ∈ T ∞ 0 (A). Elements u such that u ≤ 1 are called subunits and the set of subunits is denoted by U (T ∞ 0 (A)).

Theorem 3. The natural order relation on T ∞ 0 (A) is a partial order relation stable under product, that is if u ≤ v then uw ≤ vw and wu ≤ wv for all u, v, w ∈ T ∞ 0 (A). Subunits and idempotents coincide, that is, we have u ≤ 1 if and only if u = uu for all u ∈ T ∞ 0 (A). Moreover, the set U (T ∞ 0 (A)) ordered by the natural order is a complete lattice with product as meet.

Proof. All statements can directly be proved by routine arguments. More interestingly, on can check that the set T ∞ 0 (A) of (right) birooted words is indeed isomorphic to the filter completion of the set T + 0 (A) of one-sided finite birooted words ordered by the natural order, or, equivalently, the polycyclic monoid of Nivat and Perrot [START_REF] Nivat | Une généralisation du monoïde bicyclique[END_REF].

More precisely, an (order) filter is a non empty subset X of T + 0 (A) that is upward closed, i.e. for every u and v ∈ T + 0 (A), if u ≤ v and u ∈ X then v ∈ X, and downward directed, i.e. for every u and v ∈ X there exists w ∈ X such that w ≤ u and w ≤ v. The set F(T + (A)) of filters is equipped with the product defined, for every filters X and Y , by

X •Y = {w ∈ T + 0 (A) : ∃u ∈ X, v ∈ Y, u•v ≤ w} that
is well defined since the natural order is stable under product.

Then, one can show that the mapping ϕ : T ∞ (A) → F(T + (A)) that maps every bi-rooted word u ∈ T ∞ (A) to the set of finite birooted words ϕ(u) = {v ∈ T + (A) : u ≤ v} is an isomorphism from T ∞ (A) to the monoid of filters of T + (A). ✷

Remark. In the finite case [START_REF] Janin | On languages of one-dimensional overlapping tiles[END_REF][START_REF] Janin | Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles[END_REF], we consider positive two-sided birooted words.

Here, in a tile (u 1 , u 2 ) ∈ T ∞ 0 (A), we always have empty domain on the left of the root path: the birooted words defined here are one-sided. A two-sided positive birooted word would be a triple (u 1 , u 2 , u 3 ) with a finite or infinite left word u 1 ∈ ∞ A, a finite root path u 2 ∈ A * , and a finite or infinite right word u 3 ∈ A ∞ . All definitions and results presented here are easily extended to the two-sided case.

An immediate interest of the notion of finite and infinite birooted words is that the (two sorted) free omega monoid (A + , A ω ) can be embedded into the (one sorted) monoid

T ∞ 0 (A), that is, the pair (T ∞ 0 (A), U (T ∞ 0 (A))
) can be equipped with a mixed and an infinite product in such a way that it is an ωsemigroup into which the free ω-semigroup (A + , A ω ) can be embedded. More precisely, let u * v be the mixed product defined by

u * v = (u • v) R for all u ∈ T ∞ 0 (A) and v ∈ U (T ∞ 0 (A)), and let π(u i ) i∈ω be the infinite product defined by π(u i ) i∈ω = n∈ω (u 0 • u 1 • • • • • u n-1
) R for all infinite sequences of birooted words (u i ) i∈ω . Then we have:

Theorem 4. The pair (T + 0 (A), U (T ∞ 0 (A))
) equipped with the finite product, the mixed product and the infinite product is a well-defined ω-semigroup.

Moreover, let θ f : A * → T + 0 (A) be the mapping defined by θ f (v) = (v, 1) for every finite word v ∈ A * and let θ ω : A ω → U (T ∞ 0 (A)) be the mapping defined by θ ω (w) = (1, w) for every infinite word w ∈ A ω .

Then, the pair of mappings (θ f , θ ω ) :

(A + , A ω ) → (T + 0 (A), U (T ∞ 0 (A))
) is an ω-semigroup embedding, that is, a one-to-one mapping that preserves the finite, the mixed and the infinite products.

Proof. Clearly, the infinite product is well-defined since U (T 0 ∞) ordered by the natural order is a complete lattice with product as meet. Then, it is routine to check that the pair (T + 0 (A), U (T ∞ 0 (A)) with product •, mixed product * and infinite product π is an ω-semigroup. Moreover, θ f is clearly a one-to-one monoid morphism and θ ω is one-to-one and, moreover, for every v ∈ A * and w ∈ A ω , we easily check that we have

θ ω (v * w) = (θ f (v) • θ ω (w)) R . Then it is routine to check that θ ω (v * w) = θ f (v) * θ ω (w) for all v ∈ A * and w ∈ A ω and that θ ω (π(u i ) i∈ω ) = π i∈ω θ f (u i )
for every (u i ) i∈ω ∈ (A + ) ω . In other words, the pair of mappings (θ f , θ ω ) is an ω-semigroup morphism. ✷

In the particular case where the infinite sequence (u i ) i∈ω is constant, that is, when there is some v ∈ T ∞ 0 (A) such that u i = v for every i ∈ ω, then we write v ω for π(u i ) i∈ω . One can easily check that for every idempotent (or subunit) u ≤ 1 we have u ω = u.

Embedding ω-semigroups into ordered ω-monoids

We show here that the above embedding of the free ω-semigroup (A + , A ω ) into the monoid of birooted words T ∞ (A) can be generalized to an embedding of any ω-semigroup S into (some notion of) ordered ω-monoid M (S).

Let M be a monoid partially ordered by a relation ≤. We assume that the order relation ≤ is stable under product, i.e. if x ≤ y then xz ≤ yz and zx ≤ zy for every x, y and z ∈ M . The set U (M ) of subunits of the partially ordered monoid M is defined by

U (M ) = {y ∈ M : y ≤ 1}.
The following definition is adapted from [START_REF] Janin | Overlaping tile automata[END_REF] and then, following [START_REF] Lawson | Semigroups and ordered categories. I. the reduced case[END_REF], refined with the congruence property [START_REF] Janin | Quasi-inverse monoids (and premorphisms)[END_REF][START_REF] Dubourg | Algebraic tools for the overlapping tile product[END_REF].

Definition 5 (Adequately ordered and E-ordered monoids). A (stable)

partially ordered monoid M is an adequately ordered monoid when: (A1) idempotent subunits: for every x ∈ M , if x ≤ 1 then xx = x, (A2) left and right projection: for every x ∈ M , both the left projection defined by x L = min{y ∈ U (M ) : xy = x} and the right projection defined by

x R = min{y ∈ U (M ) : yx = x} exist in U (M ),
It is an Ehresmann-ordered monoid (or E-ordered monoid) when, moreover:

(A3) congruence property: for every x, y, z ∈ M , if x L = y L then (xz) L = (yz) L and if x R = y R then (zx) R = (zy) R ,
Examples. Every monoid trivially ordered is an adequately ordered monoid. Every inverse monoid ordered by the natural order [START_REF] Lawson | Inverse Semigroups : The theory of partial symmetries[END_REF] is also an adequately ordered monoid with left and right projections defined by x R = x • x -1 and x L = x -1 • x for every element x.

The notion of adequately ordered monoid is extended here with an infinite (right) product as follows.

Definition 6 (E-ordered ω-monoid

). An E-ordered ω-monoid if an E-ordered monoid M equipped with an infinite product operator π : M ω → U (M ) satisfying the following properties:

(I1) subunit preservation: for every (x i ) i∈ω such that for every i ∈ ω we have

x i = x for some x ∈ U (M ), then π(x i ) i∈ω = x, (I2) monotonicity: for every infinite sequences (x i i∈ω ∈ M ω and (y i ) iω , if

x i ≤ y i for every i ∈ ω then π(x i ) i∈ω ≤ π(y i ) i∈ω , (I3) mixed associativity: for every infinite sequence (x i ) i∈ω ∈ M ω , for every

x ∈ M , given x ′ i = x when i = 0 and

x ′ i = x i-1 when i > 0, we have (x • (π(x i ) i∈ω )) R = π(x ′ i ) i∈ω (I4
) infinite associativity: for every infinite sequence (x i ) i∈ω ∈ M ω , for every strictly increasing sequence (k i ) i∈ω of positive integers with k 0 = 0, given

y i = x ki • x ki+1 • • • x ki+1-1 defined for every i ∈ ω, we have π(y i ) i∈ω = π(x i ) i∈ω .

Definition 7 (Monoid completion).

Let S = (S f , S ω ) be an ω-semigroup with finite product • : S f × S f → S f , mixed product * : S f × S ω → S ω and infinite product π : (S f ) ω → S ω . By definition (see [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF]) the finite, mixed and infinite product are related by mixed and infinite associativity laws. Let S 1 f be the semigroup S f extended with a unit and let P * (S ω ) be the set of non-empty subsets of S ω .

The monoid completion M (S) of the ω-semigroup S is defined to be the M (S) = S 1 f × P * (S ω ) + 0 equipped with the product • defined, for every non zero element (x, X) and (y, Y ) ∈ M (S) by (x, X) • (y, Y ) = (xy, y -1 (X) ∩ Y ) when y -1 (X) ∩ Y = 0 with y -1 (X) = {z ∈ S ω : y * z ∈ X} and is defined to be 0 all other cases, with y -1 (X) = {z ∈ S ω : y * z ∈ X}. Element of M (S) are also ordered by the relation ≤ defined over M (S) by taking 0 to be the smallest element and by (x, X) ≤ (y, Y ) when x = y and X ⊆ Y for every (x, X) and (y, Y ) ∈ M (S). Theorem 8. The set M (S) with the above product • and the natural order ≤ is an E-ordered monoid with unit 1 = (1, S ω ).

Proof. The proof follows from the following Lemmas.

Lemma 9 (Soundness).

The set M (S) with the above product • and the natural order ≤ is a partially ordered monoid with unit 1 = (1, S ω ).

Proof. Associativity and stability of the order relation are easily proved with essentially the same argument as in [START_REF] Janin | Quasi-inverse monoids (and premorphisms)[END_REF] though with subsets of S ω instead of right ideals of S f . The fact that 1 = (1, S ω ) makes no difficulty either. ✷

Let U (M (S)) = {x ∈ M (S) : x ≤ 1} be the set of subunits of M (S).

Lemma 10 (Adequacy). The set M (S) is an adequately ordered monoid.

Proof. By definition, a subunit of M (S) is either 0 or an element of the form (1, X) for some X ⊆ S ω . It follows that (A1) holds: subunits indeed idempotent elements.

Let us prove (A2). We easily check that 0 L = 0 R = 0. Let x ∈ M (S) be some non zero element of M (S), that is an element of the form x = (s, X). We prove that we have x R = (1, s * X) and its left projection x L = (1, X).

For the right projection, let z = (1, s * X). We have z

• x = (x, X ∩ s -1 (s * X)) but X ⊆ s -1 (s * X) hence z • x = x. Now, if z ′ • x = x for some z ′ = (1, Y ) then we have X = X ∩ s -1 (Y ) hence X ⊆ s -1 (Y ) hence s * X ⊆ Y that is, following the order definition, z ≤ z ′ .
For the left projection, let z = (1, X). We have

x • z = (s, X ∩ 1 -1 (X)) = (s, X) = z. If x • z ′ = x for some z = (1, Y ) we have x • z ′ = (s, Y ∩ 1 -1 (X)) = (s, X) hence X ⊆ Y that is z ≤ z ′ .
✷

Lemma 11 (Congruence property). The monoid M (S) is even an E-ordered monoid.

Proof. We prove that M (S) satisfies (A3). Let x, y, z ∈ S. If any of x, y or z is zero then the claim is satisfied. Assume x = (x 1 , X), y = (y 1 , Y ) and z = (z 1 , Z).

For the left projection, assume that x L = y L . This means that X = Y . We have

xz = (x 1 z 1 , z -1 1 (X) ∩ Z) hence (xz) L = (1, z -1 1 (X) ∩ Z).
A similar computation shows that (yz) L = (1, z -1 1 (Y ) ∩ Z) hence the claim since X = Y . For the right projection, assume that x R = y R . This means that

x 1 * X = y 1 * Y . We have zx = (z 1 x 1 , x -1 1 (Z)∩X) hence (zx) R = (1, z 1 * x 1 * (x -1 1 (Z)∩X)). A similar computation shows that (zy) R = (1, z 1 y 1 (y -1 1 (Z) ∩ Y )). Now let z ′ ∈ z 1 * x 1 * (x -1
1 (Z)∩X). By definition, and mixed associativity in S hence we do not bother about parenthesis, this means there is

x ′ ∈ X such that z ′ = z 1 * x 1 * x ′ with the additional constraint that x 1 * x ′ ∈ Z since x ′ ∈ x -1 1 (Z). But since x 1 * X = y 1 * Y , this means there exists y ′ ∈ Y such that x 1 * x ′ = y 1 * y ′ ∈ Z hence y ′ ∈ y -1 1 (Z)∩Y and thus z ′ = z 1 * x 1 * x ′ = z 1 * y 1 * y ′ ∈ z 1 * y 1 * (y -1 1 (Z)∩Y
). This proves that (zy) R ≤ (zx) R . The reverse inequality is proved by applying a symmetrical argument. ✷

This concludes the proof of Theorem 8. ✷

Remark. The notion of E-ordered monoid, extending Ehresmann semigroups [START_REF] Lawson | Semigroups and ordered categories. I. the reduced case[END_REF], appears in [START_REF] Dubourg | Algebraic tools for the overlapping tile product[END_REF]. It is examined quite in detail in [START_REF] Janin | Quasi-inverse monoids (and premorphisms)[END_REF]. There, a general construction, based on left and right ideals, is provided to embed every monoid S into a non trivial adequately ordered monoid Q(S): the quasi-inverse expansion of S that turned out to be E-ordered as well. One can observe that the construction of M (S) is quite similar with right ideals replaced by non empty subsets of S ω .

We define the infinite product π almost by iteration although, as well known in ω-language theory, the infinite product itself cannot be defined as a limit since many regula languages are not closed in prefix topology.

Among subunits of M (S), the meet ∧ in the order correspond to the product. Indeed, a subunit in M (S) is either zero (with just behave like (1, ∅)) or of the form (1, X) for some non empty X ⊆ S ω with (1, X)

• (1, Y ) = (1, X ∩ Y ).
The monoid of subunits U (S) is thus isomorphic to the power set P(S ω ) with intersection as product. In the next definition, when appropriate, we thus may use at will the meet operator ∧ in place of the product.

Definition 12 (Infinite product). Let (x

i ) i∈ω ∈ (M (S)) ω . Let π 0 () = 1 and for every n ∈ ω, let π n+1 (x i ) i≤n = (x 0 • π n (x i+1 ) i<n ) R .
Then, the infinite product π(x i ) i∈ω is defined by

π(x i ) i∈ω = (1, X ω ) ∧ n∈ω π n (x i ) i≤n
with X ω defined by X ω = S ω when J = {i ∈ ω : x i ≤ 1} is finite and X ω defined by X ω = {x ω } when J is infinite, with x ω = π(s ji ) i<ω where (j i ) i∈ω is the increasing enumeration of the elements of J and, for very j ∈ J, the (non zero) element x j is of the form x j = (s j , X j ).

Theorem 13. The E-ordered monoid M (S) equipped with the above infinite product is an adequately ordered ω-monoid.

Proof. Subunit preservation (I1) immediately follows from the definition. Monotonicity (I2) is also easily check. Indeed, if (x i ) i≤ω ≤ (y i ) i∈ω then, by definition of the order relation, this means that for every i ∈ ω if x i = (s i , X i ) for some s i ∈ S f and X i ⊆ S ω then we have

y i = (s i , Y i ) for some Y i ⊆ S ω with X i ⊆ Y i . It is then routine to check that we indeed have π(x i ) i≤ω ≤ π(y i ) i∈ω .
Mixed associativity (I3) quite immediately follows from Lemma 11 and the mixed associativity in S.

It remains to check that the product and the infinite product also satisfies the infinite associativity law (I4). Let (x i ) i∈ω ∈ (S f × {S ω }) ω , let (j i ) i∈ω a strictly increasing sequence of integers with j 0 = 0, and, for every i ∈ ω, let

y i = x ji • x ji+1 • • • • • x ji+1-1 .
We have to prove that π(x i ) i∈ω = π(y i ) i∈ω . By definition, for every i ∈ ω, we have

π ji+1 (x j ) j<ji+1 ≤ π i (y j ) j<i ≤ π ji (x j ) j<ji hence i∈ω π i (x j ) j<i = i∈ω π i (y j ) j<i .
In the case any of these meet is zero then we are done. Otherwise, assuming that, for every i < ω we have x i = (s i , X i ) and

y i = (t i , Y i ) with t i = s ji • s ji+1 • • • • • s ji+1-1
we have to check that X ω = Y ω as defined above. But this immediately follows from the definition and the fact S is an ω-semigroup. Indeed, either we have X ω = Y ω = S ω , or we have X ω = {x ω } and Y ω = {y ω } with x ω = y ω that follows from the infinite associativity property in the ω-semigroup S. ✷ Last, we aim at showing that the ω-monoid S = (S f , S ω ) can be embedded as an ω-monoid into M (S). This means defining over M (S) an ω-monoid structure (M f (M ), M ω (S)), which can be done by taking M f (S) = M (S) for the "finitary" part and M ω (S) = U (M (S)) for the "infinitary" part. The infinite product is the one already defined, and the mixed product of two elements x ∈ M (S) and y ∈ U (M (S)) is defined to be x * y = (x • y) R . Theorem 14. The mapping θ = (θ f , θ ω ) : (S f , S ω ) → (M (S), U (M (S))), defined by θ f (x) = (x, S ω ) for every x ∈ S f and by θ ω (y) = (1, {y}) for every y ∈ S ω , is a one-to-one ω-monoid morphism.

Proof. We first check that the pair of sets (M (S), U (M (S))) equipped with the product •, the mixed product * and the infinite product π is an ω-semigroup.

Lemma 9 ensures that M (S) equipped with the product • is a semigroup. The mixed associativity law follows from Lemma 11. The infinite associativity law follows from Theorem 13.

The fact θ f is a one-to-one monoid morphism follows from the fact that for every x ∈ S f we have

x -1 (S ω ) = {y ∈ S ω : x * y ∈ S ω } = S ω hence we indeed have θ f (x • y) = θ f (x) • θ f (y) for every x, y ∈ S f .
Let us show it preserves the mixed product. Let x ∈ S f and y ∈ S ω . We have

θ(x * y) = (1, {x * y}) and θ(x) * θ(y) = ((x, S ω ) • (1, {y})) R = ((x, {y})) R =
(1, {x * y}) hence we indeed have equality. Observe that this property is also a particular case of the congruence property proved in Lemma 11.

It remains to prove that θ also preserves infinite products. Let (x i ) i<ω ∈ (S f ) ω . By definition of θ ω , we have θ ω (π(x i ) i∈ω ) = (1, {π(x i ) i∈ω }). By definition of the infinite product, since θ f (x i ) ≤ 1 for every i ∈ ω, we have π(θ f (x i )) i∈ω = θ ω (π(x i ) i∈ω ) ∧ i∈ω π i (θ(x j )) j<i . Now, by definition of θ f , for every i ∈ ω, we have θ f (x i ) = (x i , S ω ) i∈ω hence, by definition of π i , π i+1 θ(x j ) j≤i = (1, j≤i x 0 * x 1 * • • • * x j * S ω ). Now, by mixed associativity in S, we have we have π(

x i ) i∈ω ∈ x 0 * x 1 * • • • * x i * S ω for every i ∈ ω, hence θ ω (π(x i ) i∈ω ) ≤ π i (θ(x j )) j<i henceforth π(θ f (x i )) i∈ω = θ ω (π(x i ) i∈ω ). ✷

Application to language theory

We provide here a complete language theory for birooted words. Since every non-zero birooted word can just be seen as a pair composed of a finite and a finite or infinite word, the logical definability in Monadic Second-Order (MSO) logic of languages of birooted words boils down to the classical finite and infinite word language theory. More interestingly, we also provide a notion of finite-state birooted word automata and algebras that essentially captures definability in MSO logic.

A language of birooted words is a set X ⊆ T ∞ (A) of non-zero birooted words. The class of such languages is equipped with the boolean operators union (also called sum), intersection and complement, plus operators derived from the structure of T ∞ 0 (A): for all X and Y ⊆ T ∞ (A), the product X • X, the star X * , as well as X + and the omega X ω , are defined by extending the corresponding operators on T ∞ 0 (A) in a point-wise manner, always omitting the birooted word zero possibly resulting from these products. Additionally, we define the left and right projections X L and X R of the language X as the sets

X L = {x L ∈ T ∞ (A) : x ∈ X} and X R = {x R ∈ T ∞ (A) : x ∈ X}.
Theorem 15. The class of languages of (positive) birooted words definable in MSO is closed under all the operators defined above. Moreover, it is finitely generated from the finite languages of (positive) birooted words, sum, product, star, omega and left and right projections.

Proof. Easily follows from standard relativization techniques of mathematical logic.

✷

Combining the notions of Muller ω-word automata [START_REF] Muller | Infinite sequences and finite machines[END_REF] (see also [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF]) and of tile automata [START_REF] Janin | Overlaping tile automata[END_REF], we define birooted words ω-automata as follows.

Definition 16. A (finite) birooted word ω-automaton is a tuple

A = Q, δ, K, W with a (finite) set of states Q, a transition function δ : A → P(Q × Q), a fini- tary acceptance condition K ⊆ Q × Q and an infinitary acceptance condition W ⊆ P(Q).
For technical reasons, we always assume that ∅ ∈ W .

A run of the automaton A on a birooted word u

= (u 1 , u 2 ) is a labeling mapping ρ : [0, |u 1 * u 2 | + 1[→ Q that satisfies the local consistency property : (ρ(k), ρ(k + 1)) ∈ δ((u 1 * u 2 )[k]) for every 0 ≤ k ≤ |u 1 | + |u 2 |.
The run ρ of the automaton A on the birooted word u = (u 1 , u 2 ) is locally accepting when the pair of states (ρ(0), ρ(|u 1 |)) that marks the input and output roots belongs to K.

The run ρ is globally accepting when the set of states that occur infinitely often belongs to W , i.e. {q ∈ Q : |ϕ -1 (q)| = ∞} ∈ W }. Observe that when (u 1 , u 2 ) is finite then the global acceptance constraint is always satisfied since we assume that ∅ ∈ W .

The language L(A) is then defined as the set of birooted words (u 1 , u 2 ) ∈ T ∞ (A) for which there exists a locally and globally accepting run of A on (u 1 , u 2 ). Theorem 17. A language L ⊆ T ∞ (A) of non nul birooted words is recognized by a finite-state birooted word ω-automaton if and only if L is definable in MSO and upward closed.

Proof. Assume that L is recognizable by a finite-state automaton. Since the existence of an accepting run on a birooted word amounts to checking the existence of some labeling of the vertices of (the graph representation of) the birooted word, this property is classically definable in MSO. Then, by definition of birooted word automata, the language L is upward closed w.r.t. in the birooted word order.

Conversely, assume that L is definable in MSO. By applying classical automata theoretic techniques, there exists an finite-state word automaton A ′ recognizing the language of finite and infinite words L ′ = {u 1 #u 2 ∈ (A + #) ∞ : (u 1 , u 2 ) ∈ L}. It is not difficult to derive from the automaton A ′ a birooted word automaton A recognizing, under upward closure hypothesis, the language L. ✷ Corollary 18. The class of languages recognized by a finite-state birooted word ω-automaton is closed under the sum, intersection, product, star and omega operations. Moreover, it is finitely generated from finite languages of (positive) birooted words, sum, product, star and omega, and the upward closure of left and right projections.

The next definitions and theorem extend a similar result proved in [START_REF] Janin | Overlaping tile automata[END_REF] for languages of finite birooted words.

A mapping ϕ : T ∞ 0 (A) → T from birooted words to an adequately ordered monoid T is a premorphism when ϕ(1) = 1 and ϕ(xy) ≤ ϕ(x)ϕ(y) and if x ≤ y then ϕ(x) ≤ ϕ(y) for every x and y ∈ T ∞ 0 (A). The premorphism ϕ is adequate when, moreover, ϕ(x L ) = (ϕ(x)) L and ϕ(x R ) = (ϕ(x)) R for every x ∈ S, and if x L y R = 0 and x L ∨ y R = 1 then ϕ(xy) = ϕ(x)ϕ(y) for every x and y ∈ S. In the latter case we say that the product xy is disjoint.

The adequate premorphism ϕ is ω-adequate when T is an adequately ordered ω-monoid and, for every infinite sequence (u i ) 0≤i ∈ (T 0 ∞ (A)) ω , we have ϕ(π(u i ) 0≤i ) ≤ π(ϕ(u i )) 0≤i and, moreover, if the product π(u i ) 0≤i is disjoint (i.e. for every 0 < k, given x = u 0 • u 1 • • • u k-1 and y = π(u i+k ) 0≤i we have x L y R = 0 and x L ∨ y R = 1), then we also have ϕ(π(u i ) 0≤i ) = π(ϕ(u i )) 0≤i .

A language L ⊆ T ∞ (A) is quasi-recognizable when there exists a finite adequately ordered ω-monoid S and an ω-adequate premorphism ϕ : T ∞ 0 (A) → S such that L = ϕ -1 (ϕ(T )).

Theorem 19. Let L ⊆ T ∞ 0 (A) be a language of non-zero finite or infinite birooted words. The language L is quasi-recognizable if and only if it is a finite boolean combination of upward-closed (for the natural order) languages definable in monadic second order logic (MSO).

Proof. Assume that there is an ω-adequate premorphism ϕ : T ∞ 0 (A) → S that recognizes L. Without loss of generality, possibly by adding a new zero to S, we may assume that ϕ -1 (0) = 0. Then, for every non-zero s ∈ S, ϕ -1 (s) is definable in MSO.

Indeed, the mapping that maps every finite word u ∈ A * to ϕ((u, 1)) is a monoid morphism since, for every a ∈ A, every u ∈ A * , the product (a, 1)

• (u, 1) is disjoint. Then, given (u 1 , u 2 ) ∈ T ∞ (A), since (u 1 , u 2 ) = (u 1 , 1) • (1, u 2 ) with a disjoint product, we have ϕ((u 1 , u 2 )) = ϕ((u 1 , 1))•(ϕ(1, u 2 )
). In the case u 2 is also finite, we are done since ϕ(1, u 2 ) = ϕ((u 2 , 1) R ) = ϕ((u 2 , 1)) R . In the case when u 2 is infinite, we can apply Ramsey's theorem and infinite associativity, following the technique used for infinite words [START_REF] Perrin | Infinite Words: Automata, Semigroups, Logic and Games[END_REF], to show that (1, u

2 ) = π((v i , 1)) 0≤i with ϕ((v i , 1)) = ϕ((v 1 , 1)) henceforth ϕ((1, u 2 )) = (ϕ((v 0 , 1)) • (ϕ((v 1 , 1))) ω ) R .
Then, by applying classical arguments of algebraic language theory, the fact that L is a finite boolean combination of upward closed languages is a consequence of the monotonicity of ϕ and the finiteness of S since, for every s ∈ ϕ(L), we have ϕ -1 (s) = ϕ -1 (s ↑ ) ∩ ϕ -1 (s ↓ ) with s ↑ (resp. s ↓ ) is the upward closure (downward closure) of the singleton {s}.

Conversely, assume that L is a finite boolean combination of upward closed languages {L i } 0≤i≤n definable in MSO. For every 0 ≤ i ≤ n, by applying Theorem 17, the language L i is recognized by a finite-state automaton A i . Now, by applying Lemma 20 below, for every i ∈ I, there exists an ω-adequate premorphisms ϕ i : T ∞ 0 (A) → S i with finite S i such that L i = ϕ -1 i (ϕ i (L i )) hence we conclude by applying classical algebraic techniques that the product premorphism ϕ :

T ∞ 0 (A) → S = S 0 × S 1 × • • • × S n defined for every x ∈ T ∞ 0 (A) by ϕ(x) = (ϕ 0 (x), ϕ 1 (x), • • • , ϕ n (x))
quasi-recognized L. Proving that the product monoid S is a (finite) adequately ordered ω-monoid raises no particular difficulties. ✷ Lemma 20. Let A be a finite-state birooted word ω-automaton. There exists a (finite) adequately ordered ω-monoid S A and an ω-adequate premorphism ϕ A :

T ∞ 0 (A) → S A such that L(A) = ϕ -1 A (ϕ A (L(A)). Proof. Let A = Q, δ, K, W be the automaton. Let T Q ⊆ Q × P(Q) × Q × P(Q)
be the set of automaton traces, that is, quadruples of the from (p, P, q, R) ∈ Q × P(Q) × Q × P(Q) with p ∈ P when p = q, with, intendedly, a input root state p, a set of states P occurring between the input and the output root, an output root state q and a set of states R occurring infinitely often. The set T Q is equipped with the partial product • defined, for every (p, P, q, R) and (p ′ , P ′ , q ′ , R ′ ) ∈ T Q , when q = p ′ and either R = ∅ or R ′ = ∅ or R = R ′ , by (p, P, q, R) • (p ′ , P ′ , q ′ , R ′ ) = (p, P ∪ P ′ , q ′ , R ∪ R ′ ) One can check that, although partial, it is nevertheless associative in the sense that for every traces t, t ′ , t", we have the product (t • t ′ ) • t" is defined if and only if the product t • (t ′ • t") is defined and, in that case, they are equal.

The set T Q is also equipped with an infinite product π defined, for every sequence (p i , P i , q i , R i ) 0≤i of traces of T Q , when q i = p i+1 and R i = ∅ for every 0 ≤ i, by π(p i , P i , q i , ∅) 0≤i = (p 0 , {p 0 }, p 0 , R)

with R = {q ∈ Q : |{i ∈ ω : q ∈ P i }| = ∞}.

Then we define S A as the power set of T Q , with product and infinite product defined as the point-wise extensions of the product and infinite product of T Q . That is, for every X and Y ⊆ T Q , we define X • Y as the set of all defined products x • y in T Q with x ∈ X and y ∈ Y , and, for every sequence (X i ) 0≤i of subsets of traces, we define π(X i ) 0≤i as the set of all defined products of the form π(x i ) 0≤i with x i ∈ X i for every 0 ≤ i.

It is routine to check that the monoid S A obtained, ordered by inclusion, is an adequately ordered ω-monoid (following the technicalities used in [START_REF] Janin | Overlaping tile automata[END_REF][START_REF] Janin | Algebras, automata and logic for languages of labeled birooted trees[END_REF] for finite birooted words or trees).

We define ϕ A : T ∞ 0 (A) → S A by ϕ(0) = ∅ and, for all birooted words (u 1 , u 2 ), ϕ((u 1 , u 2 )) is the set of traces of the form (p, P, q, R) such that there exists a run ρ of the automaton A on (u 1 , u 2 ) with ρ(0) = p, P = ρ([0, |u 1 |]), q = ρ(|u 1 |) and R = {r ∈ |Q| : |ρ -1 (q)| = ∞}. Again, it is routine to check that ϕ A is an ω-adequate premorphism.

We finally check that, by construction, a birooted word x ∈ T ∞ 0 (A) belongs to L if and only if there exist (p, P, q, R) ∈ ϕ A (x) such that (p, q) ∈ K and R ∈ W . ✷

Conclusion

We have shown that the embedding of strings and streams into tiled streams, as done for programming purposes [START_REF] Janin | The T-calculus : towards a structured programming of (musical) time and space[END_REF], can be lifted to arbitrary ω-semigroups, thus unifying the finite and infinite word language theory into the emerging language theory of birooted words. Since regular languages of finite and infinite tiled streams can be used as programming language subtypes, this result is also a new step in developing the idea that, in the long term, inverse semigroups [START_REF] Lawson | Inverse Semigroups : The theory of partial symmetries[END_REF] may be tuned towards robust engineering practice.

Following [START_REF] Janin | Algebras, automata and logic for languages of labeled birooted trees[END_REF][START_REF] Janin | On languages of labeled birooted trees: Algebras, automata and logic[END_REF], we could also aim at generalizing the present approach to trees, possibly leading to further developments in the very subtle and difficult emerging algebraic theory of languages of infinite trees [START_REF] Blumensath | Recognisability for algebras of infinite trees[END_REF]. However, there is no evidence yet that such a generalization could lead to a successful algebraic characterization of infinite tree languages.

Fig. 1 .

 1 Fig. 1. An infinite product for abcd(ab) ω .

Fig. 3 .

 3 Fig. 3. A tiled temporal media (or birooted word).

Fig. 4 .

 4 Fig. 4. A tiled product instance

This report is the long version of[START_REF] Dicky | Embedding finite and infinite words into overlapping tiles[END_REF]