@article{angrand.2010.jalc,
author = {Pierre-Yves Angrand and Sylvain Lombardy and Jacques
Sakarovitch},
title = {On the Number of Broken Derived Terms of a Rational
Expression},
journal = {Journal of Automata, Languages and Combinatorics},
number = {1/2},
pages = {27--51},
volume = 15,
year = 2010,
abstract = {Bounds are given on the number of broken derived
terms (a variant of Antimirov's ``partial
derivatives'') of a rational expression $E$. It is
shown that this number is less than or equal to
$2l(E) + 1$ in the general case, where $l(E)$ is the
literal length of the expression $E$, and that the
classical bound $l(E) + 1$ which holds for partial
derivatives also holds for broken derived terms if E
is in star normal form.\\In a second part of the
paper, the influence of the bracketing of an
expression on the number of its derived terms is
also discussed.}
}
@article{antimirov.1996.tcs,
author = {Valentin Antimirov},
title = {Partial derivabbtives of regular expressions and
finite automaton constructions},
journal = {Theor. Comput. Sci.},
volume = 155,
number = 2,
year = 1996,
issn = {0304-3975},
pages = {291--319},
doi = {http://dx.doi.org/10.1016/0304-3975(95)00182-4},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
abstract = {We introduce a notion of \emph{partial derivative}
of a regular expression and apply it to finite
automaton constructions. The notion is a
generalization of the known notion of \emph{word
derivative} due to Brzozowski: partial derivatives
are related to non-deterministic finite automata
(NFA's) in the same natural way as derivatives are
related to deterministic ones (DFA's). We give a
constructive definition of partial derivatives and
prove several facts, in particular: (1) any
derivative of a regular expression $r$ can be
represented by a finite set of partial derivatives
of $r$; (2) the set of all partial derivatives of
$r$ is finite and its cardinality is less than or
equal to one plus the number of occurrences of
letters from $A$ appearing in $r$; (3) any partial
derivative of $r$ is either a regular unit, or a
subterm of $r$, or a concatenation of several such
subterms. These theoretical results lead us to a new
algorithm for turning regular expressions into
relatively small NFA's and allow us to provide
certain improvements to Brzozowski's algorithm for
constructing DFA's. We also report on a prototype
implementation of our NFA construction and present
several examples.}
}
@article{beal.2003.tcs,
title = {Squaring transducers: an efficient procedure for
deciding functionality and sequentiality},
author = {Marie-Pierre B\'eal and Olivier Carton and Christophe
Prieur and Jacques Sakarovitch},
journal = {Theoretical Computer Science},
volume = {292},
number = {1},
pages = {45--63},
year = {2003},
note = {Selected Papers in honor of Jean Berstel},
issn = {0304-3975},
doi = {http://dx.doi.org/10.1016/S0304-3975(01)00214-6},
url = {http://www.sciencedirect.com/science/article/pii/S0304397501002146},
keywords = {Finite automata},
keywords = {Functional transducer},
keywords = {Sequential transducer},
abstract = {We describe here a construction on transducers that
give a new conceptual proof for two classical
decidability results on transducers: it is decidable
whether a finite transducer realizes a functional
relation, and whether a finite transducer realizes a
sequential relation. A better complexity follows
then for the two decision procedures.}
}
@article{lombardy.2005.tcs,
title = {Derivatives of rational expressions with
multiplicity},
author = {Sylvain Lombardy and Jacques Sakarovitch},
journal = {Theoretical Computer Science},
volume = 332,
number = {1-3},
pages = {141--177},
year = 2005,
issn = {0304-3975},
keywords = {Rational expression, Regular
expression,Automata,Automata with multiplicity},
abstract = {This paper addresses the problem of turning a
rational (i.e. regular) expression into a finite
automaton. We formalize and generalize the idea of
``partial derivatives'' introduced in 1995 by
Antimirov, in order to obtain a construction of an
automaton with multiplicity from a rational
expression describing a formal power series with
coefficients in a semiring.\\ We first define
precisely what is such a rational expression with
multiplicity and which hypothesis should be put on
the semiring of coefficients in order to keep the
usual identities.\\ We then define the derivative of
such a rational expression as a linear combination
of expressions called derived terms and we show that
all derivatives of a given expression are generated
by a finite set of derived terms, that yields a
finite automaton with multiplicity whose behaviour
is the series denoted by the expression. We also
prove that this automaton is a quotient of the
standard (or Glushkov) automaton of the
expression. Finally, we propose and discuss some
possible modifications to our definition of
derivation.}
}
@article{lombardy.2010.rairo,
author = {Sylvain Lombardy and Jacques Sakarovitch},
title = {Corrigendum to our paper: How Expressions Can Code
for Automata},
journal = {{RAIRO} --- Theoretical Informatics and Applications},
year = {2010},
volume = {44},
number = {3},
pages = {339--361},
abstract = {In a previous paper, we have described the
construction of an automaton from a rational
expression which has the property that the automaton
built from an expression which is itself computed
from a co-deterministic automaton by the state
elimination method is co-deterministic. It turned
out that the definition on which the construction is
based was inappropriate, and thus the proof of the
property was flawed. We give here the correct
definition of the broken derived terms of an
expression which allow to define the automaton and
the detailed full proof of the property.}
}
@article{lombardy.2013.ijac,
author = {Sylvain Lombardy and Jacques Sakarovitch},
title = {The validity of weighted automata},
volume = 23,
number = 4,
year = 2013,
pages = {863-914},
journal = {Int. J. of Algebra and Computation},
year = 2013,
abstract = {This paper addresses the problem of the validity of
weighted automata in which the presence of
$\varepsilon$-circuits results in infinite
summations. Earlier works either rule out such
automata or characterise the semirings in which
these infinite sums are all well-defined.\\ By means
of a topological approach, we take here a definition
of validity that is strong enough to insure that in
any kind of semirings, any closure algorithm will
succeed on every valid weighted automaton and turn
it into an equivalent proper automaton. This
definition is stable with respect to natural
transformations of automata.\\ The classical closure
algorithms, in particular algorithms based on the
computation of the star of the matrix of
$\varepsilon$-transitions, cannot be used to decide
validity. This decision problem remains open for
general topological semirings. We present a closure
algorithm that yields a decision procedure for the
validity of automata in the case where the weights
are taken in $\mathbb{Q}$ or $\mathbb{R}$, two cases
that had never been treated before. These algorithm
and procedure are implemented in the Vaucanson
platform.}
}
@incollection{mohri.2009.hwa,
title = {Weighted Automata Algorithms},
author = {Mehryar Mohri},
year = 2009,
isbn = {978-3-642-01491-8},
booktitle = {Handbook of Weighted Automata},
series = {Monographs in Theoretical Computer Science. An EATCS
Series},
editor = {Droste, Manfred and Kuich, Werner and Vogler, Heiko},
publisher = {Springer Berlin Heidelberg},
pages = {213-254},
language = {English}
}
@INPROCEEDINGS{mohri.2002.ciaa,
author = {Mehryar Mohri},
title = {Edit-Distance of Weighted Automata},
booktitle = {In Jean-Marc Champarnaud and Denis Maurel, editor, Seventh International Conference, CIAA 2002},
year = {2002},
pages = {1--23},
publisher = {Springer Verlag}
}
@TechReport{tolmer.14.seminar,
author = {Valentin Tolmer},
title = {Transducer composition in {V}aucanson 2},
institution = {EPITA Research and Development Laboratory (LRDE)},
year = 2014,
number = 1401,
url = {http://publications.lrde.epita.fr/201401-Seminar-Tolmer}
}