
We describe a structure of PRO on hypermatrices. This structure allows us to
define multilinear representations of PROs and in particular of free Pros. As
an example of applications, we investigate the relations of the representations
of Pros with the theory of automata.

We generalize the construction of multitildes in the aim to provide
multitilde operators for regular languages. We show that the underliying
algebraic structure involves the action of some operads. An operad is an
algebraic structure that mimics the composition of the functions. The involved
operads are described in terms of combinatorial objects. These operads are
obtained from more primitive objects, namely precompositions, whose algebraic
counterparts are investigated. One of these operads acts faithfully on
languages in the sense that two different operators act in two different ways.

This paper proposes an extension to classical regular expressions by the
addition of two operators allowing the inclusion of boolean formulae from the
zeroth order logic. These expressions are called constrained expressions. The
associated language is defined thanks to the notion of interpretation and of
realization.
We show that the language associated when both interpretation and realization
are fixed is stricly regular and can be not regular otherwise.
Furthermore, we use an extension of Antimirov partial derivatives in order to
solve the membership test in the general case. Finally, we show that once the
interpretation is fixed, the membership test of a word in the language denoted
by a constrained expression can be undecidable whereas it is always decidable
when the interpretation is not fixed.

Multitildes are regular operators that were introduced by Caron et al. in
order to increase the number of Glushkov automata. In this paper, we study the
family of the multitilde operators from an algebraic point of view using the
notion of operad. This leads to a combinatorial description of already known
results as well as new results on compositions, actions and enumerations.