Search results for " Natural Language"
showing 10 items of 192 documents
Special factors and the combinatorics of suffix and factor automata
2011
AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.
The Shuffle Product: New Research Directions
2015
In this paper we survey some recent researches concerning the shuffle operation that arise both in Formal Languages and in Combinatorics on Words.
On the empirical spectral distribution for certain models related to sample covariance matrices with different correlations
2021
Given [Formula: see text], we study two classes of large random matrices of the form [Formula: see text] where for every [Formula: see text], [Formula: see text] are iid copies of a random variable [Formula: see text], [Formula: see text], [Formula: see text] are two (not necessarily independent) sets of independent random vectors having different covariance matrices and generating well concentrated bilinear forms. We consider two main asymptotic regimes as [Formula: see text]: a standard one, where [Formula: see text], and a slightly modified one, where [Formula: see text] and [Formula: see text] while [Formula: see text] for some [Formula: see text]. Assuming that vectors [Formula: see t…
Lévy–Khintchine decompositions for generating functionals on algebras associated to universal compact quantum groups
2018
We study the first and second cohomology groups of the $^*$-algebras of the universal unitary and orthogonal quantum groups $U_F^+$ and $O_F^+$. This provides valuable information for constructing and classifying L\'evy processes on these quantum groups, as pointed out by Sch\"urmann. In the case when all eigenvalues of $F^*F$ are distinct, we show that these $^*$-algebras have the properties (GC), (NC), and (LK) introduced by Sch\"urmann and studied recently by Franz, Gerhold and Thom. In the degenerate case $F=I_d$, we show that they do not have any of these properties. We also compute the second cohomology group of $U_d^+$ with trivial coefficients -- $H^2(U_d^+,{}_\epsilon\Bbb{C}_\epsil…
Tally languages accepted by Monte Carlo pushdown automata
1997
Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
Minimal forbidden words and factor automata
1998
International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
Learning the structure of HMM's through grammatical inference techniques
2002
A technique is described in which all the components of a hidden Markov model are learnt from training speech data. The structure or topology of the model (i.e. the number of states and the actual transitions) is obtained by means of an error-correcting grammatical inference algorithm (ECGI). This structure is then reduced by using an appropriate state pruning criterion. The statistical parameters that are associated with the obtained topology are estimated from the same training data by means of the standard Baum-Welch algorithm. Experimental results showing the applicability of this technique to speech recognition are presented. >
A simple algorithm for finding short sigma-definite representatives
2010
We describe a new algorithm which for each braid returns a quasi-geodesic sigma-definite word representative, defined as a braid word in which the generator sigma_i with maximal index i appears either only positively or only negatively.
Le grand débat national, une aide pour prendre des décisions locales?
2021
The Great National Debate, decided by Emmanuel Macron at the beginning of 2019 to respond to the Yellow Vests social movement, allowed the collection of citizens’ contributions on the ecological transition via an online platform. In this article, we use the corpus constituted by these contributions to identify areas where participants are asking for the development of bicycle paths and railway facilities. For this purpose, we have created a classification model to identify contributions dealing with the theme of transportation and proposed a method for extracting patterns that reflect the contributors’ proposals. We then represented these patterns on maps, using the contributors’ postal cod…