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