References

References¶

angrand.2010.jalc¶

@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.} }

antimirov.1996.tcs¶

@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.} }

beal.2003.tcs¶

@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.} }

demaille.16.ciaa¶

@InProceedings{ demaille.16.ciaa, author = {Akim Demaille}, title = {Derived-Term Automata of Multitape Rational Expressions}, booktitle = {Proceedings of Implementation and Application of Automata, 21st International Conference (CIAA'16)}, editor = {Yo-Sub Han and Kai Salomaa}, year = 2016, publisher = {Springer}, address = {Cham}, pages = {51--63}, isbn = {978-3-319-40946-7}, doi = {10.1007/978-3-319-40946-7_5}, series = {Lecture Notes in Computer Science}, volume = 9705, address = {Seoul, South Korea}, month = jul, abstract = {We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator $\mid$ to build multitape expressions such as $(a^+\mid x + b^+\mid y)^*$. We define expansions, which generalize the concept of derivative of a rational expression, but relieved from the need of a free monoid. We propose an algorithm based on expansions to build multitape automata from multitape expressions.}, }

demaille.2016.ictac¶

@InProceedings{ demaille.16.ictac, author = {Akim Demaille}, title = {Derived-term Automata for Extended Weighted Rational Expressions}, booktitle = {Proceedings of the Thirteenth International Colloquium on Theoretical Aspects of Computing (ICTAC)}, year = 2016, publisher = {Springer}, series = {Lecture Notes in Computer Science}, address = {Taipei, Taiwan}, month = oct, abstract = {We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different construct, rational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata. These constructs are implemented in Vcsn, a free-software platform dedicated to weighted automata and rational expressions.}, }

lombardy.2005.tcs¶

@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.} }

lombardy.2010.rairo¶

@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.} }

lombardy.2013.ijac¶

@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.} }

mohri.2009.hwa¶

@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} }

mohri.2002.ciaa¶

@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} }

tolmer.2014.seminar¶

@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} }

yvon.2010.nle¶

@article{yvon.2010.nle, author = {François Yvon}, Journal = {Natural Language Engineering}, Number = 2, Pages = {133--159}, Title = {Rewriting the orthography of SMS messages}, Url = {http://journals.cambridge.org/repo_A74GiYsr}, Volume = {16}, Year = 2010, Abstract = {Electronic written texts used in computer-mediated interactions (e-mails, blogs, chats, etc) contain significant deviations from the norm of the language. This paper presents the detail of a system aiming at normalizing the orthography of French SMS messages: after discussing the linguistic peculiarities of these messages, and possible approaches to their automatic normalization, we present, compare and evaluate various instanciations of a normalization device based on weighted finite-state transducers. These experiments show that, using an intermediate phonemic representation and training, our system outperforms an alternative normalisation system based on phrase-based statistical machine translation techniques.}, }