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.
Br\"uggemann-Klein and Wood define a one-unambiguous regular language as a
language that can be recognized by a deterministic Glushkov automaton. They
give a procedure performed on the minimal DFA, the BW-test, to decide whether a
language is one-unambiguous. Block determinism is an extension of
one-unambiguity while considering non-empty words as symbols and
prefix-freeness as determinism. A block automaton is compact if it does not
have two equivalent states (same right language). We showed that a language is
$k$-block deterministic if it is recognized by some deterministic $k$-block
automaton passing the BW-test. In this paper, we show that any $k$-block
deterministic language is recognized by a compact deterministic $k$-block
automaton passing the BW-test. We also give a procedure which enumerates, for a
given language, the finite set of compact deterministic $k$-block automata. It
gives us a decidable procedure to test whether a language is $k$-block
We focus on the family of $(k,l)$-unambiguous automata that encompasses the
one of deterministic $k$-lookahead automata introduced by Han and Wood. We show
that this family presents nice theoretical properties that allow us to compute
quasi-deterministic structures. These structures are smaller than DFAs and can
be used to solve the membership problem faster than NFAs.
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
counter-parts are investigated. One of these operads acts faithfully on
languages in the sense that two different operators act in two different ways.
A regular language is $k$-lookahead deterministic (resp. $k$-block
deterministic) if it is specified by a $k$-lookahead deterministic (resp.
$k$-block deterministic) regular expression. These two subclasses of regular
languages have been respectively introduced by Han and Wood ($k$-lookahead
determinism) and by Giammarresi et al. ($k$-block determinism) as a possible
extension of one-unambiguous languages defined and characterized by
Br\"uggemann-Klein and Wood. In this paper, we study the hierarchy and the
inclusion links of these families. We first show that each $k$-block
deterministic language is the alphabetic image of some one-unambiguous
language. Moreover, we show that the conversion from a minimal DFA of a
$k$-block deterministic regular language to a $k$-block deterministic automaton
not only requires state elimination, and that the proof given by Han and Wood
of a proper hierarchy in $k$-block deterministic languages based on this result
is erroneous. Despite these results, we show by giving a parameterized family
that there is a proper hierarchy in $k$-block deterministic regular languages.
We also prove that there is a proper hierarchy in $k$-lookahead deterministic
regular languages by studying particular properties of unary regular
expressions. Finally, using our valid results, we confirm that the family of
$k$-block deterministic regular languages is strictly included into the one of
$k$-lookahead deterministic regular languages by showing that any $k$-block
deterministic unary language is one-unambiguous.
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
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.
In this paper, we extend the notion of tree language quotients to bottom-up
quotients. Instead of computing the residual of a tree language from top to
bottom and producing a list of tree languages, we show how to compute a set of
k-ary trees, where k is an arbitrary integer. We define the quotient formula
for different combinations of tree languages: union, symbol products,
compositions, iterated symbol products and iterated composition. These
computations lead to the definition of the bottom-up quotient tree automaton,
that turns out to be the minimal deterministic tree automaton associated with a
regular tree language in the case of the 0-ary trees.
In this paper we study the state complexity of catenation combined with
symmetric difference. First, an upper bound is computed using some combinatoric
tools. Then, this bound is shown to be tight by giving a witness for it.
Moreover, we relate this work with the study of state complexity for two other
combinations: catenation with union and catenation with intersection. And we
extract a unified approach which allows to obtain the state complexity of any
combination involving catenation and a binary boolean operation.
Arden's Lemma is a classical result in language theory allowing the
computation of a rational expression denoting the language recognized by a
finite string automaton. In this paper we generalize this important lemma to
the rational tree languages. Moreover, we propose also a construction of a
rational tree expression which denotes the accepted tree language of a finite
In this paper, we define a new kind of weighted tree automata where the
weights are only supported by final states. We show that these automata are
sequentializable and we study their closures under classical regular and
algebraic operations. We then use these automata to compute the subtree kernel
of two finite tree languages in an efficient way. Finally, we present some
perspectives involving the root-weighted tree automata.
Champarnaud and Ziadi, and Khorsi et al. show how to compute the equation
automaton of word regular expression $E$ via the $k$-C-Continuations.
Kuske and Meinecke extend the computation of the equation automaton to a
regular tree expression $E$ over a ranked alphabet $\Sigma$ and produce a
$O(R\cdot|E|^2)$ time and space complexity algorithm, where $R$ is the maximal
rank of a symbol occurring in $\Sigma$ and $|E|$ is the size of $E$. In this
paper, we give a full description of the algorithm based on the acyclic
minimization of Revuz. Our algorithm, which is performed in an $O(|Q|\cdot|E|)$
time and space complexity, where $|Q|$ is the number of states of the produced
automaton, is more efficient than the one obtained by Kuske and Meinecke.
The aim of this paper is to design the polynomial construction of a finite
recognizer for hairpin completions of regular languages. This is achieved by
considering completions as new expression operators and by applying derivation
techniques to the associated extended expressions called hairpin expressions.
More precisely, we extend partial derivation of regular expressions to
two-sided partial derivation of hairpin expressions and we show how to deduce a
recognizer for a hairpin expression from its two-sided derived term automaton,
providing an alternative proof of the fact that hairpin completions of regular
languages are linear context-free.
The aim of this paper is to design a theoretical framework that allows us to
perform the computation of regular expression derivatives through a space of
generic structures. Thanks to this formalism, the main properties of regular
expression derivation, such as the finiteness of the set of derivatives, need
only be stated and proved one time, at the top level. Moreover, it is shown how
to construct an alternating automaton associated with the derivation of a
regular expression in this general framework. Finally, Brzozowski's derivation
and Antimirov's derivation turn out to be a particular case of this general
scheme and it is shown how to construct a DFA, a NFA and an AFA for both of
Our aim is to construct a finite automaton recognizing the set of words that
are at a bounded distance from some word of a given regular language. We define
new regular operators, the similarity operators, based on a generalization of
the notion of distance and we introduce the family of regular expressions
extended to similarity operators, that we call AREs (Approximate Regular
Expressions). We set formulae to compute the Brzozowski derivatives and the
Antimirov derivatives of an ARE, which allows us to give a solution to the ARE
membership problem and to provide the construction of two recognizers for the
language denoted by an ARE. As far as we know, the family of approximative
regular expressions is introduced for the first time in this paper. Classical
approximate regular expression matching algorithms are approximate matching
algorithms on regular expressions. Our approach is rather to process an exact
matching on approximate regular expressions.
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.